git://git.onelab.eu
/
sliver-openvswitch.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
Prepare for post-2.2.0 (2.2.90).
[sliver-openvswitch.git]
/
lib
/
hmap.c
diff --git
a/lib/hmap.c
b/lib/hmap.c
index
f15e72c
..
542d8b5
100644
(file)
--- a/
lib/hmap.c
+++ b/
lib/hmap.c
@@
-21,6
+21,9
@@
#include "coverage.h"
#include "random.h"
#include "util.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);
COVERAGE_DEFINE(hmap_pathological);
COVERAGE_DEFINE(hmap_expand);
@@
-85,7
+88,7
@@
hmap_moved(struct hmap *hmap)
}
static void
}
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;
{
struct hmap tmp;
size_t i;
@@
-109,7
+112,10
@@
resize(struct hmap *hmap, size_t new_mask)
count++;
}
if (count > 5) {
count++;
}
if (count > 5) {
+ static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(10, 10);
COVERAGE_INC(hmap_pathological);
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);
}
}
hmap_swap(hmap, &tmp);
@@
-136,38
+142,50
@@
calc_mask(size_t capacity)
return mask;
}
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
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);
{
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
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);
{
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
}
}
/* 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
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);
{
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
);
}
}
}
}
@@
-196,8
+214,8
@@
hmap_random_node(const struct hmap *hmap)
size_t n, i;
/* Choose a random non-empty bucket. */
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;
}
if (bucket) {
break;
}