Simplify compact_hash_table implementation

Instead of a separate implementation for find/insert, use just one that can do both. This reduces the code size and simplifies code coverage; the resulting code is close to what we had in terms of performance and since hash table is a fall back should not affect any real workloads.
9drops · Mar 3, 2017 · 8ce4592 · 8ce4592
1 parent 03e4b8d
commit 8ce4592
Showing 1 changed file with 38 additions and 45 deletions.
diff --git a/src/pugixml.cpp b/src/pugixml.cpp
@@ -274,61 +274,31 @@ PUGI__NS_BEGIN
 			}
 		}
 
-		void** find(const void* key)
+		void* find(const void* key)
 		{
-			assert(key);
-
 			if (_capacity == 0) return 0;
 
-			size_t hashmod = _capacity - 1;
-			size_t bucket = hash(key) & hashmod;
+			item_t* item = get_item(key);
+			assert(item);
+			assert(item->key == key || (item->key == 0 && item->value == 0));
 
-			for (size_t probe = 0; probe <= hashmod; ++probe)
-			{
-				item_t& probe_item = _items[bucket];
-
-				if (probe_item.key == key)
-					return &probe_item.value;
-
-				if (probe_item.key == 0)
-					return 0;
-
-				// hash collision, quadratic probing
-				bucket = (bucket + probe + 1) & hashmod;
-			}
-
-			assert(false && "Hash table is full");
-			return 0;
+			return item->value;
 		}
 
-		void** insert(const void* key)
+		void insert(const void* key, void* value)
 		{
-			assert(key);
 			assert(_capacity != 0 && _count < _capacity - _capacity / 4);
 
-			size_t hashmod = _capacity - 1;
-			size_t bucket = hash(key) & hashmod;
+			item_t* item = get_item(key);
+			assert(item);
 
-			for (size_t probe = 0; probe <= hashmod; ++probe)
+			if (item->key == 0)
 			{
-				item_t& probe_item = _items[bucket];
-
-				if (probe_item.key == 0)
-				{
-					probe_item.key = key;
-					_count++;
-					return &probe_item.value;
-				}
-
-				if (probe_item.key == key)
-					return &probe_item.value;
-
-				// hash collision, quadratic probing
-				bucket = (bucket + probe + 1) & hashmod;
+				_count++;
+				item->key = key;
 			}
 
-			assert(false && "Hash table is full");
-			return 0;
+			item->value = value;
 		}
 
 		bool reserve()
@@ -353,6 +323,29 @@ PUGI__NS_BEGIN
 
 		bool rehash();
 
+		item_t* get_item(const void* key)
+		{
+			assert(key);
+			assert(_capacity > 0);
+
+			size_t hashmod = _capacity - 1;
+			size_t bucket = hash(key) & hashmod;
+
+			for (size_t probe = 0; probe <= hashmod; ++probe)
+			{
+				item_t& probe_item = _items[bucket];
+
+				if (probe_item.key == key || probe_item.key == 0)
+					return &probe_item;
+
+				// hash collision, quadratic probing
+				bucket = (bucket + probe + 1) & hashmod;
+			}
+
+			assert(false && "Hash table is full");
+			return 0;
+		}
+
 		static unsigned int hash(const void* key)
 		{
 			unsigned int h = static_cast<unsigned int>(reinterpret_cast<uintptr_t>(key));
@@ -381,7 +374,7 @@ PUGI__NS_BEGIN
 
 		for (size_t i = 0; i < _capacity; ++i)
 			if (_items[i].key)
-				*rt.insert(_items[i].key) = _items[i].value;
+				rt.insert(_items[i].key, _items[i].value);
 
 		if (_items)
 			xml_memory::deallocate(_items);
@@ -773,12 +766,12 @@ PUGI__NS_BEGIN
 
 	template <int header_offset, typename T> PUGI__FN_NO_INLINE T* compact_get_value(const void* object)
 	{
-		return static_cast<T*>(*compact_get_page(object, header_offset)->allocator->_hash->find(object));
+		return static_cast<T*>(compact_get_page(object, header_offset)->allocator->_hash->find(object));
 	}
 
 	template <int header_offset, typename T> PUGI__FN_NO_INLINE void compact_set_value(const void* object, T* value)
 	{
-		*compact_get_page(object, header_offset)->allocator->_hash->insert(object) = value;
+		compact_get_page(object, header_offset)->allocator->_hash->insert(object, value);
 	}
 
 	template <typename T, int header_offset, int start = -126> class compact_pointer