1 /******************************************************************************
4 * Lock-based binary search trees (BSTs), based on:
5 * H. T. Kung and Philip L. Lehman.
6 * "Concurrent manipulation of binary search trees".
7 * ACM Tranactions on Database Systems, Vol. 5, No. 3, September 1980.
9 * Copyright (c) 2002-2003, K A Fraser
11 Redistribution and use in source and binary forms, with or without
12 modification, are permitted provided that the following conditions are
15 * Redistributions of source code must retain the above copyright
16 * notice, this list of conditions and the following disclaimer.
17 * Redistributions in binary form must reproduce the above
18 * copyright notice, this list of conditions and the following
19 * disclaimer in the documentation and/or other materials provided
20 * with the distribution. Neither the name of the Keir Fraser
21 * nor the names of its contributors may be used to endorse or
22 * promote products derived from this software without specific
23 * prior written permission.
25 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
26 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
27 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
28 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
29 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
30 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
31 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
32 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
33 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
34 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
35 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
38 #define __SET_IMPLEMENTATION__
47 #include <sys/types.h>
52 #include "portable_defns.h"
56 #define IS_BLUE(_n) ((int)(_n)->v & 1)
57 #define MK_BLUE(_n) ((_n)->v = (setval_t)((unsigned long)(_n)->v | 1))
59 #define GET_VALUE(_n) ((setval_t)((unsigned long)(_n)->v & ~1UL))
63 #define FOLLOW(_n, _d) ((_d) ? (_n)->r : (_n)->l)
64 #define UPDATE(_n, _d, _x) ((_d) ? ((_n)->r = (_x)) : ((_n)->l = (_x)))
65 #define FLIP(_d) ((_d)^1)
67 typedef struct node_st node_t;
68 typedef struct set_st set_t;
85 #define LOCK(_n, _pqn) mcs_lock(&(_n)->lock, (_pqn))
86 #define UNLOCK(_n, _pqn) mcs_unlock(&(_n)->lock, (_pqn))
89 static node_t *weak_find(node_t *n, setkey_t k)
104 static node_t *find(node_t *n, setkey_t k, qnode_t *qn, int *pdir)
125 while ( (s != NULL) && (s->k != k) );
134 if ( s != FOLLOW(f, dir) )
145 static node_t *rotate(ptst_t *ptst, node_t *a, int dir1,
146 int dir2, node_t **pc, qnode_t *pqn[])
148 node_t *b = FOLLOW(a, dir1), *c = FOLLOW(b, dir2);
149 node_t *bp = gc_alloc(ptst, gc_id), *cp = gc_alloc(ptst, gc_id);
154 memcpy(bp, b, sizeof(*b));
155 memcpy(cp, c, sizeof(*c));
167 UPDATE(cp, FLIP(dir2), bp);
168 UPDATE(bp, dir2, FOLLOW(c, FLIP(dir2)));
176 gc_free(ptst, b, gc_id);
177 gc_free(ptst, c, gc_id);
188 static void _remove(ptst_t *ptst, node_t *a, int dir1, int dir2, qnode_t **pqn)
190 node_t *b = FOLLOW(a, dir1), *c = FOLLOW(b, dir2);
191 assert(FOLLOW(b, FLIP(dir2)) == NULL);
195 UPDATE(b, FLIP(dir2), c);
198 gc_free(ptst, b, gc_id);
204 static void delete_by_rotation(ptst_t *ptst, node_t *f, int dir,
205 qnode_t *pqn[], int lock_idx)
207 node_t *g, *h, *s = FOLLOW(f, dir);
211 UNLOCK(f, pqn[lock_idx+0]);
212 UNLOCK(s, pqn[lock_idx+1]);
217 _remove(ptst, f, dir, RIGHT, pqn+lock_idx);
218 else if ( s->r == NULL )
219 _remove(ptst, f, dir, LEFT, pqn+lock_idx);
222 g = rotate(ptst, f, dir, LEFT, &h, pqn+lock_idx);
226 assert(h->v == NULL);
227 _remove(ptst, g, RIGHT, RIGHT, pqn+lock_idx);
231 delete_by_rotation(ptst, g, RIGHT, pqn, lock_idx);
233 if ( (g != FOLLOW(f, dir)) || IS_BLUE(f) )
241 * XXX Check that there is a node H to be rotated up.
242 * This is missing from the original paper, and must surely
243 * be a bug (we lost all locks at previous delete_by_rotation,
244 * so we can't know the existence of G's children).
248 g = rotate(ptst, f, dir, RIGHT, &h, pqn);
263 set_t *set_alloc(void)
267 s = malloc(sizeof(*s));
268 mcs_init(&s->root.lock);
269 s->root.k = SENTINEL_KEYMIN;
270 s->root.v = (setval_t)(~1UL); /* dummy root node is white. */
278 setval_t set_update(set_t *s, setkey_t k, setval_t v, int overwrite)
286 k = CALLER_TO_INTERNAL_KEY(k);
288 ptst = critical_enter();
291 f = find(&s->root, k, &f_qn, &dir);
293 if ( (w = FOLLOW(f, dir)) != NULL )
295 /* Protected by parent lock. */
298 if ( overwrite || (ov == NULL) ) w->v = v;
302 w = gc_alloc(ptst, gc_id);
319 setval_t set_remove(set_t *s, setkey_t k)
322 qnode_t qn[4], *pqn[] = { qn+0, qn+1, qn+2, qn+3, qn+0, qn+1 };
327 k = CALLER_TO_INTERNAL_KEY(k);
329 ptst = critical_enter();
331 f = find(&s->root, k, pqn[0], &dir);
332 if ( (w = FOLLOW(f, dir)) != NULL )
338 delete_by_rotation(ptst, f, dir, pqn, 0);
351 setval_t set_lookup(set_t *s, setkey_t k)
357 k = CALLER_TO_INTERNAL_KEY(k);
359 ptst = critical_enter();
361 n = weak_find(&s->root, k);
362 if ( n != NULL ) v = GET_VALUE(n);
369 void _init_set_subsystem(void)
371 gc_id = gc_add_allocator(sizeof(node_t));