doc/examples/rculfhash/cds_lfht_lookup.c

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