A few more tweaks.

[rsync.git] / hashtable.c

diff --git a/hashtable.c b/hashtable.c
index 238db08d00b5863d1d99f04516df72571f7ad02a..e272f439db5e81c2d8e42772eea7c3258a333eae 100644 (file)
--- a/hashtable.c
+++ b/hashtable.c
@@ -1,7 +1,7 @@
 /*
  * Routines to provide a memory-efficient hashtable.
  *
- * Copyright (C) 2007-2015 Wayne Davison
+ * Copyright (C) 2007-2020 Wayne Davison
  *
  * This program is free software; you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
@@ -35,9 +35,8 @@ struct hashtable *hashtable_create(int size, int key64)
                        size *= 2;
        }
 
-       if (!(tbl = new(struct hashtable))
-        || !(tbl->nodes = new_array0(char, size * node_size)))
-               out_of_memory("hashtable_create");
+       tbl = new(struct hashtable);
+       tbl->nodes = new_array0(char, size * node_size);
        tbl->size = size;
        tbl->entries = 0;
        tbl->node_size = node_size;
@@ -66,9 +65,19 @@ void hashtable_destroy(struct hashtable *tbl)
        free(tbl);
 }
 
-/* This returns the node for the indicated key, either newly created or
- * already existing.  Returns NULL if not allocating and not found. */
-void *hashtable_find(struct hashtable *tbl, int64 key, int allocate_if_missing)
+/* Returns the node that holds the indicated key if it exists. When it does not
+ * exist, it returns either NULL (when data_when_new is NULL), or it returns a
+ * new node with its node->data set to the indicated value.
+ *
+ * If your code doesn't know the data value for a new node in advance (usually
+ * because it doesn't know if a node is new or not) you should pass in a unique
+ * (non-0) value that you can use to check if the returned node is new. You can
+ * then overwrite the data with any value you want (even 0) since it only needs
+ * to be different than whatever data_when_new value you use later on.
+ *
+ * This return is a void* just because it might be pointing at a ht_int32_node
+ * or a ht_int64_node, and that makes the caller's assignment a little easier. */
+void *hashtable_find(struct hashtable *tbl, int64 key, void *data_when_new)
 {
        int key64 = tbl->key64;
        struct ht_int32_node *node;
@@ -79,13 +88,12 @@ void *hashtable_find(struct hashtable *tbl, int64 key, int allocate_if_missing)
                exit_cleanup(RERR_MESSAGEIO);
        }
 
-       if (allocate_if_missing && tbl->entries > HASH_LOAD_LIMIT(tbl->size)) {
+       if (data_when_new && tbl->entries > HASH_LOAD_LIMIT(tbl->size)) {
                void *old_nodes = tbl->nodes;
                int size = tbl->size * 2;
                int i;
 
-               if (!(tbl->nodes = new_array0(char, size * tbl->node_size)))
-                       out_of_memory("hashtable_node");
+               tbl->nodes = new_array0(char, size * tbl->node_size);
                tbl->size = size;
                tbl->entries = 0;
 
@@ -99,8 +107,12 @@ void *hashtable_find(struct hashtable *tbl, int64 key, int allocate_if_missing)
                        int64 move_key = HT_KEY(move_node, key64);
                        if (move_key == 0)
                                continue;
-                       node = hashtable_find(tbl, move_key, 1);
-                       node->data = move_node->data;
+                       if (move_node->data)
+                               hashtable_find(tbl, move_key, move_node->data);
+                       else {
+                               node = hashtable_find(tbl, move_key, "");
+                               node->data = 0;
+                       }
                }
 
                free(old_nodes);
@@ -155,7 +167,7 @@ void *hashtable_find(struct hashtable *tbl, int64 key, int allocate_if_missing)
                if (nkey == key)
                        return node;
                if (nkey == 0) {
-                       if (!allocate_if_missing)
+                       if (!data_when_new)
                                return NULL;
                        break;
                }
@@ -167,6 +179,7 @@ void *hashtable_find(struct hashtable *tbl, int64 key, int allocate_if_missing)
                ((struct ht_int64_node*)node)->key = key;
        else
                node->key = (int32)key;
+       node->data = data_when_new;
        tbl->entries++;
        return node;
 }
@@ -453,16 +466,27 @@ uint32_t hashlittle(const void *key, size_t length)
     switch(length)                   /* all the case statements fall through */
     {
     case 12: c+=((uint32_t)k[11])<<24;
+            /* FALLTHROUGH */
     case 11: c+=((uint32_t)k[10])<<16;
+            /* FALLTHROUGH */
     case 10: c+=((uint32_t)k[9])<<8;
+            /* FALLTHROUGH */
     case 9 : c+=k[8];
+            /* FALLTHROUGH */
     case 8 : b+=((uint32_t)k[7])<<24;
+            /* FALLTHROUGH */
     case 7 : b+=((uint32_t)k[6])<<16;
+            /* FALLTHROUGH */
     case 6 : b+=((uint32_t)k[5])<<8;
+            /* FALLTHROUGH */
     case 5 : b+=k[4];
+            /* FALLTHROUGH */
     case 4 : a+=((uint32_t)k[3])<<24;
+            /* FALLTHROUGH */
     case 3 : a+=((uint32_t)k[2])<<16;
+            /* FALLTHROUGH */
     case 2 : a+=((uint32_t)k[1])<<8;
+            /* FALLTHROUGH */
     case 1 : a+=k[0];
              break;
     case 0 : return c;