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
52 extern "C" {
53 #endif
54 
58 #define FHT_TABLE_COLS 4
59 
63 #define FHT_COL_FULL ((uint8_t) 0x000F)
64 
68 extern uint8_t lt_free_flag[];
69 extern uint8_t lt_pow_of_two[];
70 extern uint8_t lt_replacement_vector[][4];
71 extern uint8_t lt_replacement_vector_remove[][4];
72 extern uint8_t lt_replacement_index[];
73 
78 {
85 };
86 
91 {
97 };
98 
127 typedef 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;
136  uint8_t *free_flag_field;
138  uint8_t *stash_key_field;
139  uint8_t *stash_data_field;
141  int8_t *lock_table;
142  int8_t lock_stash;
143  uint32_t (*hash_function)(const void *, int32_t);
144 } fht_table_t;
145 
149 typedef 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 
175 fht_table_t * fht_init(uint32_t table_rows, uint32_t key_size, uint32_t data_size, uint32_t stash_size);
176 
200 int fht_insert(fht_table_t *table, const void *key, const void *data, void *key_lost, void *data_lost);
201 
214 int fht_insert_wr(fht_table_t *table, const void *key, const void *data);
215 
244 int fht_insert_with_stash(fht_table_t *table, const void *key, const void *data, void *key_lost, void *data_lost);
245 
260 int fht_insert_with_stash_wr(fht_table_t *table, const void *key, const void *data);
261 
275 static 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 
344 static 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 
406 static 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 
494 static 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 
571 int fht_remove(fht_table_t *table, const void *key);
572 
585 int fht_remove_locked(fht_table_t *table, const void *key, int8_t *lock_ptr);
586 
600 int fht_remove_with_stash(fht_table_t *table, const void *key);
601 
614 int fht_remove_with_stash_locked(fht_table_t *table, const void *key, int8_t *lock_ptr);
615 
624 int fht_remove_iter(fht_iter_t *iter);
625 
634 void fht_clear(fht_table_t *table);
635 
643 void fht_destroy(fht_table_t *table);
644 
650 static inline void fht_unlock_data(int8_t *lock)
651 {
652  __sync_lock_release(lock);
653 }
654 
664 
670 void fht_reinit_iter(fht_iter_t *iter);
671 
681 int32_t fht_get_next_iter(fht_iter_t *iter);
682 
691 void fht_destroy_iter(fht_iter_t *iter);
692 
693 #ifdef __cplusplus
694 }
695 #endif
696 
697 #endif
uint8_t * data_ptr
uint8_t lt_replacement_vector_remove[][4]
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_remove(fht_table_t *table, const void *key)
Function for removing item from the table without looking for in stash.
uint32_t stash_size
void fht_destroy(fht_table_t *table)
Function for destroying the table and freeing memory.
uint8_t lt_replacement_index[]
uint32_t key_size
uint8_t lt_replacement_vector[][4]
uint8_t * stash_free_flag_field
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...
void fht_reinit_iter(fht_iter_t *iter)
Function for reinitializing iterator for the table.
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_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[]
uint8_t * key_field
uint8_t lt_free_flag[]
void fht_clear(fht_table_t *table)
Function for clearing the table.
uint8_t * replacement_vector_field
#define FHT_TABLE_COLS
int fht_remove_iter(fht_iter_t *iter)
Function for removing actual item from the table when using iterator.
fht_iter_t * fht_init_iter(fht_table_t *table)
Function for initializing iterator for the table.
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...
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...
int8_t * lock_table
uint32_t data_size
uint8_t * data_field
uint32_t(* hash_function)(const void *, int32_t)
uint8_t * free_flag_field
void fht_destroy_iter(fht_iter_t *iter)
Function for destroying iterator and freeing memory.
uint32_t stash_index
fht_iter
uint8_t * stash_data_field
uint8_t * stash_key_field
uint32_t table_rows
fht_table
uint8_t * key_ptr
fht_table_t * table
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.
int32_t fht_get_next_iter(fht_iter_t *iter)
Function for getting next item in the table.
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...