nemea-common  1.6.3
fast_hash_filter.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_FILTER_H__
45 #define __FAST_HASH_FILTER_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 #ifndef UINT64_MAX
59 #define UINT64_MAX -1ULL
60 #endif
61 
65 #define FHF_TABLE_COLS 8
66 
70 #define FHF_COL_FULL ((uint8_t) 0xFF)
71 
75 enum fhf_insert {
78  FHF_INSERT_FULL = -2
79 };
80 
84 enum fhf_resize {
88 };
89 
93 enum fhf_found {
94  FHF_FOUND = 0,
95  FHF_NOT_FOUND = 1
96 };
97 
103  FHF_NOT_REMOVED = 1
104 };
105 
109 enum fhf_iter {
113  FHF_ITER_END = -2
114 };
115 
119 extern uint8_t fhf_lt_free_flag[];
120 extern uint8_t fhf_lt_pow_of_two[];
121 
133 typedef struct fhf_table_struct fhf_table_t;
135  uint64_t table_rows;
136  uint32_t key_size;
137  uint32_t data_size;
138  uint8_t *key_field;
139  uint8_t *data_field;
140  uint8_t *free_flag_field;
141  int8_t *lock_table;
143  uint64_t (*hash_function)(const void *, uint32_t, uint64_t);
144 };
145 
149 typedef struct {
151  int64_t row;
152  int32_t col;
153  uint8_t *key_ptr;
154  uint8_t *data_ptr;
155 } fhf_iter_t;
156 
172 fhf_table_t * fhf_init(uint64_t table_rows, uint32_t key_size, uint32_t data_size);
173 
183 void fhf_clear(fhf_table_t *table);
184 
193 
203 
210 
219 
236 static inline int fhf_insert(fhf_table_t *table, const void *key, const void *data)
237 {
238  uint64_t table_row = (table->table_rows - 1) & (table->hash_function)(key, table->key_size, (uint64_t) table);
239  uint64_t table_col_row = table_row * FHF_TABLE_COLS;
240 
241  //lock row
242  while (__sync_lock_test_and_set(&table->lock_table[table_row], 1))
243  ;
244 
245  //looking for item
246  if ((table->free_flag_field[table_row] & 0x01U) && !memcmp(&table->key_field[table_col_row * table->key_size], key, table->key_size)) {
247  //unlock row
248  __sync_lock_release(&table->lock_table[table_row]);
249  return FHF_INSERT_FAILED;
250  }
251 
252  if ((table->free_flag_field[table_row] & 0x02U) && !memcmp(&table->key_field[(table_col_row + 1) * table->key_size], key, table->key_size)) {
253  //unlock row
254  __sync_lock_release(&table->lock_table[table_row]);
255  return FHF_INSERT_FAILED;
256  }
257 
258  if ((table->free_flag_field[table_row] & 0x04U) && !memcmp(&table->key_field[(table_col_row + 2) * table->key_size], key, table->key_size)) {
259  //unlock row
260  __sync_lock_release(&table->lock_table[table_row]);
261  return FHF_INSERT_FAILED;
262  }
263 
264  if ((table->free_flag_field[table_row] & 0x08U) && !memcmp(&table->key_field[(table_col_row + 3) * table->key_size], key, table->key_size)) {
265  //unlock row
266  __sync_lock_release(&table->lock_table[table_row]);
267  return FHF_INSERT_FAILED;
268  }
269 
270  if ((table->free_flag_field[table_row] & 0x10U) && !memcmp(&table->key_field[(table_col_row + 4) * table->key_size], key, table->key_size)) {
271  //unlock row
272  __sync_lock_release(&table->lock_table[table_row]);
273  return FHF_INSERT_FAILED;
274  }
275 
276  if ((table->free_flag_field[table_row] & 0x20U) && !memcmp(&table->key_field[(table_col_row + 5) * table->key_size], key, table->key_size)) {
277  //unlock row
278  __sync_lock_release(&table->lock_table[table_row]);
279  return FHF_INSERT_FAILED;
280  }
281 
282  if ((table->free_flag_field[table_row] & 0x40U) && !memcmp(&table->key_field[(table_col_row + 6) * table->key_size], key, table->key_size)) {
283  //unlock row
284  __sync_lock_release(&table->lock_table[table_row]);
285  return FHF_INSERT_FAILED;
286  }
287 
288  if ((table->free_flag_field[table_row] & 0x80U) && !memcmp(&table->key_field[(table_col_row + 7) * table->key_size], key, table->key_size)) {
289  //unlock row
290  __sync_lock_release(&table->lock_table[table_row]);
291  return FHF_INSERT_FAILED;
292  }
293 
294  if (table->free_flag_field[table_row] < FHF_COL_FULL) {
295  //insert item
296  memcpy(&table->key_field[(table_col_row + fhf_lt_free_flag[table->free_flag_field[table_row]]) * table->key_size], key, table->key_size);
297  memcpy(&table->data_field[(table_col_row + fhf_lt_free_flag[table->free_flag_field[table_row]]) * table->data_size], data, table->data_size);
298 
299  //change free flag
300  table->free_flag_field[table_row] += fhf_lt_pow_of_two[fhf_lt_free_flag[table->free_flag_field[table_row]]];
301 
302  //unlock row
303  __sync_lock_release(&table->lock_table[table_row]);
304  return FHF_INSERT_OK;
305  }
306  else {
307  //unlock row
308  __sync_lock_release(&table->lock_table[table_row]);
309  return FHF_INSERT_FULL;
310  }
311 }
312 
339 static inline int fhf_insert_own_or_update(fhf_table_t *table, const void *key, int8_t **lock, void ** data_ptr)
340 {
341  uint64_t table_row = (table->table_rows - 1) & (table->hash_function)(key, table->key_size, (uint64_t) table);
342  uint64_t table_col_row = table_row * FHF_TABLE_COLS;
343 
344  //lock row
345  while (__sync_lock_test_and_set(&table->lock_table[table_row], 1))
346  ;
347 
348  //looking for item
349  if ((table->free_flag_field[table_row] & 0x01U) && !memcmp(&table->key_field[table_col_row * table->key_size], key, table->key_size)) {
350  *lock = &table->lock_table[table_row];
351  *data_ptr = &table->data_field[table_col_row * table->data_size];
352  return FHF_INSERT_FAILED;
353  }
354 
355  if ((table->free_flag_field[table_row] & 0x02U) && !memcmp(&table->key_field[(table_col_row + 1) * table->key_size], key, table->key_size)) {
356  *lock = &table->lock_table[table_row];
357  *data_ptr = &table->data_field[(table_col_row + 1) * table->data_size];
358  return FHF_INSERT_FAILED;
359  }
360 
361  if ((table->free_flag_field[table_row] & 0x04U) && !memcmp(&table->key_field[(table_col_row + 2) * table->key_size], key, table->key_size)) {
362  *lock = &table->lock_table[table_row];
363  *data_ptr = &table->data_field[(table_col_row + 2) * table->data_size];
364  return FHF_INSERT_FAILED;
365  }
366 
367  if ((table->free_flag_field[table_row] & 0x08U) && !memcmp(&table->key_field[(table_col_row + 3) * table->key_size], key, table->key_size)) {
368  *lock = &table->lock_table[table_row];
369  *data_ptr = &table->data_field[(table_col_row + 3) * table->data_size];
370  return FHF_INSERT_FAILED;
371  }
372 
373  if ((table->free_flag_field[table_row] & 0x10U) && !memcmp(&table->key_field[(table_col_row + 4) * table->key_size], key, table->key_size)) {
374  *lock = &table->lock_table[table_row];
375  *data_ptr = &table->data_field[(table_col_row + 4) * table->data_size];
376  return FHF_INSERT_FAILED;
377  }
378 
379  if ((table->free_flag_field[table_row] & 0x20U) && !memcmp(&table->key_field[(table_col_row + 5) * table->key_size], key, table->key_size)) {
380  *lock = &table->lock_table[table_row];
381  *data_ptr = &table->data_field[(table_col_row + 5) * table->data_size];
382  return FHF_INSERT_FAILED;
383  }
384 
385  if ((table->free_flag_field[table_row] & 0x40U) && !memcmp(&table->key_field[(table_col_row + 6) * table->key_size], key, table->key_size)) {
386  *lock = &table->lock_table[table_row];
387  *data_ptr = &table->data_field[(table_col_row + 6) * table->data_size];
388  return FHF_INSERT_FAILED;
389  }
390 
391  if ((table->free_flag_field[table_row] & 0x80U) && !memcmp(&table->key_field[(table_col_row + 7) * table->key_size], key, table->key_size)) {
392  *lock = &table->lock_table[table_row];
393  *data_ptr = &table->data_field[(table_col_row + 7) * table->data_size];
394  return FHF_INSERT_FAILED;
395  }
396 
397  if (table->free_flag_field[table_row] < FHF_COL_FULL) {
398  //insert item
399  memcpy(&table->key_field[(table_col_row + fhf_lt_free_flag[table->free_flag_field[table_row]]) * table->key_size], key, table->key_size);
400 
401  *lock = &table->lock_table[table_row];
402  *data_ptr = &table->data_field[(table_col_row + fhf_lt_free_flag[table->free_flag_field[table_row]]) * table->data_size];
403 
404  //change free flag
405  table->free_flag_field[table_row] += fhf_lt_pow_of_two[fhf_lt_free_flag[table->free_flag_field[table_row]]];
406  return FHF_INSERT_OK;
407  }
408  else
409  {
410  //unlock row
411  __sync_lock_release(&table->lock_table[table_row]);
412  return FHF_INSERT_FULL;
413  }
414 }
415 
431 static inline int fhf_update_data(fhf_table_t *table, const void *key, int8_t **lock, void **data_ptr)
432 {
433  uint64_t table_row = (table->table_rows - 1) & (table->hash_function)(key, table->key_size, (uint64_t) table);
434  uint64_t table_col_row = table_row * FHF_TABLE_COLS;
435 
436  //lock row
437  while (__sync_lock_test_and_set(&table->lock_table[table_row], 1))
438  ;
439 
440  if ((table->free_flag_field[table_row] & 0x01U) && !memcmp(&table->key_field[table_col_row * table->key_size], key, table->key_size)) {
441  *lock = &table->lock_table[table_row];
442  *data_ptr = (void *) &table->data_field[table_col_row * table->data_size];
443  return FHF_FOUND;
444  }
445  if ((table->free_flag_field[table_row] & 0x02U) && !memcmp(&table->key_field[(table_col_row + 1) * table->key_size], key, table->key_size)) {
446  *lock = &table->lock_table[table_row];
447  *data_ptr = (void *) &table->data_field[(table_col_row + 1) * table->data_size];
448  return FHF_FOUND;
449  }
450  if ((table->free_flag_field[table_row] & 0x04U) && !memcmp(&table->key_field[(table_col_row + 2) * table->key_size], key, table->key_size)) {
451  *lock = &table->lock_table[table_row];
452  *data_ptr = (void *) &table->data_field[(table_col_row + 2) * table->data_size];
453  return FHF_FOUND;
454  }
455  if ((table->free_flag_field[table_row] & 0x08U) && !memcmp(&table->key_field[(table_col_row + 3) * table->key_size], key, table->key_size)) {
456  *lock = &table->lock_table[table_row];
457  *data_ptr = (void *) &table->data_field[(table_col_row + 3) * table->data_size];
458  return FHF_FOUND;
459  }
460  if ((table->free_flag_field[table_row] & 0x10U) && !memcmp(&table->key_field[(table_col_row + 4) * table->key_size], key, table->key_size)) {
461  *lock = &table->lock_table[table_row];
462  *data_ptr = (void *) &table->data_field[(table_col_row + 4) * table->data_size];
463  return FHF_FOUND;
464  }
465  if ((table->free_flag_field[table_row] & 0x20U) && !memcmp(&table->key_field[(table_col_row + 5) * table->key_size], key, table->key_size)) {
466  *lock = &table->lock_table[table_row];
467  *data_ptr = (void *) &table->data_field[(table_col_row + 5) * table->data_size];
468  return FHF_FOUND;
469  }
470  if ((table->free_flag_field[table_row] & 0x40U) && !memcmp(&table->key_field[(table_col_row + 6) * table->key_size], key, table->key_size)) {
471  *lock = &table->lock_table[table_row];
472  *data_ptr = (void *) &table->data_field[(table_col_row + 6) * table->data_size];
473  return FHF_FOUND;
474  }
475  if ((table->free_flag_field[table_row] & 0x80U) && !memcmp(&table->key_field[(table_col_row + 7) * table->key_size], key, table->key_size)) {
476  *lock = &table->lock_table[table_row];
477  *data_ptr = (void *) &table->data_field[(table_col_row + 7) * table->data_size];
478  return FHF_FOUND;
479  }
480 
481  //unlock row
482  __sync_lock_release(&table->lock_table[table_row]);
483  return FHF_NOT_FOUND;
484 }
485 
500 static inline int fhf_get_data(fhf_table_t *table, const void *key, const void **data_ptr)
501 {
502  uint64_t table_row = (table->table_rows - 1) & (table->hash_function)(key, table->key_size, (uint64_t) table);
503  uint64_t table_col_row = table_row * FHF_TABLE_COLS;
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  *data_ptr = (const void *) &table->data_field[table_col_row * table->data_size];
507  return FHF_FOUND;
508  }
509  if ((table->free_flag_field[table_row] & 0x02U) && !memcmp(&table->key_field[(table_col_row + 1) * table->key_size], key, table->key_size)) {
510  *data_ptr = (const void *) &table->data_field[(table_col_row + 1) * table->data_size];
511  return FHF_FOUND;
512  }
513  if ((table->free_flag_field[table_row] & 0x04U) && !memcmp(&table->key_field[(table_col_row + 2) * table->key_size], key, table->key_size)) {
514  *data_ptr = (const void *) &table->data_field[(table_col_row + 2) * table->data_size];
515  return FHF_FOUND;
516  }
517  if ((table->free_flag_field[table_row] & 0x08U) && !memcmp(&table->key_field[(table_col_row + 3) * table->key_size], key, table->key_size)) {
518  *data_ptr = (const void *) &table->data_field[(table_col_row + 3) * table->data_size];
519  return FHF_FOUND;
520  }
521  if ((table->free_flag_field[table_row] & 0x10U) && !memcmp(&table->key_field[(table_col_row + 4) * table->key_size], key, table->key_size)) {
522  *data_ptr = (const void *) &table->data_field[(table_col_row + 4) * table->data_size];
523  return FHF_FOUND;
524  }
525  if ((table->free_flag_field[table_row] & 0x20U) && !memcmp(&table->key_field[(table_col_row + 5) * table->key_size], key, table->key_size)) {
526  *data_ptr = (const void *) &table->data_field[(table_col_row + 5) * table->data_size];
527  return FHF_FOUND;
528  }
529  if ((table->free_flag_field[table_row] & 0x40U) && !memcmp(&table->key_field[(table_col_row + 6) * table->key_size], key, table->key_size)) {
530  *data_ptr = (const void *) &table->data_field[(table_col_row + 6) * table->data_size];
531  return FHF_FOUND;
532  }
533  if ((table->free_flag_field[table_row] & 0x80U) && !memcmp(&table->key_field[(table_col_row + 7) * table->key_size], key, table->key_size)) {
534  *data_ptr = (const void *) &table->data_field[(table_col_row + 7) * table->data_size];
535  return FHF_FOUND;
536  }
537 
538  return FHF_NOT_FOUND;
539 }
540 
557 static inline int fhf_get_data_locked(fhf_table_t *table, const void *key, int8_t **lock, const void **data_ptr)
558 {
559  uint64_t table_row = (table->table_rows - 1) & (table->hash_function)(key, table->key_size, (uint64_t) table);
560  uint64_t table_col_row = table_row * FHF_TABLE_COLS;
561 
562  //lock row
563  while (__sync_lock_test_and_set(&table->lock_table[table_row], 1))
564  ;
565 
566  if ((table->free_flag_field[table_row] & 0x01U) && !memcmp(&table->key_field[table_col_row * table->key_size], key, table->key_size)) {
567  *lock = &table->lock_table[table_row];
568  *data_ptr = (const void *) &table->data_field[table_col_row * table->data_size];
569  return FHF_FOUND;
570  }
571  if ((table->free_flag_field[table_row] & 0x02U) && !memcmp(&table->key_field[(table_col_row + 1) * table->key_size], key, table->key_size)) {
572  *lock = &table->lock_table[table_row];
573  *data_ptr = (const void *) &table->data_field[(table_col_row + 1) * table->data_size];
574  return FHF_FOUND;
575  }
576  if ((table->free_flag_field[table_row] & 0x04U) && !memcmp(&table->key_field[(table_col_row + 2) * table->key_size], key, table->key_size)) {
577  *lock = &table->lock_table[table_row];
578  *data_ptr = (const void *) &table->data_field[(table_col_row + 2) * table->data_size];
579  return FHF_FOUND;
580  }
581  if ((table->free_flag_field[table_row] & 0x08U) && !memcmp(&table->key_field[(table_col_row + 3) * table->key_size], key, table->key_size)) {
582  *lock = &table->lock_table[table_row];
583  *data_ptr = (const void *) &table->data_field[(table_col_row + 3) * table->data_size];
584  return FHF_FOUND;
585  }
586  if ((table->free_flag_field[table_row] & 0x10U) && !memcmp(&table->key_field[(table_col_row + 4) * table->key_size], key, table->key_size)) {
587  *lock = &table->lock_table[table_row];
588  *data_ptr = (const void *) &table->data_field[(table_col_row + 4) * table->data_size];
589  return FHF_FOUND;
590  }
591  if ((table->free_flag_field[table_row] & 0x20U) && !memcmp(&table->key_field[(table_col_row + 5) * table->key_size], key, table->key_size)) {
592  *lock = &table->lock_table[table_row];
593  *data_ptr = (const void *) &table->data_field[(table_col_row + 5) * table->data_size];
594  return FHF_FOUND;
595  }
596  if ((table->free_flag_field[table_row] & 0x40U) && !memcmp(&table->key_field[(table_col_row + 6) * table->key_size], key, table->key_size)) {
597  *lock = &table->lock_table[table_row];
598  *data_ptr = (const void *) &table->data_field[(table_col_row + 6) * table->data_size];
599  return FHF_FOUND;
600  }
601  if ((table->free_flag_field[table_row] & 0x80U) && !memcmp(&table->key_field[(table_col_row + 7) * table->key_size], key, table->key_size)) {
602  *lock = &table->lock_table[table_row];
603  *data_ptr = (const void *) &table->data_field[(table_col_row + 7) * table->data_size];
604  return FHF_FOUND;
605  }
606 
607  //unlock row
608  __sync_lock_release(&table->lock_table[table_row]);
609  return FHF_NOT_FOUND;
610 }
611 
617 static inline void fhf_unlock_data(int8_t *lock)
618 {
619  __sync_lock_release(lock);
620 }
621 
635 static inline int fhf_remove(fhf_table_t *table, const void *key)
636 {
637  uint64_t table_row = (table->table_rows - 1) & (table->hash_function)(key, table->key_size, (uint64_t) table);
638  uint64_t table_col_row = table_row * FHF_TABLE_COLS;
639  unsigned int i;
640 
641  //lock row
642  while (__sync_lock_test_and_set(&table->lock_table[table_row], 1))
643  ;
644 
645  for (i = 0; i < FHF_TABLE_COLS; i++) {
646  if ((table->free_flag_field[table_row] & (1 << i)) && !memcmp(&table->key_field[(table_col_row + i) * table->key_size], key, table->key_size)) {
647  table->free_flag_field[table_row] &= ~(1 << i);
648  //unlock row
649  __sync_lock_release(&table->lock_table[table_row]);
650  return FHF_REMOVED;
651  }
652  }
653  //unlock row
654  __sync_lock_release(&table->lock_table[table_row]);
655  return FHF_NOT_REMOVED;
656 }
657 
675 static inline int fhf_remove_locked(fhf_table_t *table, const void *key, int8_t *lock_ptr)
676 {
677  uint64_t table_row = (table->table_rows - 1) & (table->hash_function)(key, table->key_size, (uint64_t) table);
678  uint64_t table_col_row = table_row * FHF_TABLE_COLS;
679  unsigned int i;
680 
681  if (lock_ptr == &table->lock_table[table_row]) {
682  for (i = 0; i < FHF_TABLE_COLS; i++) {
683  if ((table->free_flag_field[table_row] & (1 << i)) && !memcmp(&table->key_field[(table_col_row + i) * table->key_size], key, table->key_size)) {
684  table->free_flag_field[table_row] &= ~(1 << i);
685  //unlock row
686  __sync_lock_release(&table->lock_table[table_row]);
687  return FHF_REMOVED;
688  }
689  }
690  }
691  return FHF_NOT_REMOVED;
692 }
693 
702 static inline int fhf_remove_iter(fhf_iter_t *iter)
703 {
704  switch(iter->row) {
705  case FHF_ITER_START:
706  case FHF_ITER_END:
707  return FHF_NOT_REMOVED;
708 
709  default:
710  if (iter->table->free_flag_field[iter->row] & (1 << iter->col)) {
711  iter->table->free_flag_field[iter->row] &= ~(1 << iter->col);
712  iter->key_ptr = NULL;
713  iter->data_ptr = NULL;
714  return FHF_REMOVED;
715  }
716  return FHF_NOT_REMOVED;
717  }
718 }
719 
729 static inline int fhf_get_next_iter(fhf_iter_t *iter)
730 {
731  uint32_t i, j;
732 
733  switch (iter->row) {
734  default:
735  for (j = iter->col + 1; j < FHF_TABLE_COLS; j++) {
736  if (iter->table->free_flag_field[iter->row] & (1 << j)) {
737  iter->col = j;
738  iter->key_ptr = &iter->table->key_field[(iter->row * FHF_TABLE_COLS + j) * iter->table->key_size];
739  iter->data_ptr = &iter->table->data_field[(iter->row * FHF_TABLE_COLS + j) * iter->table->data_size];
740  return FHF_ITER_RET_OK;
741  }
742  }
743  //unlock row
744  __sync_lock_release(&iter->table->lock_table[iter->row]);
745 
746  case FHF_ITER_START:
747  for (i = iter->row + 1; i < iter->table->table_rows; i++) {
748  //lock row
749  while (__sync_lock_test_and_set(&iter->table->lock_table[i], 1))
750  ;
751  for (j = 0; j < FHF_TABLE_COLS; j++) {
752  if (iter->table->free_flag_field[i] & (1 << j)) {
753  iter->row = i;
754  iter->col = j;
755  iter->key_ptr = &iter->table->key_field[(i * FHF_TABLE_COLS + j) * iter->table->key_size];
756  iter->data_ptr = &iter->table->data_field[(i * FHF_TABLE_COLS + j) * iter->table->data_size];
757  return FHF_ITER_RET_OK;
758  }
759  }
760  //unlock row
761  __sync_lock_release(&iter->table->lock_table[i]);
762  }
763 
764  case FHF_ITER_END:
765  iter->row = FHF_ITER_END;
766  iter->col = FHF_ITER_END;
767  iter->key_ptr = NULL;
768  iter->data_ptr = NULL;
769  return FHF_ITER_RET_END;
770  }
771 }
772 
789 static inline int fhf_resize(fhf_table_t **table)
790 {
791  int ret = 0;
792  uint64_t new_table_rows;
793  fhf_table_t * old_table;
794  fhf_table_t * new_table;
795 
796  old_table = *table;
797 
798  if (old_table->old_table != NULL) {
799  fhf_destroy(old_table->old_table);
800  old_table->old_table = NULL;
801  }
802 
803  new_table_rows = 2 * old_table->table_rows;
804 
805  while (new_table_rows <= UINT64_MAX/2 + 1 && new_table_rows != 0) {
806  fhf_iter_t * iterator_old_table;
807 
808  new_table = fhf_init(new_table_rows, old_table->key_size, old_table->data_size);
809  if (new_table == NULL)
811 
812  iterator_old_table = fhf_init_iter(old_table);
813  if (iterator_old_table == NULL) {
814  fhf_destroy(new_table);
816  }
817 
818  while (fhf_get_next_iter(iterator_old_table) != FHF_ITER_RET_END) {
819  ret = fhf_insert(new_table, (const void *) iterator_old_table->key_ptr, (const void *) iterator_old_table->data_ptr);
820  if (ret != FHF_INSERT_OK) {
821  break;
822  }
823  }
824  fhf_destroy_iter(iterator_old_table);
825 
826  if (ret != FHF_INSERT_OK) {
827  fhf_destroy(new_table);
828  new_table_rows *= 2;
829  continue;
830  }
831  new_table->old_table = old_table;
832  *table = new_table;
833  return FHF_RESIZE_OK;
834  }
836 }
837 
838 
839 #ifdef __cplusplus
840 }
841 #endif
842 
843 #endif
fhf_found
@ FHF_FOUND
@ FHF_NOT_FOUND
#define FHF_COL_FULL
fhf_resize
@ FHF_RESIZE_FAILED_INSERT
@ FHF_RESIZE_FAILED_ALLOC
@ FHF_RESIZE_OK
#define FHF_TABLE_COLS
void fhf_destroy_iter(fhf_iter_t *iter)
Function for destroying iterator and freeing memory.
#define UINT64_MAX
fhf_iter
@ FHF_ITER_START
@ FHF_ITER_END
@ FHF_ITER_RET_OK
@ FHF_ITER_RET_END
fhf_iter_t * fhf_init_iter(fhf_table_t *table)
Function for initializing iterator for the table.
uint8_t fhf_lt_pow_of_two[]
void fhf_reinit_iter(fhf_iter_t *iter)
Function for reinitializing iterator for table.
fhf_insert
@ FHF_INSERT_OK
@ FHF_INSERT_FULL
@ FHF_INSERT_FAILED
void fhf_clear(fhf_table_t *table)
Function for clearing table.
fhf_table_t * fhf_init(uint64_t table_rows, uint32_t key_size, uint32_t data_size)
Function for initializing table.
void fhf_destroy(fhf_table_t *table)
Function for destroying table and freeing memory.
uint8_t fhf_lt_free_flag[]
fhf_remove
@ FHF_REMOVED
@ FHF_NOT_REMOVED
uint8_t * data_ptr
uint8_t * key_ptr
fhf_table_t * table
uint64_t(* hash_function)(const void *, uint32_t, uint64_t)
uint8_t * free_flag_field
fhf_table_t * old_table