1 /******************************************************************************
4 * Lock-free binary search trees (BSTs), based on MCAS.
5 * Uses a threaded representation to synchronise searches with deletions.
7 * Copyright (c) 2002-2003, K A Fraser
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are
13 * Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above
16 * copyright notice, this list of conditions and the following
17 * disclaimer in the documentation and/or other materials provided
18 * with the distribution. Neither the name of the Keir Fraser
19 * nor the names of its contributors may be used to endorse or
20 * promote products derived from this software without specific
21 * prior written permission.
23 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
26 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
27 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
28 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
29 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
30 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
31 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
32 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
33 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36 #define __SET_IMPLEMENTATION__
41 #include "portable_defns.h"
45 /* Allow MCAS marks to be detected using a single bitop (see IS_MCAS_OWNED). */
46 #define MARK_IN_PROGRESS 2
47 #define MARK_PTR_TO_CD 3
50 #define MARK_GARBAGE 4
52 #define THREAD(_p) ((node_t *)((int_addr_t)(_p)|(MARK_THREAD)))
53 #define GARBAGE(_p) ((node_t *)((int_addr_t)(_p)|(MARK_GARBAGE)))
54 #define UNTHREAD(_p) ((node_t *)((int_addr_t)(_p)&~MARK_THREAD))
55 #define UNGARBAGE(_p) ((node_t *)((int_addr_t)(_p)&~MARK_GARBAGE))
56 /* Following only matches 2 and 3 (mod 4). Those happen to be MCAS marks :) */
57 #define IS_MCAS_OWNED(_p) ((int)((int_addr_t)(_p)&2))
58 /* Matches 1 and 3 (mod 4). So only use if the ref is *not* owned by MCAS!! */
59 #define IS_THREAD(_p) ((int)((int_addr_t)(_p)&MARK_THREAD))
60 /* Only use if the ref is *not* owned by MCAS (which may use bit 2)!! */
61 #define IS_GARBAGE(_p) ((int)((int_addr_t)(_p)&MARK_GARBAGE))
65 typedef struct node_st node_t;
66 typedef struct set_st set_t;
83 #define READ_LINK(_var, _link) \
86 if ( !IS_MCAS_OWNED(_var) ) break; \
87 mcas_fixup((void **)&(_link), (_var)); \
90 #define WEAK_READ_LINK(_var, _link) \
92 READ_LINK(_var, _link); \
93 (_var) = UNGARBAGE(_var); \
96 #define STRONG_READ_LINK(_var, _link) \
98 READ_LINK(_var, _link); \
99 if ( IS_GARBAGE(_var) ) goto retry; \
102 #define PROCESS_VAL(_v,_pv) \
104 while ( IS_MCAS_OWNED(_v) ) \
106 mcas_fixup((void **)(_pv), (_v)); \
113 * Search for node with key == k. Return NULL if none such, else ptr to node.
114 * @ppn is filled in with parent node, or closest leaf if no match.
115 * p and n will both be unmarked and adjacent on return.
117 static node_t *search(set_t *s, setkey_t k, node_t **ppn)
123 WEAK_READ_LINK(n, p->r);
125 while ( !IS_THREAD(n) )
128 WEAK_READ_LINK(c, n->l);
129 assert(UNTHREAD(c)->k < n->k);
130 } else if ( k > n->k ) {
131 WEAK_READ_LINK(c, n->r);
132 assert(UNTHREAD(c)->k > n->k);
133 } else /* k == n->k */
139 /* Follow final thread, just in case. */
141 if ( k == c->k ) goto followed_thread;
148 if ( ppn ) { RMB(); goto retry; }
153 set_t *set_alloc(void)
157 static int mcas_inited = 0;
158 if ( !CASIO(&mcas_inited, 0, 1) )
160 if ( (sizeof(node_t) % 8) != 0 )
162 fprintf(stderr, "FATAL: node_t must be multiple of 8 bytes\n");
168 s = malloc(sizeof(*s));
169 s->root.k = SENTINEL_KEYMIN;
171 s->root.l = THREAD(&s->root);
172 s->root.r = THREAD(&s->sentinel);
174 s->sentinel.k = SENTINEL_KEYMAX;
180 setval_t set_update(set_t *s, setkey_t k, setval_t v, int overwrite)
183 node_t *p, *n, *new = NULL, **ppc;
186 k = CALLER_TO_INTERNAL_KEY(k);
188 ptst = critical_enter();
194 n = search(s, k, &p);
197 /* Already a @k node in the set: update its mapping. */
201 PROCESS_VAL(ov, &n->v);
202 if ( ov == NULL ) goto retry;
204 while ( overwrite && ((nov = CASPO(&n->v, ov, v)) != ov) );
211 new = gc_alloc(ptst, gc_id);
218 /* Ensure we insert in the correct interval. */
219 if ( UNTHREAD(n)->k < k ) goto retry;
226 if ( UNTHREAD(n)->k > k ) goto retry;
234 while ( CASPO(ppc, n, new) != n );
239 if ( new ) gc_free(ptst, new, gc_id);
245 #define FIND_HELPER(_d1, _d2, _n, _ap, _a) \
250 WEAK_READ_LINK(ac, (_a)->_d1); \
251 while ( !IS_THREAD(ac) ) \
255 WEAK_READ_LINK(ac, (_a)->_d2); \
261 * Order of first two cases does matter! If @n is the left-link of @p, then
262 * we use DELETE_HELPER(l, r). What matters is what we do when @n is a leaf.
263 * In this case we end up choosing n->l to propagate to p->l -- this
264 * happens to be the correct choice :-)
266 * NB. Note symmetric deletion cases dependent on parameter @dir. We
267 * could simplify the algorithm by always following one direction. In fact,
268 * that is slightly worse, or much worse, depending on the chosen case
269 * (hint: works best with dir hardwired to zero :-)....
272 #define DELETE_HELPER(_d1, _d2) \
273 FIND_HELPER(_d1, _d2, n, pal, al); \
274 FIND_HELPER(_d2, _d1, n, par, ar); \
275 if ( IS_THREAD(n ## _d2) ) \
277 if ( IS_THREAD(n ## _d1) ) \
280 (void **)&n->v, v, NULL, \
281 (void **)&n->l, nl, GARBAGE(nl), \
282 (void **)&n->r, nr, GARBAGE(nr), \
283 (void **)p_pc, n, n ## _d1); \
287 if ( al == n ) goto retry; \
289 (void **)&n->v, v, NULL, \
290 (void **)&n->l, nl, GARBAGE(nl), \
291 (void **)&n->r, nr, GARBAGE(nr), \
292 (void **)p_pc, n, n ## _d1, \
293 (void **)&al->_d2, THREAD(n), n ## _d2); \
296 else if ( IS_THREAD(n ## _d1) ) \
298 if ( ar == n ) goto retry; \
300 (void **)&n->v, v, NULL, \
301 (void **)&n->l, nl, GARBAGE(nl), \
302 (void **)&n->r, nr, GARBAGE(nr), \
303 (void **)p_pc, n, n ## _d2, \
304 (void **)&ar->_d1, THREAD(n), n ## _d1); \
308 if ( (al == n) || (ar == n) ) goto retry; \
312 (void **)&n->v, v, NULL, \
313 (void **)&ar->_d1, THREAD(n), n ## _d1, \
314 (void **)&al->_d2, THREAD(n), THREAD(ar), \
315 (void **)&n->l, nl, GARBAGE(nl), \
316 (void **)&n->r, nr, GARBAGE(nr), \
317 (void **)p_pc, n, ar); \
321 STRONG_READ_LINK(ac, ar->_d2); \
323 (void **)&n->v, v, NULL, \
324 (void **)&par->_d1, ar, \
325 (IS_THREAD(ac) ? THREAD(ar) : ac), \
326 (void **)&ar->_d2, ac, n ## _d2, \
327 (void **)&ar->_d1, THREAD(n), n ## _d1, \
328 (void **)&al->_d2, THREAD(n), THREAD(ar), \
329 (void **)&n->l, nl, GARBAGE(nl), \
330 (void **)&n->r, nr, GARBAGE(nr), \
331 (void **)p_pc, n, ar); \
336 if ( (al == n) || (ar == n) ) goto retry; \
340 (void **)&n->v, v, NULL, \
341 (void **)&al->_d2, THREAD(n), n ## _d2, \
342 (void **)&ar->_d1, THREAD(n), THREAD(al), \
343 (void **)&n->l, nl, GARBAGE(nl), \
344 (void **)&n->r, nr, GARBAGE(nr), \
345 (void **)p_pc, n, al); \
349 STRONG_READ_LINK(ac, al->_d1); \
351 (void **)&n->v, v, NULL, \
352 (void **)&pal->_d2, al, \
353 (IS_THREAD(ac) ? THREAD(al) : ac), \
354 (void **)&al->_d1, ac, n ## _d1, \
355 (void **)&al->_d2, THREAD(n), n ## _d2, \
356 (void **)&ar->_d1, THREAD(n), THREAD(al), \
357 (void **)&n->l, nl, GARBAGE(nl), \
358 (void **)&n->r, nr, GARBAGE(nr), \
359 (void **)p_pc, n, al); \
364 /* @k: key of node to be deleted */
365 setval_t set_remove(set_t *s, setkey_t k)
367 node_t *p, *n, *nl, *nr, *al, *ar, *pal, *par, *ac, **p_pc;
372 k = CALLER_TO_INTERNAL_KEY(k);
374 ptst = critical_enter();
382 n = search(s, k, &p);
383 if ( IS_THREAD(n) ) goto out;
385 /* Already deleted? */
387 PROCESS_VAL(v, &n->v);
388 if ( v == NULL ) goto out;
390 STRONG_READ_LINK(nl, n->l);
391 STRONG_READ_LINK(nr, n->r);
392 p_pc = (p->k > n->k) ? &p->l : &p->r;
396 /* @n is leftwards link from @p. */
401 /* @n is rightwards link from @p. */
406 gc_free(ptst, n, gc_id);
414 setval_t set_lookup(set_t *s, setkey_t k)
420 k = CALLER_TO_INTERNAL_KEY(k);
422 ptst = critical_enter();
424 n = search(s, k, NULL);
425 v = (!IS_THREAD(n)) ? n->v : NULL;
426 PROCESS_VAL(v, &n->v);
433 void _init_set_subsystem(void)
435 gc_id = gc_add_allocator(sizeof(node_t));