alpm_lib_trie.h (13409B)
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 * trie data structure 7 * 8 *-----------------------------------------------------------------------------*/ 9 #ifndef _ALPM_LIB_TRIE4_H_ 10 #define _ALPM_LIB_TRIE4_H_ 11 12 #include <sal/types.h> 13 14 #ifdef ALPM_ENABLE 15 16 typedef struct alpm_lib_trie_node_s alpm_lib_trie_node_t; 17 18 typedef enum alpm_lib_trie_node_type_e { 19 trieNodeTypeInternal, 20 trieNodeTypePayload, 21 trieNodeTypeInternalPpg, 22 trieNodeTypeMax 23 } alpm_lib_trie_node_type_t; 24 25 struct alpm_lib_trie_node_s { 26 alpm_lib_trie_node_t *trie_node; 27 alpm_lib_trie_node_t *child[2]; 28 uint32 skip_len; 29 uint32 skip_addr; 30 alpm_lib_trie_node_type_t type; 31 uint32 count; /* number of payload node counts */ 32 }; 33 34 typedef struct alpm_lib_trie_s { 35 alpm_lib_trie_node_t *trie; /* trie root pointer */ 36 uint32 v6_key; /* support 144 bits key, otherwise expect 48 bits key */ 37 } alpm_lib_trie_t; 38 39 typedef int (*alpm_lib_trie_callback_f)(alpm_lib_trie_node_t *trie, void *datum); 40 41 typedef struct alpm_lib_trie_bpm_cb_info_s { 42 uint32 *pfx; /* prefix buffer pointer from caller space */ 43 uint32 len; /* prefix length */ 44 void *user_data; 45 } alpm_lib_trie_bpm_cb_info_t; 46 47 typedef int (*alpm_lib_trie_ppg_cb_f)(alpm_lib_trie_node_t *trie, alpm_lib_trie_bpm_cb_info_t *info); 48 49 typedef struct trie_list_s { 50 alpm_lib_trie_node_t *node; 51 struct trie_list_s *next; 52 } trie_list_t; 53 54 typedef enum alpm_lib_trie_traverse_order_e { 55 trieTraverseOrderPre, /* root, left, right */ 56 trieTraverseOrderIn, /* left, root, right */ 57 trieTraverseOrderPost, /* left, right, root */ 58 trieTraverseOrderMax 59 } alpm_lib_trie_traverse_order_t; 60 61 typedef enum alpm_lib_trie_traverse_state_e { 62 trieTraverseStateNone, 63 trieTraverseStateDel, 64 trieTraverseStateDone, 65 trieTraverseStateMax 66 } alpm_lib_trie_traverse_state_t; 67 68 #define TRIE_TRAVERSE_STOP(state, rv) \ 69 {if (state == trieTraverseStateDone || rv < 0) {return rv;} } 70 71 typedef int (*alpm_lib_trie_callback_ext_f)(alpm_lib_trie_node_t *ptrie, alpm_lib_trie_node_t *trie, 72 alpm_lib_trie_traverse_state_t *state, void *info); 73 74 typedef enum alpm_lib_trie_split_state_e { 75 trieSplitStateNone, 76 trieSplitStatePayloadSplit, 77 trieSplitStatePayloadSplitDone, 78 trieSplitStatePruneNodes, 79 trieSplitStateDone, 80 trieSplitStateMax 81 } alpm_lib_trie_split_state_t; 82 83 typedef enum alpm_lib_trie_split2_state_e { 84 trieSplit2StateNone, 85 trieSplit2StatePruneNodes, 86 trieSplit2StateDone, 87 trieSplit2StateMax 88 } alpm_lib_trie_split2_state_t; 89 90 /* 91 * This macro is a tidy way of performing subtraction to move from a 92 * pointer within an object to a pointer to the object. 93 * 94 * Arguments are: 95 * type of object to recover 96 * pointer to object from which to recover element pointer 97 * pointer to an object of type t 98 * name of the trie node field in t through which the object is linked on trie 99 * Returns: 100 * a pointer to the object, of type t 101 */ 102 #define TRIE_ELEMENT(t, p, ep, f) \ 103 ((t) (((char *) (p)) - (((char *) &((ep)->f)) - ((char *) (ep))))) 104 105 /* 106 * TRIE_ELEMENT_GET performs the same function as TRIE_ELEMENT, but does not 107 * require a pointer of type (t). This form is preferred as TRIE_ELEMENT 108 * typically generate Coverity errors, and the (ep) argument is unnecessary. 109 * 110 * Arguments are: 111 * type of object to recover 112 * pointer to object from which to recover element pointer 113 * name of the trie node field in t through which the object is linked on trie 114 * Returns: 115 * a pointer to the object, of type t 116 */ 117 #define TRIE_ELEMENT_GET(t, p, f) \ 118 ((t) (((char *) (p)) - (((char *) &(((t)(0))->f))))) 119 120 121 #define _TRIE_NODE_CLONE_(dest,src) \ 122 sal_memcpy((dest),(src),sizeof(alpm_lib_trie_node_t)) 123 124 /* allocates a trie & initializes it */ 125 extern int alpm_lib_trie_init(uint32 max_key_len, alpm_lib_trie_t **ptrie); 126 127 /* destroys a trie */ 128 extern int alpm_lib_trie_destroy(alpm_lib_trie_t *trie); 129 130 /* Inserts provided prefix/length in to the trie */ 131 extern int alpm_lib_trie_insert(alpm_lib_trie_t *trie, uint32 *key, uint32 length, alpm_lib_trie_node_t *payload); 132 133 /* Deletes provided prefix/length in to the trie */ 134 extern int alpm_lib_trie_delete(alpm_lib_trie_t *trie, uint32 *key, uint32 length, alpm_lib_trie_node_t **payload); 135 136 /* Search the given trie for provided prefix/length */ 137 extern int alpm_lib_trie_search(alpm_lib_trie_t *trie, uint32 *key, uint32 length, alpm_lib_trie_node_t **payload); 138 139 /* Dumps the trie pre-order [root|left|child] */ 140 extern int alpm_lib_trie_dump(alpm_lib_trie_t *trie, alpm_lib_trie_callback_f cb, void *user_data); 141 142 /* Find the longest prefix matched with given prefix */ 143 extern int alpm_lib_trie_find_lpm(alpm_lib_trie_t *trie, uint32 *key, uint32 length, alpm_lib_trie_node_t **payload); 144 145 /* Split the trie into 2 based on optimum pivot */ 146 extern int alpm_lib_trie_split(alpm_lib_trie_t *trie, const uint32 max_split_len, 147 uint32 *pivot, uint32 *length, 148 alpm_lib_trie_node_t **split_trie_root, 149 /* if set split will strictly split only on payload nodes 150 * if not set splits at optimal point on the trie */ 151 uint8 payload_node_split, 152 alpm_lib_trie_callback_ext_f cb, 153 void *user_data, 154 int max_split_count); 155 156 /* unsplit or fuse the child trie with parent trie */ 157 extern int alpm_lib_trie_merge(alpm_lib_trie_t *parent_trie, alpm_lib_trie_node_t *child_trie, uint32 *child_pivot, uint32 length); 158 159 /* Split the trie such that the new sub trie covers given prefix/length. Basically this is a reverse of alpm_lib_trie_merge. */ 160 extern int alpm_lib_trie_split2(alpm_lib_trie_t *trie, uint32 *key, uint32 key_len, uint32 *pivot, uint32 *pivot_len, alpm_lib_trie_node_t **split_trie_root, const int max_split_count, const int exact_same); 161 162 /* Traverse the trie & call the application callback with user data */ 163 extern int alpm_lib_trie_traverse(alpm_lib_trie_t *trie, alpm_lib_trie_callback_f cb, void *user_data, alpm_lib_trie_traverse_order_t order); 164 165 /* Traverse the trie (trieNodeTypePayload) & call the extended application callback which has current node's trieNodeTypePayload parent node with user data. */ 166 extern int alpm_lib_trie_traverse2(alpm_lib_trie_t *trie, alpm_lib_trie_callback_ext_f cb, void *user_data, alpm_lib_trie_traverse_order_t order); 167 168 extern int _alpm_lib_trie_ppg_prefix(alpm_lib_trie_node_t *pivot, uint32 pivot_len, uint32 *pfx, uint32 len, alpm_lib_trie_ppg_cb_f cb, alpm_lib_trie_bpm_cb_info_t *cb_info); 169 170 extern int alpm_lib_trie_ppg(alpm_lib_trie_t *trie, uint32 pivot_len, uint32 *pfx, uint32 len, alpm_lib_trie_ppg_cb_f cb, alpm_lib_trie_bpm_cb_info_t *cb_info); 171 172 /* ====================== v6 ======================== */ 173 174 /* get bit at bit_position from uint32 key array of maximum length of max_len 175 * assuming the big-endian word order. bit_pos is 0 based. for example, assuming 176 * the max_len is 48 bits, then key[0] has bits 47-32, and key[1] has bits 31-0. 177 * use _TAPS_GET_KEY_BIT(key, 0, 48) to get bit 0. 178 */ 179 #define TP_BITS2IDX(x) ((BITS2WORDS(_MAX_KEY_LEN_144_) - 1) - (x)/32) 180 181 /* Get "len" number of bits start with lsb bit postion from an uint32 array 182 * the array is assumed to be with format described above in _TAPS_GET_KEY_BIT 183 * NOTE: len must be <= 32 bits 184 */ 185 #define _TAPS_GET_KEY_BITS(key, lsb, len) \ 186 ((TRIE_SHR((key)[TP_BITS2IDX(lsb)], ((lsb)%_NUM_WORD_BITS_), _NUM_WORD_BITS_) | \ 187 ((TP_BITS2IDX(lsb)<1)?0:(TRIE_SHL((key)[TP_BITS2IDX(lsb)-1], _NUM_WORD_BITS_-((lsb)%_NUM_WORD_BITS_), _NUM_WORD_BITS_)))) & \ 188 (BITMASK((len)))) 189 190 extern int _alpm_lib_trie_v6_search(alpm_lib_trie_node_t *trie, 191 uint32 *key, 192 uint32 length, 193 alpm_lib_trie_node_t **payload, 194 uint32 *result_key, 195 uint32 *result_len, 196 uint32 dump, 197 uint32 find_pivot); 198 199 extern int _alpm_lib_trie_v6_find_lpm(alpm_lib_trie_node_t *trie, 200 uint32 *key, 201 uint32 length, 202 alpm_lib_trie_node_t **payload, 203 alpm_lib_trie_callback_f cb, 204 void *user_data, 205 uint32 exclude_self); 206 207 extern int _alpm_lib_trie_v6_skip_node_free(alpm_lib_trie_node_t *trie, 208 uint32 *key, 209 uint32 length); 210 211 extern int _alpm_lib_trie_v6_skip_node_alloc(alpm_lib_trie_node_t **node, 212 uint32 *key, 213 uint32 msb, /* NOTE: valid msb position 1 based, 0 means skip0/0 node */ 214 uint32 skip_len, 215 alpm_lib_trie_node_t *payload, 216 uint32 count); 217 218 extern int _alpm_lib_trie_v6_insert(alpm_lib_trie_node_t *trie, 219 uint32 *key, 220 uint32 length, 221 alpm_lib_trie_node_t *payload, /* payload node */ 222 alpm_lib_trie_node_t **child, /* child pointer if the child is modified */ 223 int child_count); 224 225 extern int _alpm_lib_trie_v6_delete(alpm_lib_trie_node_t *trie, 226 uint32 *key, 227 uint32 length, 228 alpm_lib_trie_node_t **payload, 229 alpm_lib_trie_node_t **child); 230 231 extern int _alpm_lib_trie_v6_split(alpm_lib_trie_node_t *trie, 232 uint32 *pivot, 233 uint32 *length, 234 uint32 *split_count, 235 alpm_lib_trie_node_t **split_node, 236 alpm_lib_trie_node_t **child, 237 const uint32 max_count, 238 const uint32 max_split_len, 239 alpm_lib_trie_split_state_t *state, 240 alpm_lib_trie_callback_ext_f cb, 241 void *user_data, 242 int max_split_count); 243 244 extern int _alpm_lib_trie_v6_merge(alpm_lib_trie_node_t *parent_trie, 245 alpm_lib_trie_node_t *child_trie, 246 uint32 *child_pivot, 247 uint32 length, 248 alpm_lib_trie_node_t **new_parent); 249 250 extern int _alpm_lib_trie_v6_split2(alpm_lib_trie_node_t *trie, 251 uint32 *key, 252 uint32 key_len, 253 uint32 *pivot, 254 uint32 *pivot_len, 255 uint32 *split_count, 256 alpm_lib_trie_node_t **split_node, 257 alpm_lib_trie_node_t **child, 258 alpm_lib_trie_split2_state_t *state, 259 const int max_split_count, 260 const int exact_same); 261 262 extern int _alpm_lib_trie_v6_ppg_prefix(alpm_lib_trie_node_t *pivot, 263 uint32 pivot_len, 264 uint32 *pfx, 265 uint32 len, 266 alpm_lib_trie_ppg_cb_f cb, 267 alpm_lib_trie_bpm_cb_info_t *cb_info); 268 269 /*================================= 270 * Used by internal functions only 271 *================================*/ 272 #define _MAX_KEY_LEN_48_ (48) 273 #define _MAX_KEY_LEN_144_ (144) 274 /* key packing expetations: 275 * eg., 48 bit key 276 * - 10/8 -> key[0]=0, key[1]=8 277 * - 0x123456789a -> key[0] = 0x12 key[1] = 0x3456789a 278 * length - represents number of valid bits from farther to lower index ie., 1->0 279 * eg., 144 bit key 280 * - 0x10/8 -> key[0]=0, key[1]=0, key[2]=0, key[3]=0, key[0]=0x10 281 * - 0x123456789a/48 -> key[0]=0, key[1]=0, key[2]=0, key[3] = 0x12 key[4] = 0x3456789a 282 * length - represents number of valid bits from farther to lower index ie., 1->0 283 */ 284 #define KEY48_BIT2IDX(x) (((BITS2WORDS(_MAX_KEY_LEN_48_)*32) - (x))/32) 285 #define KEY144_BIT2IDX(x) (((BITS2WORDS(_MAX_KEY_LEN_144_)*32) - (x))/32) 286 287 #define _MAX_SKIP_LEN_ (31) 288 289 #define _SHL(data, shift) ((data) << (shift)) 290 #define _SHR(data, shift) ((data) >> (shift)) 291 #define _MASK(len) ((1 << (len)) - 1) 292 293 #define TRIE_SHL(data, shift, max) \ 294 (((shift)>=(max))?0:(_SHL(data, shift))) 295 296 #define TRIE_SHR(data, shift, max) \ 297 (((shift)>=(max))?0:(_SHR(data, shift))) 298 299 #define TRIE_MASK(len) \ 300 (((len)>=32 || (len)==0) ? 0xFFFFFFFF :(_MASK(len))) 301 302 #define BITMASK(len) \ 303 (((len)>=32)?0xFFFFFFFF:((1<<(len))-1)) 304 305 #define ABS(n) ((((int)(n)) < 0) ? -(n) : (n)) 306 307 #define _NUM_WORD_BITS_ (32) 308 309 /* 310 * bit 0 - 0 311 * bit [1, _MAX_SKIP_LEN] - 1 312 * bit [_MAX_SKIP_LEN+1, 2*_MAX_SKIP_LEN] - 2... 313 */ 314 #define BITS2SKIPOFF(x) (((x) + _MAX_SKIP_LEN_-1) / _MAX_SKIP_LEN_) 315 316 /* (internal) Generic operation macro on bit array _a, with bit _b */ 317 #define _BITOP(_a, _b, _op) \ 318 ((_a) _op (1U << ((_b) % _NUM_WORD_BITS_))) 319 320 /* Specific operations */ 321 #define _BITGET(_a, _b) _BITOP(_a, _b, &) 322 #define _BITSET(_a, _b) _BITOP(_a, _b, |=) 323 #define _BITCLR(_a, _b) _BITOP(_a, _b, &= ~) 324 325 extern int _alpm_lib_trie_fuse_child(alpm_lib_trie_node_t *trie, int bit); 326 extern int _alpm_lib_print_trie_node(alpm_lib_trie_node_t *trie, void *datum); 327 extern int _trie_traverse_ppg_prefix(alpm_lib_trie_node_t *trie, alpm_lib_trie_ppg_cb_f cb, alpm_lib_trie_bpm_cb_info_t *cb_info); 328 329 #endif /* ALPM_ENABLE */ 330 331 #endif /* _ALPM_LIB_TRIE4_H_ */