]>
Commit | Line | Data |
---|---|---|
1 | #define JEMALLOC_RTREE_C_ | |
2 | #include "jemalloc/internal/jemalloc_internal.h" | |
3 | ||
4 | static unsigned | |
5 | hmin(unsigned ha, unsigned hb) | |
6 | { | |
7 | ||
8 | return (ha < hb ? ha : hb); | |
9 | } | |
10 | ||
11 | /* Only the most significant bits of keys passed to rtree_[gs]et() are used. */ | |
12 | bool | |
13 | rtree_new(rtree_t *rtree, unsigned bits, rtree_node_alloc_t *alloc, | |
14 | rtree_node_dalloc_t *dalloc) | |
15 | { | |
16 | unsigned bits_in_leaf, height, i; | |
17 | ||
18 | assert(bits > 0 && bits <= (sizeof(uintptr_t) << 3)); | |
19 | ||
20 | bits_in_leaf = (bits % RTREE_BITS_PER_LEVEL) == 0 ? RTREE_BITS_PER_LEVEL | |
21 | : (bits % RTREE_BITS_PER_LEVEL); | |
22 | if (bits > bits_in_leaf) { | |
23 | height = 1 + (bits - bits_in_leaf) / RTREE_BITS_PER_LEVEL; | |
24 | if ((height-1) * RTREE_BITS_PER_LEVEL + bits_in_leaf != bits) | |
25 | height++; | |
26 | } else | |
27 | height = 1; | |
28 | assert((height-1) * RTREE_BITS_PER_LEVEL + bits_in_leaf == bits); | |
29 | ||
30 | rtree->alloc = alloc; | |
31 | rtree->dalloc = dalloc; | |
32 | rtree->height = height; | |
33 | ||
34 | /* Root level. */ | |
35 | rtree->levels[0].subtree = NULL; | |
36 | rtree->levels[0].bits = (height > 1) ? RTREE_BITS_PER_LEVEL : | |
37 | bits_in_leaf; | |
38 | rtree->levels[0].cumbits = rtree->levels[0].bits; | |
39 | /* Interior levels. */ | |
40 | for (i = 1; i < height-1; i++) { | |
41 | rtree->levels[i].subtree = NULL; | |
42 | rtree->levels[i].bits = RTREE_BITS_PER_LEVEL; | |
43 | rtree->levels[i].cumbits = rtree->levels[i-1].cumbits + | |
44 | RTREE_BITS_PER_LEVEL; | |
45 | } | |
46 | /* Leaf level. */ | |
47 | if (height > 1) { | |
48 | rtree->levels[height-1].subtree = NULL; | |
49 | rtree->levels[height-1].bits = bits_in_leaf; | |
50 | rtree->levels[height-1].cumbits = bits; | |
51 | } | |
52 | ||
53 | /* Compute lookup table to be used by rtree_start_level(). */ | |
54 | for (i = 0; i < RTREE_HEIGHT_MAX; i++) { | |
55 | rtree->start_level[i] = hmin(RTREE_HEIGHT_MAX - 1 - i, height - | |
56 | 1); | |
57 | } | |
58 | ||
59 | return (false); | |
60 | } | |
61 | ||
62 | static void | |
63 | rtree_delete_subtree(rtree_t *rtree, rtree_node_elm_t *node, unsigned level) | |
64 | { | |
65 | ||
66 | if (level + 1 < rtree->height) { | |
67 | size_t nchildren, i; | |
68 | ||
69 | nchildren = ZU(1) << rtree->levels[level].bits; | |
70 | for (i = 0; i < nchildren; i++) { | |
71 | rtree_node_elm_t *child = node[i].child; | |
72 | if (child != NULL) | |
73 | rtree_delete_subtree(rtree, child, level + 1); | |
74 | } | |
75 | } | |
76 | rtree->dalloc(node); | |
77 | } | |
78 | ||
79 | void | |
80 | rtree_delete(rtree_t *rtree) | |
81 | { | |
82 | unsigned i; | |
83 | ||
84 | for (i = 0; i < rtree->height; i++) { | |
85 | rtree_node_elm_t *subtree = rtree->levels[i].subtree; | |
86 | if (subtree != NULL) | |
87 | rtree_delete_subtree(rtree, subtree, i); | |
88 | } | |
89 | } | |
90 | ||
91 | static rtree_node_elm_t * | |
92 | rtree_node_init(rtree_t *rtree, unsigned level, rtree_node_elm_t **elmp) | |
93 | { | |
94 | rtree_node_elm_t *node; | |
95 | ||
96 | if (atomic_cas_p((void **)elmp, NULL, RTREE_NODE_INITIALIZING)) { | |
97 | /* | |
98 | * Another thread is already in the process of initializing. | |
99 | * Spin-wait until initialization is complete. | |
100 | */ | |
101 | do { | |
102 | CPU_SPINWAIT; | |
103 | node = atomic_read_p((void **)elmp); | |
104 | } while (node == RTREE_NODE_INITIALIZING); | |
105 | } else { | |
106 | node = rtree->alloc(ZU(1) << rtree->levels[level].bits); | |
107 | if (node == NULL) | |
108 | return (NULL); | |
109 | atomic_write_p((void **)elmp, node); | |
110 | } | |
111 | ||
112 | return (node); | |
113 | } | |
114 | ||
115 | rtree_node_elm_t * | |
116 | rtree_subtree_read_hard(rtree_t *rtree, unsigned level) | |
117 | { | |
118 | ||
119 | return (rtree_node_init(rtree, level, &rtree->levels[level].subtree)); | |
120 | } | |
121 | ||
122 | rtree_node_elm_t * | |
123 | rtree_child_read_hard(rtree_t *rtree, rtree_node_elm_t *elm, unsigned level) | |
124 | { | |
125 | ||
126 | return (rtree_node_init(rtree, level, &elm->child)); | |
127 | } |