/*
- * Copyright (c) 2008, 2009 Nicira Networks.
+ * Copyright (c) 2008, 2009, 2010, 2013, 2014 Nicira, Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* hmap.h. */
#include <config.h>
-#include "hmap.h"
+#undef NDEBUG
+#include "openvswitch/hmap.h"
+#include <assert.h>
#include <string.h>
#include "hash.h"
+#include "ovstest.h"
+#include "random.h"
#include "util.h"
-#undef NDEBUG
-#include <assert.h>
-
/* Sample hmap element. */
struct element {
int value;
hmap_values = xmalloc(sizeof *sort_values * n);
i = 0;
- HMAP_FOR_EACH (e, struct element, node, hmap) {
+ HMAP_FOR_EACH (e, node, hmap) {
assert(i < n);
hmap_values[i++] = e->value;
}
for (i = 0; i < n; i++) {
size_t count = 0;
- HMAP_FOR_EACH_WITH_HASH (e, struct element, node,
- hash(values[i]), hmap) {
+ HMAP_FOR_EACH_WITH_HASH (e, node, hash(values[i]), hmap) {
count += e->value == values[i];
}
assert(count == 1);
shuffle(int *p, size_t n)
{
for (; n > 1; n--, p++) {
- int *q = &p[rand() % n];
+ int *q = &p[random_range(n)];
int tmp = *p;
*p = *q;
*q = tmp;
struct element *e;
printf("%s:", name);
- HMAP_FOR_EACH (e, struct element, node, hmap) {
- printf(" %d(%zu)", e->value, e->node.hash & hmap->mask);
+ HMAP_FOR_EACH (e, node, hmap) {
+ printf(" %d(%"PRIuSIZE")", e->value, e->node.hash & hmap->mask);
}
printf("\n");
}
}
static size_t
-constant_hash(int value UNUSED)
+constant_hash(int value OVS_UNUSED)
{
return 123;
}
i = 0;
n_remaining = n;
- HMAP_FOR_EACH_SAFE (e, next, struct element, node, &hmap) {
+ HMAP_FOR_EACH_SAFE (e, next, node, &hmap) {
assert(i < n);
if (pattern & (1ul << e->value)) {
size_t j;
}
}
+/* Tests that HMAP_FOR_EACH_POP removes every element of a hmap. */
+static void
+test_hmap_for_each_pop(hash_func *hash)
+{
+ enum { MAX_ELEMS = 10 };
+ size_t n;
+
+ for (n = 0; n <= MAX_ELEMS; n++) {
+ struct element elements[MAX_ELEMS];
+ int values[MAX_ELEMS];
+ struct hmap hmap;
+ struct element *e;
+ size_t n_remaining, i;
+
+ make_hmap(&hmap, elements, values, n, hash);
+
+ i = 0;
+ n_remaining = n;
+ HMAP_FOR_EACH_POP (e, node, &hmap) {
+ size_t j;
+
+ assert(i < n);
+
+ for (j = 0; ; j++) {
+ assert(j < n_remaining);
+ if (values[j] == e->value) {
+ values[j] = values[--n_remaining];
+ break;
+ }
+ }
+ /* Trash the element memory (including the hmap node) */
+ memset(e, 0, sizeof *e);
+ check_hmap(&hmap, values, n_remaining, hash);
+ i++;
+ }
+ assert(i == n);
+
+ hmap_destroy(&hmap);
+ }
+}
+
static void
run_test(void (*function)(hash_func *))
{
}
}
-int
-main(void)
+static void
+test_hmap_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
{
run_test(test_hmap_insert_delete);
run_test(test_hmap_for_each_safe);
run_test(test_hmap_reserve_shrink);
+ run_test(test_hmap_for_each_pop);
printf("\n");
- return 0;
}
+OVSTEST_REGISTER("test-hmap", test_hmap_main);