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