]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
1 | #define JEMALLOC_RTREE_C_ |
2 | #include "jemalloc/internal/jemalloc_internal.h" | |
3 | ||
54a0048b SL |
4 | static unsigned |
5 | hmin(unsigned ha, unsigned hb) | |
1a4d82fc | 6 | { |
54a0048b SL |
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; | |
1a4d82fc JJ |
17 | |
18 | assert(bits > 0 && bits <= (sizeof(uintptr_t) << 3)); | |
19 | ||
54a0048b SL |
20 | bits_in_leaf = (bits % RTREE_BITS_PER_LEVEL) == 0 ? RTREE_BITS_PER_LEVEL |
21 | : (bits % RTREE_BITS_PER_LEVEL); | |
1a4d82fc | 22 | if (bits > bits_in_leaf) { |
54a0048b SL |
23 | height = 1 + (bits - bits_in_leaf) / RTREE_BITS_PER_LEVEL; |
24 | if ((height-1) * RTREE_BITS_PER_LEVEL + bits_in_leaf != bits) | |
1a4d82fc | 25 | height++; |
54a0048b | 26 | } else |
1a4d82fc | 27 | height = 1; |
54a0048b SL |
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; | |
1a4d82fc | 45 | } |
54a0048b | 46 | /* Leaf level. */ |
7453a54e | 47 | if (height > 1) { |
54a0048b SL |
48 | rtree->levels[height-1].subtree = NULL; |
49 | rtree->levels[height-1].bits = bits_in_leaf; | |
50 | rtree->levels[height-1].cumbits = bits; | |
51 | } | |
1a4d82fc | 52 | |
54a0048b SL |
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); | |
1a4d82fc | 57 | } |
1a4d82fc | 58 | |
54a0048b | 59 | return (false); |
1a4d82fc JJ |
60 | } |
61 | ||
62 | static void | |
54a0048b | 63 | rtree_delete_subtree(rtree_t *rtree, rtree_node_elm_t *node, unsigned level) |
1a4d82fc JJ |
64 | { |
65 | ||
54a0048b | 66 | if (level + 1 < rtree->height) { |
1a4d82fc JJ |
67 | size_t nchildren, i; |
68 | ||
54a0048b | 69 | nchildren = ZU(1) << rtree->levels[level].bits; |
1a4d82fc | 70 | for (i = 0; i < nchildren; i++) { |
54a0048b | 71 | rtree_node_elm_t *child = node[i].child; |
1a4d82fc JJ |
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 | { | |
54a0048b | 82 | unsigned i; |
1a4d82fc | 83 | |
54a0048b SL |
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 | } | |
1a4d82fc JJ |
89 | } |
90 | ||
54a0048b SL |
91 | static rtree_node_elm_t * |
92 | rtree_node_init(rtree_t *rtree, unsigned level, rtree_node_elm_t **elmp) | |
1a4d82fc | 93 | { |
54a0048b SL |
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 | } | |
1a4d82fc | 111 | |
54a0048b | 112 | return (node); |
1a4d82fc JJ |
113 | } |
114 | ||
54a0048b SL |
115 | rtree_node_elm_t * |
116 | rtree_subtree_read_hard(rtree_t *rtree, unsigned level) | |
1a4d82fc JJ |
117 | { |
118 | ||
54a0048b | 119 | return (rtree_node_init(rtree, level, &rtree->levels[level].subtree)); |
1a4d82fc JJ |
120 | } |
121 | ||
54a0048b SL |
122 | rtree_node_elm_t * |
123 | rtree_child_read_hard(rtree_t *rtree, rtree_node_elm_t *elm, unsigned level) | |
1a4d82fc JJ |
124 | { |
125 | ||
54a0048b | 126 | return (rtree_node_init(rtree, level, &elm->child)); |
1a4d82fc | 127 | } |