trie.h (14587B)
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 _ESW_TRIDENT2_TRIE_H_ 10 #define _ESW_TRIDENT2_TRIE_H_ 11 12 #ifdef ALPM_ENABLE 13 14 typedef struct trie_node_s trie_node_t; 15 16 typedef enum _node_type_e { 17 INTERNAL, PAYLOAD, MAX 18 } node_type_e_t; 19 20 typedef struct child_node_s { 21 trie_node_t *child_node; 22 } child_node_t; 23 24 struct trie_node_s { 25 trie_node_t *trie_node; 26 #define _MAX_CHILD_ (2) 27 child_node_t child[_MAX_CHILD_]; 28 unsigned int skip_len; 29 unsigned int skip_addr; 30 node_type_e_t type; 31 unsigned int count; /* number of payload node counts */ 32 unsigned int bpm; /* best prefix match bit map - 32 bits */ 33 }; 34 35 typedef struct trie_s { 36 trie_node_t *trie; /* trie root pointer */ 37 unsigned int v6_key; /* support 144 bits key, otherwise expect 48 bits key */ 38 } trie_t; 39 40 typedef int (*trie_callback_f)(trie_node_t *trie, void *datum); 41 42 typedef struct trie_bpm_cb_info_s { 43 unsigned int *pfx; /* prefix buffer pointer from caller space */ 44 unsigned int len; /* prefix length */ 45 void *user_data; 46 } trie_bpm_cb_info_t; 47 48 typedef int (*trie_propagate_cb_f)(trie_node_t *trie, 49 trie_bpm_cb_info_t *info); 50 51 /* 52 * This macro is a tidy way of performing subtraction to move from a 53 * pointer within an object to a pointer to the object. 54 * 55 * Arguments are: 56 * type of object to recover 57 * pointer to object from which to recover element pointer 58 * pointer to an object of type t 59 * name of the trie node field in t through which the object is linked on trie 60 * Returns: 61 * a pointer to the object, of type t 62 */ 63 #define TRIE_ELEMENT(t, p, ep, f) \ 64 ((t) (((char *) (p)) - (((char *) &((ep)->f)) - ((char *) (ep))))) 65 66 /* 67 * TRIE_ELEMENT_GET performs the same function as TRIE_ELEMENT, but does not 68 * require a pointer of type (t). This form is preferred as TRIE_ELEMENT 69 * typically generate Coverity errors, and the (ep) argument is unnecessary. 70 * 71 * Arguments are: 72 * type of object to recover 73 * pointer to object from which to recover element pointer 74 * name of the trie node field in t through which the object is linked on trie 75 * Returns: 76 * a pointer to the object, of type t 77 */ 78 #define TRIE_ELEMENT_GET(t, p, f) \ 79 ((t) (((char *) (p)) - (((char *) &(((t)(0))->f))))) 80 81 82 #define _CLONE_TRIE_NODE_(dest,src) \ 83 sal_memcpy((dest),(src),sizeof(trie_node_t)) 84 85 /* 86 * Function: 87 * trie_init 88 * Purpose: 89 * allocates a trie & initializes it 90 */ 91 extern int trie_init(unsigned int max_key_len, trie_t **ptrie); 92 93 /* 94 * Function: 95 * trie_destroy 96 * Purpose: 97 * destroys a trie 98 */ 99 extern int trie_destroy(trie_t *trie); 100 101 /* 102 * Function: 103 * trie_insert 104 * Purpose: 105 * Inserts provided prefix/length in to the trie 106 */ 107 extern int trie_insert(trie_t *trie, 108 unsigned int *key, 109 /* bpm bit map if bpm management is required, 110 passing null skips bpm management */ 111 unsigned int *bpm, 112 unsigned int length, 113 trie_node_t *payload); 114 115 /* 116 * Function: 117 * trie_delete 118 * Purpose: 119 * Deletes provided prefix/length in to the trie 120 */ 121 extern int trie_delete(trie_t *trie, 122 unsigned int *key, 123 unsigned int length, 124 trie_node_t **payload); 125 126 /* 127 * Function: 128 * trie_search 129 * Purpose: 130 * Search the given trie for provided prefix/length 131 */ 132 extern int trie_search(trie_t *trie, 133 unsigned int *key, 134 unsigned int length, 135 trie_node_t **payload); 136 137 /* 138 * Function: 139 * trie_search_verbose 140 * Purpose: 141 * Search the given trie for provided prefix/length, 142 * return the matched prefix/length 143 */ 144 extern int trie_search_verbose(trie_t *trie, 145 unsigned int *key, 146 unsigned int length, 147 trie_node_t **payload, 148 unsigned int *result_key, 149 unsigned int *result_len); 150 /* 151 * Function: 152 * trie_dump 153 * Purpose: 154 * Dumps the trie pre-order [root|left|child] 155 */ 156 extern int trie_dump(trie_t *trie, trie_callback_f cb, void *user_data); 157 158 /* 159 * Function: 160 * trie_find_lpm 161 * Purpose: 162 * Find the longest prefix matched with given prefix 163 */ 164 extern int trie_find_lpm(trie_t *trie, 165 unsigned int *key, 166 unsigned int length, 167 trie_node_t **payload); 168 169 /* 170 * Function: 171 * trie_find_lpm2 172 * Purpose: 173 * Find the longest prefix matched with given prefix, exclude itself. 174 */ 175 extern int trie_find_lpm2(trie_t *trie, 176 unsigned int *key, 177 unsigned int length, 178 trie_node_t **payload); 179 180 /* 181 * Function: 182 * trie_find_pm 183 * Purpose: 184 * Find the prefix matched nodes with given prefix and callback 185 * with specified callback funtion and user data 186 */ 187 extern int trie_find_pm(trie_t *trie, 188 unsigned int *key, 189 unsigned int length, 190 trie_callback_f cb, 191 void *user_data); 192 193 /* 194 * Function: 195 * trie_find_prefix_bpm 196 * Purpose: 197 * Given a key/length return the Best prefix match length 198 * key/bpm_pfx_len will be the BPM for the key/length 199 */ 200 extern int trie_find_prefix_bpm(trie_t *trie, 201 unsigned int *key, 202 unsigned int length, 203 unsigned int *bpm_pfx_len); 204 205 /* 206 * Function: 207 * trie_bpm_mask_get 208 * Purpose: 209 * Get the bpm mask of target key. This key is already in the trie. 210 */ 211 extern int trie_bpm_mask_get(trie_t *trie, 212 unsigned int *key, 213 unsigned int length, 214 unsigned int *bpm_mask); 215 /* 216 * Function: 217 * trie_split 218 * Purpose: 219 * Split the trie into 2 based on optimum pivot 220 */ 221 extern int trie_split(trie_t *trie, 222 const unsigned int max_split_len, 223 const int split_to_pair, 224 unsigned int *pivot, 225 unsigned int *length, 226 trie_node_t **split_trie_root, 227 unsigned int *bpm, 228 /* if set split will strictly split only on payload nodes 229 * if not set splits at optimal point on the trie */ 230 uint8 payload_node_split, 231 int max_split_count); 232 233 /* 234 * Function: 235 * trie_merge 236 * Purpose: 237 * unsplit or fuse the child trie with parent trie 238 */ 239 extern int trie_merge(trie_t *parent_trie, 240 trie_node_t *child_trie, 241 unsigned int *child_pivot, 242 unsigned int length); 243 /* 244 * Function: 245 * trie_split2 246 * Purpose: 247 * Split the trie such that the new sub trie covers given prefix/length. 248 * Basically this is a reverse of trie_merge. 249 */ 250 extern int trie_split2(trie_t *trie, 251 unsigned int *key, 252 unsigned int key_len, 253 unsigned int *pivot, 254 unsigned int *pivot_len, 255 trie_node_t **split_trie_root, 256 const int max_split_count, 257 const int exact_same); 258 259 extern int trie_clone(trie_t *trie_src, trie_t **trie_dst); 260 extern int trie_compare(trie_t *trie_src, trie_t *trie_dst, int *equal); 261 262 typedef enum _trie_traverse_order_e_s { 263 _TRIE_PREORDER_TRAVERSE, /* root, left, right */ 264 _TRIE_INORDER_TRAVERSE, /* left, root, right */ 265 _TRIE_POSTORDER_TRAVERSE, /* left, right, root */ 266 _TRIE_TRAVERSE_MAX 267 } trie_traverse_order_e_t; 268 269 typedef enum _trie_traverse_states_e_s { 270 TRIE_TRAVERSE_STATE_NONE, 271 TRIE_TRAVERSE_STATE_DELETED, 272 TRIE_TRAVERSE_STATE_DONE, 273 TRIE_TRAVERSE_STATE_MAX 274 } trie_traverse_states_e_t; 275 typedef int (*trie_callback_ext_f)(trie_node_t *ptrie, trie_node_t *trie, 276 trie_traverse_states_e_t *state, void *info); 277 278 typedef int (*trie_repartition_callback_f)(trie_node_t *ptrie, trie_node_t *trie, 279 trie_traverse_states_e_t *state, void *info, 280 trie_node_t **new_ptrie); 281 282 /* 283 * Function: 284 * trie_traverse 285 * Purpose: 286 * Traverse the trie & call the application callback with user data 287 */ 288 extern int trie_traverse(trie_t *trie, 289 trie_callback_f cb, 290 void *user_data, 291 trie_traverse_order_e_t order); 292 /* 293 * Function: 294 * trie_traverse2 295 * Purpose: 296 * Traverse the trie (PAYLOAD) & call the extended application callback 297 * which has current node's PAYLOAD parent node with user data. 298 */ 299 extern int trie_traverse2(trie_t *trie, 300 trie_callback_ext_f cb, 301 void *user_data, 302 trie_traverse_order_e_t order); 303 304 /* 305 * Function: 306 * trie_repartition 307 * Purpose: 308 * Traverse the trie & call the extended application callback 309 * which has current node's parent node with user data. 310 */ 311 extern int trie_repartition(trie_t *trie, 312 trie_repartition_callback_f cb, 313 void *user_data, 314 trie_traverse_order_e_t order); 315 316 /* 317 * Function: 318 * trie_pivot_propagate_prefix 319 * Purpose: 320 * Propogate prefix BPM from a given pivot. 321 */ 322 extern int trie_pivot_propagate_prefix(trie_node_t *pivot, 323 unsigned int pivot_len, 324 unsigned int *pfx, 325 unsigned int len, 326 unsigned int add, /* 0-del/1-add */ 327 trie_propagate_cb_f cb, 328 trie_bpm_cb_info_t *cb_info); 329 330 extern int pvt_trie_propagate_prefix(trie_node_t *pivot, 331 unsigned int pivot_len, 332 unsigned int *pfx, 333 unsigned int len, 334 trie_propagate_cb_f cb, 335 trie_bpm_cb_info_t *cb_info); 336 337 extern int trie_ppg_prefix(trie_t *trie, 338 unsigned int pivot_len, 339 unsigned int *pfx, 340 unsigned int len, 341 trie_propagate_cb_f cb, 342 trie_bpm_cb_info_t *cb_info); 343 344 /* 345 * Function: 346 * trie_propagate_prefix 347 * Purpose: 348 * Propogate prefix BPM on a given trie. 349 */ 350 extern int trie_propagate_prefix(trie_t *trie, 351 unsigned int *pfx, 352 unsigned int len, 353 unsigned int add, /* 0-del/1-add */ 354 trie_propagate_cb_f cb, 355 trie_bpm_cb_info_t *cb_info); 356 357 /* 358 * Function: 359 * trie_util_get_bpm_pfx 360 * Purpose: 361 * finds best prefix match given a bpm bitmap & key 362 */ 363 extern int trie_util_get_bpm_pfx(unsigned int *bpm, 364 unsigned int key_len, 365 /* OUT */ 366 unsigned int *pfx_len); 367 368 /* 369 * Function: 370 * trie_iter_get_first 371 * Purpose: 372 * Traverse the trie & return pointer to first payload node 373 */ 374 extern int trie_iter_get_first(trie_t *trie, 375 trie_node_t **payload); 376 377 /*================================= 378 * Used by internal functions only 379 *================================*/ 380 #define _MAX_KEY_LEN_48_ (48) 381 #define _MAX_KEY_LEN_144_ (144) 382 383 typedef enum _trie_split_states_e_s { 384 TRIE_SPLIT_STATE_NONE, 385 TRIE_SPLIT_STATE_PAYLOAD_SPLIT, 386 TRIE_SPLIT_STATE_PAYLOAD_SPLIT_DONE, 387 TRIE_SPLIT_STATE_PRUNE_NODES, 388 TRIE_SPLIT_STATE_DONE, 389 TRIE_SPLIT_STATE_MAX 390 } trie_split_states_e_t; 391 392 typedef enum _trie_split2_states_e_s { 393 TRIE_SPLIT2_STATE_NONE, 394 TRIE_SPLIT2_STATE_PRUNE_NODES, 395 TRIE_SPLIT2_STATE_DONE, 396 TRIE_SPLIT2_STATE_MAX 397 } trie_split2_states_e_t; 398 399 400 #define _MAX_SKIP_LEN_ (31) 401 402 #define SHL(data, shift, max) \ 403 (((shift)>=(max))?0:((data)<<(shift))) 404 405 #define SHR(data, shift, max) \ 406 (((shift)>=(max))?0:((data)>>(shift))) 407 408 #define MASK(len) \ 409 (((len)>=32 || (len)==0)?0xFFFFFFFF:((1<<(len))-1)) 410 411 #define BITMASK(len) \ 412 (((len)>=32)?0xFFFFFFFF:((1<<(len))-1)) 413 414 #define ABS(n) ((((int)(n)) < 0) ? -(n) : (n)) 415 416 #define _NUM_WORD_BITS_ (32) 417 418 /* 419 * bit 0 - 0 420 * bit [1, _MAX_SKIP_LEN] - 1 421 * bit [_MAX_SKIP_LEN+1, 2*_MAX_SKIP_LEN] - 2... 422 */ 423 #define BITS2SKIPOFF(x) (((x) + _MAX_SKIP_LEN_-1) / _MAX_SKIP_LEN_) 424 425 /* (internal) Generic operation macro on bit array _a, with bit _b */ 426 #define _BITOP(_a, _b, _op) \ 427 ((_a) _op (1U << ((_b) % _NUM_WORD_BITS_))) 428 429 /* Specific operations */ 430 #define _BITGET(_a, _b) _BITOP(_a, _b, &) 431 #define _BITSET(_a, _b) _BITOP(_a, _b, |=) 432 #define _BITCLR(_a, _b) _BITOP(_a, _b, &= ~) 433 434 /* get the bit position of the LSB set in bit 0 to bit "msb" of "data" 435 * (max 32 bits), "lsb" is set to -1 if no bit is set in "data". 436 */ 437 #define BITGETLSBSET(data, msb, lsb) \ 438 { \ 439 lsb = 0; \ 440 while ((lsb)<=(msb)) { \ 441 if ((data)&(1<<(lsb))) { \ 442 break; \ 443 } else { (lsb)++;} \ 444 } \ 445 lsb = ((lsb)>(msb))?-1:(lsb); \ 446 } 447 448 extern int _trie_fuse_child(trie_node_t *trie, int bit); 449 450 extern int _print_trie_node(trie_node_t *trie, void *datum); 451 452 extern int _trie_init_propagate_info(unsigned int *pfx, 453 unsigned int len, 454 trie_propagate_cb_f cb, 455 trie_bpm_cb_info_t *cb_info); 456 457 extern int _trie_traverse_propagate_prefix(trie_node_t *trie, 458 trie_propagate_cb_f cb, 459 trie_bpm_cb_info_t *cb_info, 460 unsigned int mask); 461 462 extern int _pvt_trie_traverse_propagate_prefix(trie_node_t *trie, 463 trie_propagate_cb_f cb, 464 trie_bpm_cb_info_t *cb_info); 465 466 #endif /* ALPM_ENABLE */ 467 468 #endif /* _ESW_TRIDENT2_TRIE_H_ */