From c0bb9790bd00a076c405f3eefe6c052427d8bac1 Mon Sep 17 00:00:00 2001 From: Chengwei Yang Date: Thu, 4 Jul 2013 15:59:38 +0800 Subject: [PATCH 1/2] Hash: clean up dead code and fix comments Signed-off-by: Chengwei Yang --- dbus/dbus-hash.c | 43 +++++++++++++++++-------------------------- 1 file changed, 17 insertions(+), 26 deletions(-) diff --git a/dbus/dbus-hash.c b/dbus/dbus-hash.c index c80835a..f75bcc0 100644 --- a/dbus/dbus-hash.c +++ b/dbus/dbus-hash.c @@ -110,14 +110,27 @@ * different buckets. The hash function was taken from a * random-number generator. (This is used to hash integers.) * - * The down_shift drops off the high bits of the hash index, and + * The down_shift drops off the low bits of the hash index, and * decreases as we increase the number of hash buckets (to keep more * range in the hash index). The mask also strips high bits and strips * fewer high bits as the number of hash buckets increases. - * I don't understand two things: why is the initial downshift 28 + * + * Q: I don't understand two things: why is the initial down_shift 28 * to keep 4 bits when the initial mask is 011 to keep 2 bits, * and why do we have both a mask and a downshift? - * + * + * A: In fact, we can merge down_shift and mask into one MASK, like + * at init: MASK = (0x3 << 28) + * at growing: MASK += (0x3 << 26) + * at shrinking: MASK -= (0x3 << 26) + * As the above example, it's ugly and confusing, also need another + * field to place the role as how many bits should we shift to left, + * that is the down_shift(may be up_shift) in fact. + * + * The answer to why down_shift init to 28 while mask to 3. Thinking + * again that we're creating hash table, so we *need* some chances to + * conflicts. So the highest *2* bits are left to do so, just as an + * granularity, in theoritical it can be any other value. */ #define RANDOM_INDEX(table, i) \ (((((intptr_t) (i))*1103515245) >> (table)->down_shift) & (table)->mask) @@ -364,25 +377,6 @@ _dbus_hash_table_unref (DBusHashTable *table) if (table->refcount == 0) { -#if 0 - DBusHashEntry *entry; - DBusHashEntry *next; - int i; - - /* Free the entries in the table. */ - for (i = 0; i < table->n_buckets; i++) - { - entry = table->buckets[i]; - while (entry != NULL) - { - next = entry->next; - - free_entry (table, entry); - - entry = next; - } - } -#else DBusHashEntry *entry; int i; @@ -399,7 +393,6 @@ _dbus_hash_table_unref (DBusHashTable *table) } /* We can do this very quickly with memory pools ;-) */ _dbus_mem_pool_free (table->entry_pool); -#endif /* Free the bucket array, if it was dynamically allocated. */ if (table->buckets != table->static_buckets) @@ -982,14 +975,12 @@ rebuild_table (DBusHashTable *table) table->mask = table->mask >> 2; /* keep 2 fewer high bits */ } -#if 0 - printf ("%s table to lo = %d hi = %d downshift = %d mask = 0x%x\n", + _dbus_verbose ("%s table to lo = %d hi = %d downshift = %d mask = 0x%x\n", growing ? "GROW" : "SHRINK", table->lo_rebuild_size, table->hi_rebuild_size, table->down_shift, table->mask); -#endif _dbus_assert (table->lo_rebuild_size >= 0); _dbus_assert (table->hi_rebuild_size > table->lo_rebuild_size); -- 1.7.9.5