1 /* 2 * Copyright (c) 2023 Institute of Parallel And Distributed Systems (IPADS), Shanghai Jiao Tong University (SJTU) 3 * Licensed under the Mulan PSL v2. 4 * You can use this software according to the terms and conditions of the Mulan PSL v2. 5 * You may obtain a copy of Mulan PSL v2 at: 6 * http://license.coscl.org.cn/MulanPSL2 7 * THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND, EITHER EXPRESS OR 8 * IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT, MERCHANTABILITY OR FIT FOR A PARTICULAR 9 * PURPOSE. 10 * See the Mulan PSL v2 for more details. 11 */ 12 #ifndef COMMON_RADIX_H 13 #define COMMON_RADIX_H 14 15 #include <common/types.h> 16 #include <common/lock.h> 17 #include <common/macro.h> 18 19 /* Each tree level represents RADIX_NODE_BITS bits of the key */ 20 #define RADIX_NODE_BITS (4) 21 #define RADIX_NODE_SIZE (1 << (RADIX_NODE_BITS)) 22 #define RADIX_NODE_MASK (RADIX_NODE_SIZE - 1) 23 #define RADIX_MAX_BITS (64) 24 25 #define RADIX_LEVELS (DIV_ROUND_UP(RADIX_MAX_BITS, RADIX_NODE_BITS)) 26 27 struct radix_node { 28 union { 29 struct radix_node *children[RADIX_NODE_SIZE]; 30 void *values[RADIX_NODE_SIZE]; 31 }; 32 }; 33 struct radix { 34 struct radix_node *root; 35 struct lock radix_lock; 36 void (*value_deleter)(void *); 37 }; 38 39 /* interfaces */ 40 struct radix *new_radix(void); 41 void init_radix(struct radix *radix); 42 int radix_add(struct radix *radix, u64 key, void *value); 43 void *radix_get(struct radix *radix, u64 key); 44 int radix_free(struct radix *radix); 45 int radix_del(struct radix *radix, u64 key); 46 47 void init_radix_w_deleter(struct radix *radix, void (*value_deleter)(void *)); 48 49 #endif /* COMMON_RADIX_H */