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