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