#3531

Committed 19 Nov 2024 10:42AM UTC coverage: 60.213% (-0.006%) from 60.219%

Build # #3531

Build Type

push

travis-ci

Committed by

web-flow

Commit Message

Merge pull request #28777 from taosdata/fix/3.0/TD-32366

fix:TD-32366/stmt add geometry datatype check

Run Details

118529 of 252344 branches covered (46.97%)

Branch coverage included in aggregate %.

7 of 48 new or added lines in 3 files covered. (14.58%)

2282 existing lines in 115 files now uncovered.

199096 of 275161 relevant lines covered (72.36%)

6067577.83 hits per line

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

87.95

/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
    taosArrayDestroy(pq->container);
  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);
  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 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;
      n->data = p;
      if (q->queue->deleteFn) 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; }	23,827,290✔
20
21	Heap* heapCreate(HeapCompareFn fn) {	469,421✔
22	Heap* heap = taosMemoryCalloc(1, sizeof(Heap));	469,421✔
23	if (heap == NULL) {	469,481!
24	return NULL;	×
25	}
26
27	heap->min = NULL;	469,481✔
28	heap->nelts = 0;	469,481✔
29	heap->compFn = fn;	469,481✔
30	return heap;	469,481✔
31	}
32
33	void heapDestroy(Heap* heap) { taosMemoryFree(heap); }	198,666✔
34
35	HeapNode* heapMin(const Heap* heap) { return heap->min; }	16,577,977✔
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) {	4,837✔
39	HeapNode* sibling;
40	HeapNode t;
41
42	t = *parent;	4,837✔
43	parent = child;	4,837✔
44	*child = t;	4,837✔
45
46	parent->parent = child;	4,837✔
47	if (child->left == child) {	4,837✔
48	child->left = parent;	4,747✔
49	sibling = child->right;	4,747✔
50	} else {
51	child->right = parent;	90✔
52	sibling = child->left;	90✔
53	}
54	if (sibling != NULL) sibling->parent = child;	4,837✔
55
56	if (parent->left != NULL) parent->left->parent = parent;	4,837✔
57	if (parent->right != NULL) parent->right->parent = parent;	4,837!
58
59	if (child->parent == NULL)	4,837✔
60	heap->min = child;	4,820✔
61	else if (child->parent->left == parent)	17!
62	child->parent->left = child;	17✔
63	else
64	child->parent->right = child;	×
65	}	4,837✔
66
67	void heapInsert(Heap* heap, HeapNode* newnode) {	7,474,408✔
68	HeapNode** parent;
69	HeapNode** child;
70	uint32_t path;
71	uint32_t n;
72	uint32_t k;
73
74	newnode->left = NULL;	7,474,408✔
75	newnode->right = NULL;	7,474,408✔
76	newnode->parent = NULL;	7,474,408✔
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;	7,474,408✔
82	for (k = 0, n = 1 + heap->nelts; n >= 2; k += 1, n /= 2) path = (path << 1) \| (n & 1);	7,481,612✔
83
84	/* Now traverse the heap using the path we calculated in the previous step. */
85	parent = child = &heap->min;	7,474,408✔
86	while (k > 0) {	7,481,612✔
87	parent = child;	7,204✔
88	if (path & 1)	7,204✔
89	child = &(*child)->right;	139✔
90	else
91	child = &(*child)->left;	7,065✔
92	path >>= 1;	7,204✔
93	k -= 1;	7,204✔
94	}
95
96	/* Insert the new node. */
97	newnode->parent = *parent;	7,474,408✔
98	*child = newnode;	7,474,408✔
99	heap->nelts += 1;	7,474,408✔
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))	7,478,969✔
105	heapNodeSwap(heap, newnode->parent, newnode);	4,561✔
106	}	7,474,408✔
107
108	void heapRemove(Heap* heap, HeapNode* node) {	7,476,875✔
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;	7,476,875!
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;	7,476,875✔
122	for (k = 0, n = heap->nelts; n >= 2; k += 1, n /= 2) path = (path << 1) \| (n & 1);	7,484,078✔
123
124	/* Now traverse the heap using the path we calculated in the previous step. */
125	max = &heap->min;	7,476,875✔
126	while (k > 0) {	7,484,078✔
127	if (path & 1)	7,203✔
128	max = &(*max)->right;	139✔
129	else
130	max = &(*max)->left;	7,064✔
131	path >>= 1;	7,203✔
132	k -= 1;	7,203✔
133	}
134
135	heap->nelts -= 1;	7,476,875✔
136
137	/* Unlink the max node. */
138	child = *max;	7,476,875✔
139	*max = NULL;	7,476,875✔
140
141	if (child == node) {	7,476,875✔
142	/* We're removing either the max or the last node in the tree. */
143	if (child == heap->min) {	7,470,539!
144	heap->min = NULL;	×
145	}
146	return;	7,470,539✔
147	}
148
149	/* Replace the to be deleted node with the max node. */
150	child->left = node->left;	6,336✔
151	child->right = node->right;	6,336✔
152	child->parent = node->parent;	6,336✔
153
154	if (child->left != NULL) {	6,336✔
155	child->left->parent = child;	303✔
156	}
157
158	if (child->right != NULL) {	6,336✔
159	child->right->parent = child;	164✔
160	}
161
162	if (node->parent == NULL) {	6,336!
163	heap->min = child;	6,978✔
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;	7,251✔
176	if (child->left != NULL && (heap->compFn)(child->left, smallest)) smallest = child->left;	7,251✔
177	if (child->right != NULL && (heap->compFn)(child->right, smallest)) smallest = child->right;	7,251✔
178	if (smallest == child) break;	7,251✔
179	heapNodeSwap(heap, child, smallest);	273✔
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);	6,981✔
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) {	44,478✔
198	PriorityQueue* pq = (PriorityQueue*)taosMemoryCalloc(1, sizeof(PriorityQueue));	44,478✔
199	if (pq == NULL) {	44,518!
200	return NULL;	×
201	}
202
203	pq->container = taosArrayInit(1, sizeof(PriorityQueueNode));	44,518✔
204	if (pq->container == NULL) {	44,519!
UNCOV 205	taosMemoryFree(pq);	×
206	return NULL;	×
207	}
208
209	pq->fn = fn;	44,519✔
210	pq->deleteFn = deleteFn;	44,519✔
211	pq->param = param;	44,519✔
212	return pq;	44,519✔
213	}
214
215	void taosPQSetFn(PriorityQueue* pq, pq_comp_fn fn) { pq->fn = fn; }	16,783✔
216
217	void destroyPriorityQueue(PriorityQueue* pq) {	44,512✔
218	if (pq->deleteFn)	44,512!
219	taosArrayDestroyP(pq->container, pq->deleteFn);	44,512✔
220	else
221	taosArrayDestroy(pq->container);	×
222	taosMemoryFree(pq);	44,523✔
223	}	44,522✔
224
225	static size_t pqParent(size_t i) { return (--i) >> 1; /* (i - 1) / 2 */ }	23,699,260✔
226	static size_t pqLeft(size_t i) { return (i << 1) \| 1; /* i * 2 + 1 */ }	5,483,837✔
227	static size_t pqRight(size_t i) { return (++i) << 1; /* (i + 1) * 2 */ }	5,483,687✔
228
229	static void pqSwapPQNode(PriorityQueueNode* a, PriorityQueueNode* b) {	16,492,921✔
230	void* tmp = a->data;	16,492,921✔
231	a->data = b->data;	16,492,921✔
232	b->data = tmp;	16,492,921✔
233	}	16,492,921✔
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); }	4,816,017✔
239
240	static PriorityQueueNode* pqHeapify(PriorityQueue* pq, size_t from, size_t last) {	1,108,374✔
241	size_t largest = from;	1,108,374✔
242	do {
243	from = largest;	5,484,536✔
244	size_t l = pqLeft(from);	5,484,536✔
245	size_t r = pqRight(from);	5,483,791✔
246	if (l < last && pq->fn(pqContainerGetEle(pq, from)->data, pqContainerGetEle(pq, l)->data, pq->param)) {	5,483,685✔
247	largest = l;	4,267,695✔
248	}
249	if (r < last && pq->fn(pqContainerGetEle(pq, largest)->data, pqContainerGetEle(pq, r)->data, pq->param)) {	5,482,970✔
250	largest = r;	1,999,661✔
251	}
252	if (largest != from) {	5,482,489✔
253	pqSwapPQNode(pqContainerGetEle(pq, from), pqContainerGetEle(pq, largest));	4,376,411✔
254	}
255	} while (largest != from);	5,483,190✔
256	return pqContainerGetEle(pq, largest);	1,107,028✔
257	}
258
259	static void pqBuildHeap(PriorityQueue* pq) {	16,783✔
260	if (pqContainerSize(pq) > 1) {	16,783✔
261	PriorityQueueNode* node;
262	for (size_t i = pqContainerSize(pq) - 1; i > 0; --i) {	259,455✔
263	node = pqHeapify(pq, i, pqContainerSize(pq));	251,136✔
264	}
265	node = pqHeapify(pq, 0, pqContainerSize(pq));	8,319✔
266	}
267	}	16,783✔
268
269	static PriorityQueueNode* pqReverseHeapify(PriorityQueue* pq, size_t i) {	1,791,015✔
270	while (i > 0 && !pq->fn(pqContainerGetEle(pq, i)->data, pqContainerGetEle(pq, pqParent(i))->data, pq->param)) {	13,907,583✔
271	size_t parentIdx = pqParent(i);	12,197,155✔
272	pqSwapPQNode(pqContainerGetEle(pq, i), pqContainerGetEle(pq, parentIdx));	12,185,938✔
273	i = parentIdx;	12,116,568✔
274	}
275	return pqContainerGetEle(pq, i);	1,640,556✔
276	}
277
278	static void pqUpdate(PriorityQueue* pq, size_t i) {	264,837✔
279	PriorityQueueNode* node;
280	if (i == 0 \|\| pq->fn(pqContainerGetEle(pq, i)->data, pqContainerGetEle(pq, pqParent(i))->data, pq->param)) {	264,837!
281	// if value in pos i is smaller than parent, heapify down from i to the end
282	node = pqHeapify(pq, i, pqContainerSize(pq));	264,837✔
283	} else {
284	// if value in pos i is big than parent, heapify up from i
285	node = pqReverseHeapify(pq, i);	×
286	}
287	}	264,837✔
288
289	static void pqRemove(PriorityQueue* pq, size_t i) {	281,620✔
290	if (i == pqContainerSize(pq) - 1) {	281,620✔
291	void* tmp = taosArrayPop(pq->container);	16,783✔
292	return;	16,783✔
293	}
294
295	taosArraySet(pq->container, i, taosArrayGet(pq->container, pqContainerSize(pq) - 1));	264,837✔
296	void* tmp = taosArrayPop(pq->container);	264,837✔
297	pqUpdate(pq, i);	264,837✔
298	}
299
300	PriorityQueueNode* taosPQTop(PriorityQueue* pq) { return pqContainerGetEle(pq, 0); }	2,125,611✔
301
302	PriorityQueueNode* taosPQPush(PriorityQueue* pq, const PriorityQueueNode* node) {	1,838,992✔
303	if (taosArrayPush(pq->container, node) == NULL) {	3,659,776!
304	return NULL;	×
305	}
306	return pqReverseHeapify(pq, pqContainerSize(pq) - 1);	1,820,784✔
307	}
308
309	void taosPQPop(PriorityQueue* pq) {	281,619✔
310	PriorityQueueNode* top = taosPQTop(pq);	281,619✔
311	if (pq->deleteFn) pq->deleteFn(top->data);	281,619!
312	pqRemove(pq, 0);	281,620✔
313	}	281,620✔
314
315	struct BoundedQueue {
316	PriorityQueue* queue;
317	uint32_t maxSize;
318	};
319
320	BoundedQueue* createBoundedQueue(uint32_t maxSize, pq_comp_fn fn, FDelete deleteFn, void* param) {	44,462✔
321	BoundedQueue* q = (BoundedQueue*)taosMemoryCalloc(1, sizeof(BoundedQueue));	44,462✔
322	if (q == NULL) {	44,513!
323	return NULL;	×
324	}
325
326	q->queue = createPriorityQueue(fn, deleteFn, param);	44,513✔
327	if (q->queue == NULL) {	44,517!
328	taosMemoryFree(q);	×
329	return NULL;	×
330	}
331
332	int32_t code = taosArrayEnsureCap(q->queue->container, maxSize + 1);	44,517✔
333	if (code) {	44,519✔
334	destroyPriorityQueue(q->queue);	26✔
335	taosMemoryFree(q);	×
336	terrno = code;	×
337	return NULL;	×
338	}
339	q->maxSize = maxSize;	44,493✔
340	return q;	44,493✔
341	}
342
343	void taosBQSetFn(BoundedQueue* q, pq_comp_fn fn) { taosPQSetFn(q->queue, fn); }	16,783✔
344
345	void destroyBoundedQueue(BoundedQueue* q) {	224,818✔
346	if (!q) return;	224,818✔
347	destroyPriorityQueue(q->queue);	44,512✔
348	taosMemoryFree(q);	44,523✔
349	}
350
351	PriorityQueueNode* taosBQPush(BoundedQueue* q, PriorityQueueNode* n) {	7,261,000✔
352	if (pqContainerSize(q->queue) == q->maxSize + 1) {	7,261,000✔
353	PriorityQueueNode* top = pqContainerGetEle(q->queue, 0);	5,404,335✔
354	if (q->queue->fn(top->data, n->data, q->queue->param)) {	5,404,373✔
355	return NULL;	4,820,601✔
356	} else {
357	void* p = top->data;	583,498✔
358	top->data = n->data;	583,498✔
359	n->data = p;	583,498✔
360	if (q->queue->deleteFn) q->queue->deleteFn(n->data);	583,498✔
361	}
362	return pqHeapify(q->queue, 0, taosBQSize(q));	584,366✔
363	} else {
364	return taosPQPush(q->queue, n);	1,843,124✔
365	}
366	}
367
368	PriorityQueueNode* taosBQTop(BoundedQueue* q) { return taosPQTop(q->queue); }	1,844,096✔
369
370	void taosBQBuildHeap(BoundedQueue* q) { pqBuildHeap(q->queue); }	16,783✔
371
372	size_t taosBQMaxSize(BoundedQueue* q) { return q->maxSize; }	3,925,435✔
373
374	size_t taosBQSize(BoundedQueue* q) { return taosPQSize(q->queue); }	4,822,933✔
375
376	void taosBQPop(BoundedQueue* q) { taosPQPop(q->queue); }	281,619✔

taosdata / TDengine / #3531

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