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 }