From b5e35d2dfb026d7f06eec10b3d4794646680429f Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Sun, 23 Jun 2013 15:03:45 -0400 Subject: [PATCH] doc/examples: cds_lfht_for_each_entry_duplicate Signed-off-by: Mathieu Desnoyers --- .gitignore | 1 + doc/examples/Makefile.am | 4 +- doc/examples/rculfhash/Makefile | 2 + ...Makefile.cds_lfht_for_each_entry_duplicate | 22 +++ .../cds_lfht_for_each_entry_duplicate.c | 143 ++++++++++++++++++ 5 files changed, 171 insertions(+), 1 deletion(-) create mode 100644 doc/examples/rculfhash/Makefile.cds_lfht_for_each_entry_duplicate create mode 100644 doc/examples/rculfhash/cds_lfht_for_each_entry_duplicate.c diff --git a/.gitignore b/.gitignore index 9d49661..00dbc40 100644 --- a/.gitignore +++ b/.gitignore @@ -112,6 +112,7 @@ doc/examples/rculfhash/cds_lfht_add_replace doc/examples/rculfhash/cds_lfht_del doc/examples/rculfhash/cds_lfht_destroy doc/examples/rculfhash/cds_lfht_lookup +doc/examples/rculfhash/cds_lfht_for_each_entry_duplicate #automake /config.h diff --git a/doc/examples/Makefile.am b/doc/examples/Makefile.am index 9441296..16477b5 100644 --- a/doc/examples/Makefile.am +++ b/doc/examples/Makefile.am @@ -102,12 +102,14 @@ dist_doc_examples_rculfhash_DATA = \ rculfhash/Makefile.cds_lfht_del \ rculfhash/Makefile.cds_lfht_destroy \ rculfhash/Makefile.cds_lfht_lookup \ + rculfhash/Makefile.cds_lfht_for_each_entry_duplicate \ rculfhash/cds_lfht_add.c \ rculfhash/cds_lfht_add_unique.c \ rculfhash/cds_lfht_add_replace.c \ rculfhash/cds_lfht_del.c \ rculfhash/cds_lfht_destroy.c \ - rculfhash/cds_lfht_lookup.c + rculfhash/cds_lfht_lookup.c \ + rculfhash/cds_lfht_for_each_entry_duplicate.c if NO_SHARED # Don't build examples if shared libraries support was explicitly diff --git a/doc/examples/rculfhash/Makefile b/doc/examples/rculfhash/Makefile index 2739499..b0dd948 100644 --- a/doc/examples/rculfhash/Makefile +++ b/doc/examples/rculfhash/Makefile @@ -18,6 +18,7 @@ all: $(MAKE) -f Makefile.cds_lfht_del $(MAKE) -f Makefile.cds_lfht_destroy $(MAKE) -f Makefile.cds_lfht_lookup + $(MAKE) -f Makefile.cds_lfht_for_each_entry_duplicate .PHONY: clean clean: @@ -27,3 +28,4 @@ clean: $(MAKE) -f Makefile.cds_lfht_del clean $(MAKE) -f Makefile.cds_lfht_destroy clean $(MAKE) -f Makefile.cds_lfht_lookup clean + $(MAKE) -f Makefile.cds_lfht_for_each_entry_duplicate clean diff --git a/doc/examples/rculfhash/Makefile.cds_lfht_for_each_entry_duplicate b/doc/examples/rculfhash/Makefile.cds_lfht_for_each_entry_duplicate new file mode 100644 index 0000000..7020b14 --- /dev/null +++ b/doc/examples/rculfhash/Makefile.cds_lfht_for_each_entry_duplicate @@ -0,0 +1,22 @@ +# Copyright (C) 2013 Mathieu Desnoyers +# +# THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED +# OR IMPLIED. ANY USE IS AT YOUR OWN RISK. +# +# Permission is hereby granted to use or copy this program for any +# purpose, provided the above notices are retained on all copies. +# Permission to modify the code and to distribute modified code is +# granted, provided the above notices are retained, and a notice that +# the code was modified is included with the above copyright notice. +# +# This makefile is purposefully kept simple to support GNU and BSD make. + +EXAMPLE_NAME = cds_lfht_for_each_entry_duplicate + +SOURCES = $(EXAMPLE_NAME).c +DEPS = jhash.h +OBJECTS = $(EXAMPLE_NAME).o +BINARY = $(EXAMPLE_NAME) +LIBS = -lurcu-cds -lurcu + +include ../Makefile.examples.template diff --git a/doc/examples/rculfhash/cds_lfht_for_each_entry_duplicate.c b/doc/examples/rculfhash/cds_lfht_for_each_entry_duplicate.c new file mode 100644 index 0000000..e57509d --- /dev/null +++ b/doc/examples/rculfhash/cds_lfht_for_each_entry_duplicate.c @@ -0,0 +1,143 @@ +/* + * Copyright (C) 2013 Mathieu Desnoyers + * + * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED + * OR IMPLIED. ANY USE IS AT YOUR OWN RISK. + * + * Permission is hereby granted to use or copy this program for any + * purpose, provided the above notices are retained on all copies. + * Permission to modify the code and to distribute modified code is + * granted, provided the above notices are retained, and a notice that + * the code was modified is included with the above copyright notice. + * + * This example shows how to iterate on duplicate keys within a RCU + * lock-free hash table. This hash table requires using a RCU scheme. + */ + +#include +#include +#include + +#include /* RCU flavor */ +#include /* RCU Lock-free hash table */ +#include /* For CAA_ARRAY_SIZE */ +#include "jhash.h" /* Example hash function */ + +/* + * Nodes populated into the hash table. + */ +struct mynode { + int value; /* Node content */ + int seqnum; /* Our node sequence number */ + struct cds_lfht_node node; /* Chaining in hash table */ +}; + +static +int match(struct cds_lfht_node *ht_node, const void *_key) +{ + struct mynode *node = + caa_container_of(ht_node, struct mynode, node); + const unsigned int *key = _key; + + return *key == node->value; +} + +int main(int argc, char **argv) +{ + int values[] = { -5, 42, 42, 36, 24, }; /* 42 is duplicated */ + int lookup_values[] = { 42, 200, 36, }; + struct cds_lfht *ht; /* Hash table */ + unsigned int i; + int ret = 0, seqnum = 0; + uint32_t seed; + struct cds_lfht_iter iter; /* For iteration on hash table */ + struct mynode *node; + + /* + * Each thread need using RCU read-side need to be explicitly + * registered. + */ + rcu_register_thread(); + + /* Use time as seed for hash table hashing. */ + seed = (uint32_t) time(NULL); + + /* + * Allocate hash table. + */ + ht = cds_lfht_new(1, 1, 0, + CDS_LFHT_AUTO_RESIZE | CDS_LFHT_ACCOUNTING, + NULL); + if (!ht) { + printf("Error allocating hash table\n"); + ret = -1; + goto end; + } + + /* + * Add nodes to hash table. + */ + for (i = 0; i < CAA_ARRAY_SIZE(values); i++) { + unsigned long hash; + int value; + + node = malloc(sizeof(*node)); + if (!node) { + ret = -1; + goto end; + } + + cds_lfht_node_init(&node->node); + value = values[i]; + node->value = value; + node->seqnum = seqnum++; + hash = jhash(&value, sizeof(value), seed); + + /* + * cds_lfht_add() needs to be called from RCU read-side + * critical section. + */ + rcu_read_lock(); + cds_lfht_add(ht, hash, &node->node); + printf("Add (key: %d, seqnum: %d)\n", + node->value, node->seqnum); + rcu_read_unlock(); + } + + /* + * Iterate over each hash table node. Those will appear in + * random order, depending on the hash seed. Iteration needs to + * be performed within RCU read-side critical section. + */ + printf("hash table content (random order):"); + rcu_read_lock(); + cds_lfht_for_each_entry(ht, &iter, node, node) { + printf(" (key: %d, seqnum: %d)", + node->value, node->seqnum); + } + rcu_read_unlock(); + printf("\n"); + + /* + * Lookup queries. Note that which node (seqnum) within + * duplicates will be found by lookup is random. + */ + printf("Lookups, with iteration on duplicates:\n"); + for (i = 0; i < CAA_ARRAY_SIZE(lookup_values); i++) { + int value = lookup_values[i]; + unsigned long hash = jhash(&value, sizeof(value), seed); + + printf("lookup key: %d\n", value); + rcu_read_lock(); + cds_lfht_for_each_entry_duplicate(ht, hash, match, + &value, &iter, node, node) { + printf(" (key %d, seqnum %d) found\n", + node->value, node->seqnum); + } + rcu_read_unlock(); + } + +end: + rcu_unregister_thread(); + return ret; +} -- 2.34.1