hash_tbl.h (4003B)
1 /* 2 * 3 * This license is set out in https://raw.githubusercontent.com/Broadcom-Network-Switching-Software/OpenBCM/master/Legal/LICENSE file. 4 * 5 * Copyright 2007-2019 Broadcom Inc. All rights reserved. 6 * 7 * File: shr_hash.h 8 * Purpose: Defines a generic hash table for key/value pairs. 9 * 10 * Overview: 11 * Provides a generic hash table interface with configurable and default hash 12 * and key compare functions. The interface allows for complex key types, but 13 * the caller must implement a _cast_ method to transform the complex type into 14 * a string of bytes for the hash function. Alternatively, the caller may 15 * replace the hash function itself, in which case, the default _cast_ method 16 * may be used to return the complex key and complex key size. 17 * 18 * Memory is allocated on-demand in blocks for hash entries, and freed in 19 * blocks when the free pool becomes large. 20 * 21 * Collisions are handled simply by creating a linked list per hash index and 22 * a linear search is performed within the list to find an entry. The list is 23 * not sorted. (future upgrade?) 24 * 25 * The caller defined KEY is *copied* and stored in the variable sized hash 26 * table entry for comparison. A *pointer* to the caller defined DATA is 27 * stored. The caller is reponsible for managing the memory where DATA points 28 * if any. Callbacks are provided upon hash destruction to free any allocated 29 * memory. The hash table module itself does not explitly free any DATA 30 * pointer at any time. 31 */ 32 33 #ifndef _HASH_TBL_H_ 34 #define _HASH_TBL_H_ 35 36 #include <sal/types.h> 37 #include <sal/core/sync.h> 38 39 typedef void* shr_htb_key_t; 40 typedef void* shr_htb_data_t; 41 42 typedef uint32 (*shr_htb_hash_f)(uint8* key_bytes, uint32 length); 43 typedef void (*shr_htb_cast_key_f)(shr_htb_key_t key, 44 uint8 **key_bytes, 45 uint32 *key_size); 46 typedef int (*shr_htb_key_cmp_f)(shr_htb_key_t a, 47 shr_htb_key_t b, 48 uint32 size); 49 typedef void (*shr_htb_data_free_f)(shr_htb_data_t data); 50 51 typedef struct _hash_entry_s { 52 struct _hash_entry_s *next; 53 shr_htb_data_t *data; /* caller managed memory */ 54 shr_htb_key_t key; /* NOTE: Variable size field. Struct 55 * is extented to caller supplied key_size 56 */ 57 } _hash_entry_t; 58 59 typedef struct hash_table_s { 60 int max_num_entries; 61 int key_size; /* size of variable length key 62 * in shr_htb_key_t */ 63 int alloc_blk_cnt; /* number of entries to allocate 64 * when the free list runs dry */ 65 int num_free; 66 _hash_entry_t *free_list; 67 _hash_entry_t **table; 68 sal_mutex_t lock; 69 70 shr_htb_hash_f hash_f; 71 shr_htb_key_cmp_f key_cmp_f; 72 shr_htb_cast_key_f cast_key_f; 73 74 } hash_table_t; 75 76 typedef hash_table_t* shr_htb_hash_table_t; 77 78 int 79 shr_htb_create(shr_htb_hash_table_t *ht, int max_num_entries, int key_size, 80 char* tbl_name); 81 82 int 83 shr_htb_destroy(shr_htb_hash_table_t *ht, shr_htb_data_free_f cb); 84 85 int 86 shr_htb_find(shr_htb_hash_table_t ht, shr_htb_key_t key, shr_htb_data_t *data, 87 int remove); 88 89 int 90 shr_htb_insert(shr_htb_hash_table_t ht, shr_htb_key_t key, shr_htb_data_t data); 91 92 93 typedef int (*shr_htb_cb_t)(int unit, shr_htb_key_t key, shr_htb_data_t data); 94 95 int 96 shr_htb_iterate(int unit, shr_htb_hash_table_t ht, shr_htb_cb_t restore_cb); 97 98 99 /* Configuration routines */ 100 void 101 shr_htb_cast_key_func_set(shr_htb_hash_table_t ht, 102 shr_htb_cast_key_f func); 103 void 104 shr_htb_hash_func_set(shr_htb_hash_table_t ht, 105 shr_htb_hash_f func); 106 107 void 108 shr_htb_key_cmp_func_set(shr_htb_hash_table_t ht, 109 shr_htb_key_cmp_f func); 110 111 112 113 #endif /* _HASH_TBL_H_ */ 114