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