Home | History | Annotate | Line # | Download | only in rculfhash 
      1 // SPDX-FileCopyrightText: 2013 Mathieu Desnoyers <mathieu.desnoyers (at) 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 }
    141