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