1
/* Copyright (c) 2015-2018, Linaro Limited
2
 * All rights reserved.
3
 *
4
 * SPDX-License-Identifier:   BSD-3-Clause
5
 */
6

7
#include <stdio.h>
8
#include <string.h>
9
#include <malloc.h>
10

11
#include <odp/helper/odph_hashtable.h>
12
#include <odp/helper/odph_debug.h>
13
#include "odph_list_internal.h"
14
#include <odp_api.h>
15

16
#define    ODPH_SUCCESS	0
17
#define    ODPH_FAIL	-1
18

19
/** @magic word, write to the first byte of the memory block
20
 *	to indicate this block is used by a hash table structure
21
 */
22
#define    ODPH_HASH_TABLE_MAGIC_WORD	0xABABBABA
23

24
/** @support 64k buckets. Bucket is a list that composed of
25
 * elements with the same HASH-value but different keys
26
 */
27
#define    ODPH_MAX_BUCKET_NUM			0x10000
28

29
/** @inner element structure of hash table
30
 * To resolve the hash confict:
31
 * we put the elements with different keys but a same HASH-value
32
 * into a list
33
 */
34
typedef struct odph_hash_node {
35
	/** list structure,for list opt */
36
	odph_list_object list_node;
37
	/** Flexible Array,memory will be alloced when table has been created
38
	 * Its length is key_size + value_size,
39
	 * suppose key_size = m; value_size = n;
40
	 * its structure is like:
41
	 * k_byte1 k_byte2...k_byten v_byte1...v_bytem
42
	 */
43
	char content[0];
44
} odph_hash_node;
45

46
typedef struct {
47
	uint32_t magicword; /**< for check */
48
	uint32_t key_size; /**< input param when create,in Bytes */
49
	uint32_t value_size; /**< input param when create,in Bytes */
50
	uint32_t init_cap; /**< input param when create,in Bytes */
51
	/** multi-process support,every list has one rw lock */
52
	odp_rwlock_t *lock_pool;
53
	/** table bucket pool,every hash value has one list head */
54
	odph_list_head *list_head_pool;
55
	/** number of the list head in list_head_pool */
56
	uint32_t head_num;
57
	/** table element pool */
58
	odph_hash_node *hash_node_pool;
59
	/** number of element in the hash_node_pool */
60
	uint32_t hash_node_num;
61
	char rsv[7]; /**< Reserved,for alignment */
62
	char name[ODPH_TABLE_NAME_LEN]; /**< table name */
63
} odph_hash_table_imp;
64

65 1
odph_table_t odph_hash_table_create(const char *name, uint32_t capacity,
66
				    uint32_t key_size,
67
				    uint32_t value_size)
68
{
69
	int i;
70
	uint32_t node_num;
71
	odph_hash_table_imp *tbl;
72
	odp_shm_t shmem;
73
	uint32_t node_mem;
74

75 1
	if (strlen(name) >= ODPH_TABLE_NAME_LEN || capacity < 1 ||
76 1
	    capacity >= 0x1000 || key_size == 0 || value_size == 0) {
77 0
		ODPH_DBG("create para input error!\n");
78 0
		return NULL;
79
	}
80 1
	if (odp_shm_lookup(name) != ODP_SHM_INVALID) {
81 0
		ODPH_DBG("name already exist\n");
82 0
		return NULL;
83
	}
84 1
	shmem = odp_shm_reserve(name, capacity << 20, 64, ODP_SHM_SW_ONLY);
85 1
	if (shmem == ODP_SHM_INVALID) {
86 0
		ODPH_DBG("shm reserve fail\n");
87 0
		return NULL;
88
	}
89 1
	tbl = (odph_hash_table_imp *)odp_shm_addr(shmem);
90

91
	/* clean this block of memory */
92 1
	memset(tbl, 0, capacity << 20);
93

94 1
	tbl->init_cap = capacity << 20;
95 1
	strncpy(tbl->name, name, ODPH_TABLE_NAME_LEN - 1);
96 1
	tbl->key_size = key_size;
97 1
	tbl->value_size = value_size;
98

99
	/* header of this mem block is the table control struct,
100
	 * then the lock pool, then the list header pool
101
	 * the last part is the element node pool
102
	 */
103

104 1
	tbl->lock_pool = (odp_rwlock_t *)(void *)((char *)tbl
105
			+ sizeof(odph_hash_table_imp));
106 1
	tbl->list_head_pool = (odph_list_head *)(void *)((char *)tbl->lock_pool
107
			+ ODPH_MAX_BUCKET_NUM * sizeof(odp_rwlock_t));
108

109 1
	node_mem = tbl->init_cap - sizeof(odph_hash_table_imp)
110
		- ODPH_MAX_BUCKET_NUM * sizeof(odph_list_head)
111
		- ODPH_MAX_BUCKET_NUM * sizeof(odp_rwlock_t);
112

113 1
	node_num = node_mem / (sizeof(odph_hash_node) + key_size + value_size);
114 1
	tbl->hash_node_num = node_num;
115 1
	tbl->hash_node_pool =
116 1
		(odph_hash_node *)(void *)((char *)tbl->list_head_pool
117
		+ ODPH_MAX_BUCKET_NUM * sizeof(odph_list_head));
118

119
	/* init every list head and rw lock */
120 1
	for (i = 0; i < ODPH_MAX_BUCKET_NUM; i++) {
121 1
		ODPH_INIT_LIST_HEAD(&tbl->list_head_pool[i]);
122 1
		odp_rwlock_init((odp_rwlock_t *)&tbl->lock_pool[i]);
123
	}
124

125 1
	tbl->magicword = ODPH_HASH_TABLE_MAGIC_WORD;
126 1
	return (odph_table_t)tbl;
127
}
128

129 1
int odph_hash_table_destroy(odph_table_t table)
130
{
131
	int ret;
132

133 1
	if (table != NULL) {
134
		odph_hash_table_imp *hash_tbl;
135

136 1
		hash_tbl = (odph_hash_table_imp *)(void *)table;
137 1
		if (hash_tbl->magicword != ODPH_HASH_TABLE_MAGIC_WORD)
138 0
			return ODPH_FAIL;
139

140 1
		ret = odp_shm_free(odp_shm_lookup(hash_tbl->name));
141 1
		if (ret != 0) {
142 0
			ODPH_DBG("free fail\n");
143 0
			return ret;
144
		}
145
		/* clean head */
146 1
		return ODPH_SUCCESS;
147
	}
148 0
	return ODPH_FAIL;
149
}
150

151 1
odph_table_t odph_hash_table_lookup(const char *name)
152
{
153 1
	odph_hash_table_imp *hash_tbl = NULL;
154
	odp_shm_t shm;
155

156 1
	if (name == NULL || strlen(name) >= ODPH_TABLE_NAME_LEN)
157 0
		return NULL;
158

159 1
	shm = odp_shm_lookup(name);
160 1
	if (shm != ODP_SHM_INVALID)
161 1
		hash_tbl = (odph_hash_table_imp *)odp_shm_addr(shm);
162 1
	if (hash_tbl != NULL && strcmp(hash_tbl->name, name) == 0)
163 1
		return (odph_table_t)hash_tbl;
164 0
	return NULL;
165
}
166

167
/**
168
 * Calculate has value by the input key and key_size
169
 * This hash algorithm is the most simple one, so we choose it as an DEMO
170
 * User can use any other algorithm, like CRC...
171
 */
172 1
static uint16_t odp_key_hash(void *key, uint32_t key_size)
173
{
174 1
	register uint32_t hash = 0;
175 1
	uint32_t idx = (key_size == 0 ? 1 : key_size);
176
	uint32_t ch;
177

178 1
	while (idx != 0) {
179 1
		ch = (uint32_t)(*(char *)key);
180 1
		hash = hash * 131 + ch;
181 1
		idx--;
182
	}
183 1
	return (uint16_t)(hash & 0x0000FFFF);
184
}
185

186
/**
187
 * Get an available node from pool
188
 */
189 1
static odph_hash_node *hashnode_take(odph_table_t table)
190
{
191
	odph_hash_table_imp *tbl;
192
	uint32_t idx;
193
	odph_hash_node *node;
194

195 1
	tbl = (odph_hash_table_imp *)(void *)table;
196 1
	for (idx = 0; idx < tbl->hash_node_num; idx++) {
197
		/** notice: memory of one hash_node is
198
		 * not only sizeof(odph_hash_node)
199
		 * should add the size of Flexible Array
200
		 */
201 1
		node = (odph_hash_node *)(void *)((char *)tbl->hash_node_pool
202 1
				+ idx * (sizeof(odph_hash_node)
203 1
						+ tbl->key_size
204 1
						+ tbl->value_size));
205 1
		if (node->list_node.next == NULL &&
206 1
		    node->list_node.prev == NULL) {
207 1
			ODPH_INIT_LIST_HEAD(&node->list_node);
208 1
			return node;
209
		}
210
	}
211 0
	return NULL;
212
}
213

214
/**
215
 * Release an node to the pool
216
 */
217 1
static void hashnode_give(odph_table_t table, odph_hash_node *node)
218
{
219
	odph_hash_table_imp *tbl;
220

221 1
	if (node == NULL)
222 0
		return;
223

224 1
	tbl = (odph_hash_table_imp *)(void *)table;
225

226 1
	odph_list_del(&node->list_node);
227 1
	memset(node, 0,
228 1
	       (sizeof(odph_hash_node) + tbl->key_size + tbl->value_size));
229
}
230

231
/* should make sure the input table exists and is available */
232 1
int odph_hash_put_value(odph_table_t table, void *key, void *value)
233
{
234
	odph_hash_table_imp *tbl;
235 1
	uint16_t hash = 0;
236 1
	odph_hash_node *node = NULL;
237 1
	char *tmp = NULL;
238

239 1
	if (table == NULL || key == NULL || value == NULL)
240 0
		return ODPH_FAIL;
241

242 1
	tbl = (odph_hash_table_imp *)(void *)table;
243
	/* hash value is just the index of the list head in pool */
244 1
	hash = odp_key_hash(key, tbl->key_size);
245

246 1
	odp_rwlock_write_lock(&tbl->lock_pool[hash]);
247
	/* First, check if the key already exist */
248 1
	ODPH_LIST_FOR_EACH(node, &tbl->list_head_pool[hash], odph_hash_node,
249
			   list_node)
250
	{
251 1
		if (memcmp(node->content, key, tbl->key_size) == 0) {
252
			/* copy value content to hash node*/
253 1
			tmp = (void *)((char *)node->content + tbl->key_size);
254 1
			memcpy(tmp, value, tbl->value_size);
255 1
			odp_rwlock_write_unlock(&tbl->lock_pool[hash]);
256 1
			return ODPH_SUCCESS;
257
		}
258
	}
259

260
	/*if the key is a new one, get a new hash node form the pool */
261 1
	node = hashnode_take(table);
262 1
	if (node == NULL) {
263 0
		odp_rwlock_write_unlock(&tbl->lock_pool[hash]);
264 0
		return ODPH_FAIL;
265
	}
266

267
	/* copy both key and value content to the hash node */
268 1
	memcpy(node->content, key, tbl->key_size);
269 1
	tmp = (void *)((char *)node->content + tbl->key_size);
270 1
	memcpy(tmp, value, tbl->value_size);
271

272
	/* add the node to list */
273 1
	odph_list_add(&node->list_node, &tbl->list_head_pool[hash]);
274

275 1
	odp_rwlock_write_unlock(&tbl->lock_pool[hash]);
276 1
	return ODPH_SUCCESS;
277
}
278

279
/* should make sure the input table exists and is available */
280 1
int odph_hash_get_value(odph_table_t table, void *key, void *buffer,
281
			uint32_t buffer_size)
282
{
283
	odph_hash_table_imp *tbl;
284 1
	uint16_t hash = 0;
285
	odph_hash_node *node;
286 1
	char *tmp = NULL;
287

288 1
	tbl = (odph_hash_table_imp *)(void *)table;
289

290 1
	if (table == NULL || key == NULL || buffer == NULL ||
291 1
	    buffer_size < tbl->value_size)
292 0
		return ODPH_FAIL;
293

294
	/* hash value is just the index of the list head in pool */
295 1
	hash = odp_key_hash(key, tbl->key_size);
296

297 1
	odp_rwlock_read_lock(&tbl->lock_pool[hash]);
298

299 1
	ODPH_LIST_FOR_EACH(node, &tbl->list_head_pool[hash],
300
			   odph_hash_node, list_node)
301
	{
302
		/* in case of hash conflict, compare the whole key */
303 1
		if (memcmp(node->content, key, tbl->key_size) == 0) {
304
			/* find the target */
305 1
			tmp = (void *)((char *)node->content + tbl->key_size);
306 1
			memcpy(buffer, tmp, tbl->value_size);
307

308 1
			odp_rwlock_read_unlock(&tbl->lock_pool[hash]);
309

310 1
			return ODPH_SUCCESS;
311
		}
312
	}
313

314 1
	odp_rwlock_read_unlock(&tbl->lock_pool[hash]);
315

316 1
	return ODPH_FAIL;
317
}
318

319
/* should make sure the input table exists and is available */
320 1
int odph_hash_remove_value(odph_table_t table, void *key)
321
{
322
	odph_hash_table_imp *tbl;
323 1
	uint16_t hash = 0;
324
	odph_hash_node *node;
325

326 1
	if (table == NULL || key == NULL)
327 0
		return ODPH_FAIL;
328

329 1
	tbl = (odph_hash_table_imp *)(void *)table;
330

331
	/* hash value is just the index of the list head in pool */
332 1
	hash = odp_key_hash(key, tbl->key_size);
333

334 1
	odp_rwlock_write_lock(&tbl->lock_pool[hash]);
335

336 1
	ODPH_LIST_FOR_EACH(node, &tbl->list_head_pool[hash], odph_hash_node,
337
			   list_node)
338
	{
339 1
		if (memcmp(node->content, key, tbl->key_size) == 0) {
340 1
			hashnode_give(table, node);
341 1
			odp_rwlock_write_unlock(&tbl->lock_pool[hash]);
342 1
			return ODPH_SUCCESS;
343
		}
344
	}
345

346 0
	odp_rwlock_write_unlock(&tbl->lock_pool[hash]);
347

348 0
	return ODPH_SUCCESS;
349
}
350

351
odph_table_ops_t odph_hash_table_ops = {
352
	odph_hash_table_create,
353
	odph_hash_table_lookup,
354
	odph_hash_table_destroy,
355
	odph_hash_put_value,
356
	odph_hash_get_value,
357
	odph_hash_remove_value};
358

Read our documentation on viewing source code .

Loading