Changeset View
Changeset View
Standalone View
Standalone View
sys/sys/tree.h
| Show First 20 Lines • Show All 328 Lines • ▼ Show 20 Lines | |||||
| * always zero, this implementation sets those bits to indicate | * always zero, this implementation sets those bits to indicate | ||||
| * that the left or right child of the tree node is "red". | * that the left or right child of the tree node is "red". | ||||
| */ | */ | ||||
| #define _RB_LINK(elm, dir, field) (elm)->field.rbe_link[dir] | #define _RB_LINK(elm, dir, field) (elm)->field.rbe_link[dir] | ||||
| #define _RB_UP(elm, field) _RB_LINK(elm, 0, field) | #define _RB_UP(elm, field) _RB_LINK(elm, 0, field) | ||||
| #define _RB_L ((__uintptr_t)1) | #define _RB_L ((__uintptr_t)1) | ||||
| #define _RB_R ((__uintptr_t)2) | #define _RB_R ((__uintptr_t)2) | ||||
| #define _RB_LR ((__uintptr_t)3) | #define _RB_LR ((__uintptr_t)3) | ||||
| #define _RB_BITS(elm) (*(__uintptr_t *)&elm) | #define _RB_BITS(elm) ((__uintptr_t)elm) | ||||
| #define _RB_BITSUP(elm, field) _RB_BITS(_RB_UP(elm, field)) | #define _RB_BITSUP(elm, field) _RB_BITS(_RB_UP(elm, field)) | ||||
| #define _RB_PTR(elm) (__typeof(elm)) \ | #define _RB_PTR_OP(elm, op, dir) ((__typeof(elm)) \ | ||||
| ((__uintptr_t)elm & ~_RB_LR) | ((__uintptr_t)(elm) op (dir))) | ||||
| #define _RB_PTR(elm) _RB_PTR_OP((elm), &, ~_RB_LR) | |||||
| #define _RB_MOD_OR(elm, dir) ((elm) = _RB_PTR_OP((elm), |, (dir))) | |||||
dougm: The names _RB_XOR and _RB_OR don't suggest that the macros have side effects. I suggest either… | |||||
| #define _RB_MOD_XOR(elm, dir) ((elm) = _RB_PTR_OP((elm), ^, (dir))) | |||||
| #define _RB_UPMOD_OR(elm, field, dir) _RB_MOD_OR(_RB_UP((elm), field), (dir)) | |||||
Done Inline ActionsI'm not sure that these two macros improve the clarity of the code. _RB_MOD_XOR(_RB_UP(parent, field), elmdir) is pretty clear. dougm: I'm not sure that these two macros improve the clarity of the code.
_RB_MOD_XOR(_RB_UP(parent… | |||||
Done Inline ActionsUpdated the patch to remove the UPMOD macros. A slight downside is that this spelling is a little longer, which results in several lines now needing to be continued. rlibby: Updated the patch to remove the UPMOD macros. A slight downside is that this spelling is a… | |||||
| #define _RB_UPMOD_XOR(elm, field, dir) _RB_MOD_XOR( \ | |||||
| _RB_UP((elm), field), (dir)) | |||||
| #define RB_PARENT(elm, field) _RB_PTR(_RB_UP(elm, field)) | #define RB_PARENT(elm, field) _RB_PTR(_RB_UP(elm, field)) | ||||
| #define RB_LEFT(elm, field) _RB_LINK(elm, _RB_L, field) | #define RB_LEFT(elm, field) _RB_LINK(elm, _RB_L, field) | ||||
| #define RB_RIGHT(elm, field) _RB_LINK(elm, _RB_R, field) | #define RB_RIGHT(elm, field) _RB_LINK(elm, _RB_R, field) | ||||
| #define RB_ROOT(head) (head)->rbh_root | #define RB_ROOT(head) (head)->rbh_root | ||||
| #define RB_EMPTY(head) (RB_ROOT(head) == NULL) | #define RB_EMPTY(head) (RB_ROOT(head) == NULL) | ||||
| #define RB_SET_PARENT(dst, src, field) do { \ | #define RB_SET_PARENT(dst, src, field) do { \ | ||||
| _RB_BITSUP(dst, field) = (__uintptr_t)src | \ | _RB_UP(dst, field) = (__typeof(src))((__uintptr_t)src | \ | ||||
| (_RB_BITSUP(dst, field) & _RB_LR); \ | (_RB_BITSUP(dst, field) & _RB_LR)); \ | ||||
| } while (/*CONSTCOND*/ 0) | } while (/*CONSTCOND*/ 0) | ||||
| #define RB_SET(elm, parent, field) do { \ | #define RB_SET(elm, parent, field) do { \ | ||||
| _RB_UP(elm, field) = parent; \ | _RB_UP(elm, field) = parent; \ | ||||
| RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ | RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ | ||||
| } while (/*CONSTCOND*/ 0) | } while (/*CONSTCOND*/ 0) | ||||
| /* | /* | ||||
| ▲ Show 20 Lines • Show All 182 Lines • ▼ Show 20 Lines | name##_RB_INSERT_COLOR(struct name *head, \ | ||||
| __uintptr_t elmdir, sibdir; \ | __uintptr_t elmdir, sibdir; \ | ||||
| \ | \ | ||||
| do { \ | do { \ | ||||
| /* the rank of the tree rooted at elm grew */ \ | /* the rank of the tree rooted at elm grew */ \ | ||||
| gpar = _RB_UP(parent, field); \ | gpar = _RB_UP(parent, field); \ | ||||
| elmdir = RB_RIGHT(parent, field) == elm ? _RB_R : _RB_L; \ | elmdir = RB_RIGHT(parent, field) == elm ? _RB_R : _RB_L; \ | ||||
| if (_RB_BITS(gpar) & elmdir) { \ | if (_RB_BITS(gpar) & elmdir) { \ | ||||
| /* shorten the parent-elm edge to rebalance */ \ | /* shorten the parent-elm edge to rebalance */ \ | ||||
| _RB_BITSUP(parent, field) ^= elmdir; \ | _RB_UPMOD_XOR(parent, field, elmdir); \ | ||||
| return (NULL); \ | return (NULL); \ | ||||
| } \ | } \ | ||||
| sibdir = elmdir ^ _RB_LR; \ | sibdir = elmdir ^ _RB_LR; \ | ||||
| /* the other edge must change length */ \ | /* the other edge must change length */ \ | ||||
| _RB_BITSUP(parent, field) ^= sibdir; \ | _RB_UPMOD_XOR(parent, field, sibdir); \ | ||||
| if ((_RB_BITS(gpar) & _RB_LR) == 0) { \ | if ((_RB_BITS(gpar) & _RB_LR) == 0) { \ | ||||
| /* both edges now short, retry from parent */ \ | /* both edges now short, retry from parent */ \ | ||||
| child = elm; \ | child = elm; \ | ||||
| elm = parent; \ | elm = parent; \ | ||||
| continue; \ | continue; \ | ||||
| } \ | } \ | ||||
| _RB_UP(parent, field) = gpar = _RB_PTR(gpar); \ | _RB_UP(parent, field) = gpar = _RB_PTR(gpar); \ | ||||
| if (_RB_BITSUP(elm, field) & elmdir) { \ | if (_RB_BITSUP(elm, field) & elmdir) { \ | ||||
| Show All 15 Lines | if (_RB_BITSUP(elm, field) & elmdir) { \ | ||||
| * / / \ elm \ \ | * / / \ elm \ \ | ||||
| * w / \ / \ y \ | * w / \ / \ y \ | ||||
| * x y w \ \ | * x y w \ \ | ||||
| * x \ | * x \ | ||||
| */ \ | */ \ | ||||
| RB_ROTATE(elm, child, elmdir, field); \ | RB_ROTATE(elm, child, elmdir, field); \ | ||||
| child_up = _RB_UP(child, field); \ | child_up = _RB_UP(child, field); \ | ||||
| if (_RB_BITS(child_up) & sibdir) \ | if (_RB_BITS(child_up) & sibdir) \ | ||||
| _RB_BITSUP(parent, field) ^= elmdir; \ | _RB_UPMOD_XOR(parent, field, elmdir); \ | ||||
| if (_RB_BITS(child_up) & elmdir) \ | if (_RB_BITS(child_up) & elmdir) \ | ||||
| _RB_BITSUP(elm, field) ^= _RB_LR; \ | _RB_UPMOD_XOR(elm, field, _RB_LR); \ | ||||
| else \ | else \ | ||||
| _RB_BITSUP(elm, field) ^= elmdir; \ | _RB_UPMOD_XOR(elm, field, elmdir); \ | ||||
| /* if child is a leaf, don't augment elm, \ | /* if child is a leaf, don't augment elm, \ | ||||
| * since it is restored to be a leaf again. */ \ | * since it is restored to be a leaf again. */ \ | ||||
| if ((_RB_BITS(child_up) & _RB_LR) == 0) \ | if ((_RB_BITS(child_up) & _RB_LR) == 0) \ | ||||
| elm = child; \ | elm = child; \ | ||||
| } else \ | } else \ | ||||
| child = elm; \ | child = elm; \ | ||||
| \ | \ | ||||
| /* \ | /* \ | ||||
| ▲ Show 20 Lines • Show All 52 Lines • ▼ Show 20 Lines | if (RB_RIGHT(parent, field) == elm && \ | ||||
| elm = parent; \ | elm = parent; \ | ||||
| if ((parent = _RB_UP(elm, field)) == NULL) \ | if ((parent = _RB_UP(elm, field)) == NULL) \ | ||||
| return (NULL); \ | return (NULL); \ | ||||
| } \ | } \ | ||||
| do { \ | do { \ | ||||
| /* the rank of the tree rooted at elm shrank */ \ | /* the rank of the tree rooted at elm shrank */ \ | ||||
| gpar = _RB_UP(parent, field); \ | gpar = _RB_UP(parent, field); \ | ||||
| elmdir = RB_RIGHT(parent, field) == elm ? _RB_R : _RB_L; \ | elmdir = RB_RIGHT(parent, field) == elm ? _RB_R : _RB_L; \ | ||||
| _RB_BITS(gpar) ^= elmdir; \ | _RB_MOD_XOR(gpar, elmdir); \ | ||||
| if (_RB_BITS(gpar) & elmdir) { \ | if (_RB_BITS(gpar) & elmdir) { \ | ||||
| /* lengthen the parent-elm edge to rebalance */ \ | /* lengthen the parent-elm edge to rebalance */ \ | ||||
| _RB_UP(parent, field) = gpar; \ | _RB_UP(parent, field) = gpar; \ | ||||
| return (NULL); \ | return (NULL); \ | ||||
| } \ | } \ | ||||
| if (_RB_BITS(gpar) & _RB_LR) { \ | if (_RB_BITS(gpar) & _RB_LR) { \ | ||||
| /* shorten other edge, retry from parent */ \ | /* shorten other edge, retry from parent */ \ | ||||
| _RB_BITS(gpar) ^= _RB_LR; \ | _RB_MOD_XOR(gpar, _RB_LR); \ | ||||
| _RB_UP(parent, field) = gpar; \ | _RB_UP(parent, field) = gpar; \ | ||||
| gpar = _RB_PTR(gpar); \ | gpar = _RB_PTR(gpar); \ | ||||
| continue; \ | continue; \ | ||||
| } \ | } \ | ||||
| sibdir = elmdir ^ _RB_LR; \ | sibdir = elmdir ^ _RB_LR; \ | ||||
| sib = _RB_LINK(parent, sibdir, field); \ | sib = _RB_LINK(parent, sibdir, field); \ | ||||
| up = _RB_UP(sib, field); \ | up = _RB_UP(sib, field); \ | ||||
| _RB_BITS(up) ^= _RB_LR; \ | _RB_MOD_XOR(up, _RB_LR); \ | ||||
| if ((_RB_BITS(up) & _RB_LR) == 0) { \ | if ((_RB_BITS(up) & _RB_LR) == 0) { \ | ||||
| /* shorten edges descending from sib, retry */ \ | /* shorten edges descending from sib, retry */ \ | ||||
| _RB_UP(sib, field) = up; \ | _RB_UP(sib, field) = up; \ | ||||
| continue; \ | continue; \ | ||||
| } \ | } \ | ||||
| if ((_RB_BITS(up) & sibdir) == 0) { \ | if ((_RB_BITS(up) & sibdir) == 0) { \ | ||||
| /* \ | /* \ | ||||
| * The edge descending from 'sib' away from \ | * The edge descending from 'sib' away from \ | ||||
| Show All 14 Lines | if ((_RB_BITS(up) & sibdir) == 0) { \ | ||||
| * / \ \ | * / \ \ | ||||
| * / z \ | * / z \ | ||||
| * y \ | * y \ | ||||
| */ \ | */ \ | ||||
| elm = _RB_LINK(sib, elmdir, field); \ | elm = _RB_LINK(sib, elmdir, field); \ | ||||
| /* elm is a 1-child. First rotate at elm. */ \ | /* elm is a 1-child. First rotate at elm. */ \ | ||||
| RB_ROTATE(sib, elm, sibdir, field); \ | RB_ROTATE(sib, elm, sibdir, field); \ | ||||
| up = _RB_UP(elm, field); \ | up = _RB_UP(elm, field); \ | ||||
| _RB_BITSUP(parent, field) ^= \ | _RB_UPMOD_XOR(parent, field, \ | ||||
| (_RB_BITS(up) & elmdir) ? _RB_LR : elmdir; \ | (_RB_BITS(up) & elmdir) ? _RB_LR : elmdir); \ | ||||
| _RB_BITSUP(sib, field) ^= \ | _RB_UPMOD_XOR(sib, field, \ | ||||
| (_RB_BITS(up) & sibdir) ? _RB_LR : sibdir; \ | (_RB_BITS(up) & sibdir) ? _RB_LR : sibdir); \ | ||||
| _RB_BITSUP(elm, field) |= _RB_LR; \ | _RB_UPMOD_OR(elm, field, _RB_LR); \ | ||||
| } else { \ | } else { \ | ||||
| if ((_RB_BITS(up) & elmdir) == 0 && \ | if ((_RB_BITS(up) & elmdir) == 0 && \ | ||||
| RB_STRICT_HST && elm != NULL) { \ | RB_STRICT_HST && elm != NULL) { \ | ||||
| /* if parent does not become a leaf, \ | /* if parent does not become a leaf, \ | ||||
| do not demote parent yet. */ \ | do not demote parent yet. */ \ | ||||
| _RB_BITSUP(parent, field) ^= sibdir; \ | _RB_UPMOD_XOR(parent, field, sibdir); \ | ||||
| _RB_BITSUP(sib, field) ^= _RB_LR; \ | _RB_UPMOD_XOR(sib, field, _RB_LR); \ | ||||
| } else if ((_RB_BITS(up) & elmdir) == 0) { \ | } else if ((_RB_BITS(up) & elmdir) == 0) { \ | ||||
| /* demote parent. */ \ | /* demote parent. */ \ | ||||
| _RB_BITSUP(parent, field) ^= elmdir; \ | _RB_UPMOD_XOR(parent, field, elmdir); \ | ||||
| _RB_BITSUP(sib, field) ^= sibdir; \ | _RB_UPMOD_XOR(sib, field, sibdir); \ | ||||
| } else \ | } else \ | ||||
| _RB_BITSUP(sib, field) ^= sibdir; \ | _RB_UPMOD_XOR(sib, field, sibdir); \ | ||||
| elm = sib; \ | elm = sib; \ | ||||
| } \ | } \ | ||||
| \ | \ | ||||
| /* \ | /* \ | ||||
| * The edge descending from 'elm' away from 'parent' \ | * The edge descending from 'elm' away from 'parent' \ | ||||
| * is short. Rotate to make 'parent' a child of 'elm', \ | * is short. Rotate to make 'parent' a child of 'elm', \ | ||||
| * then lengthen the short edges descending from \ | * then lengthen the short edges descending from \ | ||||
| * 'parent' and 'elm' to rebalance. \ | * 'parent' and 'elm' to rebalance. \ | ||||
| ▲ Show 20 Lines • Show All 331 Lines • Show Last 20 Lines | |||||
The names _RB_XOR and _RB_OR don't suggest that the macros have side effects. I suggest either _RB_FLIP/_RB_SET or _RB_XOR_EQ/_RB_OR_EQ. to make the side effects more obvious.
(I wrote this before the 'MOD' parts got added.)