FreeBSD/Linux Kernel Cross Reference
sys/sys/pctrie.h
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: releng/10.4/sys/sys/pctrie.h 260266 2014-01-04 17:36:13Z dim $
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 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 #endif /* _KERNEL */
123 #endif /* !_SYS_PCTRIE_H_ */
Cache object: 3999d27bd675c2c4a5c098f71b943be4
|