updated for version 7.0067
diff --git a/src/hashtable.c b/src/hashtable.c
index 0263f6f..a8cd1b7 100644
--- a/src/hashtable.c
+++ b/src/hashtable.c
@@ -32,7 +32,10 @@
#if defined(FEAT_EVAL) || defined(FEAT_SYN_HL) || defined(PROTO)
#if 0
-# define HT_DEBUG /* extra checks for table consistency */
+# define HT_DEBUG /* extra checks for table consistency and statistics */
+
+static long hash_count_lookup = 0; /* count number of hashtab lookups */
+static long hash_count_perturb = 0; /* count number of "misses" */
#endif
/* Magic value for algorithm that walks through the array. */
@@ -40,7 +43,7 @@
static int hash_may_resize __ARGS((hashtab_T *ht, int minitems));
-#if defined(FEAT_SYN_HL) || defined(PROTO)
+#if 0 /* currently not used */
/*
* Create an empty hash table.
* Returns NULL when out of memory.
@@ -112,6 +115,10 @@
hashitem_T *hi;
int idx;
+#ifdef HT_DEBUG
+ ++hash_count_lookup;
+#endif
+
/*
* Quickly handle the most common situations:
* - return if there is no item at all
@@ -141,6 +148,9 @@
*/
for (perturb = hash; ; perturb >>= PERTURB_SHIFT)
{
+#ifdef HT_DEBUG
+ ++hash_count_perturb; /* count a "miss" for hashtab lookup */
+#endif
idx = (idx << 2) + idx + perturb + 1;
hi = &ht->ht_array[idx & ht->ht_mask];
if (hi->hi_key == NULL)
@@ -155,6 +165,23 @@
}
/*
+ * Print the efficiency of hashtable lookups.
+ * Useful when trying different hash algorithms.
+ * Called when exiting.
+ */
+ void
+hash_debug_results()
+{
+#ifdef HT_DEBUG
+ fprintf(stderr, "\r\n\r\n\r\n\r\n");
+ fprintf(stderr, "Number of hashtable lookups: %ld\r\n", hash_count_lookup);
+ fprintf(stderr, "Number of perturb loops: %ld\r\n", hash_count_perturb);
+ fprintf(stderr, "Percentage of perturb loops: %ld%%\r\n",
+ hash_count_perturb * 100 / hash_count_lookup);
+#endif
+}
+
+/*
* Add item with key "key" to hashtable "ht".
* Returns FAIL when out of memory or the key is already present.
*/
@@ -332,7 +359,7 @@
else
{
/* Use specified size. */
- if (minitems < ht->ht_used) /* just in case... */
+ if ((long_u)minitems < ht->ht_used) /* just in case... */
minitems = ht->ht_used;
minsize = minitems * 3 / 2; /* array is up to 2/3 full */
}
@@ -420,16 +447,28 @@
}
/*
- * Get the hash number for a key. Uses the ElfHash algorithm, which is
- * supposed to have an even distribution (suggested by Charles Campbell).
+ * Get the hash number for a key.
+ * If you think you know a better hash function: Compile with HT_DEBUG set and
+ * run a script that uses hashtables a lot. Vim will then print statistics
+ * when exiting. Try that with the current hash algorithm and yours. The
+ * lower the percentage the better.
*/
hash_T
hash_hash(key)
char_u *key;
{
- hash_T hash = 0;
+ hash_T hash;
+ char_u *p;
+
+ if ((hash = *key) == 0)
+ return (hash_T)0; /* Empty keys are not allowed, but we don't
+ want to crash if we get one. */
+ p = key + 1;
+
+#if 0
+ /* ElfHash algorithm, which is supposed to have an even distribution.
+ * Suggested by Charles Campbell. */
hash_T g;
- char_u *p = key;
while (*p != NUL)
{
@@ -438,6 +477,13 @@
if (g != 0)
hash ^= g >> 24; /* xor g's high 4 bits into hash */
}
+#else
+
+ /* A simplistic algorithm that appears to do very well.
+ * Suggested by George Reilly. */
+ while (*p != NUL)
+ hash = hash * 101 + *p++;
+#endif
return hash;
}