From 650b434b12597af49cad28c5c4b5faa3c98c04b0 Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Sun, 23 Jun 2013 14:01:01 -0400 Subject: [PATCH] doc/examples: cds_lfht_add_unique Signed-off-by: Mathieu Desnoyers --- .gitignore | 1 + doc/examples/Makefile.am | 2 + doc/examples/rculfhash/Makefile | 3 + .../rculfhash/Makefile.cds_lfht_add_unique | 22 +++ doc/examples/rculfhash/cds_lfht_add_unique.c | 143 ++++++++++++++++++ 5 files changed, 171 insertions(+) create mode 100644 doc/examples/rculfhash/Makefile.cds_lfht_add_unique create mode 100644 doc/examples/rculfhash/cds_lfht_add_unique.c diff --git a/.gitignore b/.gitignore index 9f46a43..0286f0a 100644 --- a/.gitignore +++ b/.gitignore @@ -107,6 +107,7 @@ doc/examples/lfstack/cds_lfs_pop_blocking doc/examples/lfstack/cds_lfs_pop_all_blocking doc/examples/rculfhash/cds_lfht_add +doc/examples/rculfhash/cds_lfht_add_unique doc/examples/rculfhash/cds_lfht_del #automake diff --git a/doc/examples/Makefile.am b/doc/examples/Makefile.am index 75021aa..60848e9 100644 --- a/doc/examples/Makefile.am +++ b/doc/examples/Makefile.am @@ -97,8 +97,10 @@ dist_doc_examples_rculfhash_DATA = \ rculfhash/Makefile \ rculfhash/jhash.h \ rculfhash/Makefile.cds_lfht_add \ + rculfhash/Makefile.cds_lfht_add_unique \ rculfhash/Makefile.cds_lfht_del \ rculfhash/cds_lfht_add.c \ + rculfhash/cds_lfht_add_unique.c \ rculfhash/cds_lfht_del.c if NO_SHARED diff --git a/doc/examples/rculfhash/Makefile b/doc/examples/rculfhash/Makefile index 87a6faf..009aa7c 100644 --- a/doc/examples/rculfhash/Makefile +++ b/doc/examples/rculfhash/Makefile @@ -13,8 +13,11 @@ all: $(MAKE) -f Makefile.cds_lfht_add + $(MAKE) -f Makefile.cds_lfht_add_unique $(MAKE) -f Makefile.cds_lfht_del .PHONY: clean clean: + $(MAKE) -f Makefile.cds_lfht_add clean + $(MAKE) -f Makefile.cds_lfht_add_unique clean $(MAKE) -f Makefile.cds_lfht_del clean diff --git a/doc/examples/rculfhash/Makefile.cds_lfht_add_unique b/doc/examples/rculfhash/Makefile.cds_lfht_add_unique new file mode 100644 index 0000000..c74c61e --- /dev/null +++ b/doc/examples/rculfhash/Makefile.cds_lfht_add_unique @@ -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_add_unique + +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_add_unique.c b/doc/examples/rculfhash/cds_lfht_add_unique.c new file mode 100644 index 0000000..ec594c8 --- /dev/null +++ b/doc/examples/rculfhash/cds_lfht_add_unique.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 add unique nodes into a RCU lock-free hash + * table. We use a "seqnum" field to show which node is staying in the + * 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 */ +}; + +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 */ + 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 cds_lfht_node *ht_node; + 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(); + ht_node = cds_lfht_add_unique(ht, hash, match, &value, + &node->node); + /* + * cds_lfht_add_unique() returns the added node if not + * already present, else returns the node matching the + * key. + */ + if (ht_node != &node->node) { + /* + * We found a match. Therefore, to ensure we + * don't add duplicates, cds_lfht_add_unique() + * acted as a RCU lookup, returning the found + * match. It did not add the new node to the + * hash table, so we can free it on the spot. + */ + printf("Not adding duplicate key: %d, seqnum: %d\n", + node->value, node->seqnum); + free(node); + } else { + 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"); + +end: + rcu_unregister_thread(); + return ret; +} -- 2.34.1