1 /*- 2 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD 3 * 4 * Copyright (c) 2013 EMC Corp. 5 * Copyright (c) 2011 Jeffrey Roberson <jeff@freebsd.org> 6 * Copyright (c) 2008 Mayur Shardul <mayur.shardul@gmail.com> 7 * All rights reserved. 8 * 9 * Redistribution and use in source and binary forms, with or without 10 * modification, are permitted provided that the following conditions 11 * are met: 12 * 1. Redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer. 14 * 2. Redistributions in binary form must reproduce the above copyright 15 * notice, this list of conditions and the following disclaimer in the 16 * documentation and/or other materials provided with the distribution. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 21 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 22 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 23 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 24 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 25 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 26 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 27 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 28 * SUCH DAMAGE. 29 * 30 * $FreeBSD$ 31 */ 32 33 #ifndef _SYS_PCTRIE_H_ 34 #define _SYS_PCTRIE_H_ 35 36 #include <sys/_pctrie.h> 37 38 #ifdef _KERNEL 39 40 #define PCTRIE_DEFINE(name, type, field, allocfn, freefn) \ 41 \ 42 CTASSERT(sizeof(((struct type *)0)->field) == sizeof(uint64_t)); \ 43 /* \ 44 * XXX This assert protects flag bits, it does not enforce natural \ 45 * alignment. 32bit architectures do not naturally align 64bit fields. \ 46 */ \ 47 CTASSERT((__offsetof(struct type, field) & (sizeof(uint32_t) - 1)) == 0); \ 48 \ 49 static __inline struct type * \ 50 name##_PCTRIE_VAL2PTR(uint64_t *val) \ 51 { \ 52 \ 53 if (val == NULL) \ 54 return (NULL); \ 55 return (struct type *) \ 56 ((uintptr_t)val - __offsetof(struct type, field)); \ 57 } \ 58 \ 59 static __inline uint64_t * \ 60 name##_PCTRIE_PTR2VAL(struct type *ptr) \ 61 { \ 62 \ 63 return &ptr->field; \ 64 } \ 65 \ 66 static __inline int \ 67 name##_PCTRIE_INSERT(struct pctrie *ptree, struct type *ptr) \ 68 { \ 69 \ 70 return pctrie_insert(ptree, name##_PCTRIE_PTR2VAL(ptr), \ 71 allocfn); \ 72 } \ 73 \ 74 static __inline struct type * \ 75 name##_PCTRIE_LOOKUP(struct pctrie *ptree, uint64_t key) \ 76 { \ 77 \ 78 return name##_PCTRIE_VAL2PTR(pctrie_lookup(ptree, key)); \ 79 } \ 80 \ 81 static __inline __unused struct type * \ 82 name##_PCTRIE_LOOKUP_LE(struct pctrie *ptree, uint64_t key) \ 83 { \ 84 \ 85 return name##_PCTRIE_VAL2PTR(pctrie_lookup_le(ptree, key)); \ 86 } \ 87 \ 88 static __inline __unused struct type * \ 89 name##_PCTRIE_LOOKUP_GE(struct pctrie *ptree, uint64_t key) \ 90 { \ 91 \ 92 return name##_PCTRIE_VAL2PTR(pctrie_lookup_ge(ptree, key)); \ 93 } \ 94 \ 95 static __inline __unused void \ 96 name##_PCTRIE_RECLAIM(struct pctrie *ptree) \ 97 { \ 98 \ 99 pctrie_reclaim_allnodes(ptree, freefn); \ 100 } \ 101 \ 102 static __inline void \ 103 name##_PCTRIE_REMOVE(struct pctrie *ptree, uint64_t key) \ 104 { \ 105 \ 106 pctrie_remove(ptree, key, freefn); \ 107 } 108 109 typedef void *(*pctrie_alloc_t)(struct pctrie *ptree); 110 typedef void (*pctrie_free_t)(struct pctrie *ptree, void *node); 111 112 int pctrie_insert(struct pctrie *ptree, uint64_t *val, 113 pctrie_alloc_t allocfn); 114 uint64_t *pctrie_lookup(struct pctrie *ptree, uint64_t key); 115 uint64_t *pctrie_lookup_ge(struct pctrie *ptree, uint64_t key); 116 uint64_t *pctrie_lookup_le(struct pctrie *ptree, uint64_t key); 117 void pctrie_reclaim_allnodes(struct pctrie *ptree, 118 pctrie_free_t freefn); 119 void pctrie_remove(struct pctrie *ptree, uint64_t key, 120 pctrie_free_t freefn); 121 size_t pctrie_node_size(void); 122 int pctrie_zone_init(void *mem, int size, int flags); 123 124 static __inline void 125 pctrie_init(struct pctrie *ptree) 126 { 127 128 ptree->pt_root = 0; 129 } 130 131 static __inline bool 132 pctrie_is_empty(struct pctrie *ptree) 133 { 134 135 return (ptree->pt_root == 0); 136 } 137 138 /* 139 * These widths should allow the pointers to a node's children to fit within 140 * a single cache line. The extra levels from a narrow width should not be 141 * a problem thanks to path compression. 142 */ 143 #ifdef __LP64__ 144 #define PCTRIE_WIDTH 4 145 #else 146 #define PCTRIE_WIDTH 3 147 #endif 148 149 #define PCTRIE_COUNT (1 << PCTRIE_WIDTH) 150 151 #endif /* _KERNEL */ 152 #endif /* !_SYS_PCTRIE_H_ */ 153