#5011

Committed 03 Apr 2026 03:59PM UTC coverage: 72.3% (+0.008%) from 72.292%

Build # #5011

Build Type

push

travis-ci

Committed by

web-flow

Commit Message

merge: from main to 3.0 branch #35067

Coverage Stats

4053 of 5985 new or added lines in 68 files covered. (67.72%)

732 existing lines in 143 files now uncovered.

257430 of 356056 relevant lines covered (72.3%)

131834103.52 hits per line

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

90.55

/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) {	445,695,301✔
20	SRBTreeNode *y = x->right;	445,695,301✔
21	x->right = y->left;	445,747,291✔
22	if (y->left != pTree->NIL) {	445,741,348✔
23	y->left->parent = x;	153,588,894✔
24	}
25	y->parent = x->parent;	445,748,544✔
26	if (x->parent == pTree->NIL) {	445,744,761✔
27	pTree->root = y;	188,179,842✔
28	} else if (x == x->parent->left) {	257,578,746✔
29	x->parent->left = y;	59,115,380✔
30	} else {
31	x->parent->right = y;	198,439,930✔
32	}
33	y->left = x;	445,787,032✔
34	x->parent = y;	445,785,051✔
35	}	445,776,745✔
36
37	static void tRBTreeRotateRight(SRBTree pTree, SRBTreeNode x) {	39,722,691✔
38	SRBTreeNode *y = x->left;	39,722,691✔
39	x->left = y->right;	39,725,027✔
40	if (y->right != pTree->NIL) {	39,725,027✔
41	y->right->parent = x;	9,611,478✔
42	}
43	y->parent = x->parent;	39,725,611✔
44	if (x->parent == pTree->NIL) {	39,726,779✔
45	pTree->root = y;	4,899,540✔
46	} else if (x == x->parent->right) {	34,823,742✔
47	x->parent->right = y;	23,192,395✔
48	} else {
49	x->parent->left = y;	11,631,347✔
50	}
51	y->right = x;	39,725,027✔
52	x->parent = y;	39,725,611✔
53	}	39,725,618✔
54
55	static void tRBTreePutFix(SRBTree pTree, SRBTreeNode z) {	2,147,483,647✔
56	while (z->parent->color == RED) {	2,147,483,647✔
57	if (z->parent == z->parent->parent->left) { // z.parent is the left child	577,042,557✔
58
59	SRBTreeNode *y = z->parent->parent->right; // uncle of z	19,470,326✔
60
61	if (y->color == RED) { // case 1	19,471,570✔
62	z->parent->color = BLACK;	3,414,263✔
63	y->color = BLACK;	3,414,923✔
64	z->parent->parent->color = RED;	3,414,923✔
65	z = z->parent->parent;	3,414,263✔
66	} else { // case2 or case3
67	if (z == z->parent->right) { // case2	16,056,063✔
68	z = z->parent; // marked z.parent as new z	9,580,540✔
69	tRBTreeRotateLeft(pTree, z);	9,580,540✔
70	}
71	// case3
72	z->parent->color = BLACK; // made parent black	16,056,647✔
73	z->parent->parent->color = RED; // made parent red	16,056,647✔
74	tRBTreeRotateRight(pTree, z->parent->parent);	16,056,647✔
75	}
76	} else { // z.parent is the right child
77	SRBTreeNode *y = z->parent->parent->left; // uncle of z	557,533,201✔
78
79	if (y->color == RED) {	557,567,931✔
80	z->parent->color = BLACK;	199,556,044✔
81	y->color = BLACK;	199,556,920✔
82	z->parent->parent->color = RED;	199,554,018✔
83	z = z->parent->parent;	199,552,543✔
84	} else {
85	if (z == z->parent->left) {	357,990,254✔
86	z = z->parent; // marked z.parent as new z	9,167,359✔
87	tRBTreeRotateRight(pTree, z);	9,167,943✔
88	}
89	z->parent->color = BLACK; // made parent black	358,011,840✔
90	z->parent->parent->color = RED; // made parent red	358,013,090✔
91	tRBTreeRotateLeft(pTree, z->parent->parent);	358,039,536✔
92	}
93	}
94	}
95	pTree->root->color = BLACK;	2,147,483,647✔
96	}	2,147,483,647✔
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) {	2,147,483,647✔
109	if (pNode->right != pTree->NIL) {	2,147,483,647✔
110	pNode = pNode->right;	2,147,483,647✔
111	while (pNode->left != pTree->NIL) {	2,147,483,647✔
112	pNode = pNode->left;	169,054,467✔
113	}
114	} else {
115	while (true) {
116	if (pNode->parent == pTree->NIL \|\| pNode == pNode->parent->left) {	1,410,999,209✔
117	pNode = pNode->parent;	1,220,722,673✔
118	break;	1,219,239,842✔
119	} else {
120	pNode = pNode->parent;	190,499,230✔
121	}
122	}
123	}
124
125	return pNode;	2,147,483,647✔
126	}
127
128	static SRBTreeNode tRBTreePredecessor(const SRBTree pTree, SRBTreeNode *pNode) {	334,992,281✔
129	if (pNode->left != pTree->NIL) {	334,992,281✔
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) {	334,947,937✔
137	pNode = pNode->parent;	334,999,321✔
138	break;	334,916,239✔
139	} else {
140	pNode = pNode->parent;	×
141	}
142	}
143	}
144
145	return pNode;	334,916,239✔
146	}
147
148	void tRBTreeCreate(SRBTree *pTree, tRBTreeCmprFn cmprFn) {	785,407,120✔
149	pTree->cmprFn = cmprFn;	785,407,120✔
150	tRBTreeClear(pTree);	785,563,397✔
151	}	785,402,359✔
152
153	void tRBTreeClear(SRBTree *pTree) {	785,426,457✔
154	pTree->n = 0;	785,426,457✔
155	pTree->NIL = &pTree->NILNODE;	785,641,279✔
156	pTree->NIL->color = BLACK;	785,654,024✔
157	pTree->NIL->parent = NULL;	785,621,743✔
158	pTree->NIL->left = NULL;	785,615,363✔
159	pTree->NIL->right = NULL;	785,620,555✔
160	pTree->root = pTree->NIL;	785,618,144✔
161	pTree->min = pTree->NIL;	785,611,296✔
162	pTree->max = pTree->NIL;	785,553,366✔
163	}	785,533,940✔
164
165	SRBTreeNode tRBTreePut(SRBTree pTree, SRBTreeNode *z) {	2,147,483,647✔
166	SRBTreeNode *y = pTree->NIL; // variable for the parent of the added node	2,147,483,647✔
167	SRBTreeNode *temp = pTree->root;	2,147,483,647✔
168
169	while (temp != pTree->NIL) {	2,147,483,647✔
170	y = temp;	2,147,483,647✔
171
172	int32_t c = pTree->cmprFn(z, temp);	2,147,483,647✔
173	if (c < 0) {	2,147,483,647✔
174	temp = temp->left;	291,154,944✔
175	} else if (c > 0) {	2,147,483,647✔
176	temp = temp->right;	2,147,483,647✔
177	} else {
178	return NULL;	×
179	}
180	}
181	z->parent = y;	2,147,483,647✔
182
183	if (y == pTree->NIL) {	2,147,483,647✔
184	pTree->root = z;	343,322,108✔
185	} else if (pTree->cmprFn(z, y) < 0) {	2,147,483,647✔
186	y->left = z;	99,639,706✔
187	} else {
188	y->right = z;	2,147,483,647✔
189	}
190
191	z->color = RED;	2,147,483,647✔
192	z->left = pTree->NIL;	2,147,483,647✔
193	z->right = pTree->NIL;	2,147,483,647✔
194
195	tRBTreePutFix(pTree, z);	2,147,483,647✔
196
197	// update min/max node
198	if (pTree->min == pTree->NIL \|\| pTree->cmprFn(pTree->min, z) > 0) {	2,147,483,647✔
199	pTree->min = z;	418,845,857✔
200	}
201	if (pTree->max == pTree->NIL \|\| pTree->cmprFn(pTree->max, z) < 0) {	2,147,483,647✔
202	pTree->max = z;	2,147,483,647✔
203	}
204	pTree->n++;	2,147,483,647✔
205	return z;	2,147,483,647✔
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) {	438,711,394✔
215	rbnode_t *sibling;
216	int go_up = 1;	438,711,394✔
217
218	/* determine sibling to the node that is one-black short */
219	if (child_parent->right == child)	438,711,394✔
220	sibling = child_parent->left;	12,218,245✔
221	else
222	sibling = child_parent->right;	426,487,708✔
223
224	while (go_up) {	612,320,009✔
225	if (child_parent == RBTREE_NULL) {	513,152,969✔
226	/* removed parent==black from root, every path, so ok */
227	return;	339,600,808✔
228	}
229
230	if (sibling->color == RED) { /* rotate to get a black sibling */	173,672,970✔
231	child_parent->color = RED;	62,828,801✔
232	sibling->color = BLACK;	62,828,141✔
233	if (child_parent->right == child)	62,828,801✔
234	rbtree_rotate_right(rbtree, child_parent);	6,797,115✔
235	else
236	rbtree_rotate_left(rbtree, child_parent);	56,031,555✔
237	/* new sibling after rotation */
238	if (child_parent->right == child)	62,825,209✔
239	sibling = child_parent->left;	6,797,115✔
240	else
241	sibling = child_parent->right;	56,029,552✔
242	}
243
244	if (child_parent->color == BLACK && sibling->color == BLACK && sibling->left->color == BLACK &&	173,670,002✔
245	sibling->right->color == BLACK) { /* fixup local with recolor of sibling */	91,203,857✔
246	if (sibling != RBTREE_NULL) sibling->color = RED;	74,473,807✔
247
248	child = child_parent;	74,473,052✔
249	child_parent = child_parent->parent;	74,473,052✔
250	/* prepare to go up, new sibling */
251	if (child_parent->right == child)	74,472,483✔
252	sibling = child_parent->left;	6,585,930✔
253	else
254	sibling = child_parent->right;	67,881,580✔
255	} else
256	go_up = 0;	99,193,283✔
257	}
258
259	if (child_parent->color == RED && sibling->color == BLACK && sibling->left->color == BLACK &&	99,167,040✔
260	sibling->right->color == BLACK) {	74,548,190✔
261	/* move red to sibling to rebalance */
262	if (sibling != RBTREE_NULL) sibling->color = RED;	73,409,873✔
263	child_parent->color = BLACK;	73,409,250✔
264	return;	73,410,948✔
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 &&	25,782,652✔
270	sibling->left->color == BLACK) {	2,272,920✔
271	sibling->color = RED;	1,126,125✔
272	sibling->right->color = BLACK;	1,126,125✔
273	rbtree_rotate_left(rbtree, sibling);	1,126,125✔
274	/* new sibling after rotation */
275	if (child_parent->right == child)	1,126,125✔
276	sibling = child_parent->left;	1,126,125✔
277	else
278	sibling = child_parent->right;	×
279	} else if (child_parent->left == child && sibling->color == BLACK && sibling->left->color == RED &&	24,662,669✔
280	sibling->right->color == BLACK) {	4,241,976✔
281	sibling->color = RED;	2,902,102✔
282	sibling->left->color = BLACK;	2,902,102✔
283	rbtree_rotate_right(rbtree, sibling);	2,902,102✔
284	/* new sibling after rotation */
285	if (child_parent->right == child)	2,902,102✔
286	sibling = child_parent->left;	×
287	else
288	sibling = child_parent->right;	2,902,102✔
289	}
290
291	/* now we have a black sibling with a red child. rotate and exchange colors. */
292	sibling->color = child_parent->color;	25,788,583✔
293	child_parent->color = BLACK;	25,788,442✔
294	if (child_parent->right == child) {	25,785,885✔
295	sibling->left->color = BLACK;	4,802,388✔
296	rbtree_rotate_right(rbtree, child_parent);	4,802,388✔
297	} else {
298	sibling->right->color = BLACK;	20,983,344✔
299	rbtree_rotate_left(rbtree, child_parent);	20,986,301✔
300	}
301	}
302
303	/** helpers for delete: swap node colours */
304	static void swap_int8(ECOLOR x, ECOLOR y) {	53,854,502✔
305	ECOLOR t = *x;	53,854,502✔
306	x = y;	53,854,502✔
307	*y = t;	53,854,502✔
308	}	53,854,502✔
309
310	/** helpers for delete: swap node pointers */
311	static void swap_np(rbnode_t x, rbnode_t y) {	161,563,506✔
312	rbnode_t t = x;	161,563,506✔
313	x = y;	161,563,506✔
314	*y = t;	161,563,506✔
315	}	161,563,506✔
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) {	2,147,483,647✔
319	if (parent == RBTREE_NULL) {	2,147,483,647✔
320	if (rbtree->root == old) rbtree->root = new;	2,147,483,647✔
321	return;	2,147,483,647✔
322	}
323	if (parent->left == old) parent->left = new;	506,720,798✔
324	if (parent->right == old) parent->right = new;	506,766,163✔
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) {	2,147,483,647✔
328	if (child == RBTREE_NULL) return;	2,147,483,647✔
329	if (child->parent == old) child->parent = new;	2,147,483,647✔
330	}
331
332	rbnode_t rbtree_delete(rbtree_t rbtree, void *key) {	2,147,483,647✔
333	rbnode_t *to_delete = key;	2,147,483,647✔
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) {	2,147,483,647✔
338	/* swap with smallest from right subtree (or largest from left) */
339	rbnode_t *smright = to_delete->right;	53,854,502✔
340	while (smright->left != RBTREE_NULL) smright = smright->left;	96,777,434✔
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);	53,854,502✔
348
349	/* swap child pointers in parents of smright/to_delete */
350	change_parent_ptr(rbtree, to_delete->parent, to_delete, smright);	53,854,502✔
351	if (to_delete->right != smright) change_parent_ptr(rbtree, smright->parent, smright, to_delete);	53,854,502✔
352
353	/* swap parent pointers in children of smright/to_delete */
354	change_child_ptr(rbtree, smright->left, smright, to_delete);	53,854,502✔
355	change_child_ptr(rbtree, smright->left, smright, to_delete);	53,854,502✔
356	change_child_ptr(rbtree, smright->right, smright, to_delete);	53,854,502✔
357	change_child_ptr(rbtree, smright->right, smright, to_delete);	53,854,502✔
358	change_child_ptr(rbtree, to_delete->left, to_delete, smright);	53,854,502✔
359	if (to_delete->right != smright) change_child_ptr(rbtree, to_delete->right, to_delete, smright);	53,854,502✔
360	if (to_delete->right == smright) {	53,854,502✔
361	/* set up so after swap they work */
362	to_delete->right = to_delete;	17,526,074✔
363	smright->parent = smright;	17,526,074✔
364	}
365
366	/* swap pointers in to_delete/smright nodes */
367	swap_np(&to_delete->parent, &smright->parent);	53,854,502✔
368	swap_np(&to_delete->left, &smright->left);	53,854,502✔
369	swap_np(&to_delete->right, &smright->right);	53,854,502✔
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)	2,147,483,647✔
375	child = to_delete->left;	4,477,030✔
376	else
377	child = to_delete->right;	2,147,483,647✔
378
379	/* unlink to_delete from the tree, replace to_delete with child */
380	change_parent_ptr(rbtree, to_delete->parent, to_delete, child);	2,147,483,647✔
381	change_child_ptr(rbtree, child, to_delete, to_delete->parent);	2,147,483,647✔
382
383	if (to_delete->color == RED) {	2,147,483,647✔
384	/* if node is red then the child (black) can be swapped in */
385	} else if (child->color == RED) {	2,147,483,647✔
386	/* change child to BLACK, removing a RED node is no problem */
387	if (child != RBTREE_NULL) child->color = BLACK;	2,147,483,647✔
388	} else
389	rbtree_delete_fixup(rbtree, child, to_delete->parent);	437,926,947✔
390
391	/* unlink completely */
392	to_delete->parent = RBTREE_NULL;	2,147,483,647✔
393	to_delete->left = RBTREE_NULL;	2,147,483,647✔
394	to_delete->right = RBTREE_NULL;	2,147,483,647✔
395	to_delete->color = BLACK;	2,147,483,647✔
396	return to_delete;	2,147,483,647✔
397	}
398
399	void tRBTreeDrop(SRBTree pTree, SRBTreeNode z) {	2,147,483,647✔
400	// update min/max node
401	if (pTree->min == z) {	2,147,483,647✔
402	pTree->min = tRBTreeSuccessor(pTree, pTree->min);	2,147,483,647✔
403	}
404	if (pTree->max == z) {	2,147,483,647✔
405	pTree->max = tRBTreePredecessor(pTree, pTree->max);	334,990,947✔
406	}
407
408	(void)rbtree_delete(pTree, z);	2,147,483,647✔
409
410	pTree->n--;	2,147,483,647✔
411	}	2,147,483,647✔
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) {	2,147,483,647✔
424	SRBTreeNode *pNode = tRBTreeMin(pTree);	2,147,483,647✔
425	if (pNode) {	2,147,483,647✔
426	tRBTreeDrop(pTree, pNode);	2,147,483,647✔
427	}
428	return pNode;	2,147,483,647✔
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) {	1,474,995✔
440	SRBTreeNode *pNode = pTree->root;	1,474,995✔
441
442	while (pNode != pTree->NIL) {	5,819,871✔
443	int32_t c = pTree->cmprFn(pKeyNode, pNode);	5,811,678✔
444
445	if (c < 0) {	5,811,000✔
446	pNode = pNode->left;	1,995,393✔
447	} else if (c > 0) {	3,815,607✔
448	pNode = pNode->right;	2,349,483✔
449	} else {
450	break;	1,466,124✔
451	}
452	}
453
454	return (pNode == pTree->NIL) ? NULL : pNode;	1,474,317✔
455	}
456
457	// SRBTreeIter ================================================
458	SRBTreeNode tRBTreeIterNext(SRBTreeIter pIter) {	1,097,683,358✔
459	SRBTreeNode *pNode = pIter->pNode;	1,097,683,358✔
460
461	if (pIter->pNode != pIter->pTree->NIL) {	1,097,915,504✔
462	if (pIter->asc) {	903,238,158✔
463	// ascend
464	pIter->pNode = tRBTreeSuccessor(pIter->pTree, pIter->pNode);	903,268,932✔
465	} else {
466	// descend
UNCOV 467	pIter->pNode = tRBTreePredecessor(pIter->pTree, pIter->pNode);	×
468	}
469	}
470
471	_exit:	194,776,727✔
472	return (pNode == pIter->pTree->NIL) ? NULL : pNode;	1,098,142,739✔
473	}

taosdata / TDengine / #5011

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