/usr/share/doc/liburcu-dev/examples/rculfhash/cds_lfht_for_each_entry_duplicate.c is in liburcu-dev 0.9.1-3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 | /*
* Copyright (C) 2013 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
*
* 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 <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <urcu.h> /* RCU flavor */
#include <urcu/rculfhash.h> /* RCU Lock-free hash table */
#include <urcu/compiler.h> /* 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;
}
|