6b06095df1631f0a0640837a72cf0aac58985ec4
[urcu.git] / doc / examples / rculfhash / cds_lfht_lookup.c
1 // SPDX-FileCopyrightText: 2013 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
2 //
3 // SPDX-License-Identifier: MIT
4
5 /*
6 * This example shows how to lookup keys within a RCU lock-free hash
7 * table. This hash table requires using a RCU scheme.
8 */
9
10 #include <stdio.h>
11 #include <stdlib.h>
12 #include <time.h>
13
14 #include <urcu/urcu-memb.h> /* RCU flavor */
15 #include <urcu/rculfhash.h> /* RCU Lock-free hash table */
16 #include <urcu/compiler.h> /* For CAA_ARRAY_SIZE */
17 #include "jhash.h" /* Example hash function */
18
19 /*
20 * Nodes populated into the hash table.
21 */
22 struct mynode {
23 int value; /* Node content */
24 int seqnum; /* Our node sequence number */
25 struct cds_lfht_node node; /* Chaining in hash table */
26 };
27
28 static
29 int match(struct cds_lfht_node *ht_node, const void *_key)
30 {
31 struct mynode *node =
32 caa_container_of(ht_node, struct mynode, node);
33 const int *key = _key;
34
35 return *key == node->value;
36 }
37
38 int main(void)
39 {
40 int values[] = { -5, 42, 42, 36, 24, }; /* 42 is duplicated */
41 int lookup_values[] = { 42, 200, 36, };
42 struct cds_lfht *ht; /* Hash table */
43 unsigned int i;
44 int ret = 0, seqnum = 0;
45 uint32_t seed;
46 struct cds_lfht_iter iter; /* For iteration on hash table */
47 struct cds_lfht_node *ht_node;
48 struct mynode *node;
49
50 /*
51 * Each thread need using RCU read-side need to be explicitly
52 * registered.
53 */
54 urcu_memb_register_thread();
55
56 /* Use time as seed for hash table hashing. */
57 seed = (uint32_t) time(NULL);
58
59 /*
60 * Allocate hash table.
61 */
62 ht = cds_lfht_new_flavor(1, 1, 0,
63 CDS_LFHT_AUTO_RESIZE | CDS_LFHT_ACCOUNTING,
64 &urcu_memb_flavor, NULL);
65 if (!ht) {
66 printf("Error allocating hash table\n");
67 ret = -1;
68 goto end;
69 }
70
71 /*
72 * Add nodes to hash table.
73 */
74 for (i = 0; i < CAA_ARRAY_SIZE(values); i++) {
75 unsigned long hash;
76 int value;
77
78 node = malloc(sizeof(*node));
79 if (!node) {
80 ret = -1;
81 goto end;
82 }
83
84 cds_lfht_node_init(&node->node);
85 value = values[i];
86 node->value = value;
87 node->seqnum = seqnum++;
88 hash = jhash(&value, sizeof(value), seed);
89
90 /*
91 * cds_lfht_add() needs to be called from RCU read-side
92 * critical section.
93 */
94 urcu_memb_read_lock();
95 cds_lfht_add(ht, hash, &node->node);
96 printf("Add (key: %d, seqnum: %d)\n",
97 node->value, node->seqnum);
98 urcu_memb_read_unlock();
99 }
100
101 /*
102 * Iterate over each hash table node. Those will appear in
103 * random order, depending on the hash seed. Iteration needs to
104 * be performed within RCU read-side critical section.
105 */
106 printf("hash table content (random order):");
107 urcu_memb_read_lock();
108 cds_lfht_for_each_entry(ht, &iter, node, node) {
109 printf(" (key: %d, seqnum: %d)",
110 node->value, node->seqnum);
111 }
112 urcu_memb_read_unlock();
113 printf("\n");
114
115 /*
116 * Lookup queries. Note that which node (seqnum) within
117 * duplicates will be found by lookup is random.
118 */
119 printf("Lookups:\n");
120 for (i = 0; i < CAA_ARRAY_SIZE(lookup_values); i++) {
121 int value = lookup_values[i];
122 unsigned long hash = jhash(&value, sizeof(value), seed);
123
124 urcu_memb_read_lock();
125 cds_lfht_lookup(ht, hash, match, &value, &iter);
126 ht_node = cds_lfht_iter_get_node(&iter);
127 if (!ht_node) {
128 printf("Key %d not found\n", value);
129 } else {
130 node = caa_container_of(ht_node, struct mynode, node);
131 printf("(key %d, seqnum %d) found\n",
132 node->value, node->seqnum);
133 }
134 urcu_memb_read_unlock();
135 }
136
137 end:
138 urcu_memb_unregister_thread();
139 return ret;
140 }
This page took 0.032527 seconds and 4 git commands to generate.