#4720

Committed 08 Sep 2025 08:43AM UTC coverage: 58.139% (-0.6%) from 58.762%

Build # #4720

Build Type

push

travis-ci

Committed by

web-flow

Commit Message

Merge pull request #32881 from taosdata/enh/add-new-windows-ci

fix(ci): update workflow reference to use new Windows CI YAML

Run Details

133181 of 292179 branches covered (45.58%)

Branch coverage included in aggregate %.

201691 of 283811 relevant lines covered (71.07%)

5442780.71 hits per line

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

81.51

/source/util/src/theap.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/>.
 */

#define _DEFAULT_SOURCE
#include "theap.h"

size_t heapSize(Heap* heap) { return heap->nelts; }

Heap* heapCreate(HeapCompareFn fn) {
  Heap* heap = taosMemoryCalloc(1, sizeof(Heap));
  if (heap == NULL) {
    return NULL;
  }

  heap->min = NULL;
  heap->nelts = 0;
  heap->compFn = fn;
  return heap;
}

void heapDestroy(Heap* heap) { taosMemoryFree(heap); }

HeapNode* heapMin(const Heap* heap) { return heap->min; }

/* Swap parent with child. Child moves closer to the root, parent moves away. */
static void heapNodeSwap(Heap* heap, HeapNode* parent, HeapNode* child) {
  HeapNode* sibling;
  HeapNode  t;

  t = *parent;
  *parent = *child;
  *child = t;

  parent->parent = child;
  if (child->left == child) {
    child->left = parent;
    sibling = child->right;
  } else {
    child->right = parent;
    sibling = child->left;
  }
  if (sibling != NULL) sibling->parent = child;

  if (parent->left != NULL) parent->left->parent = parent;
  if (parent->right != NULL) parent->right->parent = parent;

  if (child->parent == NULL)
    heap->min = child;
  else if (child->parent->left == parent)
    child->parent->left = child;
  else
    child->parent->right = child;
}

void heapInsert(Heap* heap, HeapNode* newnode) {
  HeapNode** parent;
  HeapNode** child;
  uint32_t   path;
  uint32_t   n;
  uint32_t   k;

  newnode->left = NULL;
  newnode->right = NULL;
  newnode->parent = NULL;

  /* Calculate the path from the root to the insertion point.  This is a min
   * heap so we always insert at the left-most free node of the bottom row.
   */
  path = 0;
  for (k = 0, n = 1 + heap->nelts; n >= 2; k += 1, n /= 2) path = (path << 1) | (n & 1);

  /* Now traverse the heap using the path we calculated in the previous step. */
  parent = child = &heap->min;
  while (k > 0) {
    parent = child;
    if (path & 1)
      child = &(*child)->right;
    else
      child = &(*child)->left;
    path >>= 1;
    k -= 1;
  }

  /* Insert the new node. */
  newnode->parent = *parent;
  *child = newnode;
  heap->nelts += 1;

  /* Walk up the tree and check at each node if the heap property holds.
   * It's a min heap so parent < child must be true.
   */
  while (newnode->parent != NULL && (heap->compFn)(newnode, newnode->parent))
    heapNodeSwap(heap, newnode->parent, newnode);
}

void heapRemove(Heap* heap, HeapNode* node) {
  HeapNode*  smallest;
  HeapNode** max;
  HeapNode*  child;
  uint32_t   path;
  uint32_t   k;
  uint32_t   n;

  if (heap->nelts == 0) return;

  /* Calculate the path from the min (the root) to the max, the left-most node
   * of the bottom row.
   */
  path = 0;
  for (k = 0, n = heap->nelts; n >= 2; k += 1, n /= 2) path = (path << 1) | (n & 1);

  /* Now traverse the heap using the path we calculated in the previous step. */
  max = &heap->min;
  while (k > 0) {
    if (path & 1)
      max = &(*max)->right;
    else
      max = &(*max)->left;
    path >>= 1;
    k -= 1;
  }

  heap->nelts -= 1;

  /* Unlink the max node. */
  child = *max;
  *max = NULL;

  if (child == node) {
    /* We're removing either the max or the last node in the tree. */
    if (child == heap->min) {
      heap->min = NULL;
    }
    return;
  }

  /* Replace the to be deleted node with the max node. */
  child->left = node->left;
  child->right = node->right;
  child->parent = node->parent;

  if (child->left != NULL) {
    child->left->parent = child;
  }

  if (child->right != NULL) {
    child->right->parent = child;
  }

  if (node->parent == NULL) {
    heap->min = child;
  } else if (node->parent->left == node) {
    node->parent->left = child;
  } else {
    node->parent->right = child;
  }

  /* Walk down the subtree and check at each node if the heap property holds.
   * It's a min heap so parent < child must be true.  If the parent is bigger,
   * swap it with the smallest child.
   */
  for (;;) {
    smallest = child;
    if (child->left != NULL && (heap->compFn)(child->left, smallest)) smallest = child->left;
    if (child->right != NULL && (heap->compFn)(child->right, smallest)) smallest = child->right;
    if (smallest == child) break;
    heapNodeSwap(heap, child, smallest);
  }

  /* Walk up the subtree and check that each parent is less than the node
   * this is required, because `max` node is not guaranteed to be the
   * actual maximum in tree
   */
  while (child->parent != NULL && (heap->compFn)(child, child->parent)) heapNodeSwap(heap, child->parent, child);
}

void heapDequeue(Heap* heap) { heapRemove(heap, heap->min); }

struct PriorityQueue {
  SArray*    container;
  pq_comp_fn fn;
  FDelete    deleteFn;
  void*      param;
};
PriorityQueue* createPriorityQueue(pq_comp_fn fn, FDelete deleteFn, void* param) {
  PriorityQueue* pq = (PriorityQueue*)taosMemoryCalloc(1, sizeof(PriorityQueue));
  if (pq == NULL) {
    return NULL;
  }

  pq->container = taosArrayInit(1, sizeof(PriorityQueueNode));
  if (pq->container == NULL) {
    taosMemoryFree(pq);
    return NULL;
  }

  pq->fn = fn;
  pq->deleteFn = deleteFn;
  pq->param = param;
  return pq;
}

void taosPQSetFn(PriorityQueue* pq, pq_comp_fn fn) { pq->fn = fn; }

void destroyPriorityQueue(PriorityQueue* pq) {
  if (pq->deleteFn)
    taosArrayDestroyP(pq->container, pq->deleteFn);
  else
    taosArrayDestroyP(pq->container, NULL);
  taosMemoryFree(pq);
}

static size_t pqParent(size_t i) { return (--i) >> 1; /* (i - 1) / 2 */ }
static size_t pqLeft(size_t i) { return (i << 1) | 1; /* i * 2 + 1 */ }
static size_t pqRight(size_t i) { return (++i) << 1; /* (i + 1) * 2 */ }

static void pqSwapPQNode(PriorityQueueNode* a, PriorityQueueNode* b) {
  void* tmp = a->data;
  a->data = b->data;
  b->data = tmp;
}

#define pqContainerGetEle(pq, i) ((PriorityQueueNode*)taosArrayGet((pq)->container, (i)))
#define pqContainerSize(pq)      (taosArrayGetSize((pq)->container))

size_t taosPQSize(PriorityQueue* pq) { return pqContainerSize(pq); }

static PriorityQueueNode* pqHeapify(PriorityQueue* pq, size_t from, size_t last) {
  size_t largest = from;
  do {
    from = largest;
    size_t l = pqLeft(from);
    size_t r = pqRight(from);
    if (l < last && pq->fn(pqContainerGetEle(pq, from)->data, pqContainerGetEle(pq, l)->data, pq->param)) {
      largest = l;
    }
    if (r < last && pq->fn(pqContainerGetEle(pq, largest)->data, pqContainerGetEle(pq, r)->data, pq->param)) {
      largest = r;
    }
    if (largest != from) {
      pqSwapPQNode(pqContainerGetEle(pq, from), pqContainerGetEle(pq, largest));
    }
  } while (largest != from);
  return pqContainerGetEle(pq, largest);
}

static void pqBuildHeap(PriorityQueue* pq) {
  if (pqContainerSize(pq) > 1) {
    PriorityQueueNode* node;
    for (size_t i = pqContainerSize(pq) - 1; i > 0; --i) {
      node = pqHeapify(pq, i, pqContainerSize(pq));
    }
    node = pqHeapify(pq, 0, pqContainerSize(pq));
  }
}

static PriorityQueueNode* pqReverseHeapify(PriorityQueue* pq, size_t i) {
  while (i > 0 && !pq->fn(pqContainerGetEle(pq, i)->data, pqContainerGetEle(pq, pqParent(i))->data, pq->param)) {
    size_t parentIdx = pqParent(i);
    pqSwapPQNode(pqContainerGetEle(pq, i), pqContainerGetEle(pq, parentIdx));
    i = parentIdx;
  }
  return pqContainerGetEle(pq, i);
}

static void pqUpdate(PriorityQueue* pq, size_t i) {
  PriorityQueueNode* node;
  if (i == 0 || pq->fn(pqContainerGetEle(pq, i)->data, pqContainerGetEle(pq, pqParent(i))->data, pq->param)) {
    // if value in pos i is smaller than parent, heapify down from i to the end
    node = pqHeapify(pq, i, pqContainerSize(pq));
  } else {
    // if value in pos i is big than parent, heapify up from i
    node = pqReverseHeapify(pq, i);
  }
}

static void pqRemove(PriorityQueue* pq, size_t i) {
  if (i == pqContainerSize(pq) - 1) {
    void* tmp = taosArrayPop(pq->container);
    return;
  }

  taosArraySet(pq->container, i, taosArrayGet(pq->container, pqContainerSize(pq) - 1));
  void* tmp = taosArrayPop(pq->container);
  pqUpdate(pq, i);
}

PriorityQueueNode* taosPQTop(PriorityQueue* pq) { return pqContainerGetEle(pq, 0); }

PriorityQueueNode* taosPQPush(PriorityQueue* pq, const PriorityQueueNode* node) {
  if (taosArrayPush(pq->container, node) == NULL) {
    return NULL;
  }
  return pqReverseHeapify(pq, pqContainerSize(pq) - 1);
}

void taosPQPop(PriorityQueue* pq) {
  PriorityQueueNode* top = taosPQTop(pq);
  if (pq->deleteFn) {
    pq->deleteFn(top->data);
  } else {
    taosMemoryFree(top->data);
  }
  pqRemove(pq, 0);
}

struct BoundedQueue {
  PriorityQueue* queue;
  uint32_t       maxSize;
};

BoundedQueue* createBoundedQueue(uint32_t maxSize, pq_comp_fn fn, FDelete deleteFn, void* param) {
  BoundedQueue* q = (BoundedQueue*)taosMemoryCalloc(1, sizeof(BoundedQueue));
  if (q == NULL) {
    return NULL;
  }

  q->queue = createPriorityQueue(fn, deleteFn, param);
  if (q->queue == NULL) {
    taosMemoryFree(q);
    return NULL;
  }

  int32_t code = taosArrayEnsureCap(q->queue->container, maxSize + 1);
  if (code) {
    destroyPriorityQueue(q->queue);
    taosMemoryFree(q);
    terrno = code;
    return NULL;
  }
  q->maxSize = maxSize;
  return q;
}

void taosBQSetFn(BoundedQueue* q, pq_comp_fn fn) { taosPQSetFn(q->queue, fn); }

void taosBQClear(BoundedQueue* q) {
  if (q->queue->deleteFn)
    taosArrayClearEx(q->queue->container, q->queue->deleteFn);
  else
    taosArrayClear(q->queue->container);
}

void destroyBoundedQueue(BoundedQueue* q) {
  if (!q) return;
  destroyPriorityQueue(q->queue);
  taosMemoryFree(q);
}

PriorityQueueNode* taosBQPush(BoundedQueue* q, PriorityQueueNode* n) {
  if (pqContainerSize(q->queue) == q->maxSize + 1) {
    PriorityQueueNode* top = pqContainerGetEle(q->queue, 0);
    if (q->queue->fn(top->data, n->data, q->queue->param)) {
      return NULL;
    } else {
      void* p = top->data;
      top->data = n->data;
      if (q->queue->deleteFn) {
        n->data = p;
        q->queue->deleteFn(n->data);
      }
    }
    return pqHeapify(q->queue, 0, taosBQSize(q));
  } else {
    return taosPQPush(q->queue, n);
  }
}

PriorityQueueNode* taosBQTop(BoundedQueue* q) { return taosPQTop(q->queue); }

void taosBQBuildHeap(BoundedQueue* q) { pqBuildHeap(q->queue); }

size_t taosBQMaxSize(BoundedQueue* q) { return q->maxSize; }

size_t taosBQSize(BoundedQueue* q) { return taosPQSize(q->queue); }

void taosBQPop(BoundedQueue* q) { taosPQPop(q->queue); }

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	#define _DEFAULT_SOURCE
17	#include "theap.h"
18
19	size_t heapSize(Heap* heap) { return heap->nelts; }	5,851,552✔
20
21	Heap* heapCreate(HeapCompareFn fn) {	250,479✔
22	Heap* heap = taosMemoryCalloc(1, sizeof(Heap));	250,479!
23	if (heap == NULL) {	250,450!
24	return NULL;	×
25	}
26
27	heap->min = NULL;	250,450✔
28	heap->nelts = 0;	250,450✔
29	heap->compFn = fn;	250,450✔
30	return heap;	250,450✔
31	}
32
33	void heapDestroy(Heap* heap) { taosMemoryFree(heap); }	250,510!
34
35	HeapNode* heapMin(const Heap* heap) { return heap->min; }	3,566,190✔
36
37	/* Swap parent with child. Child moves closer to the root, parent moves away. */
38	static void heapNodeSwap(Heap* heap, HeapNode* parent, HeapNode* child) {	10,424✔
39	HeapNode* sibling;
40	HeapNode t;
41
42	t = *parent;	10,424✔
43	parent = child;	10,424✔
44	*child = t;	10,424✔
45
46	parent->parent = child;	10,424✔
47	if (child->left == child) {	10,424✔
48	child->left = parent;	6,957✔
49	sibling = child->right;	6,957✔
50	} else {
51	child->right = parent;	3,467✔
52	sibling = child->left;	3,467✔
53	}
54	if (sibling != NULL) sibling->parent = child;	10,424✔
55
56	if (parent->left != NULL) parent->left->parent = parent;	10,424✔
57	if (parent->right != NULL) parent->right->parent = parent;	10,424✔
58
59	if (child->parent == NULL)	10,424✔
60	heap->min = child;	6,434✔
61	else if (child->parent->left == parent)	3,990✔
62	child->parent->left = child;	2,334✔
63	else
64	child->parent->right = child;	1,656✔
65	}	10,424✔
66
67	void heapInsert(Heap* heap, HeapNode* newnode) {	2,271,676✔
68	HeapNode** parent;
69	HeapNode** child;
70	uint32_t path;
71	uint32_t n;
72	uint32_t k;
73
74	newnode->left = NULL;	2,271,676✔
75	newnode->right = NULL;	2,271,676✔
76	newnode->parent = NULL;	2,271,676✔
77
78	/* Calculate the path from the root to the insertion point. This is a min
79	* heap so we always insert at the left-most free node of the bottom row.
80	*/
81	path = 0;	2,271,676✔
82	for (k = 0, n = 1 + heap->nelts; n >= 2; k += 1, n /= 2) path = (path << 1) \| (n & 1);	2,284,012✔
83
84	/* Now traverse the heap using the path we calculated in the previous step. */
85	parent = child = &heap->min;	2,271,676✔
86	while (k > 0) {	2,284,012✔
87	parent = child;	12,336✔
88	if (path & 1)	12,336✔
89	child = &(*child)->right;	2,989✔
90	else
91	child = &(*child)->left;	9,347✔
92	path >>= 1;	12,336✔
93	k -= 1;	12,336✔
94	}
95
96	/* Insert the new node. */
97	newnode->parent = *parent;	2,271,676✔
98	*child = newnode;	2,271,676✔
99	heap->nelts += 1;	2,271,676✔
100
101	/* Walk up the tree and check at each node if the heap property holds.
102	* It's a min heap so parent < child must be true.
103	*/
104	while (newnode->parent != NULL && (heap->compFn)(newnode, newnode->parent))	2,276,013✔
105	heapNodeSwap(heap, newnode->parent, newnode);	4,337✔
106	}	2,271,676✔
107
108	void heapRemove(Heap* heap, HeapNode* node) {	2,275,582✔
109	HeapNode* smallest;
110	HeapNode** max;
111	HeapNode* child;
112	uint32_t path;
113	uint32_t k;
114	uint32_t n;
115
116	if (heap->nelts == 0) return;	2,275,582!
117
118	/* Calculate the path from the min (the root) to the max, the left-most node
119	* of the bottom row.
120	*/
121	path = 0;	2,275,582✔
122	for (k = 0, n = heap->nelts; n >= 2; k += 1, n /= 2) path = (path << 1) \| (n & 1);	2,287,918✔
123
124	/* Now traverse the heap using the path we calculated in the previous step. */
125	max = &heap->min;	2,275,582✔
126	while (k > 0) {	2,287,918✔
127	if (path & 1)	12,336✔
128	max = &(*max)->right;	2,989✔
129	else
130	max = &(*max)->left;	9,347✔
131	path >>= 1;	12,336✔
132	k -= 1;	12,336✔
133	}
134
135	heap->nelts -= 1;	2,275,582✔
136
137	/* Unlink the max node. */
138	child = *max;	2,275,582✔
139	*max = NULL;	2,275,582✔
140
141	if (child == node) {	2,275,582✔
142	/* We're removing either the max or the last node in the tree. */
143	if (child == heap->min) {	2,268,809!
144	heap->min = NULL;	×
145	}
146	return;	2,268,809✔
147	}
148
149	/* Replace the to be deleted node with the max node. */
150	child->left = node->left;	6,773✔
151	child->right = node->right;	6,773✔
152	child->parent = node->parent;	6,773✔
153
154	if (child->left != NULL) {	6,773✔
155	child->left->parent = child;	3,971✔
156	}
157
158	if (child->right != NULL) {	6,773✔
159	child->right->parent = child;	2,931✔
160	}
161
162	if (node->parent == NULL) {	6,773!
163	heap->min = child;	6,960✔
164	} else if (node->parent->left == node) {	×
165	node->parent->left = child;	1✔
166	} else {
167	node->parent->right = child;	×
168	}
169
170	/* Walk down the subtree and check at each node if the heap property holds.
171	* It's a min heap so parent < child must be true. If the parent is bigger,
172	* swap it with the smallest child.
173	*/
174	for (;;) {
175	smallest = child;	12,930✔
176	if (child->left != NULL && (heap->compFn)(child->left, smallest)) smallest = child->left;	12,930✔
177	if (child->right != NULL && (heap->compFn)(child->right, smallest)) smallest = child->right;	12,930✔
178	if (smallest == child) break;	12,930✔
179	heapNodeSwap(heap, child, smallest);	5,969✔
180	}
181
182	/* Walk up the subtree and check that each parent is less than the node
183	* this is required, because `max` node is not guaranteed to be the
184	* actual maximum in tree
185	*/
186	while (child->parent != NULL && (heap->compFn)(child, child->parent)) heapNodeSwap(heap, child->parent, child);	7,079✔
187	}
188
189	void heapDequeue(Heap* heap) { heapRemove(heap, heap->min); }	×
190
191	struct PriorityQueue {
192	SArray* container;
193	pq_comp_fn fn;
194	FDelete deleteFn;
195	void* param;
196	};
197	PriorityQueue* createPriorityQueue(pq_comp_fn fn, FDelete deleteFn, void* param) {	33,225✔
198	PriorityQueue* pq = (PriorityQueue*)taosMemoryCalloc(1, sizeof(PriorityQueue));	33,225!
199	if (pq == NULL) {	33,190!
200	return NULL;	×
201	}
202
203	pq->container = taosArrayInit(1, sizeof(PriorityQueueNode));	33,190✔
204	if (pq->container == NULL) {	33,215✔
205	taosMemoryFree(pq);	1!
206	return NULL;	×
207	}
208
209	pq->fn = fn;	33,214✔
210	pq->deleteFn = deleteFn;	33,214✔
211	pq->param = param;	33,214✔
212	return pq;	33,214✔
213	}
214
215	void taosPQSetFn(PriorityQueue* pq, pq_comp_fn fn) { pq->fn = fn; }	12,463✔
216
217	void destroyPriorityQueue(PriorityQueue* pq) {	33,264✔
218	if (pq->deleteFn)	33,264!
219	taosArrayDestroyP(pq->container, pq->deleteFn);	33,265✔
220	else
221	taosArrayDestroyP(pq->container, NULL);	×
222	taosMemoryFree(pq);	33,251!
223	}	33,251✔
224
225	static size_t pqParent(size_t i) { return (--i) >> 1; /* (i - 1) / 2 */ }	5,255,898✔
226	static size_t pqLeft(size_t i) { return (i << 1) \| 1; /* i * 2 + 1 */ }	1,685,740✔
227	static size_t pqRight(size_t i) { return (++i) << 1; /* (i + 1) * 2 */ }	1,685,567✔
228
229	static void pqSwapPQNode(PriorityQueueNode* a, PriorityQueueNode* b) {	3,654,334✔
230	void* tmp = a->data;	3,654,334✔
231	a->data = b->data;	3,654,334✔
232	b->data = tmp;	3,654,334✔
233	}	3,654,334✔
234
235	#define pqContainerGetEle(pq, i) ((PriorityQueueNode*)taosArrayGet((pq)->container, (i)))
236	#define pqContainerSize(pq) (taosArrayGetSize((pq)->container))
237
238	size_t taosPQSize(PriorityQueue* pq) { return pqContainerSize(pq); }	985,658✔
239
240	static PriorityQueueNode* pqHeapify(PriorityQueue* pq, size_t from, size_t last) {	641,089✔
241	size_t largest = from;	641,089✔
242	do {
243	from = largest;	1,686,865✔
244	size_t l = pqLeft(from);	1,686,865✔
245	size_t r = pqRight(from);	1,685,664✔
246	if (l < last && pq->fn(pqContainerGetEle(pq, from)->data, pqContainerGetEle(pq, l)->data, pq->param)) {	1,685,467✔
247	largest = l;	1,010,470✔
248	}
249	if (r < last && pq->fn(pqContainerGetEle(pq, largest)->data, pqContainerGetEle(pq, r)->data, pq->param)) {	1,684,344✔
250	largest = r;	405,762✔
251	}
252	if (largest != from) {	1,683,323✔
253	pqSwapPQNode(pqContainerGetEle(pq, from), pqContainerGetEle(pq, largest));	1,046,251✔
254	}
255	} while (largest != from);	1,684,433✔
256	return pqContainerGetEle(pq, largest);	638,657✔
257	}
258
259	static void pqBuildHeap(PriorityQueue* pq) {	12,463✔
260	if (pqContainerSize(pq) > 1) {	12,463✔
261	PriorityQueueNode* node;
262	for (size_t i = pqContainerSize(pq) - 1; i > 0; --i) {	92,670✔
263	node = pqHeapify(pq, i, pqContainerSize(pq));	86,437✔
264	}
265	node = pqHeapify(pq, 0, pqContainerSize(pq));	6,233✔
266	}
267	}	12,463✔
268
269	static PriorityQueueNode* pqReverseHeapify(PriorityQueue* pq, size_t i) {	316,298✔
270	while (i > 0 && !pq->fn(pqContainerGetEle(pq, i)->data, pqContainerGetEle(pq, pqParent(i))->data, pq->param)) {	2,925,119✔
271	size_t parentIdx = pqParent(i);	2,608,844✔
272	pqSwapPQNode(pqContainerGetEle(pq, i), pqContainerGetEle(pq, parentIdx));	2,608,839✔
273	i = parentIdx;	2,608,821✔
274	}
275	return pqContainerGetEle(pq, i);	316,146✔
276	}
277
278	static void pqUpdate(PriorityQueue* pq, size_t i) {	97,391✔
279	PriorityQueueNode* node;
280	if (i == 0 \|\| pq->fn(pqContainerGetEle(pq, i)->data, pqContainerGetEle(pq, pqParent(i))->data, pq->param)) {	97,391!
281	// if value in pos i is smaller than parent, heapify down from i to the end
282	node = pqHeapify(pq, i, pqContainerSize(pq));	97,391✔
283	} else {
284	// if value in pos i is big than parent, heapify up from i
285	node = pqReverseHeapify(pq, i);	×
286	}
287	}	97,388✔
288
289	static void pqRemove(PriorityQueue* pq, size_t i) {	109,855✔
290	if (i == pqContainerSize(pq) - 1) {	109,855✔
291	void* tmp = taosArrayPop(pq->container);	12,464✔
292	return;	12,463✔
293	}
294
295	taosArraySet(pq->container, i, taosArrayGet(pq->container, pqContainerSize(pq) - 1));	97,391✔
296	void* tmp = taosArrayPop(pq->container);	97,391✔
297	pqUpdate(pq, i);	97,391✔
298	}
299
300	PriorityQueueNode* taosPQTop(PriorityQueue* pq) { return pqContainerGetEle(pq, 0); }	295,267✔
301
302	PriorityQueueNode* taosPQPush(PriorityQueue* pq, const PriorityQueueNode* node) {	316,304✔
303	if (taosArrayPush(pq->container, node) == NULL) {	632,603!
304	return NULL;	×
305	}
306	return pqReverseHeapify(pq, pqContainerSize(pq) - 1);	316,299✔
307	}
308
309	void taosPQPop(PriorityQueue* pq) {	109,850✔
310	PriorityQueueNode* top = taosPQTop(pq);	109,850✔
311	if (pq->deleteFn) {	109,850!
312	pq->deleteFn(top->data);	109,850✔
313	} else {
314	taosMemoryFree(top->data);	×
315	}
316	pqRemove(pq, 0);	109,855✔
317	}	109,851✔
318
319	struct BoundedQueue {
320	PriorityQueue* queue;
321	uint32_t maxSize;
322	};
323
324	BoundedQueue* createBoundedQueue(uint32_t maxSize, pq_comp_fn fn, FDelete deleteFn, void* param) {	33,252✔
325	BoundedQueue* q = (BoundedQueue*)taosMemoryCalloc(1, sizeof(BoundedQueue));	33,252!
326	if (q == NULL) {	33,231!
327	return NULL;	×
328	}
329
330	q->queue = createPriorityQueue(fn, deleteFn, param);	33,231✔
331	if (q->queue == NULL) {	33,214!
332	taosMemoryFree(q);	×
333	return NULL;	×
334	}
335
336	int32_t code = taosArrayEnsureCap(q->queue->container, maxSize + 1);	33,214✔
337	if (code) {	33,231!
338	destroyPriorityQueue(q->queue);	×
339	taosMemoryFree(q);	×
340	terrno = code;	×
341	return NULL;	×
342	}
343	q->maxSize = maxSize;	33,233✔
344	return q;	33,233✔
345	}
346
347	void taosBQSetFn(BoundedQueue* q, pq_comp_fn fn) { taosPQSetFn(q->queue, fn); }	12,463✔
348
349	void taosBQClear(BoundedQueue* q) {	×
350	if (q->queue->deleteFn)	×
351	taosArrayClearEx(q->queue->container, q->queue->deleteFn);	×
352	else
353	taosArrayClear(q->queue->container);	×
354	}	×
355
356	void destroyBoundedQueue(BoundedQueue* q) {	129,125✔
357	if (!q) return;	129,125✔
358	destroyPriorityQueue(q->queue);	33,264✔
359	taosMemoryFree(q);	33,249!
360	}
361
362	PriorityQueueNode* taosBQPush(BoundedQueue* q, PriorityQueueNode* n) {	7,755,991✔
363	if (pqContainerSize(q->queue) == q->maxSize + 1) {	7,755,991✔
364	PriorityQueueNode* top = pqContainerGetEle(q->queue, 0);	7,439,614✔
365	if (q->queue->fn(top->data, n->data, q->queue->param)) {	7,439,546✔
366	return NULL;	6,989,378✔
367	} else {
368	void* p = top->data;	449,630✔
369	top->data = n->data;	449,630✔
370	if (q->queue->deleteFn) {	449,630!
371	n->data = p;	449,630✔
372	q->queue->deleteFn(n->data);	449,630✔
373	}
374	}
375	return pqHeapify(q->queue, 0, taosBQSize(q));	451,304✔
376	} else {
377	return taosPQPush(q->queue, n);	316,252✔
378	}
379	}
380
381	PriorityQueueNode* taosBQTop(BoundedQueue* q) { return taosPQTop(q->queue); }	185,420✔
382
383	void taosBQBuildHeap(BoundedQueue* q) { pqBuildHeap(q->queue); }	12,463✔
384
385	size_t taosBQMaxSize(BoundedQueue* q) { return q->maxSize; }	415,335✔
386
387	size_t taosBQSize(BoundedQueue* q) { return taosPQSize(q->queue); }	985,676✔
388
389	void taosBQPop(BoundedQueue* q) { taosPQPop(q->queue); }	109,850✔

taosdata / TDengine / #4720

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