#3911

Committed 24 Apr 2025 11:36PM UTC coverage: 53.735% (-1.6%) from 55.295%

Build # #3911

Build Type

push

travis-ci

Committed by

happyguoxy

Commit Message

Sync branches at 2025-04-25 07:35

Run Details

170049 of 316459 relevant lines covered (53.73%)

1192430.54 hits per line

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

62.32

/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; }	623,008✔
20
21	Heap* heapCreate(HeapCompareFn fn) {	27,565✔
22	Heap* heap = taosMemoryCalloc(1, sizeof(Heap));	27,565✔
23	if (heap == NULL) {	27,566✔
24	return NULL;	×
25	}
26
27	heap->min = NULL;	27,566✔
28	heap->nelts = 0;	27,566✔
29	heap->compFn = fn;	27,566✔
30	return heap;	27,566✔
31	}
32
33	void heapDestroy(Heap* heap) { taosMemoryFree(heap); }	27,566✔
34
35	HeapNode* heapMin(const Heap* heap) { return heap->min; }	303,721✔
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) {	2,721✔
39	HeapNode* sibling;
40	HeapNode t;
41
42	t = *parent;	2,721✔
43	parent = child;	2,721✔
44	*child = t;	2,721✔
45
46	parent->parent = child;	2,721✔
47	if (child->left == child) {	2,721✔
48	child->left = parent;	2,004✔
49	sibling = child->right;	2,004✔
50	} else {
51	child->right = parent;	717✔
52	sibling = child->left;	717✔
53	}
54	if (sibling != NULL) sibling->parent = child;	2,721✔
55
56	if (parent->left != NULL) parent->left->parent = parent;	2,721✔
57	if (parent->right != NULL) parent->right->parent = parent;	2,721✔
58
59	if (child->parent == NULL)	2,721✔
60	heap->min = child;	1,574✔
61	else if (child->parent->left == parent)	1,147✔
62	child->parent->left = child;	595✔
63	else
64	child->parent->right = child;	552✔
65	}	2,721✔
66
67	void heapInsert(Heap* heap, HeapNode* newnode) {	349,999✔
68	HeapNode** parent;
69	HeapNode** child;
70	uint32_t path;
71	uint32_t n;
72	uint32_t k;
73
74	newnode->left = NULL;	349,999✔
75	newnode->right = NULL;	349,999✔
76	newnode->parent = NULL;	349,999✔
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;	349,999✔
82	for (k = 0, n = 1 + heap->nelts; n >= 2; k += 1, n /= 2) path = (path << 1) \| (n & 1);	353,499✔
83
84	/* Now traverse the heap using the path we calculated in the previous step. */
85	parent = child = &heap->min;	349,999✔
86	while (k > 0) {	353,499✔
87	parent = child;	3,500✔
88	if (path & 1)	3,500✔
89	child = &(*child)->right;	648✔
90	else
91	child = &(*child)->left;	2,852✔
92	path >>= 1;	3,500✔
93	k -= 1;	3,500✔
94	}
95
96	/* Insert the new node. */
97	newnode->parent = *parent;	349,999✔
98	*child = newnode;	349,999✔
99	heap->nelts += 1;	349,999✔
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))	351,617✔
105	heapNodeSwap(heap, newnode->parent, newnode);	1,618✔
106	}	349,999✔
107
108	void heapRemove(Heap* heap, HeapNode* node) {	349,940✔
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;	349,940✔
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;	349,940✔
122	for (k = 0, n = heap->nelts; n >= 2; k += 1, n /= 2) path = (path << 1) \| (n & 1);	353,440✔
123
124	/* Now traverse the heap using the path we calculated in the previous step. */
125	max = &heap->min;	349,940✔
126	while (k > 0) {	353,440✔
127	if (path & 1)	3,500✔
128	max = &(*max)->right;	648✔
129	else
130	max = &(*max)->left;	2,852✔
131	path >>= 1;	3,500✔
132	k -= 1;	3,500✔
133	}
134
135	heap->nelts -= 1;	349,940✔
136
137	/* Unlink the max node. */
138	child = *max;	349,940✔
139	*max = NULL;	349,940✔
140
141	if (child == node) {	349,940✔
142	/* We're removing either the max or the last node in the tree. */
143	if (child == heap->min) {	347,400✔
144	heap->min = NULL;	×
145	}
146	return;	347,400✔
147	}
148
149	/* Replace the to be deleted node with the max node. */
150	child->left = node->left;	2,540✔
151	child->right = node->right;	2,540✔
152	child->parent = node->parent;	2,540✔
153
154	if (child->left != NULL) {	2,540✔
155	child->left->parent = child;	311✔
156	}
157
158	if (child->right != NULL) {	2,540✔
159	child->right->parent = child;	197✔
160	}
161
162	if (node->parent == NULL) {	2,540✔
163	heap->min = child;	2,546✔
164	} else if (node->parent->left == node) {	×
165	node->parent->left = child;	×
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;	3,598✔
176	if (child->left != NULL && (heap->compFn)(child->left, smallest)) smallest = child->left;	3,598✔
177	if (child->right != NULL && (heap->compFn)(child->right, smallest)) smallest = child->right;	3,598✔
178	if (smallest == child) break;	3,598✔
179	heapNodeSwap(heap, child, smallest);	1,052✔
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);	2,597✔
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) {	6✔
198	PriorityQueue* pq = (PriorityQueue*)taosMemoryCalloc(1, sizeof(PriorityQueue));	6✔
199	if (pq == NULL) {	6✔
200	return NULL;	×
201	}
202
203	pq->container = taosArrayInit(1, sizeof(PriorityQueueNode));	6✔
204	if (pq->container == NULL) {	6✔
205	taosMemoryFree(pq);	×
206	return NULL;	×
207	}
208
209	pq->fn = fn;	6✔
210	pq->deleteFn = deleteFn;	6✔
211	pq->param = param;	6✔
212	return pq;	6✔
213	}
214
215	void taosPQSetFn(PriorityQueue* pq, pq_comp_fn fn) { pq->fn = fn; }	×
216
217	void destroyPriorityQueue(PriorityQueue* pq) {	5✔
218	if (pq->deleteFn)	5✔
219	taosArrayDestroyP(pq->container, pq->deleteFn);	5✔
220	else
221	taosArrayDestroyP(pq->container, NULL);	×
222	taosMemoryFree(pq);	5✔
223	}	5✔
224
225	static size_t pqParent(size_t i) { return (--i) >> 1; /* (i - 1) / 2 */ }	220✔
226	static size_t pqLeft(size_t i) { return (i << 1) \| 1; /* i * 2 + 1 */ }	×
227	static size_t pqRight(size_t i) { return (++i) << 1; /* (i + 1) * 2 */ }	×
228
229	static void pqSwapPQNode(PriorityQueueNode* a, PriorityQueueNode* b) {	110✔
230	void* tmp = a->data;	110✔
231	a->data = b->data;	110✔
232	b->data = tmp;	110✔
233	}	110✔
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); }	55✔
239
240	static PriorityQueueNode* pqHeapify(PriorityQueue* pq, size_t from, size_t last) {	×
241	size_t largest = from;	×
242	do {
243	from = largest;	×
244	size_t l = pqLeft(from);	×
245	size_t r = pqRight(from);	×
246	if (l < last && pq->fn(pqContainerGetEle(pq, from)->data, pqContainerGetEle(pq, l)->data, pq->param)) {	×
247	largest = l;	×
248	}
249	if (r < last && pq->fn(pqContainerGetEle(pq, largest)->data, pqContainerGetEle(pq, r)->data, pq->param)) {	×
250	largest = r;	×
251	}
252	if (largest != from) {	×
253	pqSwapPQNode(pqContainerGetEle(pq, from), pqContainerGetEle(pq, largest));	×
254	}
255	} while (largest != from);	×
256	return pqContainerGetEle(pq, largest);	×
257	}
258
259	static void pqBuildHeap(PriorityQueue* pq) {	×
260	if (pqContainerSize(pq) > 1) {	×
261	PriorityQueueNode* node;
262	for (size_t i = pqContainerSize(pq) - 1; i > 0; --i) {	×
263	node = pqHeapify(pq, i, pqContainerSize(pq));	×
264	}
265	node = pqHeapify(pq, 0, pqContainerSize(pq));	×
266	}
267	}	×
268
269	static PriorityQueueNode* pqReverseHeapify(PriorityQueue* pq, size_t i) {	55✔
270	while (i > 0 && !pq->fn(pqContainerGetEle(pq, i)->data, pqContainerGetEle(pq, pqParent(i))->data, pq->param)) {	165✔
271	size_t parentIdx = pqParent(i);	110✔
272	pqSwapPQNode(pqContainerGetEle(pq, i), pqContainerGetEle(pq, parentIdx));	110✔
273	i = parentIdx;	110✔
274	}
275	return pqContainerGetEle(pq, i);	55✔
276	}
277
278	static void pqUpdate(PriorityQueue* pq, size_t i) {	×
279	PriorityQueueNode* node;
280	if (i == 0 \|\| pq->fn(pqContainerGetEle(pq, i)->data, pqContainerGetEle(pq, pqParent(i))->data, pq->param)) {	×
281	// if value in pos i is smaller than parent, heapify down from i to the end
282	node = pqHeapify(pq, i, pqContainerSize(pq));	×
283	} else {
284	// if value in pos i is big than parent, heapify up from i
285	node = pqReverseHeapify(pq, i);	×
286	}
287	}	×
288
289	static void pqRemove(PriorityQueue* pq, size_t i) {	×
290	if (i == pqContainerSize(pq) - 1) {	×
291	void* tmp = taosArrayPop(pq->container);	×
292	return;	×
293	}
294
295	taosArraySet(pq->container, i, taosArrayGet(pq->container, pqContainerSize(pq) - 1));	×
296	void* tmp = taosArrayPop(pq->container);	×
297	pqUpdate(pq, i);	×
298	}
299
300	PriorityQueueNode* taosPQTop(PriorityQueue* pq) { return pqContainerGetEle(pq, 0); }	×
301
302	PriorityQueueNode* taosPQPush(PriorityQueue* pq, const PriorityQueueNode* node) {	55✔
303	if (taosArrayPush(pq->container, node) == NULL) {	110✔
304	return NULL;	×
305	}
306	return pqReverseHeapify(pq, pqContainerSize(pq) - 1);	55✔
307	}
308
309	void taosPQPop(PriorityQueue* pq) {	×
310	PriorityQueueNode* top = taosPQTop(pq);	×
311	if (pq->deleteFn) {	×
312	pq->deleteFn(top->data);	×
313	} else {
314	taosMemoryFree(top->data);	×
315	}
316	pqRemove(pq, 0);	×
317	}	×
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) {	6✔
325	BoundedQueue* q = (BoundedQueue*)taosMemoryCalloc(1, sizeof(BoundedQueue));	6✔
326	if (q == NULL) {	6✔
327	return NULL;	×
328	}
329
330	q->queue = createPriorityQueue(fn, deleteFn, param);	6✔
331	if (q->queue == NULL) {	6✔
332	taosMemoryFree(q);	×
333	return NULL;	×
334	}
335
336	int32_t code = taosArrayEnsureCap(q->queue->container, maxSize + 1);	6✔
337	if (code) {	6✔
338	destroyPriorityQueue(q->queue);	×
339	taosMemoryFree(q);	×
340	terrno = code;	×
341	return NULL;	×
342	}
343	q->maxSize = maxSize;	6✔
344	return q;	6✔
345	}
346
347	void taosBQSetFn(BoundedQueue* q, pq_comp_fn fn) { taosPQSetFn(q->queue, fn); }	×
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) {	203✔
357	if (!q) return;	203✔
358	destroyPriorityQueue(q->queue);	5✔
359	taosMemoryFree(q);	5✔
360	}
361
362	PriorityQueueNode* taosBQPush(BoundedQueue* q, PriorityQueueNode* n) {	55✔
363	if (pqContainerSize(q->queue) == q->maxSize + 1) {	55✔
364	PriorityQueueNode* top = pqContainerGetEle(q->queue, 0);	×
365	if (q->queue->fn(top->data, n->data, q->queue->param)) {	×
366	return NULL;	×
367	} else {
368	void* p = top->data;	×
369	top->data = n->data;	×
370	if (q->queue->deleteFn) {	×
371	n->data = p;	×
372	q->queue->deleteFn(n->data);	×
373	}
374	}
375	return pqHeapify(q->queue, 0, taosBQSize(q));	×
376	} else {
377	return taosPQPush(q->queue, n);	55✔
378	}
379	}
380
381	PriorityQueueNode* taosBQTop(BoundedQueue* q) { return taosPQTop(q->queue); }	×
382
383	void taosBQBuildHeap(BoundedQueue* q) { pqBuildHeap(q->queue); }	×
384
385	size_t taosBQMaxSize(BoundedQueue* q) { return q->maxSize; }	55✔
386
387	size_t taosBQSize(BoundedQueue* q) { return taosPQSize(q->queue); }	55✔
388
389	void taosBQPop(BoundedQueue* q) { taosPQPop(q->queue); }	×

taosdata / TDengine / #3911

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