Merge pull request universal-ctags#3481 from masatake/dyn-hashtable-mini

main: extend the bucket array of hashTable dynamically
catap · Sep 17, 2022 · 0f04663 · 0f04663
2 parents b7798da + fad4051
commit 0f04663
Show file tree

Hide file tree

Showing 7 changed files with 135 additions and 28 deletions.
diff --git a/Tmain/optscript.d/arrayx.expected b/Tmain/optscript.d/arrayx.expected
@@ -0,0 +1,2 @@
+unmatchedmark
+null
diff --git a/Tmain/optscript.d/arrayx.ps b/Tmain/optscript.d/arrayx.ps
diff --git a/Tmain/optscript.d/dictx.expected b/Tmain/optscript.d/dictx.expected
@@ -0,0 +1,17 @@
+-dict:0-
+-dict:1-
+-dict:0-
+-dict:1-
+-dict:0-
+-dict:1-
+rangecheck
+null
+-dict:0-
+-dict:1-
+-dict:1-
+-dict:2-
+-dict:2-
+-dict:3-
+unmatchedmark
+rangecheck
+null
diff --git a/Tmain/optscript.d/dictx.ps b/Tmain/optscript.d/dictx.ps
diff --git a/Tmain/optscript.d/stdout-expected.txt b/Tmain/optscript.d/stdout-expected.txt
@@ -1,8 +1,10 @@
 arithmetic.ps...0
 array.ps...0
+arrayx.ps...0
 compound.ps...0
 control.ps...0
 dict.ps...0
+dictx.ps...0
 error-undefined-if-if.ps...1
 error-undefined-if.ps...1
 misc.ps...0

diff --git a/dsl/optscript.c b/dsl/optscript.c
@@ -475,8 +475,8 @@ opt_init (void)
 
 	defOP (opt_system_dict, op_mark,           "<<",  0,  "- << mark");
 	defOP (opt_system_dict, op_mark,           "[",   0,  "- [ mark");
-	defOP (opt_system_dict, op__make_array,    "]",   1,  "[ any1 ... anyn ] array");
-	defOP (opt_system_dict, op__make_dict ,    ">>",  1, "<< key1 value1 ... keyn valuen >> dict");
+	defOP (opt_system_dict, op__make_array,    "]",   0,  "[ any1 ... anyn ] array");
+	defOP (opt_system_dict, op__make_dict ,    ">>",  0, "<< key1 value1 ... keyn valuen >> dict");
 
 	defop (opt_system_dict, _help,  0, "- _HELP -");
 	defop (opt_system_dict, pstack, 0, "|- any1 ... anyn PSTACK |- any1 ... anyn");
@@ -2464,7 +2464,14 @@ op__make_dict (OptVM *vm, EsObject *name)
 			return OPT_ERR_TYPECHECK;
 	}
 
-	EsObject *d = dict_new (n > 0? (n / 2): 1, ATTR_READABLE|ATTR_WRITABLE);
+	/* A hashtable grows automatically when its filling rate is
+	 * grater than 80%. If we put elements between `<<' and `>>' to a dictionary
+	 * initialized with the size equal to the number of elements, the dictionary
+	 * grows once during putting them. Making a 1/0.8 times larger dictionary can
+	 * avoid the predictable growing. */
+	int size = (10 * (n > 0? (n / 2): 1)) / 8;
+
+	EsObject *d = dict_new (size, ATTR_READABLE|ATTR_WRITABLE);
 	for (int i = 0; i < (n / 2); i++)
 	{
 		EsObject *val = ptrArrayLast (vm->ostack);
@@ -3029,8 +3036,10 @@ op_dict (OptVM *vm, EsObject *name)
 		return OPT_ERR_TYPECHECK;
 
 	int n = es_integer_get (nobj);
-	if (n < 1)
+	if (n < 0)
 		return OPT_ERR_RANGECHECK;
+	else if (n == 0)
+		n = 1;
 
 	ptrArrayDeleteLast (vm->ostack);
 

diff --git a/main/htable.c b/main/htable.c
@@ -11,6 +11,7 @@
 
 #include "general.h"
 #include "htable.h"
+#include "debug.h"
 
 #ifndef MAIN
 #include <stdio.h>
@@ -35,12 +36,14 @@ typedef struct sHashEntry hentry;
 struct sHashEntry {
 	void *key;
 	void *value;
+	unsigned int hash;
 	hentry *next;
 };
 
 struct sHashTable {
 	hentry** table;
 	unsigned int size;
+	unsigned int count;
 	hashTableHashFunc hashfn;
 	hashTableEqualFunc equalfn;
 	hashTableDeleteFunc keyfreefn;
@@ -56,13 +59,14 @@ struct chainTracker {
 	hashTableEqualFunc equalfn;
 };
 
-static hentry* entry_new (void *key, void *value, hentry* next)
+static hentry* entry_new (void *key, void *value, unsigned int hash, hentry* next)
 {
 	hentry* entry = xMalloc (1, hentry);
 
 	entry->key = key;
 	entry->value = value;
 	entry->next = next;
+	entry->hash = hash;
 
 	return entry;
 }
@@ -164,7 +168,14 @@ extern hashTable *hashTableNew    (unsigned int size,
 	hashTable *htable;
 
 	htable = xMalloc (1, hashTable);
+
+	if (size < 3)
+		size = 3;
+	if ((size % 2) == 0)
+		size++;
+
 	htable->size = size;
+	htable->count = 0;
 	htable->table = xCalloc (size, hentry*);
 
 	htable->hashfn = hashfn;
@@ -217,40 +228,114 @@ extern void       hashTableClear (hashTable *htable)
 	}
 }
 
-extern void       hashTablePutItem    (hashTable *htable, void *key, void *value)
+static void       hashTablePutItem00    (hashTable *htable, void *key, void *value, unsigned int h)
 {
-	unsigned int i;
+	unsigned int i = h % htable->size;
+	htable->table[i] = entry_new(key, value, h, htable->table[i]);
+	htable->count++;
+}
+
+/* TODO: A pre-calculated array can be used instead of
+ * finding a new one at runtume. */
+static unsigned int
+prime_double(unsigned int i)
+{
+	Assert (i > 2);
+	Assert (i % 2);
+
+	for (unsigned int c = 2 * i + 1; ; c += 2)
+	{
+		for (unsigned int i0 = 3; i0 < i; i0 += 2)
+		{
+			if ((c % i0) == 0)
+				goto next;
+		}
+		return c;
+	next:;
+	}
+
+	return i;
+}
+
+static void       hashTableGrow        (hashTable *htable)
+{
+	unsigned int current_size = htable->size;
+	unsigned int new_size = prime_double (current_size);
+
+	if (new_size <= current_size)
+		return;
+
+	hentry** new_table = xCalloc (new_size, hentry*);
+	for (unsigned int i = 0; i < current_size; i++)
+	{
+		hentry *entry;
+		while ((entry = htable->table[i]))
+		{
+			unsigned int hash = entry->hash;
+			unsigned int j = hash % new_size;
+			htable->table[i] = entry->next;
+			entry->next = new_table[j];
+			new_table[j] = entry;
+		}
+	}
+
+	hentry** old_table = htable->table;
+	htable->table = new_table;
+	htable->size = new_size;
+	eFree (old_table);
+}
+
+static void       hashTablePutItem0    (hashTable *htable, void *key, void *value, unsigned int h)
+{
+	if (((double)htable->count / (double)htable->size) < 0.8)
+	{
+		hashTablePutItem00 (htable, key, value,  h);
+		return;
+	}
+
+	hashTableGrow (htable);
+	hashTablePutItem00 (htable, key, value, h);
+}
 
-	i = htable->hashfn (key) % htable->size;
-	htable->table[i] = entry_new(key, value, htable->table[i]);
+extern void       hashTablePutItem    (hashTable *htable, void *key, void *value)
+{
+	hashTablePutItem0 (htable, key, value, htable->hashfn (key));
 }
 
 extern void*      hashTableGetItem   (hashTable *htable, const void * key)
 {
-	unsigned int i;
+	unsigned int h, i;
 
-	i = htable->hashfn (key) % htable->size;
+	h = htable->hashfn (key);
+	i = h % htable->size;
 	return entry_find(htable->table[i], key, htable->equalfn, htable->valForNotUnknownKey);
 }
 
 extern bool     hashTableDeleteItem (hashTable *htable, const void *key)
 {
+	unsigned int h;
 	unsigned int i;
+	h = htable->hashfn (key);
+	i = h % htable->size;
 
-	i = htable->hashfn (key) % htable->size;
-	return entry_delete(&htable->table[i], key,
+	bool r = entry_delete(&htable->table[i], key,
 			    htable->equalfn, htable->keyfreefn, htable->valfreefn);
+	if (r)
+		htable->count--;
+	return r;
 }
 
 extern bool    hashTableUpdateItem (hashTable *htable, void *key, void *value)
 {
-	unsigned int i;
+	unsigned int h, i;
 
-	i = htable->hashfn (key) % htable->size;
+	h = htable->hashfn (key);
+	i = h % htable->size;
 	bool r = entry_update(htable->table[i], key, value,
 						  htable->equalfn, htable->keyfreefn, htable->valfreefn);
 	if (!r)
-		htable->table[i] = entry_new(key, value, htable->table[i]);
+		hashTablePutItem0(htable, key, value, h);
+
 	return r;
 }
 
@@ -283,32 +368,24 @@ static bool track_chain (const void *const key, void *value, void *chain_data)
 
 extern bool       hashTableForeachItemOnChain (hashTable *htable, const void *key, hashTableForeachFunc proc, void *user_data)
 {
-	unsigned int i;
+	unsigned int h, i;
 	struct chainTracker chain_tracker = {
 		.target_key = key,
 		.user_proc = proc,
 		.user_data = user_data,
 		.equalfn   = htable->equalfn,
 	};
 
-	i = htable->hashfn (key) % htable->size;
+	h = htable->hashfn (key);
+	i = h % htable->size;
 	if (!entry_foreach(htable->table[i], track_chain, &chain_tracker))
 		return false;
 	return true;
 }
 
-static bool count (const void *const key CTAGS_ATTR_UNUSED, void *value CTAGS_ATTR_UNUSED, void *data)
-{
-	int *c = data;
-	++*c;
-	return true;
-}
-
 extern unsigned int hashTableCountItem   (hashTable *htable)
 {
-	int c = 0;
-	hashTableForeachItem (htable, count, &c);
-	return c;
+	return htable->count;
 }
 
 unsigned int hashPtrhash (const void * const x)