From 2dbf31c9e6479b126f67a3494a9b4dfaa57b39b3 Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Sun, 23 Jun 2013 14:56:44 -0400 Subject: [PATCH] doc/examples: cds_lfht_lookup Signed-off-by: Mathieu Desnoyers --- .gitignore | 1 + doc/examples/Makefile.am | 4 +- doc/examples/rculfhash/Makefile | 2 + .../rculfhash/Makefile.cds_lfht_lookup | 22 +++ doc/examples/rculfhash/cds_lfht_lookup.c | 147 ++++++++++++++++++ 5 files changed, 175 insertions(+), 1 deletion(-) create mode 100644 doc/examples/rculfhash/Makefile.cds_lfht_lookup create mode 100644 doc/examples/rculfhash/cds_lfht_lookup.c diff --git a/.gitignore b/.gitignore index bca252a..9d49661 100644 --- a/.gitignore +++ b/.gitignore @@ -111,6 +111,7 @@ doc/examples/rculfhash/cds_lfht_add_unique 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 #automake /config.h diff --git a/doc/examples/Makefile.am b/doc/examples/Makefile.am index 31bac6d..9441296 100644 --- a/doc/examples/Makefile.am +++ b/doc/examples/Makefile.am @@ -101,11 +101,13 @@ dist_doc_examples_rculfhash_DATA = \ rculfhash/Makefile.cds_lfht_add_replace \ rculfhash/Makefile.cds_lfht_del \ rculfhash/Makefile.cds_lfht_destroy \ + rculfhash/Makefile.cds_lfht_lookup \ 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_destroy.c \ + rculfhash/cds_lfht_lookup.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 d7918ee..2739499 100644 --- a/doc/examples/rculfhash/Makefile +++ b/doc/examples/rculfhash/Makefile @@ -17,6 +17,7 @@ all: $(MAKE) -f Makefile.cds_lfht_add_replace $(MAKE) -f Makefile.cds_lfht_del $(MAKE) -f Makefile.cds_lfht_destroy + $(MAKE) -f Makefile.cds_lfht_lookup .PHONY: clean clean: @@ -25,3 +26,4 @@ clean: $(MAKE) -f Makefile.cds_lfht_add_replace clean $(MAKE) -f Makefile.cds_lfht_del clean $(MAKE) -f Makefile.cds_lfht_destroy clean + $(MAKE) -f Makefile.cds_lfht_lookup clean diff --git a/doc/examples/rculfhash/Makefile.cds_lfht_lookup b/doc/examples/rculfhash/Makefile.cds_lfht_lookup new file mode 100644 index 0000000..79eb6c4 --- /dev/null +++ b/doc/examples/rculfhash/Makefile.cds_lfht_lookup @@ -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_lookup + +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_lookup.c b/doc/examples/rculfhash/cds_lfht_lookup.c new file mode 100644 index 0000000..e76827b --- /dev/null +++ b/doc/examples/rculfhash/cds_lfht_lookup.c @@ -0,0 +1,147 @@ +/* + * 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 lookup 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 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(); + 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:\n"); + for (i = 0; i < CAA_ARRAY_SIZE(lookup_values); i++) { + int value = lookup_values[i]; + unsigned long hash = jhash(&value, sizeof(value), seed); + + rcu_read_lock(); + cds_lfht_lookup(ht, hash, match, &value, &iter); + ht_node = cds_lfht_iter_get_node(&iter); + if (!ht_node) { + printf("Key %d not found\n", value); + } else { + node = caa_container_of(ht_node, struct mynode, node); + printf("(key %d, seqnum %d) found\n", + node->value, node->seqnum); + } + rcu_read_unlock(); + } + +end: + rcu_unregister_thread(); + return ret; +} -- 2.34.1