38 #ifndef included_hash_h 39 #define included_hash_h 62 #define HASH_FLAG_NO_AUTO_GROW (1 << 0) 64 #define HASH_FLAG_NO_AUTO_SHRINK (1 << 1) 66 #define HASH_FLAG_HASH_NEXT_IN_PROGRESS (1 << 2) 76 #define KEY_FUNC_NONE (0) 77 #define KEY_FUNC_POINTER_UWORD (1) 78 #define KEY_FUNC_POINTER_U32 (2) 79 #define KEY_FUNC_STRING (3) 80 #define KEY_FUNC_MEM (4) 104 uword is_user_bytes =
106 return sizeof (h[0]) + is_user_bytes;
121 return v ? h->
elts : 0;
191 #define LOG2_ALLOC_BITS (5) 192 #define PAIR_BITS (BITS (uword) - LOG2_ALLOC_BITS) 227 void *_hash_unset (
void *v,
uword key,
void *old_value);
230 void *_hash_set3 (
void *v,
uword key,
void *value,
void *old_value);
242 #define hash_set3(h,key,value,old_value) \ 244 uword _v = (uword) (value); \ 245 (h) = _hash_set3 ((h), (uword) (key), (void *) &_v, (old_value)); \ 249 #define hash_get(h,key) _hash_get ((h), (uword) (key)) 252 #define hash_get_pair(h,key) _hash_get_pair ((h), (uword) (key)) 255 #define hash_set(h,key,value) hash_set3(h,key,value,0) 258 #define hash_set1(h,key) (h) = _hash_set3(h,(uword) (key),0,0) 261 #define hash_unset(h,key) ((h) = _hash_unset ((h), (uword) (key),0)) 264 #define hash_unset3(h,key,old_value) ((h) = _hash_unset ((h), (uword) (key), (void *) (old_value))) 269 #define hash_get_mem(h,key) _hash_get ((h), pointer_to_uword (key)) 272 #define hash_get_pair_mem(h,key) _hash_get_pair ((h), pointer_to_uword (key)) 275 #define hash_set_mem(h,key,value) hash_set3 (h, pointer_to_uword (key), (value), 0) 288 #define hash_set1_mem(h,key) hash_set3 ((h), pointer_to_uword (key), 0, 0) 291 #define hash_unset_mem(h,key) ((h) = _hash_unset ((h), pointer_to_uword (key),0)) 307 extern void *_hash_free (
void *v);
310 #define hash_free(h) (h) = _hash_free ((h)) 373 #define hash_foreach_pair(p,v,body) \ 375 __label__ _hash_foreach_done; \ 376 hash_t * _h = hash_header (v); \ 378 hash_pair_t * _q, * _q_end; \ 379 uword _i, _i1, _id, _pair_increment; \ 383 _pair_increment = 1; \ 385 _pair_increment = 1 << _h->log2_pair_size; \ 386 while (_i < hash_capacity (v)) \ 388 _id = _h->is_user[_i / BITS (_h->is_user[0])]; \ 389 _i1 = _i + BITS (_h->is_user[0]); \ 395 _q_end = _q + _pair_increment; \ 399 hash_pair_indirect_t * _pi = _p; \ 401 if (_h->log2_pair_size > 0) \ 402 _q_end = hash_forward (_h, _q, indirect_pair_get_len (_pi)); \ 404 _q_end = vec_end (_q); \ 409 while (_q < _q_end) \ 411 uword _break_in_body = 1; \ 415 _break_in_body = 0; \ 417 if (_break_in_body) \ 418 goto _hash_foreach_done; \ 419 _q += _pair_increment; \ 422 _p = (hash_pair_t *)_p + _pair_increment; \ 425 } while (_i < _i1); \ 427 _hash_foreach_done: \ 442 #define hash_foreach(key_var,value_var,h,body) \ 445 hash_foreach_pair (_r, (h), { \ 446 (key_var) = (__typeof__ (key_var)) _r->key; \ 447 (value_var) = (__typeof__ (value_var)) _r->value[0]; \ 448 do { body; } while (0); \ 461 #define hash_foreach_mem(key_var,value_var,h,body) \ 464 hash_foreach_pair (_r, (h), { \ 465 (key_var) = (__typeof__ (key_var)) uword_to_pointer (_r->key, void *); \ 466 (value_var) = (__typeof__ (value_var)) _r->value[0]; \ 467 do { body; } while (0); \ 491 1) / sizeof (p->
key));
494 #define hash_create2(_elts,_user,_value_bytes, \ 495 _key_sum,_key_equal, \ 496 _format_pair,_format_pair_arg) \ 499 clib_memset (&_h, 0, sizeof (_h)); \ 501 _h.key_sum = (hash_key_sum_function_t *) (_key_sum); \ 502 _h.key_equal = (_key_equal); \ 503 hash_set_value_bytes (&_h, (_value_bytes)); \ 504 _h.format_pair = (format_function_t *) (_format_pair); \ 505 _h.format_pair_arg = (_format_pair_arg); \ 506 _hash_create ((_elts), &_h); \ 513 #define hash_mix_step(a,b,c,s0,s1,s2) \ 515 (a) -= (b) + (c); (a) ^= (c) >> (s0); \ 516 (b) -= (c) + (a); (b) ^= (a) << (s1); \ 517 (c) -= (a) + (b); (c) ^= (b) >> (s2); \ 520 #define hash_mix32_step_1(a,b,c) hash_mix_step(a,b,c,13,8,13) 521 #define hash_mix32_step_2(a,b,c) hash_mix_step(a,b,c,12,16,5) 522 #define hash_mix32_step_3(a,b,c) hash_mix_step(a,b,c,3,10,15) 524 #define hash_mix64_step_1(a,b,c) hash_mix_step(a,b,c,43,9,8) 525 #define hash_mix64_step_2(a,b,c) hash_mix_step(a,b,c,38,23,5) 526 #define hash_mix64_step_3(a,b,c) hash_mix_step(a,b,c,35,49,11) 527 #define hash_mix64_step_4(a,b,c) hash_mix_step(a,b,c,12,18,22) 531 #define hash_mix64(a0,b0,c0) \ 533 hash_mix64_step_1 (a0, b0, c0); \ 534 hash_mix64_step_2 (a0, b0, c0); \ 535 hash_mix64_step_3 (a0, b0, c0); \ 536 hash_mix64_step_4 (a0, b0, c0); \ 539 #define hash_mix32(a0,b0,c0) \ 541 hash_mix32_step_1 (a0, b0, c0); \ 542 hash_mix32_step_2 (a0, b0, c0); \ 543 hash_mix32_step_3 (a0, b0, c0); \ 551 return (x << i) | (x >> (
BITS (i) -
i));
554 #define hash_v3_mix32(a,b,c) \ 556 (a) -= (c); (a) ^= hash32_rotate_left ((c), 4); (c) += (b); \ 557 (b) -= (a); (b) ^= hash32_rotate_left ((a), 6); (a) += (c); \ 558 (c) -= (b); (c) ^= hash32_rotate_left ((b), 8); (b) += (a); \ 559 (a) -= (c); (a) ^= hash32_rotate_left ((c),16); (c) += (b); \ 560 (b) -= (a); (b) ^= hash32_rotate_left ((a),19); (a) += (c); \ 561 (c) -= (b); (c) ^= hash32_rotate_left ((b), 4); (b) += (a); \ 564 #define hash_v3_finalize32(a,b,c) \ 566 (c) ^= (b); (c) -= hash32_rotate_left ((b), 14); \ 567 (a) ^= (c); (a) -= hash32_rotate_left ((c), 11); \ 568 (b) ^= (a); (b) -= hash32_rotate_left ((a), 25); \ 569 (c) ^= (b); (c) -= hash32_rotate_left ((b), 16); \ 570 (a) ^= (c); (a) -= hash32_rotate_left ((c), 4); \ 571 (b) ^= (a); (b) -= hash32_rotate_left ((a), 14); \ 572 (c) ^= (b); (c) -= hash32_rotate_left ((b), 24); \ 577 #define hash_v3_mix32_step1(a,b,c) \ 579 (a) -= (c); (a) ^= hash32_rotate_left ((c), 4); (c) += (b); \ 580 (b) -= (a); (b) ^= hash32_rotate_left ((a), 6); (a) += (c); \ 583 #define hash_v3_mix32_step2(a,b,c) \ 585 (c) -= (b); (c) ^= hash32_rotate_left ((b), 8); (b) += (a); \ 586 (a) -= (c); (a) ^= hash32_rotate_left ((c),16); (c) += (b); \ 589 #define hash_v3_mix32_step3(a,b,c) \ 591 (b) -= (a); (b) ^= hash32_rotate_left ((a),19); (a) += (c); \ 592 (c) -= (b); (c) ^= hash32_rotate_left ((b), 4); (b) += (a); \ 595 #define hash_v3_finalize32_step1(a,b,c) \ 597 (c) ^= (b); (c) -= hash32_rotate_left ((b), 14); \ 598 (a) ^= (c); (a) -= hash32_rotate_left ((c), 11); \ 601 #define hash_v3_finalize32_step2(a,b,c) \ 603 (b) ^= (a); (b) -= hash32_rotate_left ((a), 25); \ 604 (c) ^= (b); (c) -= hash32_rotate_left ((b), 16); \ 607 #define hash_v3_finalize32_step3(a,b,c) \ 609 (a) ^= (c); (a) -= hash32_rotate_left ((c), 4); \ 610 (b) ^= (a); (b) -= hash32_rotate_left ((a), 14); \ 611 (c) ^= (b); (c) -= hash32_rotate_left ((b), 24); \ 615 #define hash_v3_mix_step_1_u32x(a,b,c) \ 617 (a) -= (c); (a) ^= u32x_irotate_left ((c), 4); (c) += (b); \ 618 (b) -= (a); (b) ^= u32x_irotate_left ((a), 6); (a) += (c); \ 619 (c) -= (b); (c) ^= u32x_irotate_left ((b), 8); (b) += (a); \ 622 #define hash_v3_mix_step_2_u32x(a,b,c) \ 624 (a) -= (c); (a) ^= u32x_irotate_left ((c),16); (c) += (b); \ 625 (b) -= (a); (b) ^= u32x_irotate_left ((a),19); (a) += (c); \ 626 (c) -= (b); (c) ^= u32x_irotate_left ((b), 4); (b) += (a); \ 629 #define hash_v3_finalize_step_1_u32x(a,b,c) \ 631 (c) ^= (b); (c) -= u32x_irotate_left ((b), 14); \ 632 (a) ^= (c); (a) -= u32x_irotate_left ((c), 11); \ 633 (b) ^= (a); (b) -= u32x_irotate_left ((a), 25); \ 636 #define hash_v3_finalize_step_2_u32x(a,b,c) \ 638 (c) ^= (b); (c) -= u32x_irotate_left ((b), 16); \ 639 (a) ^= (c); (a) -= u32x_irotate_left ((c), 4); \ 640 (b) ^= (a); (b) -= u32x_irotate_left ((a), 14); \ 641 (c) ^= (b); (c) -= u32x_irotate_left ((b), 24); \ 644 #define hash_v3_mix_u32x(a,b,c) \ 646 hash_v3_mix_step_1_u32x(a,b,c); \ 647 hash_v3_mix_step_2_u32x(a,b,c); \ 650 #define hash_v3_finalize_u32x(a,b,c) \ 652 hash_v3_finalize_step_1_u32x(a,b,c); \ 653 hash_v3_finalize_step_2_u32x(a,b,c); \ 661 #define hash_create_mem(elts,key_bytes,value_bytes) \ 662 hash_create2((elts),(key_bytes),(value_bytes),mem_key_sum,mem_key_equal,0,0) 668 #define hash_create_vec(elts,key_bytes,value_bytes) \ 669 hash_create2((elts),(key_bytes),(value_bytes),\ 670 vec_key_sum,vec_key_equal,vec_key_format_pair,0) 684 #define hash_create_shmem(elts,key_bytes,value_bytes) \ 685 hash_create2((elts),(key_bytes),(value_bytes), \ 686 (hash_key_sum_function_t *) KEY_FUNC_MEM, \ 687 (hash_key_equal_function_t *)KEY_FUNC_MEM, \ 690 #define hash_create_string(elts,value_bytes) \ 691 hash_create2((elts),0,(value_bytes), \ 692 (hash_key_sum_function_t *) KEY_FUNC_STRING, \ 693 (hash_key_equal_function_t *)KEY_FUNC_STRING, \ 696 #define hash_create(elts,value_bytes) \ 697 hash_create2((elts),0,(value_bytes), \ 698 (hash_key_sum_function_t *) KEY_FUNC_NONE, \ 699 (hash_key_equal_function_t *) KEY_FUNC_NONE, \ 702 #define hash_create_uword(elts,value_bytes) \ 703 hash_create2((elts),0,(value_bytes), \ 704 (hash_key_sum_function_t *) KEY_FUNC_POINTER_UWORD, \ 705 (hash_key_equal_function_t *) KEY_FUNC_POINTER_UWORD, \ 708 #define hash_create_u32(elts,value_bytes) \ 709 hash_create2((elts),0,(value_bytes), \ 710 (hash_key_sum_function_t *) KEY_FUNC_POINTER_U32, \ 711 (hash_key_equal_function_t *) KEY_FUNC_POINTER_U32, \
clib_error_t * hash_validate(void *v)
u8 pad[3]
log2 (size of the packing page block)
uword hash_bytes(void *v)
static uword indirect_pair_get_len(hash_pair_indirect_t *p)
unformat_function_t unformat_hash_string
uword hash_memory(void *p, word n_bytes, uword state)
#define clib_memcpy_fast(a, b, c)
u8 * format_hash(u8 *s, va_list *va)
uword mem_key_sum(hash_t *h, uword key)
static void hash_set_value_bytes(hash_t *h, uword value_bytes)
int test_hash_main(unformat_input_t *input)
static void indirect_pair_set(hash_pair_indirect_t *p, uword log2_alloc, uword len)
#define hash_set_mem(h, key, value)
uword vec_key_equal(hash_t *h, uword key1, uword key2)
#define hash_get_pair_mem(h, key)
static uword hash_header_bytes(void *v)
static void hash_set_flags(void *v, uword flags)
static uword hash_value_bytes(hash_t *h)
static hash_t * hash_header(void *v)
#define hash_unset_mem(h, key)
static uword hash_capacity(void *v)
void * hash_dup(void *old)
static uword hash_is_user(void *v, uword i)
static uword hash_pair_bytes(hash_t *h)
uword string_key_equal(hash_t *h, uword key1, uword key2)
void * hash_resize(void *old, uword new_size)
unformat_function_t unformat_hash_vec_string
uword() hash_key_equal_function_t(struct hash_header *, uword key1, uword key2)
static uword hash_pair_log2_bytes(hash_t *h)
hash_pair_indirect_t indirect
static void * hash_forward1(hash_t *h, void *v)
static void hash_set_pair_format(void *v, format_function_t *format_pair, void *format_pair_arg)
static uword hash32_rotate_left(u32 x, u32 i)
u8 * string_key_format_pair(u8 *s, va_list *args)
uword mem_key_equal(hash_t *h, uword key1, uword key2)
static uword indirect_pair_get_log2_bytes(hash_pair_indirect_t *p)
#define uword_to_pointer(u, type)
static uword hash_elts(void *v)
static void * hash_forward(hash_t *h, void *v, uword n)
uword() hash_key_sum_function_t(struct hash_header *, uword key)
static void clib_mem_free(void *p)
static void hash_unset_mem_free(uword **h, const void *key)
static void * clib_mem_alloc(uword size)
hash_pair_t * hash_next(void *v, hash_next_t *hn)
u8 * vec_key_format_pair(u8 *s, va_list *args)
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
struct hash_header hash_t
static uword max_log2(uword x)
vl_api_dhcp_client_state_t state
static void * vec_header(void *v, uword header_bytes)
Find a user vector header.
static void hash_set_mem_alloc(uword **h, const void *key, uword v)
uword string_key_sum(hash_t *h, uword key)
uword vec_key_sum(hash_t *h, uword key)
CLIB vectors are ubiquitous dynamically resized arrays with by user defined "headers".