nemea-common 1.6.3
fast_hash_table.h
Go to the documentation of this file.
1
7/*
8 * Copyright (C) 2014 CESNET
9 *
10 * LICENSE TERMS
11 *
12 * Redistribution and use in source and binary forms, with or without
13 * modification, are permitted provided that the following conditions
14 * are met:
15 * 1. Redistributions of source code must retain the above copyright
16 * notice, this list of conditions and the following disclaimer.
17 * 2. Redistributions in binary form must reproduce the above copyright
18 * notice, this list of conditions and the following disclaimer in
19 * the documentation and/or other materials provided with the
20 * distribution.
21 * 3. Neither the name of the Company nor the names of its contributors
22 * may be used to endorse or promote products derived from this
23 * software without specific prior written permission.
24 *
25 * ALTERNATIVELY, provided that this notice is retained in full, this
26 * product may be distributed under the terms of the GNU General Public
27 * License (GPL) version 2 or later, in which case the provisions
28 * of the GPL apply INSTEAD OF those given above.
29 *
30 * This software is provided ``as is'', and any express or implied
31 * warranties, including, but not limited to, the implied warranties of
32 * merchantability and fitness for a particular purpose are disclaimed.
33 * In no event shall the company or contributors be liable for any
34 * direct, indirect, incidental, special, exemplary, or consequential
35 * damages (including, but not limited to, procurement of substitute
36 * goods or services; loss of use, data, or profits; or business
37 * interruption) however caused and on any theory of liability, whether
38 * in contract, strict liability, or tort (including negligence or
39 * otherwise) arising in any way out of the use of this software, even
40 * if advised of the possibility of such damage.
41 *
42 */
43
44#ifndef __FAST_HASH_TABLE_H__
45#define __FAST_HASH_TABLE_H__
46
47#include <inttypes.h>
48#include <stdlib.h>
49#include <string.h>
50
51#ifdef __cplusplus
52extern "C" {
53#endif
54
58#define FHT_TABLE_COLS 4
59
63#define FHT_COL_FULL ((uint8_t) 0x000F)
64
68extern uint8_t lt_free_flag[];
69extern uint8_t lt_pow_of_two[];
70extern uint8_t lt_replacement_vector[][4];
71extern uint8_t lt_replacement_vector_remove[][4];
72extern uint8_t lt_replacement_index[];
73
78{
85};
86
91{
96 FHT_ITER_END = -3
97};
98
127typedef struct
128{
129 uint32_t table_rows;
130 uint32_t key_size;
131 uint32_t data_size;
132 uint32_t stash_size;
133 uint32_t stash_index;
134 uint8_t *key_field;
135 uint8_t *data_field;
141 int8_t *lock_table;
142 int8_t lock_stash;
143 uint32_t (*hash_function)(const void *, int32_t);
145
149typedef struct
150{
152 int32_t row;
153 int32_t col;
154 uint8_t *key_ptr;
155 uint8_t *data_ptr;
156} fht_iter_t;
157
175fht_table_t * fht_init(uint32_t table_rows, uint32_t key_size, uint32_t data_size, uint32_t stash_size);
176
200int fht_insert(fht_table_t *table, const void *key, const void *data, void *key_lost, void *data_lost);
201
214int fht_insert_wr(fht_table_t *table, const void *key, const void *data);
215
244int fht_insert_with_stash(fht_table_t *table, const void *key, const void *data, void *key_lost, void *data_lost);
245
260int fht_insert_with_stash_wr(fht_table_t *table, const void *key, const void *data);
261
275static inline void *fht_get_data(fht_table_t *table, const void *key)
276{
277 uint64_t table_row = (table->table_rows - 1) & (table->hash_function)(key, table->key_size);
278 uint64_t table_col_row = table_row * FHT_TABLE_COLS;
279
280 //lock row
281 while (__sync_lock_test_and_set(&table->lock_table[table_row], 1))
282 ;
283 //
284
285 if ((table->free_flag_field[table_row] & 0x01U) && !memcmp(&table->key_field[table_col_row * table->key_size], key, table->key_size)) {
286 table->replacement_vector_field[table_row] = lt_replacement_vector[table->replacement_vector_field[table_row]][0];
287
288 //unlock row
289 __sync_lock_release(&table->lock_table[table_row]);
290 //
291
292 return (void *) &table->data_field[table_col_row * table->data_size];
293 }
294
295 if ((table->free_flag_field[table_row] & 0x02U) && !memcmp(&table->key_field[(table_col_row + 1) * table->key_size], key, table->key_size)) {
296 table->replacement_vector_field[table_row] = lt_replacement_vector[table->replacement_vector_field[table_row]][1];
297
298 //unlock row
299 __sync_lock_release(&table->lock_table[table_row]);
300 //
301
302 return (void *) &table->data_field[(table_col_row + 1) * table->data_size];
303 }
304
305 if ((table->free_flag_field[table_row] & 0x04U) && !memcmp(&table->key_field[(table_col_row + 2) * table->key_size], key, table->key_size)) {
306 table->replacement_vector_field[table_row] = lt_replacement_vector[table->replacement_vector_field[table_row]][2];
307
308 //unlock row
309 __sync_lock_release(&table->lock_table[table_row]);
310 //
311
312 return (void *) &table->data_field[(table_col_row + 2) * table->data_size];
313 }
314
315 if ((table->free_flag_field[table_row] & 0x08U) && !memcmp(&table->key_field[(table_col_row + 3) * table->key_size], key, table->key_size)) {
316 table->replacement_vector_field[table_row] = lt_replacement_vector[table->replacement_vector_field[table_row]][3];
317
318 //unlock row
319 __sync_lock_release(&table->lock_table[table_row]);
320 //
321
322 return (void *) &table->data_field[(table_col_row + 3) * table->data_size];
323 }
324
325 //unlock row
326 __sync_lock_release(&table->lock_table[table_row]);
327 //
328
329 return NULL;
330}
331
344static inline void *fht_get_data_locked(fht_table_t *table, const void *key, int8_t **lock)
345{
346 uint64_t table_row = (table->table_rows - 1) & (table->hash_function)(key, table->key_size);
347 uint64_t table_col_row = table_row * FHT_TABLE_COLS;
348
349 //lock row
350 while (__sync_lock_test_and_set(&table->lock_table[table_row], 1))
351 ;
352 //
353
354 if ((table->free_flag_field[table_row] & 0x01U) && !memcmp(&table->key_field[table_col_row * table->key_size], key, table->key_size)) {
355 table->replacement_vector_field[table_row] = lt_replacement_vector[table->replacement_vector_field[table_row]][0];
356
357 *lock = &table->lock_table[table_row];
358
359 return (void *) &table->data_field[table_col_row * table->data_size];
360 }
361
362 if ((table->free_flag_field[table_row] & 0x02U) && !memcmp(&table->key_field[(table_col_row + 1) * table->key_size], key, table->key_size)) {
363 table->replacement_vector_field[table_row] = lt_replacement_vector[table->replacement_vector_field[table_row]][1];
364
365 *lock = &table->lock_table[table_row];
366
367 return (void *) &table->data_field[(table_col_row + 1) * table->data_size];
368 }
369
370 if ((table->free_flag_field[table_row] & 0x04U) && !memcmp(&table->key_field[(table_col_row + 2) * table->key_size], key, table->key_size)) {
371 table->replacement_vector_field[table_row] = lt_replacement_vector[table->replacement_vector_field[table_row]][2];
372
373 *lock = &table->lock_table[table_row];
374
375 return (void *) &table->data_field[(table_col_row + 2) * table->data_size];
376 }
377
378 if ((table->free_flag_field[table_row] & 0x08U) && !memcmp(&table->key_field[(table_col_row + 3) * table->key_size], key, table->key_size)) {
379 table->replacement_vector_field[table_row] = lt_replacement_vector[table->replacement_vector_field[table_row]][3];
380
381 *lock = &table->lock_table[table_row];
382
383 return (void *) &table->data_field[(table_col_row + 3) * table->data_size];
384 }
385
386 //unlock row
387 __sync_lock_release(&table->lock_table[table_row]);
388 //
389
390 return NULL;
391}
392
406static inline void *fht_get_data_with_stash(fht_table_t *table, const void *key)
407{
408 uint64_t table_row = (table->table_rows - 1) & (table->hash_function)(key, table->key_size);
409 uint64_t table_col_row = table_row * FHT_TABLE_COLS;
410 unsigned int i;
411
412 //lock row
413 while (__sync_lock_test_and_set(&table->lock_table[table_row], 1))
414 ;
415 //
416
417 if ((table->free_flag_field[table_row] & 0x01U) && !memcmp(&table->key_field[table_col_row * table->key_size], key, table->key_size)) {
418 table->replacement_vector_field[table_row] = lt_replacement_vector[table->replacement_vector_field[table_row]][0];
419
420 //unlock row
421 __sync_lock_release(&table->lock_table[table_row]);
422 //
423
424 return (void *) &table->data_field[table_col_row * table->data_size];
425 }
426
427 if ((table->free_flag_field[table_row] & 0x02U) && !memcmp(&table->key_field[(table_col_row + 1) * table->key_size], key, table->key_size)) {
428 table->replacement_vector_field[table_row] = lt_replacement_vector[table->replacement_vector_field[table_row]][1];
429
430 //unlock row
431 __sync_lock_release(&table->lock_table[table_row]);
432 //
433
434 return (void *) &table->data_field[(table_col_row + 1) * table->data_size];
435 }
436
437 if ((table->free_flag_field[table_row] & 0x04U) && !memcmp(&table->key_field[(table_col_row + 2) * table->key_size], key, table->key_size)) {
438 table->replacement_vector_field[table_row] = lt_replacement_vector[table->replacement_vector_field[table_row]][2];
439
440 //unlock row
441 __sync_lock_release(&table->lock_table[table_row]);
442 //
443
444 return (void *) &table->data_field[(table_col_row + 2) * table->data_size];
445 }
446
447 if ((table->free_flag_field[table_row] & 0x08U) && !memcmp(&table->key_field[(table_col_row + 3) * table->key_size], key, table->key_size)) {
448 table->replacement_vector_field[table_row] = lt_replacement_vector[table->replacement_vector_field[table_row]][3];
449
450 //unlock row
451 __sync_lock_release(&table->lock_table[table_row]);
452 //
453
454 return (void *) &table->data_field[(table_col_row + 3) * table->data_size];
455 }
456
457 //unlock row
458 __sync_lock_release(&table->lock_table[table_row]);
459 //
460
461 //searching in stash
462 //lock stash
463 while (__sync_lock_test_and_set(&table->lock_stash, 1))
464 ;
465 //
466 for (i = 0; i < table->stash_size; i++) {
467 if (table->stash_free_flag_field[i] && !memcmp(&table->stash_key_field[i * table->key_size], key, table->key_size)) {
468 //unlock stash
469 __sync_lock_release(&table->lock_stash);
470 //
471 return (void *) &table->stash_data_field[i * table->data_size];
472 }
473 }
474
475 //unlock stash
476 __sync_lock_release(&table->lock_stash);
477 //
478 return NULL;
479}
480
494static inline void *fht_get_data_with_stash_locked(fht_table_t *table, const void *key, int8_t **lock)
495{
496 uint64_t table_row = (table->table_rows - 1) & (table->hash_function)(key, table->key_size);
497 uint64_t table_col_row = table_row * FHT_TABLE_COLS;
498 unsigned int i;
499
500 //lock row
501 while (__sync_lock_test_and_set(&table->lock_table[table_row], 1))
502 ;
503 //
504
505 if ((table->free_flag_field[table_row] & 0x01U) && !memcmp(&table->key_field[table_col_row * table->key_size], key, table->key_size)) {
506 table->replacement_vector_field[table_row] = lt_replacement_vector[table->replacement_vector_field[table_row]][0];
507
508 *lock = &table->lock_table[table_row];
509
510 return (void *) &table->data_field[table_col_row * table->data_size];
511 }
512
513 if ((table->free_flag_field[table_row] & 0x02U) && !memcmp(&table->key_field[(table_col_row + 1) * table->key_size], key, table->key_size)) {
514 table->replacement_vector_field[table_row] = lt_replacement_vector[table->replacement_vector_field[table_row]][1];
515
516 *lock = &table->lock_table[table_row];
517
518 return (void *) &table->data_field[(table_col_row + 1) * table->data_size];
519 }
520
521 if ((table->free_flag_field[table_row] & 0x04U) && !memcmp(&table->key_field[(table_col_row + 2) * table->key_size], key, table->key_size)) {
522 table->replacement_vector_field[table_row] = lt_replacement_vector[table->replacement_vector_field[table_row]][2];
523
524 *lock = &table->lock_table[table_row];
525
526 return (void *) &table->data_field[(table_col_row + 2) * table->data_size];
527 }
528
529 if ((table->free_flag_field[table_row] & 0x08U) && !memcmp(&table->key_field[(table_col_row + 3) * table->key_size], key, table->key_size)) {
530 table->replacement_vector_field[table_row] = lt_replacement_vector[table->replacement_vector_field[table_row]][3];
531
532 *lock = &table->lock_table[table_row];
533
534 return (void *) &table->data_field[(table_col_row + 3) * table->data_size];
535 }
536
537 //unlock row
538 __sync_lock_release(&table->lock_table[table_row]);
539 //
540
541 //searching in stash
542 //lock stash
543 while (__sync_lock_test_and_set(&table->lock_stash, 1))
544 ;
545 //
546 for (i = 0; i < table->stash_size; i++)
547 if (table->stash_free_flag_field[i] && !memcmp(&table->stash_key_field[i * table->key_size], key, table->key_size)) {
548 *lock = &table->lock_stash;
549
550 return (void *) &table->stash_data_field[i * table->data_size];
551 }
552
553 //unlock stash
554 __sync_lock_release(&table->lock_stash);
555 //
556 return NULL;
557}
558
571int fht_remove(fht_table_t *table, const void *key);
572
585int fht_remove_locked(fht_table_t *table, const void *key, int8_t *lock_ptr);
586
600int fht_remove_with_stash(fht_table_t *table, const void *key);
601
614int fht_remove_with_stash_locked(fht_table_t *table, const void *key, int8_t *lock_ptr);
615
625
635
644
650static inline void fht_unlock_data(int8_t *lock)
651{
652 __sync_lock_release(lock);
653}
654
664
671
682
692
693#ifdef __cplusplus
694}
695#endif
696
697#endif
uint8_t lt_replacement_index[]
#define FHT_TABLE_COLS
int32_t fht_get_next_iter(fht_iter_t *iter)
Function for getting next item in the table.
uint8_t lt_free_flag[]
int fht_insert_with_stash(fht_table_t *table, const void *key, const void *data, void *key_lost, void *data_lost)
Function for inserting the item into the table using stash.
int fht_remove(fht_table_t *table, const void *key)
Function for removing item from the table without looking for in stash.
void fht_destroy_iter(fht_iter_t *iter)
Function for destroying iterator and freeing memory.
int fht_remove_with_stash(fht_table_t *table, const void *key)
Function for removing item from the table with looking for in stash.
fht_table
@ FHT_INSERT_FAILED
@ FHT_INSERT_OK
@ FHT_INSERT_STASH_LOST
@ FHT_INSERT_FULL
@ FHT_INSERT_LOST
@ FHT_INSERT_STASH_OK
fht_iter_t * fht_init_iter(fht_table_t *table)
Function for initializing iterator for the table.
fht_table_t * fht_init(uint32_t table_rows, uint32_t key_size, uint32_t data_size, uint32_t stash_size)
Function for initializing the hash table.
uint8_t lt_pow_of_two[]
int fht_remove_with_stash_locked(fht_table_t *table, const void *key, int8_t *lock_ptr)
Function for removing item from the table with looking for in stash. Function does not locks lock,...
void fht_reinit_iter(fht_iter_t *iter)
Function for reinitializing iterator for the table.
int fht_remove_locked(fht_table_t *table, const void *key, int8_t *lock_ptr)
Function for removing item from the table without looking for in stash. Function does not locks lock,...
void fht_destroy(fht_table_t *table)
Function for destroying the table and freeing memory.
uint8_t lt_replacement_vector_remove[][4]
fht_iter
@ FHT_ITER_START
@ FHT_ITER_RET_END
@ FHT_ITER_END
@ FHT_ITER_STASH
@ FHT_ITER_RET_OK
int fht_insert_wr(fht_table_t *table, const void *key, const void *data)
Function for inserting the item into the table without using stash and without replacing the oldest i...
uint8_t lt_replacement_vector[][4]
void fht_clear(fht_table_t *table)
Function for clearing the table.
int fht_remove_iter(fht_iter_t *iter)
Function for removing actual item from the table when using iterator.
int fht_insert(fht_table_t *table, const void *key, const void *data, void *key_lost, void *data_lost)
Function for inserting the item into the table without using stash.
int fht_insert_with_stash_wr(fht_table_t *table, const void *key, const void *data)
Function for inserting the item into the table using stash and without replacing items in stash.
fht_table_t * table
uint8_t * key_ptr
uint8_t * data_ptr
uint32_t data_size
uint8_t * free_flag_field
uint32_t key_size
uint8_t * data_field
uint8_t * stash_free_flag_field
uint32_t stash_index
uint8_t * replacement_vector_field
uint32_t(* hash_function)(const void *, int32_t)
uint8_t * stash_data_field
int8_t * lock_table
uint8_t * stash_key_field
uint32_t stash_size
uint32_t table_rows
uint8_t * key_field