sw_state_hash_tbl.h (4326B)
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 _SW_STATE_HASH_TBL_H_ 34 #define _SW_STATE_HASH_TBL_H_ 35 36 #include <sal/types.h> 37 #include <sal/core/sync.h> 38 #include <shared/swstate/sw_state.h> 39 40 typedef uint8* sw_state_htb_key_t; 41 typedef uint8* sw_state_htb_data_t; 42 43 typedef uint32 (*sw_state_htb_hash_f)(uint8* key_bytes, uint32 length); 44 typedef void (*sw_state_htb_cast_key_f)(sw_state_htb_key_t key, 45 uint8 **key_bytes, 46 uint32 *key_size); 47 typedef int (*sw_state_htb_key_cmp_f)(sw_state_htb_key_t a, 48 sw_state_htb_key_t b, 49 uint32 size); 50 typedef void (*sw_state_htb_data_free_f)(int unit, sw_state_htb_data_t data); 51 52 typedef struct ss_hash_entries_s { 53 PARSER_HINT_ARR int *next; 54 PARSER_HINT_ARR uint8 *datas; /* data0/data1/data2/..../datan */ 55 PARSER_HINT_ARR uint8 *keys; /* key0/key1/key2/..../keyn */ 56 } ss_hash_entries_t; 57 58 typedef struct sw_state_hash_table_s { 59 int max_num_entries; 60 int key_size; /* size of variable length key 61 * in sw_state_htb_key_t */ 62 int data_size; 63 int num_free; 64 PARSER_HINT_ARR int *free_arr; 65 ss_hash_entries_t entry_arrays /*entry_list*/; 66 PARSER_HINT_ARR int *table; 67 68 } sw_state_hash_table_t; 69 70 /* 71 * The following definition replaces: 72 * typedef sw_state_hash_table_t *sw_state_htb_hash_table_t; 73 * So that the new sw state could use a handle rather than a pointer. 74 */ 75 typedef int sw_state_htb_hash_table_t ; 76 77 typedef struct sw_state_hash_table_db_s { 78 PARSER_HINT_ARR_PTR sw_state_hash_table_t **hash_table; 79 int nof_htbl_used; 80 int max_nof_htbls; 81 } sw_state_hash_table_db_t; 82 83 84 85 int 86 sw_state_htb_create(int unit, int *ht_indx, int max_num_entries, int key_size, int data_size, 87 char* tbl_name); 88 89 int 90 sw_state_htb_destroy(int unit, int ht_indx, sw_state_htb_data_free_f cb); 91 92 int 93 sw_state_htb_find(int unit, int ht_indx, sw_state_htb_key_t key, sw_state_htb_data_t data, 94 int remove); 95 96 int 97 sw_state_htb_insert(int unit, int ht_indx, sw_state_htb_key_t key, sw_state_htb_data_t data); 98 99 100 typedef int (*sw_state_htb_cb_t)(int unit, sw_state_htb_key_t key, sw_state_htb_data_t data); 101 102 int 103 sw_state_htb_iterate(int unit, int ht_indx, sw_state_htb_cb_t restore_cb); 104 105 int 106 sw_state_htb_init(int unit, int max_nof_htbls); 107 108 int 109 sw_state_htb_deinit(int unit); 110 111 #endif /* _SW_STATE_HASH_TBL_H_ */ 112