/*
- * Copyright (c) 2008, 2009, 2010, 2012, 2013 Nicira, Inc.
+ * Copyright (c) 2008, 2009, 2010, 2012, 2013, 2015 Nicira, Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
#include "coverage.h"
#include "random.h"
#include "util.h"
+#include "openvswitch/vlog.h"
+
+VLOG_DEFINE_THIS_MODULE(hmap);
COVERAGE_DEFINE(hmap_pathological);
COVERAGE_DEFINE(hmap_expand);
* not free memory allocated for 'hmap'.
*
* This function is appropriate when 'hmap' will soon have about as many
- * elements as it before. If 'hmap' will likely have fewer elements than
- * before, use hmap_destroy() followed by hmap_clear() to save memory and
+ * elements as it did before. If 'hmap' will likely have fewer elements than
+ * before, use hmap_destroy() followed by hmap_init() to save memory and
* iteration time. */
void
hmap_clear(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;
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);
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);
}
}
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;
}