Re: Mapping mixup

[Arne Goedeke]

On Sun, 4 Sep 2011, Henrik Grubbstr?m (Lysator) @ Pike (-) developers forum 
wrote:

No. It's comparing the hashtable size with the minimum required number
of keypairs, these two usually differ by a factor of AVG_LINK_LENGTH.

One optimization we should probably do is to check if the mapping size
is already at the minimum before rehashing to a smaller one.
Currently it seems like it would rehash to the same size when
removing an element from a mapping thats already at the minimum.

Here is a patch. Maybe someone can ack this, before I push it.

diff --git a/src/mapping.c b/src/mapping.c
index def183a..ef693b2 100644
--- a/src/mapping.c
+++ b/src/mapping.c
@@ -27,6 +27,7 @@

 #define AVG_LINK_LENGTH 4
 #define MIN_LINK_LENGTH 1
+#define MIN_HASHSIZE   32
 #define MAP_SLOTS(X) ((X)?((X)+((X)>>4)+8):0)

 struct mapping *first_mapping;
@@ -182,7 +183,7 @@ static void init_mapping(struct mapping *m,
   if(size)
   {
     hashsize = size / AVG_LINK_LENGTH + 1;
-    hashsize = (hashsize <= 32) ? 32 : find_next_power(hashsize);
+    hashsize = (hashsize <= MIN_HASHSIZE) ? MIN_HASHSIZE : 
find_next_power(hashsize);

     e=MAPPING_DATA_SIZE(hashsize, size);

@@ -1017,7 +1018,7 @@ PMOD_EXPORT void map_delete_no_free(struct mapping *m,
     m->debug_size--;
 #endif

-  if(md->size < (md->hashsize + 1) * MIN_LINK_LENGTH)
+  if((md->hashsize > MIN_HASHSIZE) && (md->size < (md->hashsize + 1) * 
MIN_LINK_LENGTH))
   {
     debug_malloc_touch(m);
     rehash(m, MAP_SLOTS(m->data->size));
@@ -1092,7 +1093,7 @@ PMOD_EXPORT void check_mapping_for_destruct(struct 
mapping *m)
     md->val_types = val_types;
     md->ind_types = ind_types;

-    if(MAP_SLOTS(md->size) < md->hashsize * MIN_LINK_LENGTH)
+    if((md->hashsize > MIN_HASHSIZE) && (MAP_SLOTS(md->size) < md->hashsize * 
MIN_LINK_LENGTH))
     {
       debug_malloc_touch(m);
       rehash(m, MAP_SLOTS(md->size));