X-Git-Url: http://git.onelab.eu/?a=blobdiff_plain;f=lib%2Fhmap.c;h=542d8b5a8eb73550df8cb2322b9eb434a6f69bc9;hb=c5cf10598f8c9f4428291e9df3ecd72a05fb1ccf;hp=6b850fddcbf6d68206a560a4e3b127ce11a4fc3e;hpb=d76f09ea77e03ee5a3a7bb67bcab1ac4bb54172b;p=sliver-openvswitch.git

diff --git a/lib/hmap.c b/lib/hmap.c
index 6b850fddc..542d8b5a8 100644
--- a/lib/hmap.c
+++ b/lib/hmap.c
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2008, 2009, 2010 Nicira Networks.
+ * Copyright (c) 2008, 2009, 2010, 2012, 2013 Nicira, Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -16,12 +16,14 @@
 
 #include <config.h>
 #include "hmap.h"
-#include <assert.h>
 #include <stdint.h>
 #include <string.h>
 #include "coverage.h"
 #include "random.h"
 #include "util.h"
+#include "vlog.h"
+
+VLOG_DEFINE_THIS_MODULE(hmap);
 
 COVERAGE_DEFINE(hmap_pathological);
 COVERAGE_DEFINE(hmap_expand);
@@ -86,13 +88,12 @@ hmap_moved(struct hmap *hmap)
 }
 
 static void
-resize(struct hmap *hmap, size_t new_mask)
+resize(struct hmap *hmap, size_t new_mask, const char *where)
 {
     struct hmap tmp;
     size_t i;
 
-    assert(!(new_mask & (new_mask + 1)));
-    assert(new_mask != SIZE_MAX);
+    ovs_assert(is_pow2(new_mask + 1));
 
     hmap_init(&tmp);
     if (new_mask) {
@@ -111,7 +112,10 @@ resize(struct hmap *hmap, size_t new_mask)
             count++;
         }
         if (count > 5) {
+            static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(10, 10);
             COVERAGE_INC(hmap_pathological);
+            VLOG_DBG_RL(&rl, "%s: %d nodes in bucket (%"PRIuSIZE" nodes, %"PRIuSIZE" buckets)",
+                        where, count, hmap->n, hmap->mask + 1);
         }
     }
     hmap_swap(hmap, &tmp);
@@ -138,38 +142,50 @@ calc_mask(size_t capacity)
     return mask;
 }
 
-/* Expands 'hmap', if necessary, to optimize the performance of searches. */
+/* Expands 'hmap', if necessary, to optimize the performance of searches.
+ *
+ * ('where' is used in debug logging.  Commonly one would use hmap_expand() to
+ * automatically provide the caller's source file and line number for
+ * 'where'.) */
 void
-hmap_expand(struct hmap *hmap)
+hmap_expand_at(struct hmap *hmap, const char *where)
 {
     size_t new_mask = calc_mask(hmap->n);
     if (new_mask > hmap->mask) {
         COVERAGE_INC(hmap_expand);
-        resize(hmap, new_mask);
+        resize(hmap, new_mask, where);
     }
 }
 
-/* Shrinks 'hmap', if necessary, to optimize the performance of iteration. */
+/* Shrinks 'hmap', if necessary, to optimize the performance of iteration.
+ *
+ * ('where' is used in debug logging.  Commonly one would use hmap_shrink() to
+ * automatically provide the caller's source file and line number for
+ * 'where'.) */
 void
-hmap_shrink(struct hmap *hmap)
+hmap_shrink_at(struct hmap *hmap, const char *where)
 {
     size_t new_mask = calc_mask(hmap->n);
     if (new_mask < hmap->mask) {
         COVERAGE_INC(hmap_shrink);
-        resize(hmap, new_mask);
+        resize(hmap, new_mask, where);
     }
 }
 
 /* Expands 'hmap', if necessary, to optimize the performance of searches when
  * it has up to 'n' elements.  (But iteration will be slow in a hash map whose
- * allocated capacity is much higher than its current number of nodes.)  */
+ * allocated capacity is much higher than its current number of nodes.)
+ *
+ * ('where' is used in debug logging.  Commonly one would use hmap_reserve() to
+ * automatically provide the caller's source file and line number for
+ * 'where'.) */
 void
-hmap_reserve(struct hmap *hmap, size_t n)
+hmap_reserve_at(struct hmap *hmap, size_t n, const char *where)
 {
     size_t new_mask = calc_mask(n);
     if (new_mask > hmap->mask) {
         COVERAGE_INC(hmap_reserve);
-        resize(hmap, new_mask);
+        resize(hmap, new_mask, where);
     }
 }
 
@@ -198,8 +214,8 @@ hmap_random_node(const struct hmap *hmap)
     size_t n, i;
 
     /* Choose a random non-empty bucket. */
-    for (i = random_uint32(); ; i++) {
-        bucket = hmap->buckets[i & hmap->mask];
+    for (;;) {
+        bucket = hmap->buckets[random_uint32() & hmap->mask];
         if (bucket) {
             break;
         }
@@ -218,3 +234,61 @@ hmap_random_node(const struct hmap *hmap)
     }
     return node;
 }
+
+/* Returns the next node in 'hmap' in hash order, or NULL if no nodes remain in
+ * 'hmap'.  Uses '*bucketp' and '*offsetp' to determine where to begin
+ * iteration, and stores new values to pass on the next iteration into them
+ * before returning.
+ *
+ * It's better to use plain HMAP_FOR_EACH and related functions, since they are
+ * faster and better at dealing with hmaps that change during iteration.
+ *
+ * Before beginning iteration, store 0 into '*bucketp' and '*offsetp'.
+ */
+struct hmap_node *
+hmap_at_position(const struct hmap *hmap,
+                 uint32_t *bucketp, uint32_t *offsetp)
+{
+    size_t offset;
+    size_t b_idx;
+
+    offset = *offsetp;
+    for (b_idx = *bucketp; b_idx <= hmap->mask; b_idx++) {
+        struct hmap_node *node;
+        size_t n_idx;
+
+        for (n_idx = 0, node = hmap->buckets[b_idx]; node != NULL;
+             n_idx++, node = node->next) {
+            if (n_idx == offset) {
+                if (node->next) {
+                    *bucketp = node->hash & hmap->mask;
+                    *offsetp = offset + 1;
+                } else {
+                    *bucketp = (node->hash & hmap->mask) + 1;
+                    *offsetp = 0;
+                }
+                return node;
+            }
+        }
+        offset = 0;
+    }
+
+    *bucketp = 0;
+    *offsetp = 0;
+    return NULL;
+}
+
+/* Returns true if 'node' is in 'hmap', false otherwise. */
+bool
+hmap_contains(const struct hmap *hmap, const struct hmap_node *node)
+{
+    struct hmap_node *p;
+
+    for (p = hmap_first_in_bucket(hmap, node->hash); p; p = p->next) {
+        if (p == node) {
+            return true;
+        }
+    }
+
+    return false;
+}