Changeset View
Standalone View
sys/sys/tree.h
Show First 20 Lines • Show All 334 Lines • ▼ Show 20 Lines | |||||
*/ | */ | ||||
#define RB_UP(elm, field) (elm)->field.rbe_parent | #define RB_UP(elm, field) (elm)->field.rbe_parent | ||||
#define RB_BITS(elm, field) (*(__uintptr_t *)&RB_UP(elm, field)) | #define RB_BITS(elm, field) (*(__uintptr_t *)&RB_UP(elm, field)) | ||||
#define RB_RED_L ((__uintptr_t)1) | #define RB_RED_L ((__uintptr_t)1) | ||||
#define RB_RED_R ((__uintptr_t)2) | #define RB_RED_R ((__uintptr_t)2) | ||||
#define RB_RED_MASK ((__uintptr_t)3) | #define RB_RED_MASK ((__uintptr_t)3) | ||||
#define RB_FLIP_LEFT(elm, field) (RB_BITS(elm, field) ^= RB_RED_L) | #define RB_FLIP_LEFT(elm, field) (RB_BITS(elm, field) ^= RB_RED_L) | ||||
#define RB_FLIP_RIGHT(elm, field) (RB_BITS(elm, field) ^= RB_RED_R) | #define RB_FLIP_RIGHT(elm, field) (RB_BITS(elm, field) ^= RB_RED_R) | ||||
#define RB_FLIP_ALL(elm, field) (RB_BITS(elm, field) ^= RB_RED_MASK) | |||||
#define RB_RED_LEFT(elm, field) ((RB_BITS(elm, field) & RB_RED_L) != 0) | #define RB_RED_LEFT(elm, field) ((RB_BITS(elm, field) & RB_RED_L) != 0) | ||||
#define RB_RED_RIGHT(elm, field) ((RB_BITS(elm, field) & RB_RED_R) != 0) | #define RB_RED_RIGHT(elm, field) ((RB_BITS(elm, field) & RB_RED_R) != 0) | ||||
#define RB_PARENT(elm, field) ((__typeof(RB_UP(elm, field))) \ | #define RB_PARENT(elm, field) ((__typeof(RB_UP(elm, field))) \ | ||||
(RB_BITS(elm, field) & ~RB_RED_MASK)) | (RB_BITS(elm, field) & ~RB_RED_MASK)) | ||||
#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_BITS(dst, field) &= RB_RED_MASK; \ | RB_BITS(dst, field) = (__uintptr_t)src | \ | ||||
RB_BITS(dst, field) |= (__uintptr_t)src; \ | (RB_BITS(dst, field) & RB_RED_MASK); \ | ||||
alc: This being done as two separate assignment statements is pessimizing the generated code. | |||||
} 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) | ||||
#define RB_COLOR(elm, field) (RB_PARENT(elm, field) == NULL ? 0 : \ | #define RB_COLOR(elm, field) (RB_PARENT(elm, field) == NULL ? 0 : \ | ||||
▲ Show 20 Lines • Show All 121 Lines • ▼ Show 20 Lines | if (RB_LEFT(parent, field) == elm) { \ | ||||
} \ | } \ | ||||
RB_FLIP_RIGHT(parent, field); \ | RB_FLIP_RIGHT(parent, field); \ | ||||
if (RB_RED_RIGHT(parent, field)) { \ | if (RB_RED_RIGHT(parent, field)) { \ | ||||
child = elm; \ | child = elm; \ | ||||
elm = parent; \ | elm = parent; \ | ||||
continue; \ | continue; \ | ||||
} \ | } \ | ||||
if (!RB_RED_RIGHT(elm, field)) { \ | if (!RB_RED_RIGHT(elm, field)) { \ | ||||
RB_FLIP_LEFT(elm, field); \ | |||||
/* coverity[uninit_use] */ \ | /* coverity[uninit_use] */ \ | ||||
RB_ROTATE_LEFT(head, elm, child, field);\ | RB_ROTATE_LEFT(head, elm, child, field);\ | ||||
if (RB_RED_LEFT(child, field)) \ | if (RB_RED_RIGHT(child, field)) \ | ||||
RB_FLIP_RIGHT(elm, field); \ | |||||
else if (RB_RED_RIGHT(child, field)) \ | |||||
RB_FLIP_LEFT(parent, field); \ | RB_FLIP_LEFT(parent, field); \ | ||||
if (RB_RED_LEFT(child, field)) \ | |||||
RB_FLIP_ALL(elm, field); \ | |||||
else \ | |||||
Done Inline ActionsWhy is this flip no longer a part of the prior "else" clause? alc: Why is this flip no longer a part of the prior "else" clause? | |||||
Done Inline ActionsThe only possibilities for the state of 'child' are red-left, red-right, and red-neither (when child is a leaf). So the 'else' doesn't matter. Removing it, though, might prevent a branch instruction. dougm: The only possibilities for the state of 'child' are red-left, red-right, and red-neither (when… | |||||
Not Done Inline ActionsThis change is more likely to be a pessimization. When RB_RED_LEFT() is true, the code now has to perform another conditional branch on RB_RED_RIGHT(). alc: This change is more likely to be a pessimization. When RB_RED_LEFT() is true, the code now has… | |||||
Done Inline ActionsMaking the RED_LEFT test conditional on the RED_RIGHT test failing leads to an object code of the same size, but with two more 'jmp' statements in the compiled and disassembled code. Let me know if you want to see the diff. dougm: Making the RED_LEFT test conditional on the RED_RIGHT test failing leads to an object code of… | |||||
RB_FLIP_LEFT(elm, field); \ | |||||
elm = child; \ | elm = child; \ | ||||
} \ | } \ | ||||
RB_ROTATE_RIGHT(head, parent, elm, field); \ | RB_ROTATE_RIGHT(head, parent, elm, field); \ | ||||
} else { \ | } else { \ | ||||
if (RB_RED_RIGHT(parent, field)) { \ | if (RB_RED_RIGHT(parent, field)) { \ | ||||
RB_FLIP_RIGHT(parent, field); \ | RB_FLIP_RIGHT(parent, field); \ | ||||
return; \ | return; \ | ||||
} \ | } \ | ||||
RB_FLIP_LEFT(parent, field); \ | RB_FLIP_LEFT(parent, field); \ | ||||
if (RB_RED_LEFT(parent, field)) { \ | if (RB_RED_LEFT(parent, field)) { \ | ||||
child = elm; \ | child = elm; \ | ||||
elm = parent; \ | elm = parent; \ | ||||
continue; \ | continue; \ | ||||
} \ | } \ | ||||
if (!RB_RED_LEFT(elm, field)) { \ | if (!RB_RED_LEFT(elm, field)) { \ | ||||
RB_FLIP_RIGHT(elm, field); \ | |||||
/* coverity[uninit_use] */ \ | /* coverity[uninit_use] */ \ | ||||
RB_ROTATE_RIGHT(head, elm, child, field);\ | RB_ROTATE_RIGHT(head, elm, child, field);\ | ||||
if (RB_RED_RIGHT(child, field)) \ | if (RB_RED_LEFT(child, field)) \ | ||||
RB_FLIP_LEFT(elm, field); \ | |||||
else if (RB_RED_LEFT(child, field)) \ | |||||
RB_FLIP_RIGHT(parent, field); \ | RB_FLIP_RIGHT(parent, field); \ | ||||
if (RB_RED_RIGHT(child, field)) \ | |||||
RB_FLIP_ALL(elm, field); \ | |||||
else \ | |||||
RB_FLIP_RIGHT(elm, field); \ | |||||
elm = child; \ | elm = child; \ | ||||
} \ | } \ | ||||
RB_ROTATE_LEFT(head, parent, elm, field); \ | RB_ROTATE_LEFT(head, parent, elm, field); \ | ||||
} \ | } \ | ||||
RB_BITS(elm, field) &= ~RB_RED_MASK; \ | RB_BITS(elm, field) &= ~RB_RED_MASK; \ | ||||
break; \ | break; \ | ||||
} \ | } \ | ||||
} | } | ||||
Not Done Inline ActionsIt seems odd not to have a blank line separating this comment from insert. alc: It seems odd not to have a blank line separating this comment from insert. | |||||
#ifndef RB_STRICT_HST | |||||
/* | |||||
* In REMOVE_COLOR, the HST paper, in figure 3, in the single-rotate case, has | |||||
* 'parent' with one higher rank, and then reduces its rank if 'parent' has | |||||
* become a leaf. This implementation always has the parent in its new position | |||||
* with lower rank, to avoid the leaf check. Define RB_STRICT_HST to 1 to get | |||||
* the behavior that HST describes. | |||||
*/ | |||||
Done Inline ActionsThis could be prefixed with RB_ to reduce the likelihood of a collision. markj: This could be prefixed with RB_ to reduce the likelihood of a collision. | |||||
#define RB_STRICT_HST 0 | |||||
#endif | |||||
#define RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ | #define RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ | ||||
attr void \ | attr void \ | ||||
name##_RB_REMOVE_COLOR(struct name *head, \ | name##_RB_REMOVE_COLOR(struct name *head, \ | ||||
struct type *parent, struct type *elm) \ | struct type *parent, struct type *elm) \ | ||||
{ \ | { \ | ||||
struct type *sib; \ | struct type *sib; \ | ||||
if (RB_LEFT(parent, field) == elm && \ | if (RB_LEFT(parent, field) == elm && \ | ||||
RB_RIGHT(parent, field) == elm) { \ | RB_RIGHT(parent, field) == elm) { \ | ||||
RB_BITS(parent, field) &= ~RB_RED_MASK; \ | RB_BITS(parent, field) &= ~RB_RED_MASK; \ | ||||
elm = parent; \ | elm = parent; \ | ||||
parent = RB_PARENT(elm, field); \ | parent = RB_PARENT(elm, field); \ | ||||
if (parent == NULL) \ | if (parent == NULL) \ | ||||
return; \ | return; \ | ||||
} \ | } \ | ||||
do { \ | do { \ | ||||
if (RB_LEFT(parent, field) == elm) { \ | if (RB_LEFT(parent, field) == elm) { \ | ||||
if (!RB_RED_LEFT(parent, field)) { \ | if (!RB_RED_LEFT(parent, field)) { \ | ||||
RB_FLIP_LEFT(parent, field); \ | RB_FLIP_LEFT(parent, field); \ | ||||
return; \ | return; \ | ||||
} \ | } \ | ||||
if (RB_RED_RIGHT(parent, field)) { \ | if (RB_RED_RIGHT(parent, field)) { \ | ||||
RB_FLIP_RIGHT(parent, field); \ | RB_FLIP_RIGHT(parent, field); \ | ||||
elm = parent; \ | elm = parent; \ | ||||
continue; \ | continue; \ | ||||
} \ | } \ | ||||
sib = RB_RIGHT(parent, field); \ | sib = RB_RIGHT(parent, field); \ | ||||
if ((~RB_BITS(sib, field) & RB_RED_MASK) == 0) {\ | switch (RB_BITS(sib, field) & RB_RED_MASK) { \ | ||||
RB_BITS(sib, field) &= ~RB_RED_MASK; \ | case RB_RED_MASK: \ | ||||
RB_FLIP_ALL(sib, field); \ | |||||
elm = parent; \ | elm = parent; \ | ||||
continue; \ | continue; \ | ||||
} \ | case RB_RED_R: \ | ||||
RB_FLIP_RIGHT(sib, field); \ | |||||
if (RB_RED_LEFT(sib, field)) \ | |||||
RB_FLIP_LEFT(parent, field); \ | |||||
else if (!RB_RED_RIGHT(sib, field)) { \ | |||||
RB_FLIP_LEFT(parent, field); \ | |||||
elm = RB_LEFT(sib, field); \ | elm = RB_LEFT(sib, field); \ | ||||
RB_ROTATE_RIGHT(head, sib, elm, field); \ | RB_ROTATE_RIGHT(head, sib, elm, field); \ | ||||
if (RB_RED_RIGHT(elm, field)) \ | |||||
RB_FLIP_LEFT(sib, field); \ | |||||
if (RB_RED_LEFT(elm, field)) \ | if (RB_RED_LEFT(elm, field)) \ | ||||
RB_FLIP_RIGHT(parent, field); \ | RB_FLIP_ALL(parent, field); \ | ||||
else \ | |||||
RB_FLIP_LEFT(parent, field); \ | |||||
if (RB_RED_RIGHT(elm, field)) \ | |||||
RB_FLIP_ALL(sib, field); \ | |||||
else \ | |||||
RB_FLIP_RIGHT(sib, field); \ | |||||
RB_BITS(elm, field) |= RB_RED_MASK; \ | RB_BITS(elm, field) |= RB_RED_MASK; \ | ||||
sib = elm; \ | sib = elm; \ | ||||
break; \ | |||||
case RB_RED_L: \ | |||||
if (RB_STRICT_HST && elm != NULL) { \ | |||||
RB_FLIP_RIGHT(parent, field); \ | |||||
RB_FLIP_ALL(sib, field); \ | |||||
break; \ | |||||
} \ | } \ | ||||
RB_FLIP_LEFT(parent, field); \ | |||||
/* FALLTHROUGH */ \ | |||||
default: \ | |||||
RB_FLIP_RIGHT(sib, field); \ | |||||
break; \ | |||||
} \ | |||||
RB_ROTATE_LEFT(head, parent, sib, field); \ | RB_ROTATE_LEFT(head, parent, sib, field); \ | ||||
} else { \ | } else { \ | ||||
if (!RB_RED_RIGHT(parent, field)) { \ | if (!RB_RED_RIGHT(parent, field)) { \ | ||||
RB_FLIP_RIGHT(parent, field); \ | RB_FLIP_RIGHT(parent, field); \ | ||||
return; \ | return; \ | ||||
} \ | } \ | ||||
if (RB_RED_LEFT(parent, field)) { \ | if (RB_RED_LEFT(parent, field)) { \ | ||||
RB_FLIP_LEFT(parent, field); \ | RB_FLIP_LEFT(parent, field); \ | ||||
elm = parent; \ | elm = parent; \ | ||||
continue; \ | continue; \ | ||||
} \ | } \ | ||||
sib = RB_LEFT(parent, field); \ | sib = RB_LEFT(parent, field); \ | ||||
if ((~RB_BITS(sib, field) & RB_RED_MASK) == 0) {\ | switch (RB_BITS(sib, field) & RB_RED_MASK) { \ | ||||
RB_BITS(sib, field) &= ~RB_RED_MASK; \ | case RB_RED_MASK: \ | ||||
RB_FLIP_ALL(sib, field); \ | |||||
elm = parent; \ | elm = parent; \ | ||||
continue; \ | continue; \ | ||||
} \ | case RB_RED_L: \ | ||||
RB_FLIP_LEFT(sib, field); \ | |||||
if (RB_RED_RIGHT(sib, field)) \ | |||||
RB_FLIP_RIGHT(parent, field); \ | |||||
else if (!RB_RED_LEFT(sib, field)) { \ | |||||
RB_FLIP_RIGHT(parent, field); \ | |||||
elm = RB_RIGHT(sib, field); \ | elm = RB_RIGHT(sib, field); \ | ||||
RB_ROTATE_LEFT(head, sib, elm, field); \ | RB_ROTATE_LEFT(head, sib, elm, field); \ | ||||
if (RB_RED_LEFT(elm, field)) \ | |||||
RB_FLIP_RIGHT(sib, field); \ | |||||
if (RB_RED_RIGHT(elm, field)) \ | if (RB_RED_RIGHT(elm, field)) \ | ||||
RB_FLIP_LEFT(parent, field); \ | RB_FLIP_ALL(parent, field); \ | ||||
else \ | |||||
RB_FLIP_RIGHT(parent, field); \ | |||||
if (RB_RED_LEFT(elm, field)) \ | |||||
RB_FLIP_ALL(sib, field); \ | |||||
else \ | |||||
RB_FLIP_LEFT(sib, field); \ | |||||
RB_BITS(elm, field) |= RB_RED_MASK; \ | RB_BITS(elm, field) |= RB_RED_MASK; \ | ||||
sib = elm; \ | sib = elm; \ | ||||
break; \ | |||||
case RB_RED_R: \ | |||||
if (RB_STRICT_HST && elm != NULL) { \ | |||||
RB_FLIP_LEFT(parent, field); \ | |||||
RB_FLIP_ALL(sib, field); \ | |||||
break; \ | |||||
} \ | |||||
RB_FLIP_RIGHT(parent, field); \ | |||||
/* FALLTHROUGH */ \ | |||||
default: \ | |||||
RB_FLIP_LEFT(sib, field); \ | |||||
break; \ | |||||
} \ | } \ | ||||
RB_ROTATE_RIGHT(head, parent, sib, field); \ | RB_ROTATE_RIGHT(head, parent, sib, field); \ | ||||
} \ | } \ | ||||
break; \ | break; \ | ||||
} while ((parent = RB_PARENT(elm, field)) != NULL); \ | } while ((parent = RB_PARENT(elm, field)) != NULL); \ | ||||
} | } | ||||
#define RB_GENERATE_REMOVE(name, type, field, attr) \ | #define RB_GENERATE_REMOVE(name, type, field, attr) \ | ||||
▲ Show 20 Lines • Show All 228 Lines • Show Last 20 Lines |
This being done as two separate assignment statements is pessimizing the generated code.