#3768

Committed 28 Mar 2025 10:15AM UTC coverage: 33.726% (-0.3%) from 33.993%

Build # #3768

Build Type

push

travis-ci

Committed by

happyguoxy

Commit Message

test:alter lcov result

Coverage Stats

144891 of 592084 branches covered (24.47%)

Branch coverage included in aggregate %.

218795 of 486283 relevant lines covered (44.99%)

765715.29 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

84.29

/source/util/src/trbtree.c

/*
 * Copyright (c) 2019 TAOS Data, Inc. <jhtao@taosdata.com>
 *
 * This program is free software: you can use, redistribute, and/or modify
 * it under the terms of the GNU Affero General Public License, version 3
 * or later ("AGPL"), as published by the Free Software Foundation.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.
 *
 * You should have received a copy of the GNU Affero General Public License
 * along with this program. If not, see <http://www.gnu.org/licenses/>.
 */

#include "trbtree.h"
#include "tlog.h"

static void tRBTreeRotateLeft(SRBTree *pTree, SRBTreeNode *x) {
  SRBTreeNode *y = x->right;
  x->right = y->left;
  if (y->left != pTree->NIL) {
    y->left->parent = x;
  }
  y->parent = x->parent;
  if (x->parent == pTree->NIL) {
    pTree->root = y;
  } else if (x == x->parent->left) {
    x->parent->left = y;
  } else {
    x->parent->right = y;
  }
  y->left = x;
  x->parent = y;
}

static void tRBTreeRotateRight(SRBTree *pTree, SRBTreeNode *x) {
  SRBTreeNode *y = x->left;
  x->left = y->right;
  if (y->right != pTree->NIL) {
    y->right->parent = x;
  }
  y->parent = x->parent;
  if (x->parent == pTree->NIL) {
    pTree->root = y;
  } else if (x == x->parent->right) {
    x->parent->right = y;
  } else {
    x->parent->left = y;
  }
  y->right = x;
  x->parent = y;
}

static void tRBTreePutFix(SRBTree *pTree, SRBTreeNode *z) {
  while (z->parent->color == RED) {
    if (z->parent == z->parent->parent->left) {  // z.parent is the left child

      SRBTreeNode *y = z->parent->parent->right;  // uncle of z

      if (y->color == RED) {  // case 1
        z->parent->color = BLACK;
        y->color = BLACK;
        z->parent->parent->color = RED;
        z = z->parent->parent;
      } else {                        // case2 or case3
        if (z == z->parent->right) {  // case2
          z = z->parent;              // marked z.parent as new z
          tRBTreeRotateLeft(pTree, z);
        }
        // case3
        z->parent->color = BLACK;        // made parent black
        z->parent->parent->color = RED;  // made parent red
        tRBTreeRotateRight(pTree, z->parent->parent);
      }
    } else {                                     // z.parent is the right child
      SRBTreeNode *y = z->parent->parent->left;  // uncle of z

      if (y->color == RED) {
        z->parent->color = BLACK;
        y->color = BLACK;
        z->parent->parent->color = RED;
        z = z->parent->parent;
      } else {
        if (z == z->parent->left) {
          z = z->parent;  // marked z.parent as new z
          tRBTreeRotateRight(pTree, z);
        }
        z->parent->color = BLACK;        // made parent black
        z->parent->parent->color = RED;  // made parent red
        tRBTreeRotateLeft(pTree, z->parent->parent);
      }
    }
  }
  pTree->root->color = BLACK;
}

static void tRBTreeTransplant(SRBTree *pTree, SRBTreeNode *u, SRBTreeNode *v) {
  if (u->parent == pTree->NIL)
    pTree->root = v;
  else if (u == u->parent->left)
    u->parent->left = v;
  else
    u->parent->right = v;
  v->parent = u->parent;
}

static SRBTreeNode *tRBTreeSuccessor(const SRBTree *pTree, SRBTreeNode *pNode) {
  if (pNode->right != pTree->NIL) {
    pNode = pNode->right;
    while (pNode->left != pTree->NIL) {
      pNode = pNode->left;
    }
  } else {
    while (true) {
      if (pNode->parent == pTree->NIL || pNode == pNode->parent->left) {
        pNode = pNode->parent;
        break;
      } else {
        pNode = pNode->parent;
      }
    }
  }

  return pNode;
}

static SRBTreeNode *tRBTreePredecessor(const SRBTree *pTree, SRBTreeNode *pNode) {
  if (pNode->left != pTree->NIL) {
    pNode = pNode->left;
    while (pNode->right != pTree->NIL) {
      pNode = pNode->right;
    }
  } else {
    while (true) {
      if (pNode->parent == pTree->NIL || pNode == pNode->parent->right) {
        pNode = pNode->parent;
        break;
      } else {
        pNode = pNode->parent;
      }
    }
  }

  return pNode;
}

void tRBTreeCreate(SRBTree *pTree, tRBTreeCmprFn cmprFn) {
  pTree->cmprFn = cmprFn;
  tRBTreeClear(pTree);
}

void tRBTreeClear(SRBTree *pTree) {
  pTree->n = 0;
  pTree->NIL = &pTree->NILNODE;
  pTree->NIL->color = BLACK;
  pTree->NIL->parent = NULL;
  pTree->NIL->left = NULL;
  pTree->NIL->right = NULL;
  pTree->root = pTree->NIL;
  pTree->min = pTree->NIL;
  pTree->max = pTree->NIL;
}

SRBTreeNode *tRBTreePut(SRBTree *pTree, SRBTreeNode *z) {
  SRBTreeNode *y = pTree->NIL;  // variable for the parent of the added node
  SRBTreeNode *temp = pTree->root;

  while (temp != pTree->NIL) {
    y = temp;

    int32_t c = pTree->cmprFn(z, temp);
    if (c < 0) {
      temp = temp->left;
    } else if (c > 0) {
      temp = temp->right;
    } else {
      return NULL;
    }
  }
  z->parent = y;

  if (y == pTree->NIL) {
    pTree->root = z;
  } else if (pTree->cmprFn(z, y) < 0) {
    y->left = z;
  } else {
    y->right = z;
  }

  z->color = RED;
  z->left = pTree->NIL;
  z->right = pTree->NIL;

  tRBTreePutFix(pTree, z);

  // update min/max node
  if (pTree->min == pTree->NIL || pTree->cmprFn(pTree->min, z) > 0) {
    pTree->min = z;
  }
  if (pTree->max == pTree->NIL || pTree->cmprFn(pTree->max, z) < 0) {
    pTree->max = z;
  }
  pTree->n++;
  return z;
}

#define RBTREE_NULL         rbtree->NIL
#define rbtree_t            SRBTree
#define rbnode_t            SRBTreeNode
#define rbtree_rotate_left  tRBTreeRotateLeft
#define rbtree_rotate_right tRBTreeRotateRight

static void rbtree_delete_fixup(rbtree_t *rbtree, rbnode_t *child, rbnode_t *child_parent) {
  rbnode_t *sibling;
  int       go_up = 1;

  /* determine sibling to the node that is one-black short */
  if (child_parent->right == child)
    sibling = child_parent->left;
  else
    sibling = child_parent->right;

  while (go_up) {
    if (child_parent == RBTREE_NULL) {
      /* removed parent==black from root, every path, so ok */
      return;
    }

    if (sibling->color == RED) { /* rotate to get a black sibling */
      child_parent->color = RED;
      sibling->color = BLACK;
      if (child_parent->right == child)
        rbtree_rotate_right(rbtree, child_parent);
      else
        rbtree_rotate_left(rbtree, child_parent);
      /* new sibling after rotation */
      if (child_parent->right == child)
        sibling = child_parent->left;
      else
        sibling = child_parent->right;
    }

    if (child_parent->color == BLACK && sibling->color == BLACK && sibling->left->color == BLACK &&
        sibling->right->color == BLACK) { /* fixup local with recolor of sibling */
      if (sibling != RBTREE_NULL) sibling->color = RED;

      child = child_parent;
      child_parent = child_parent->parent;
      /* prepare to go up, new sibling */
      if (child_parent->right == child)
        sibling = child_parent->left;
      else
        sibling = child_parent->right;
    } else
      go_up = 0;
  }

  if (child_parent->color == RED && sibling->color == BLACK && sibling->left->color == BLACK &&
      sibling->right->color == BLACK) {
    /* move red to sibling to rebalance */
    if (sibling != RBTREE_NULL) sibling->color = RED;
    child_parent->color = BLACK;
    return;
  }

  /* get a new sibling, by rotating at sibling. See which child
     of sibling is red */
  if (child_parent->right == child && sibling->color == BLACK && sibling->right->color == RED &&
      sibling->left->color == BLACK) {
    sibling->color = RED;
    sibling->right->color = BLACK;
    rbtree_rotate_left(rbtree, sibling);
    /* new sibling after rotation */
    if (child_parent->right == child)
      sibling = child_parent->left;
    else
      sibling = child_parent->right;
  } else if (child_parent->left == child && sibling->color == BLACK && sibling->left->color == RED &&
             sibling->right->color == BLACK) {
    sibling->color = RED;
    sibling->left->color = BLACK;
    rbtree_rotate_right(rbtree, sibling);
    /* new sibling after rotation */
    if (child_parent->right == child)
      sibling = child_parent->left;
    else
      sibling = child_parent->right;
  }

  /* now we have a black sibling with a red child. rotate and exchange colors. */
  sibling->color = child_parent->color;
  child_parent->color = BLACK;
  if (child_parent->right == child) {
    sibling->left->color = BLACK;
    rbtree_rotate_right(rbtree, child_parent);
  } else {
    sibling->right->color = BLACK;
    rbtree_rotate_left(rbtree, child_parent);
  }
}

/** helpers for delete: swap node colours */
static void swap_int8(ECOLOR *x, ECOLOR *y) {
  ECOLOR t = *x;
  *x = *y;
  *y = t;
}

/** helpers for delete: swap node pointers */
static void swap_np(rbnode_t **x, rbnode_t **y) {
  rbnode_t *t = *x;
  *x = *y;
  *y = t;
}

/** Update parent pointers of child trees of 'parent' */
static void change_parent_ptr(rbtree_t *rbtree, rbnode_t *parent, rbnode_t *old, rbnode_t *new) {
  if (parent == RBTREE_NULL) {
    if (rbtree->root == old) rbtree->root = new;
    return;
  }
  if (parent->left == old) parent->left = new;
  if (parent->right == old) parent->right = new;
}
/** Update parent pointer of a node 'child' */
static void change_child_ptr(rbtree_t *rbtree, rbnode_t *child, rbnode_t *old, rbnode_t *new) {
  if (child == RBTREE_NULL) return;
  if (child->parent == old) child->parent = new;
}

rbnode_t *rbtree_delete(rbtree_t *rbtree, void *key) {
  rbnode_t *to_delete = key;
  rbnode_t *child;

  /* make sure we have at most one non-leaf child */
  if (to_delete->left != RBTREE_NULL && to_delete->right != RBTREE_NULL) {
    /* swap with smallest from right subtree (or largest from left) */
    rbnode_t *smright = to_delete->right;
    while (smright->left != RBTREE_NULL) smright = smright->left;
    /* swap the smright and to_delete elements in the tree,
     * but the rbnode_t is first part of user data struct
     * so cannot just swap the keys and data pointers. Instead
     * readjust the pointers left,right,parent */

    /* swap colors - colors are tied to the position in the tree */
    swap_int8(&to_delete->color, &smright->color);

    /* swap child pointers in parents of smright/to_delete */
    change_parent_ptr(rbtree, to_delete->parent, to_delete, smright);
    if (to_delete->right != smright) change_parent_ptr(rbtree, smright->parent, smright, to_delete);

    /* swap parent pointers in children of smright/to_delete */
    change_child_ptr(rbtree, smright->left, smright, to_delete);
    change_child_ptr(rbtree, smright->left, smright, to_delete);
    change_child_ptr(rbtree, smright->right, smright, to_delete);
    change_child_ptr(rbtree, smright->right, smright, to_delete);
    change_child_ptr(rbtree, to_delete->left, to_delete, smright);
    if (to_delete->right != smright) change_child_ptr(rbtree, to_delete->right, to_delete, smright);
    if (to_delete->right == smright) {
      /* set up so after swap they work */
      to_delete->right = to_delete;
      smright->parent = smright;
    }

    /* swap pointers in to_delete/smright nodes */
    swap_np(&to_delete->parent, &smright->parent);
    swap_np(&to_delete->left, &smright->left);
    swap_np(&to_delete->right, &smright->right);

    /* now delete to_delete (which is at the location where the smright previously was) */
  }

  if (to_delete->left != RBTREE_NULL)
    child = to_delete->left;
  else
    child = to_delete->right;

  /* unlink to_delete from the tree, replace to_delete with child */
  change_parent_ptr(rbtree, to_delete->parent, to_delete, child);
  change_child_ptr(rbtree, child, to_delete, to_delete->parent);

  if (to_delete->color == RED) {
    /* if node is red then the child (black) can be swapped in */
  } else if (child->color == RED) {
    /* change child to BLACK, removing a RED node is no problem */
    if (child != RBTREE_NULL) child->color = BLACK;
  } else
    rbtree_delete_fixup(rbtree, child, to_delete->parent);

  /* unlink completely */
  to_delete->parent = RBTREE_NULL;
  to_delete->left = RBTREE_NULL;
  to_delete->right = RBTREE_NULL;
  to_delete->color = BLACK;
  return to_delete;
}

void tRBTreeDrop(SRBTree *pTree, SRBTreeNode *z) {
  // update min/max node
  if (pTree->min == z) {
    pTree->min = tRBTreeSuccessor(pTree, pTree->min);
  }
  if (pTree->max == z) {
    pTree->max = tRBTreePredecessor(pTree, pTree->max);
  }

  (void)rbtree_delete(pTree, z);

  pTree->n--;
}

SRBTreeNode *tRBTreeDropByKey(SRBTree *pTree, void *pKey) {
  SRBTreeNode *pNode = tRBTreeGet(pTree, pKey);

  if (pNode) {
    tRBTreeDrop(pTree, pNode);
  }

  return pNode;
}

SRBTreeNode *tRBTreeDropMin(SRBTree *pTree) {
  SRBTreeNode *pNode = tRBTreeMin(pTree);
  if (pNode) {
    tRBTreeDrop(pTree, pNode);
  }
  return pNode;
}

SRBTreeNode *tRBTreeDropMax(SRBTree *pTree) {
  SRBTreeNode *pNode = tRBTreeMax(pTree);
  if (pNode) {
    tRBTreeDrop(pTree, pNode);
  }
  return pNode;
}

SRBTreeNode *tRBTreeGet(const SRBTree *pTree, const SRBTreeNode *pKeyNode) {
  SRBTreeNode *pNode = pTree->root;

  while (pNode != pTree->NIL) {
    int32_t c = pTree->cmprFn(pKeyNode, pNode);

    if (c < 0) {
      pNode = pNode->left;
    } else if (c > 0) {
      pNode = pNode->right;
    } else {
      break;
    }
  }

  return (pNode == pTree->NIL) ? NULL : pNode;
}

// SRBTreeIter ================================================
SRBTreeNode *tRBTreeIterNext(SRBTreeIter *pIter) {
  SRBTreeNode *pNode = pIter->pNode;

  if (pIter->pNode != pIter->pTree->NIL) {
    if (pIter->asc) {
      // ascend
      pIter->pNode = tRBTreeSuccessor(pIter->pTree, pIter->pNode);
    } else {
      // descend
      pIter->pNode = tRBTreePredecessor(pIter->pTree, pIter->pNode);
    }
  }

_exit:
  return (pNode == pIter->pTree->NIL) ? NULL : pNode;
}

1	/*
2	* Copyright (c) 2019 TAOS Data, Inc. <jhtao@taosdata.com>
3	*
4	* This program is free software: you can use, redistribute, and/or modify
5	* it under the terms of the GNU Affero General Public License, version 3
6	* or later ("AGPL"), as published by the Free Software Foundation.
7	*
8	* This program is distributed in the hope that it will be useful, but WITHOUT
9	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
10	* FITNESS FOR A PARTICULAR PURPOSE.
11	*
12	* You should have received a copy of the GNU Affero General Public License
13	* along with this program. If not, see <http://www.gnu.org/licenses/>.
14	*/
15
16	#include "trbtree.h"
17	#include "tlog.h"
18
19	static void tRBTreeRotateLeft(SRBTree pTree, SRBTreeNode x) {	470,488✔
20	SRBTreeNode *y = x->right;	470,488✔
21	x->right = y->left;	470,488✔
22	if (y->left != pTree->NIL) {	470,488✔
23	y->left->parent = x;	254,742✔
24	}
25	y->parent = x->parent;	470,488✔
26	if (x->parent == pTree->NIL) {	470,488✔
27	pTree->root = y;	1,822✔
28	} else if (x == x->parent->left) {	468,666✔
29	x->parent->left = y;	92,321✔
30	} else {
31	x->parent->right = y;	376,345✔
32	}
33	y->left = x;	470,488✔
34	x->parent = y;	470,488✔
35	}	470,488✔
36
37	static void tRBTreeRotateRight(SRBTree pTree, SRBTreeNode x) {	101,064✔
38	SRBTreeNode *y = x->left;	101,064✔
39	x->left = y->right;	101,064✔
40	if (y->right != pTree->NIL) {	101,064✔
41	y->right->parent = x;	40,858✔
42	}
43	y->parent = x->parent;	101,064✔
44	if (x->parent == pTree->NIL) {	101,064✔
45	pTree->root = y;	9✔
46	} else if (x == x->parent->right) {	101,055✔
47	x->parent->right = y;	52,764✔
48	} else {
49	x->parent->left = y;	48,291✔
50	}
51	y->right = x;	101,064✔
52	x->parent = y;	101,064✔
53	}	101,064✔
54
55	static void tRBTreePutFix(SRBTree pTree, SRBTreeNode z) {	429,063✔
56	while (z->parent->color == RED) {	1,139,874✔
57	if (z->parent == z->parent->parent->left) { // z.parent is the left child	710,810✔
58
59	SRBTreeNode *y = z->parent->parent->right; // uncle of z	36,148✔
60
61	if (y->color == RED) { // case 1	36,148✔
62	z->parent->color = BLACK;	239✔
63	y->color = BLACK;	239✔
64	z->parent->parent->color = RED;	239✔
65	z = z->parent->parent;	239✔
66	} else { // case2 or case3
67	if (z == z->parent->right) { // case2	35,909✔
68	z = z->parent; // marked z.parent as new z	31,302✔
69	tRBTreeRotateLeft(pTree, z);	31,302✔
70	}
71	// case3
72	z->parent->color = BLACK; // made parent black	35,909✔
73	z->parent->parent->color = RED; // made parent red	35,909✔
74	tRBTreeRotateRight(pTree, z->parent->parent);	35,909✔
75	}
76	} else { // z.parent is the right child
77	SRBTreeNode *y = z->parent->parent->left; // uncle of z	674,662✔
78
79	if (y->color == RED) {	674,662✔
80	z->parent->color = BLACK;	335,819✔
81	y->color = BLACK;	335,819✔
82	z->parent->parent->color = RED;	335,819✔
83	z = z->parent->parent;	335,819✔
84	} else {
85	if (z == z->parent->left) {	338,843✔
86	z = z->parent; // marked z.parent as new z	90✔
87	tRBTreeRotateRight(pTree, z);	90✔
88	}
89	z->parent->color = BLACK; // made parent black	338,843✔
90	z->parent->parent->color = RED; // made parent red	338,843✔
91	tRBTreeRotateLeft(pTree, z->parent->parent);	338,843✔
92	}
93	}
94	}
95	pTree->root->color = BLACK;	429,064✔
96	}	429,064✔
97
98	static void tRBTreeTransplant(SRBTree pTree, SRBTreeNode u, SRBTreeNode *v) {	×
99	if (u->parent == pTree->NIL)	×
100	pTree->root = v;	×
101	else if (u == u->parent->left)	×
102	u->parent->left = v;	×
103	else
104	u->parent->right = v;	×
105	v->parent = u->parent;	×
106	}	×
107
108	static SRBTreeNode tRBTreeSuccessor(const SRBTree pTree, SRBTreeNode *pNode) {	1,638,312✔
109	if (pNode->right != pTree->NIL) {	1,638,312✔
110	pNode = pNode->right;	742,207✔
111	while (pNode->left != pTree->NIL) {	1,094,751✔
112	pNode = pNode->left;	352,544✔
113	}
114	} else {
115	while (true) {
116	if (pNode->parent == pTree->NIL \|\| pNode == pNode->parent->left) {	1,244,103✔
117	pNode = pNode->parent;	896,105✔
118	break;	896,105✔
119	} else {
120	pNode = pNode->parent;	347,998✔
121	}
122	}
123	}
124
125	return pNode;	1,638,312✔
126	}
127
128	static SRBTreeNode tRBTreePredecessor(const SRBTree pTree, SRBTreeNode *pNode) {	7,924✔
129	if (pNode->left != pTree->NIL) {	7,924!
130	pNode = pNode->left;	×
131	while (pNode->right != pTree->NIL) {	×
132	pNode = pNode->right;	×
133	}
134	} else {
135	while (true) {
136	if (pNode->parent == pTree->NIL \|\| pNode == pNode->parent->right) {	7,924!
137	pNode = pNode->parent;	7,924✔
138	break;	7,924✔
139	} else {
140	pNode = pNode->parent;	×
141	}
142	}
143	}
144
145	return pNode;	7,924✔
146	}
147
148	void tRBTreeCreate(SRBTree *pTree, tRBTreeCmprFn cmprFn) {	14,483✔
149	pTree->cmprFn = cmprFn;	14,483✔
150	tRBTreeClear(pTree);	14,483✔
151	}	14,485✔
152
153	void tRBTreeClear(SRBTree *pTree) {	14,485✔
154	pTree->n = 0;	14,485✔
155	pTree->NIL = &pTree->NILNODE;	14,485✔
156	pTree->NIL->color = BLACK;	14,485✔
157	pTree->NIL->parent = NULL;	14,485✔
158	pTree->NIL->left = NULL;	14,485✔
159	pTree->NIL->right = NULL;	14,485✔
160	pTree->root = pTree->NIL;	14,485✔
161	pTree->min = pTree->NIL;	14,485✔
162	pTree->max = pTree->NIL;	14,485✔
163	}	14,485✔
164
165	SRBTreeNode tRBTreePut(SRBTree pTree, SRBTreeNode *z) {	429,064✔
166	SRBTreeNode *y = pTree->NIL; // variable for the parent of the added node	429,064✔
167	SRBTreeNode *temp = pTree->root;	429,064✔
168
169	while (temp != pTree->NIL) {	7,823,547✔
170	y = temp;	7,394,478✔
171
172	int32_t c = pTree->cmprFn(z, temp);	7,394,478✔
173	if (c < 0) {	7,394,475✔
174	temp = temp->left;	739,857✔
175	} else if (c > 0) {	6,654,618!
176	temp = temp->right;	6,654,626✔
177	} else {
178	return NULL;
179	}
180	}
181	z->parent = y;	429,069✔
182
183	if (y == pTree->NIL) {	429,069✔
184	pTree->root = z;	8,588✔
185	} else if (pTree->cmprFn(z, y) < 0) {	420,481✔
186	y->left = z;	39,139✔
187	} else {
188	y->right = z;	381,338✔
189	}
190
191	z->color = RED;	429,065✔
192	z->left = pTree->NIL;	429,065✔
193	z->right = pTree->NIL;	429,065✔
194
195	tRBTreePutFix(pTree, z);	429,065✔
196
197	// update min/max node
198	if (pTree->min == pTree->NIL \|\| pTree->cmprFn(pTree->min, z) > 0) {	429,063✔
199	pTree->min = z;	13,004✔
200	}
201	if (pTree->max == pTree->NIL \|\| pTree->cmprFn(pTree->max, z) < 0) {	429,066✔
202	pTree->max = z;	344,221✔
203	}
204	pTree->n++;	429,062✔
205	return z;	429,062✔
206	}
207
208	#define RBTREE_NULL rbtree->NIL
209	#define rbtree_t SRBTree
210	#define rbnode_t SRBTreeNode
211	#define rbtree_rotate_left tRBTreeRotateLeft
212	#define rbtree_rotate_right tRBTreeRotateRight
213
214	static void rbtree_delete_fixup(rbtree_t rbtree, rbnode_t child, rbnode_t *child_parent) {	207,694✔
215	rbnode_t *sibling;
216	int go_up = 1;	207,694✔
217
218	/* determine sibling to the node that is one-black short */
219	if (child_parent->right == child)	207,694✔
220	sibling = child_parent->left;	62,606✔
221	else
222	sibling = child_parent->right;	145,088✔
223
224	while (go_up) {	574,032✔
225	if (child_parent == RBTREE_NULL) {	374,596✔
226	/* removed parent==black from root, every path, so ok */
227	return;	8,258✔
228	}
229
230	if (sibling->color == RED) { /* rotate to get a black sibling */	366,338✔
231	child_parent->color = RED;	122,400✔
232	sibling->color = BLACK;	122,400✔
233	if (child_parent->right == child)	122,400✔
234	rbtree_rotate_right(rbtree, child_parent);	34,857✔
235	else
236	rbtree_rotate_left(rbtree, child_parent);	87,543✔
237	/* new sibling after rotation */
238	if (child_parent->right == child)	122,400✔
239	sibling = child_parent->left;	34,857✔
240	else
241	sibling = child_parent->right;	87,543✔
242	}
243
244	if (child_parent->color == BLACK && sibling->color == BLACK && sibling->left->color == BLACK &&	366,338!
245	sibling->right->color == BLACK) { /* fixup local with recolor of sibling */	169,023✔
246	if (sibling != RBTREE_NULL) sibling->color = RED;	166,903!
247
248	child = child_parent;	166,903✔
249	child_parent = child_parent->parent;	166,903✔
250	/* prepare to go up, new sibling */
251	if (child_parent->right == child)	166,903✔
252	sibling = child_parent->left;	33,774✔
253	else
254	sibling = child_parent->right;	133,129✔
255	} else
256	go_up = 0;	199,435✔
257	}
258
259	if (child_parent->color == RED && sibling->color == BLACK && sibling->left->color == BLACK &&	199,436!
260	sibling->right->color == BLACK) {	172,740✔
261	/* move red to sibling to rebalance */
262	if (sibling != RBTREE_NULL) sibling->color = RED;	167,790!
263	child_parent->color = BLACK;	167,790✔
264	return;	167,790✔
265	}
266
267	/* get a new sibling, by rotating at sibling. See which child
268	of sibling is red */
269	if (child_parent->right == child && sibling->color == BLACK && sibling->right->color == RED &&	31,646!
270	sibling->left->color == BLACK) {	11,656✔
271	sibling->color = RED;	5,775✔
272	sibling->right->color = BLACK;	5,775✔
273	rbtree_rotate_left(rbtree, sibling);	5,775✔
274	/* new sibling after rotation */
275	if (child_parent->right == child)	5,775!
276	sibling = child_parent->left;	5,775✔
277	else
278	sibling = child_parent->right;	×
279	} else if (child_parent->left == child && sibling->color == BLACK && sibling->left->color == RED &&	25,871!
280	sibling->right->color == BLACK) {	5,730✔
281	sibling->color = RED;	5,588✔
282	sibling->left->color = BLACK;	5,588✔
283	rbtree_rotate_right(rbtree, sibling);	5,588✔
284	/* new sibling after rotation */
285	if (child_parent->right == child)	5,588!
286	sibling = child_parent->left;	×
287	else
288	sibling = child_parent->right;	5,588✔
289	}
290
291	/* now we have a black sibling with a red child. rotate and exchange colors. */
292	sibling->color = child_parent->color;	31,646✔
293	child_parent->color = BLACK;	31,646✔
294	if (child_parent->right == child) {	31,646✔
295	sibling->left->color = BLACK;	24,620✔
296	rbtree_rotate_right(rbtree, child_parent);	24,620✔
297	} else {
298	sibling->right->color = BLACK;	7,026✔
299	rbtree_rotate_left(rbtree, child_parent);	7,026✔
300	}
301	}
302
303	/** helpers for delete: swap node colours */
304	static void swap_int8(ECOLOR x, ECOLOR y) {	275,466✔
305	ECOLOR t = *x;	275,466✔
306	x = y;	275,466✔
307	*y = t;	275,466✔
308	}	275,466✔
309
310	/** helpers for delete: swap node pointers */
311	static void swap_np(rbnode_t x, rbnode_t y) {	826,398✔
312	rbnode_t t = x;	826,398✔
313	x = y;	826,398✔
314	*y = t;	826,398✔
315	}	826,398✔
316
317	/** Update parent pointers of child trees of 'parent' */
318	static void change_parent_ptr(rbtree_t rbtree, rbnode_t parent, rbnode_t old, rbnode_t new) {	887,503✔
319	if (parent == RBTREE_NULL) {	887,503✔
320	if (rbtree->root == old) rbtree->root = new;	8,995!
321	return;	8,995✔
322	}
323	if (parent->left == old) parent->left = new;	878,508✔
324	if (parent->right == old) parent->right = new;	878,508✔
325	}
326	/** Update parent pointer of a node 'child' */
327	static void change_child_ptr(rbtree_t rbtree, rbnode_t child, rbnode_t old, rbnode_t new) {	1,989,368✔
328	if (child == RBTREE_NULL) return;	1,989,368✔
329	if (child->parent == old) child->parent = new;	857,479✔
330	}
331
332	rbnode_t rbtree_delete(rbtree_t rbtree, void *key) {	425,806✔
333	rbnode_t *to_delete = key;	425,806✔
334	rbnode_t *child;
335
336	/* make sure we have at most one non-leaf child */
337	if (to_delete->left != RBTREE_NULL && to_delete->right != RBTREE_NULL) {	425,806✔
338	/* swap with smallest from right subtree (or largest from left) */
339	rbnode_t *smright = to_delete->right;	275,466✔
340	while (smright->left != RBTREE_NULL) smright = smright->left;	495,503✔
341	/* swap the smright and to_delete elements in the tree,
342	* but the rbnode_t is first part of user data struct
343	* so cannot just swap the keys and data pointers. Instead
344	* readjust the pointers left,right,parent */
345
346	/* swap colors - colors are tied to the position in the tree */
347	swap_int8(&to_delete->color, &smright->color);	275,466✔
348
349	/* swap child pointers in parents of smright/to_delete */
350	change_parent_ptr(rbtree, to_delete->parent, to_delete, smright);	275,466✔
351	if (to_delete->right != smright) change_parent_ptr(rbtree, smright->parent, smright, to_delete);	275,466✔
352
353	/* swap parent pointers in children of smright/to_delete */
354	change_child_ptr(rbtree, smright->left, smright, to_delete);	275,466✔
355	change_child_ptr(rbtree, smright->left, smright, to_delete);	275,466✔
356	change_child_ptr(rbtree, smright->right, smright, to_delete);	275,466✔
357	change_child_ptr(rbtree, smright->right, smright, to_delete);	275,466✔
358	change_child_ptr(rbtree, to_delete->left, to_delete, smright);	275,466✔
359	if (to_delete->right != smright) change_child_ptr(rbtree, to_delete->right, to_delete, smright);	275,466✔
360	if (to_delete->right == smright) {	275,466✔
361	/* set up so after swap they work */
362	to_delete->right = to_delete;	89,236✔
363	smright->parent = smright;	89,236✔
364	}
365
366	/* swap pointers in to_delete/smright nodes */
367	swap_np(&to_delete->parent, &smright->parent);	275,466✔
368	swap_np(&to_delete->left, &smright->left);	275,466✔
369	swap_np(&to_delete->right, &smright->right);	275,466✔
370
371	/* now delete to_delete (which is at the location where the smright previously was) */
372	}
373
374	if (to_delete->left != RBTREE_NULL)	425,806✔
375	child = to_delete->left;	22,328✔
376	else
377	child = to_delete->right;	403,478✔
378
379	/* unlink to_delete from the tree, replace to_delete with child */
380	change_parent_ptr(rbtree, to_delete->parent, to_delete, child);	425,806✔
381	change_child_ptr(rbtree, child, to_delete, to_delete->parent);	425,808✔
382
383	if (to_delete->color == RED) {	425,808✔
384	/* if node is red then the child (black) can be swapped in */
385	} else if (child->color == RED) {	382,867✔
386	/* change child to BLACK, removing a RED node is no problem */
387	if (child != RBTREE_NULL) child->color = BLACK;	175,172!
388	} else
389	rbtree_delete_fixup(rbtree, child, to_delete->parent);	207,695✔
390
391	/* unlink completely */
392	to_delete->parent = RBTREE_NULL;	425,805✔
393	to_delete->left = RBTREE_NULL;	425,805✔
394	to_delete->right = RBTREE_NULL;	425,805✔
395	to_delete->color = BLACK;	425,805✔
396	return to_delete;	425,805✔
397	}
398
399	void tRBTreeDrop(SRBTree pTree, SRBTreeNode z) {	425,809✔
400	// update min/max node
401	if (pTree->min == z) {	425,809✔
402	pTree->min = tRBTreeSuccessor(pTree, pTree->min);	36,875✔
403	}
404	if (pTree->max == z) {	425,807✔
405	pTree->max = tRBTreePredecessor(pTree, pTree->max);	7,925✔
406	}
407
408	(void)rbtree_delete(pTree, z);	425,806✔
409
410	pTree->n--;	425,805✔
411	}	425,805✔
412
413	SRBTreeNode tRBTreeDropByKey(SRBTree pTree, void *pKey) {	×
414	SRBTreeNode *pNode = tRBTreeGet(pTree, pKey);	×
415
416	if (pNode) {	×
417	tRBTreeDrop(pTree, pNode);	×
418	}
419
420	return pNode;	×
421	}
422
423	SRBTreeNode tRBTreeDropMin(SRBTree pTree) {	3,607✔
424	SRBTreeNode *pNode = tRBTreeMin(pTree);	3,607✔
425	if (pNode) {	3,607✔
426	tRBTreeDrop(pTree, pNode);	1,740✔
427	}
428	return pNode;	3,608✔
429	}
430
431	SRBTreeNode tRBTreeDropMax(SRBTree pTree) {	×
432	SRBTreeNode *pNode = tRBTreeMax(pTree);	×
433	if (pNode) {	×
434	tRBTreeDrop(pTree, pNode);	×
435	}
436	return pNode;	×
437	}
438
439	SRBTreeNode tRBTreeGet(const SRBTree pTree, const SRBTreeNode *pKeyNode) {	×
440	SRBTreeNode *pNode = pTree->root;	×
441
442	while (pNode != pTree->NIL) {	×
443	int32_t c = pTree->cmprFn(pKeyNode, pNode);	×
444
445	if (c < 0) {	×
446	pNode = pNode->left;	×
447	} else if (c > 0) {	×
448	pNode = pNode->right;	×
449	} else {
450	break;	×
451	}
452	}
453
454	return (pNode == pTree->NIL) ? NULL : pNode;	×
455	}
456
457	// SRBTreeIter ================================================
458	SRBTreeNode tRBTreeIterNext(SRBTreeIter pIter) {	1,620,346✔
459	SRBTreeNode *pNode = pIter->pNode;	1,620,346✔
460
461	if (pIter->pNode != pIter->pTree->NIL) {	1,620,346✔
462	if (pIter->asc) {	1,601,450!
463	// ascend
464	pIter->pNode = tRBTreeSuccessor(pIter->pTree, pIter->pNode);	1,601,450✔
465	} else {
466	// descend
467	pIter->pNode = tRBTreePredecessor(pIter->pTree, pIter->pNode);	×
468	}
469	}
470
471	_exit:	18,896✔
472	return (pNode == pIter->pTree->NIL) ? NULL : pNode;	1,620,338✔
473	}

taosdata / TDengine / #3768

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous