diff options
| -rw-r--r-- | src/vppinfra/bihash_template.c | 32 | ||||
| -rw-r--r-- | src/vppinfra/bihash_template.h | 6 | ||||
| -rw-r--r-- | src/vppinfra/test_bihash_template.c | 45 |
3 files changed, 81 insertions, 2 deletions
diff --git a/src/vppinfra/bihash_template.c b/src/vppinfra/bihash_template.c index 41d7c7ce1d6..18d74d9ea2f 100644 --- a/src/vppinfra/bihash_template.c +++ b/src/vppinfra/bihash_template.c @@ -269,8 +269,9 @@ BV (split_and_rehash_linear) return new_values; } -int BV (clib_bihash_add_del) - (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, int is_add) +static inline int BV (clib_bihash_add_del_inline) + (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, int is_add, + int (*is_stale_cb) (BVT (clib_bihash_kv) *, void *), void *arg) { u32 bucket_index; BVT (clib_bihash_bucket) * b, tmp_b; @@ -366,6 +367,20 @@ int BV (clib_bihash_add_del) return (0); } } + /* look for stale data to overwrite */ + if (is_stale_cb) + { + for (i = 0; i < limit; i++) + { + if (is_stale_cb (&(v->kvp[i]), arg)) + { + CLIB_MEMORY_BARRIER (); + clib_memcpy (&(v->kvp[i]), add_v, sizeof (*add_v)); + BV (clib_bihash_unlock_bucket) (b); + return (0); + } + } + } /* Out of space in this bucket, split the bucket... */ } else /* delete case */ @@ -484,6 +499,19 @@ expand_ok: return (0); } +int BV (clib_bihash_add_del) + (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, int is_add) +{ + return BV (clib_bihash_add_del_inline) (h, add_v, is_add, 0, 0); +} + +int BV (clib_bihash_add_or_overwrite_stale) + (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, + int (*stale_callback) (BVT (clib_bihash_kv) *, void *), void *arg) +{ + return BV (clib_bihash_add_del_inline) (h, add_v, 1, stale_callback, arg); +} + int BV (clib_bihash_search) (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep) diff --git a/src/vppinfra/bihash_template.h b/src/vppinfra/bihash_template.h index 9bf4737cd84..cfb8ceac69e 100644 --- a/src/vppinfra/bihash_template.h +++ b/src/vppinfra/bihash_template.h @@ -176,6 +176,12 @@ void BV (clib_bihash_free) (BVT (clib_bihash) * h); int BV (clib_bihash_add_del) (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, int is_add); +int BV (clib_bihash_add_or_overwrite_stale) (BVT (clib_bihash) * h, + BVT (clib_bihash_kv) * add_v, + int (*is_stale_cb) (BVT + (clib_bihash_kv) + *, void *), + void *arg); int BV (clib_bihash_search) (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * search_v, BVT (clib_bihash_kv) * return_v); diff --git a/src/vppinfra/test_bihash_template.c b/src/vppinfra/test_bihash_template.c index 80e11511f62..e52f2740b3b 100644 --- a/src/vppinfra/test_bihash_template.c +++ b/src/vppinfra/test_bihash_template.c @@ -35,6 +35,7 @@ typedef struct u32 ncycles; u32 report_every_n; u32 search_iter; + u32 noverwritten; int careful_delete_tests; int verbose; int non_random_keys; @@ -95,6 +96,44 @@ test_bihash_vec64 (test_main_t * tm) return 0; } +static int +stale_cb (BVT (clib_bihash_kv) * kv, void *ctx) +{ + test_main_t *tm = ctx; + + tm->noverwritten++; + + return 1; +} + +static clib_error_t * +test_bihash_stale_overwrite (test_main_t * tm) +{ + BVT (clib_bihash) * h; + BVT (clib_bihash_kv) kv; + int i; + tm->noverwritten = 0; + + h = &tm->hash; + + BV (clib_bihash_init) (h, "test", tm->nbuckets, tm->hash_memory_size); + + fformat (stdout, "Add %d items to %d buckets\n", tm->nitems, tm->nbuckets); + + for (i = 0; i < tm->nitems; i++) + { + kv.key = i; + kv.value = 1; + + BV (clib_bihash_add_or_overwrite_stale) (h, &kv, stale_cb, tm); + } + + fformat (stdout, "%d items overwritten\n", tm->noverwritten); + fformat (stdout, "%U", BV (format_bihash), h, 0); + + return 0; +} + void * test_bihash_thread_fn (void *arg) { @@ -424,6 +463,8 @@ test_bihash_main (test_main_t * tm) which = 2; else if (unformat (i, "verbose")) tm->verbose = 1; + else if (unformat (i, "stale-overwrite")) + which = 3; else return clib_error_return (0, "unknown input '%U'", format_unformat_error, i); @@ -449,6 +490,10 @@ test_bihash_main (test_main_t * tm) error = test_bihash_threads (tm); break; + case 3: + error = test_bihash_stale_overwrite (tm); + break; + default: return clib_error_return (0, "no such test?"); } |