[urcu.git] / rculfhash-internal.h

#ifndef _URCU_RCULFHASH_INTERNAL_H
#define _URCU_RCULFHASH_INTERNAL_H

/*
 * urcu/rculfhash-internal.h
 *
 * Internal header for Lock-Free RCU Hash Table
 *
 * Copyright 2011 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
 * Copyright 2011 - Lai Jiangshan <laijs@cn.fujitsu.com>
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 */

#include <urcu/rculfhash.h>

#ifdef DEBUG
#define dbg_printf(fmt, args...)     printf("[debug rculfhash] " fmt, ## args)
#else
#define dbg_printf(fmt, args...)
#endif

#if (CAA_BITS_PER_LONG == 32)
#define MAX_TABLE_ORDER			32
#else
#define MAX_TABLE_ORDER			64
#endif

#ifndef min
#define min(a, b)	((a) < (b) ? (a) : (b))
#endif

#ifndef max
#define max(a, b)	((a) > (b) ? (a) : (b))
#endif

struct ht_items_count;

/*
 * cds_lfht: Top-level data structure representing a lock-free hash
 * table. Defined in the implementation file to make it be an opaque
 * cookie to users.
 */
struct cds_lfht {
	unsigned long size;	/* always a power of 2, shared (RCU) */
	int flags;

	/*
	 * We need to put the work threads offline (QSBR) when taking this
	 * mutex, because we use synchronize_rcu within this mutex critical
	 * section, which waits on read-side critical sections, and could
	 * therefore cause grace-period deadlock if we hold off RCU G.P.
	 * completion.
	 */
	pthread_mutex_t resize_mutex;	/* resize mutex: add/del mutex */
	pthread_attr_t *resize_attr;	/* Resize threads attributes */
	unsigned int in_progress_resize, in_progress_destroy;
	unsigned long resize_target;
	int resize_initiated;
	const struct rcu_flavor_struct *flavor;

	long count;			/* global approximate item count */
	struct ht_items_count *split_count;	/* split item count */

	/* memory management related fields are located at the end */
	const struct cds_lfht_mm_type *mm;

	unsigned long min_alloc_buckets_order;
	unsigned long min_nr_alloc_buckets;
	unsigned long max_nr_buckets;

	struct cds_lfht_node *(*bucket_at)(struct cds_lfht *ht,
			unsigned long index);

	union {
		/*
		 * Contains the per order-index-level bucket node table.
		 * The size of each bucket node table is half the number
		 * of hashes contained in this order (except for order 0).
		 * The minimum allocation buckets size parameter allows
		 * combining the bucket node arrays of the lowermost
		 * levels to improve cache locality for small index orders.
		 */
		struct cds_lfht_node *tbl_order[MAX_TABLE_ORDER];
	};
};

extern unsigned int fls_ulong(unsigned long x);
extern int get_count_order_ulong(unsigned long x);

#ifdef POISON_FREE
#define poison_free(ptr)					\
	do {							\
		if (ptr) {					\
			memset(ptr, 0x42, sizeof(*(ptr)));	\
			free(ptr);				\
		}						\
	} while (0)
#else
#define poison_free(ptr)	free(ptr)
#endif

#endif /* _URCU_RCULFHASH_INTERNAL_H */
Commit	Line	Data
0b6aa001 LJ	1	#ifndef _URCU_RCULFHASH_INTERNAL_H
	2	#define _URCU_RCULFHASH_INTERNAL_H
	3
	4	/*
	5	* urcu/rculfhash-internal.h
	6	*
	7	* Internal header for Lock-Free RCU Hash Table
	8	*
	9	* Copyright 2011 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
	10	* Copyright 2011 - Lai Jiangshan <laijs@cn.fujitsu.com>
	11	*
	12	* This library is free software; you can redistribute it and/or
	13	* modify it under the terms of the GNU Lesser General Public
	14	* License as published by the Free Software Foundation; either
	15	* version 2.1 of the License, or (at your option) any later version.
	16	*
	17	* This library is distributed in the hope that it will be useful,
	18	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	19	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	20	* Lesser General Public License for more details.
	21	*
	22	* You should have received a copy of the GNU Lesser General Public
	23	* License along with this library; if not, write to the Free Software
	24	* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
	25	*/
	26
	27	#include <urcu/rculfhash.h>
	28
	29	#ifdef DEBUG
	30	#define dbg_printf(fmt, args...) printf("[debug rculfhash] " fmt, ## args)
	31	#else
	32	#define dbg_printf(fmt, args...)
	33	#endif
	34
	35	#if (CAA_BITS_PER_LONG == 32)
	36	#define MAX_TABLE_ORDER 32
	37	#else
	38	#define MAX_TABLE_ORDER 64
	39	#endif
	40
	41	#ifndef min
	42	#define min(a, b) ((a) < (b) ? (a) : (b))
	43	#endif
	44
	45	#ifndef max
	46	#define max(a, b) ((a) > (b) ? (a) : (b))
	47	#endif
	48
	49	struct ht_items_count;
	50
	51	/*
	52	* cds_lfht: Top-level data structure representing a lock-free hash
	53	* table. Defined in the implementation file to make it be an opaque
	54	* cookie to users.
	55	*/
	56	struct cds_lfht {
	57	unsigned long size; /* always a power of 2, shared (RCU) */
	58	int flags;
	59
	60	/*
	61	* We need to put the work threads offline (QSBR) when taking this
	62	* mutex, because we use synchronize_rcu within this mutex critical
	63	* section, which waits on read-side critical sections, and could
	64	* therefore cause grace-period deadlock if we hold off RCU G.P.
65	* completion.
66	*/
67	pthread_mutex_t resize_mutex; /* resize mutex: add/del mutex */
68	pthread_attr_t resize_attr; / Resize threads attributes */
69	unsigned int in_progress_resize, in_progress_destroy;
70	unsigned long resize_target;
71	int resize_initiated;
72	const struct rcu_flavor_struct *flavor;
73
74	long count; /* global approximate item count */
75	struct ht_items_count split_count; / split item count */
76
77	/* memory management related fields are located at the end */
78	const struct cds_lfht_mm_type *mm;
79
80	unsigned long min_alloc_buckets_order;
81	unsigned long min_nr_alloc_buckets;
82	unsigned long max_nr_buckets;
83
84	struct cds_lfht_node (bucket_at)(struct cds_lfht *ht,
85	unsigned long index);
86
87	union {
88	/*
89	* Contains the per order-index-level bucket node table.
90	* The size of each bucket node table is half the number
91	* of hashes contained in this order (except for order 0).
92	* The minimum allocation buckets size parameter allows
93	* combining the bucket node arrays of the lowermost
94	* levels to improve cache locality for small index orders.
95	*/
96	struct cds_lfht_node *tbl_order[MAX_TABLE_ORDER];
97	};
98	};
99
100	extern unsigned int fls_ulong(unsigned long x);
101	extern int get_count_order_ulong(unsigned long x);
102
103	#ifdef POISON_FREE
104	#define poison_free(ptr) \
105	do { \
106	if (ptr) { \
107	memset(ptr, 0x42, sizeof(*(ptr))); \
108	free(ptr); \
109	} \
110	} while (0)
111	#else
112	#define poison_free(ptr) free(ptr)
113	#endif
114
115	#endif /* _URCU_RCULFHASH_INTERNAL_H */