Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]
FreeBSD/Linux Kernel Cross Reference
sys/sys/pctrie.h
Version:
- FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
SearchContext: - none - 3 - 10
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 #include <sys/_smr.h> 38 39 #ifdef _KERNEL 40 41 #define PCTRIE_DEFINE_SMR(name, type, field, allocfn, freefn, smr) \ 42 PCTRIE_DEFINE(name, type, field, allocfn, freefn) \ 43 \ 44 static __inline struct type * \ 45 name##_PCTRIE_LOOKUP_UNLOCKED(struct pctrie *ptree, uint64_t key) \ 46 { \ 47 \ 48 return name##_PCTRIE_VAL2PTR(pctrie_lookup_unlocked(ptree, \ 49 key, (smr))); \ 50 } \ 51 52 #define PCTRIE_DEFINE(name, type, field, allocfn, freefn) \ 53 \ 54 CTASSERT(sizeof(((struct type *)0)->field) == sizeof(uint64_t)); \ 55 /* \ 56 * XXX This assert protects flag bits, it does not enforce natural \ 57 * alignment. 32bit architectures do not naturally align 64bit fields. \ 58 */ \ 59 CTASSERT((__offsetof(struct type, field) & (sizeof(uint32_t) - 1)) == 0); \ 60 \ 61 static __inline struct type * \ 62 name##_PCTRIE_VAL2PTR(uint64_t *val) \ 63 { \ 64 \ 65 if (val == NULL) \ 66 return (NULL); \ 67 return (struct type *) \ 68 ((uintptr_t)val - __offsetof(struct type, field)); \ 69 } \ 70 \ 71 static __inline uint64_t * \ 72 name##_PCTRIE_PTR2VAL(struct type *ptr) \ 73 { \ 74 \ 75 return &ptr->field; \ 76 } \ 77 \ 78 static __inline int \ 79 name##_PCTRIE_INSERT(struct pctrie *ptree, struct type *ptr) \ 80 { \ 81 \ 82 return pctrie_insert(ptree, name##_PCTRIE_PTR2VAL(ptr), \ 83 allocfn); \ 84 } \ 85 \ 86 static __inline struct type * \ 87 name##_PCTRIE_LOOKUP(struct pctrie *ptree, uint64_t key) \ 88 { \ 89 \ 90 return name##_PCTRIE_VAL2PTR(pctrie_lookup(ptree, key)); \ 91 } \ 92 \ 93 static __inline __unused struct type * \ 94 name##_PCTRIE_LOOKUP_LE(struct pctrie *ptree, uint64_t key) \ 95 { \ 96 \ 97 return name##_PCTRIE_VAL2PTR(pctrie_lookup_le(ptree, key)); \ 98 } \ 99 \ 100 static __inline __unused struct type * \ 101 name##_PCTRIE_LOOKUP_GE(struct pctrie *ptree, uint64_t key) \ 102 { \ 103 \ 104 return name##_PCTRIE_VAL2PTR(pctrie_lookup_ge(ptree, key)); \ 105 } \ 106 \ 107 static __inline __unused void \ 108 name##_PCTRIE_RECLAIM(struct pctrie *ptree) \ 109 { \ 110 \ 111 pctrie_reclaim_allnodes(ptree, freefn); \ 112 } \ 113 \ 114 static __inline void \ 115 name##_PCTRIE_REMOVE(struct pctrie *ptree, uint64_t key) \ 116 { \ 117 \ 118 pctrie_remove(ptree, key, freefn); \ 119 } 120 121 typedef void *(*pctrie_alloc_t)(struct pctrie *ptree); 122 typedef void (*pctrie_free_t)(struct pctrie *ptree, void *node); 123 124 int pctrie_insert(struct pctrie *ptree, uint64_t *val, 125 pctrie_alloc_t allocfn); 126 uint64_t *pctrie_lookup(struct pctrie *ptree, uint64_t key); 127 uint64_t *pctrie_lookup_ge(struct pctrie *ptree, uint64_t key); 128 uint64_t *pctrie_lookup_le(struct pctrie *ptree, uint64_t key); 129 uint64_t *pctrie_lookup_unlocked(struct pctrie *ptree, uint64_t key, 130 smr_t smr); 131 void pctrie_reclaim_allnodes(struct pctrie *ptree, 132 pctrie_free_t freefn); 133 void pctrie_remove(struct pctrie *ptree, uint64_t key, 134 pctrie_free_t freefn); 135 size_t pctrie_node_size(void); 136 int pctrie_zone_init(void *mem, int size, int flags); 137 138 static __inline void 139 pctrie_init(struct pctrie *ptree) 140 { 141 142 ptree->pt_root = 0; 143 } 144 145 static __inline bool 146 pctrie_is_empty(struct pctrie *ptree) 147 { 148 149 return (ptree->pt_root == 0); 150 } 151 152 /* 153 * These widths should allow the pointers to a node's children to fit within 154 * a single cache line. The extra levels from a narrow width should not be 155 * a problem thanks to path compression. 156 */ 157 #ifdef __LP64__ 158 #define PCTRIE_WIDTH 4 159 #else 160 #define PCTRIE_WIDTH 3 161 #endif 162 163 #define PCTRIE_COUNT (1 << PCTRIE_WIDTH) 164 165 #endif /* _KERNEL */ 166 #endif /* !_SYS_PCTRIE_H_ */
Cache object: 162b105720bc8c37505eeb021d3958c4
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]