doc/examples/rculfhash/cds_lfht_del.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 remove nodes from a RCU lock-free hash table.
   7  * 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         struct cds_lfht_node node;      /* Chaining in hash table */
  25         struct rcu_head rcu_head;       /* For call_rcu() */
  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 static
  39 void free_node(struct rcu_head *head)
  40 {
  41         struct mynode *node = caa_container_of(head, struct mynode, rcu_head);
  42
  43         free(node);
  44 }
  45
  46 int main(void)
  47 {
  48         int values[] = { -5, 42, 42, 36, 24, }; /* 42 is duplicated */
  49         int remove_values[] = { 42, 36, 24, 123, };
  50         struct cds_lfht *ht;    /* Hash table */
  51         unsigned int i;
  52         int ret = 0;
  53         uint32_t seed;
  54         struct cds_lfht_iter iter;      /* For iteration on hash table */
  55         struct cds_lfht_node *ht_node;
  56         struct mynode *node;
  57
  58         /*
  59          * Each thread need using RCU read-side need to be explicitly
  60          * registered.
  61          */
  62         urcu_memb_register_thread();
  63
  64         /* Use time as seed for hash table hashing. */
  65         seed = (uint32_t) time(NULL);
  66
  67         /*
  68          * Allocate hash table.
  69          */
  70         ht = cds_lfht_new_flavor(1, 1, 0,
  71                 CDS_LFHT_AUTO_RESIZE | CDS_LFHT_ACCOUNTING,
  72                 &urcu_memb_flavor, NULL);
  73         if (!ht) {
  74                 printf("Error allocating hash table\n");
  75                 ret = -1;
  76                 goto end;
  77         }
  78
  79         /*
  80          * Add nodes to hash table.
  81          */
  82         for (i = 0; i < CAA_ARRAY_SIZE(values); i++) {
  83                 unsigned long hash;
  84                 int value;
  85
  86                 node = malloc(sizeof(*node));
  87                 if (!node) {
  88                         ret = -1;
  89                         goto end;
  90                 }
  91
  92                 cds_lfht_node_init(&node->node);
  93                 value = values[i];
  94                 node->value = value;
  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                 urcu_memb_read_unlock();
 104         }
 105
 106         /*
 107          * Iterate over each hash table node. Those will appear in
 108          * random order, depending on the hash seed. Iteration needs to
 109          * be performed within RCU read-side critical section.
 110          */
 111         printf("hash table content (random order):");
 112         urcu_memb_read_lock();
 113         cds_lfht_for_each_entry(ht, &iter, node, node) {
 114                 printf(" %d", node->value);
 115         }
 116         urcu_memb_read_unlock();
 117         printf("\n");
 118
 119         /*
 120          * Remove one node for each key, if such a node is present.
 121          */
 122         printf("removing keys (single key, not duplicates):");
 123         for (i = 0; i < CAA_ARRAY_SIZE(remove_values); i++) {
 124                 unsigned long hash;
 125                 int value;
 126
 127                 value = remove_values[i];
 128                 hash = jhash(&value, sizeof(value), seed);
 129                 printf(" %d", value);
 130                 urcu_memb_read_lock();
 131                 cds_lfht_lookup(ht, hash, match, &value, &iter);
 132                 ht_node = cds_lfht_iter_get_node(&iter);
 133                 if (ht_node) {
 134                         ret = cds_lfht_del(ht, ht_node);
 135                         if (ret) {
 136                                 printf(" (concurrently deleted)");
 137                         } else {
 138                                 struct mynode *del_node =
 139                                         caa_container_of(ht_node,
 140                                                 struct mynode, node);
 141                                 urcu_memb_call_rcu(&del_node->rcu_head, free_node);
 142                         }
 143                 } else {
 144                         printf(" (not found)");
 145                 }
 146                 urcu_memb_read_unlock();
 147         }
 148         printf("\n");
 149
 150         printf("hash table content (random order):");
 151         urcu_memb_read_lock();
 152         cds_lfht_for_each_entry(ht, &iter, node, node) {
 153                 printf(" %d", node->value);
 154         }
 155         urcu_memb_read_unlock();
 156         printf("\n");
 157
 158 end:
 159         urcu_memb_unregister_thread();
 160         return ret;
 161 }