#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

64.67

/source/util/src/tlosertree.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 "tlosertree.h"
#include "taoserror.h"
#include "tlog.h"

// Set the initial value of the multiway merge tree.
static int32_t tMergeTreeInit(SMultiwayMergeTreeInfo* pTree) {
  if (!((pTree->totalSources & 0x01) == 0 && (pTree->numOfSources << 1 == pTree->totalSources))) {
    uError("losertree failed at: %s:%d", __func__, __LINE__);
    return TSDB_CODE_INVALID_PARA;
  }

  for (int32_t i = 0; i < pTree->totalSources; ++i) {
    if (i < pTree->numOfSources) {
      pTree->pNode[i].index = -1;
    } else {
      pTree->pNode[i].index = i - pTree->numOfSources;
    }
  }
  return TSDB_CODE_SUCCESS;
}

int32_t tMergeTreeCreate(SMultiwayMergeTreeInfo** pTree, uint32_t numOfSources, void* param,
                         __merge_compare_fn_t compareFn) {
  int32_t totalEntries = numOfSources << 1u;

  SMultiwayMergeTreeInfo* pTreeInfo =
      (SMultiwayMergeTreeInfo*)taosMemoryCalloc(1, sizeof(SMultiwayMergeTreeInfo) + sizeof(STreeNode) * totalEntries);
  if (pTreeInfo == NULL) {
    uError("allocate memory for loser-tree failed. reason:%s", strerror(ERRNO));
    return terrno;
  }

  pTreeInfo->pNode = (STreeNode*)(((char*)pTreeInfo) + sizeof(SMultiwayMergeTreeInfo));

  pTreeInfo->numOfSources = numOfSources;
  pTreeInfo->totalSources = totalEntries;
  pTreeInfo->param = param;
  pTreeInfo->comparFn = compareFn;

  // set initial value for loser tree
  int32_t code = tMergeTreeInit(pTreeInfo);
  if (TSDB_CODE_SUCCESS != code) {
    taosMemoryFree(pTreeInfo);
    return code;
  }

#ifdef _DEBUG_VIEW
  printf("the initial value of loser tree:\n");
  tLoserTreeDisplaypTreeInfo;
#endif

  for (int32_t i = totalEntries - 1; i >= numOfSources; i--) {
    code = tMergeTreeAdjust(pTreeInfo, i);
    if (TSDB_CODE_SUCCESS != code) {
      taosMemoryFree(pTreeInfo);
      return code;
    }
  }

#if defined(_DEBUG_VIEW)
  printf("after adjust:\n");
  tLoserTreeDisplaypTreeInfo;
  printf("initialize local reducer completed!\n");
#endif

  *pTree = pTreeInfo;
  return 0;
}

void tMergeTreeDestroy(SMultiwayMergeTreeInfo** pTree) {
  if (pTree == NULL || *pTree == NULL) {
    return;
  }

  taosMemoryFreeClear(*pTree);
}

int32_t tMergeTreeAdjust(SMultiwayMergeTreeInfo* pTree, int32_t idx) {
  int32_t code = 0;
  if (!(idx <= pTree->totalSources - 1 && idx >= pTree->numOfSources && pTree->totalSources >= 2)) {
    uError("losertree failed at: %s:%d", __func__, __LINE__);
    return TSDB_CODE_INVALID_PARA;
  }

  if (pTree->totalSources == 2) {
    pTree->pNode[0].index = 0;
    pTree->pNode[1].index = 0;
    return code;
  }

  int32_t   parentId = idx >> 1;
  STreeNode kLeaf = pTree->pNode[idx];

  while (parentId > 0) {
    STreeNode* pCur = &pTree->pNode[parentId];
    if (pCur->index == -1) {
      pTree->pNode[parentId] = kLeaf;
      return code;
    }

    int32_t ret = pTree->comparFn(pCur, &kLeaf, pTree->param);
    if (ret < 0) {
      STreeNode t = pTree->pNode[parentId];
      pTree->pNode[parentId] = kLeaf;
      kLeaf = t;
    }

    parentId = parentId >> 1;
  }

  if (memcmp(&kLeaf, &pTree->pNode[1], sizeof(kLeaf)) != 0) {
    // winner cannot be identical to the loser, which is pTreeNode[1]
    pTree->pNode[0] = kLeaf;
  }
  return code;
}

int32_t tMergeTreeRebuild(SMultiwayMergeTreeInfo* pTree) {
  int32_t code = tMergeTreeInit(pTree);
  if (TSDB_CODE_SUCCESS != code) {
    return code;
  }
  for (int32_t i = pTree->totalSources - 1; i >= pTree->numOfSources; i--) {
    code = tMergeTreeAdjust(pTree, i);
    if (TSDB_CODE_SUCCESS != code) {
      return code;
    }
  }
  return TSDB_CODE_SUCCESS;
}

/*
 * display whole loser tree on screen for debug purpose only.
 */
void tMergeTreePrint(const SMultiwayMergeTreeInfo* pTree) {
  (void)printf("the value of loser tree:\t");
  for (int32_t i = 0; i < pTree->totalSources; ++i) {
    (void)printf("%d\t", pTree->pNode[i].index);
  }

  (void)printf("\n");
}

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 "tlosertree.h"
18	#include "taoserror.h"
19	#include "tlog.h"
20
21	// Set the initial value of the multiway merge tree.
22	static int32_t tMergeTreeInit(SMultiwayMergeTreeInfo* pTree) {	239,615✔
23	if (!((pTree->totalSources & 0x01) == 0 && (pTree->numOfSources << 1 == pTree->totalSources))) {	239,615!
24	uError("losertree failed at: %s:%d", __func__, __LINE__);	×
25	return TSDB_CODE_INVALID_PARA;	×
26	}
27
28	for (int32_t i = 0; i < pTree->totalSources; ++i) {	2,106,431✔
29	if (i < pTree->numOfSources) {	1,866,812✔
30	pTree->pNode[i].index = -1;	933,385✔
31	} else {
32	pTree->pNode[i].index = i - pTree->numOfSources;	933,427✔
33	}
34	}
35	return TSDB_CODE_SUCCESS;	239,619✔
36	}
37
38	int32_t tMergeTreeCreate(SMultiwayMergeTreeInfo** pTree, uint32_t numOfSources, void* param,	235,891✔
39	__merge_compare_fn_t compareFn) {
40	int32_t totalEntries = numOfSources << 1u;	235,891✔
41
42	SMultiwayMergeTreeInfo* pTreeInfo =	471,808✔
43	(SMultiwayMergeTreeInfo)taosMemoryCalloc(1, sizeof(SMultiwayMergeTreeInfo) + sizeof(STreeNode) totalEntries);	235,891!
44	if (pTreeInfo == NULL) {	235,917!
45	uError("allocate memory for loser-tree failed. reason:%s", strerror(ERRNO));	×
46	return terrno;	×
47	}
48
49	pTreeInfo->pNode = (STreeNode)(((char)pTreeInfo) + sizeof(SMultiwayMergeTreeInfo));	235,917✔
50
51	pTreeInfo->numOfSources = numOfSources;	235,917✔
52	pTreeInfo->totalSources = totalEntries;	235,917✔
53	pTreeInfo->param = param;	235,917✔
54	pTreeInfo->comparFn = compareFn;	235,917✔
55
56	// set initial value for loser tree
57	int32_t code = tMergeTreeInit(pTreeInfo);	235,917✔
58	if (TSDB_CODE_SUCCESS != code) {	235,917✔
59	taosMemoryFree(pTreeInfo);	9!
60	return code;	×
61	}
62
63	#ifdef _DEBUG_VIEW
64	printf("the initial value of loser tree:\n");
65	tLoserTreeDisplaypTreeInfo;
66	#endif
67
68	for (int32_t i = totalEntries - 1; i >= numOfSources; i--) {	1,139,158✔
69	code = tMergeTreeAdjust(pTreeInfo, i);	903,268✔
70	if (TSDB_CODE_SUCCESS != code) {	903,238!
71	taosMemoryFree(pTreeInfo);	×
72	return code;	×
73	}
74	}
75
76	#if defined(_DEBUG_VIEW)
77	printf("after adjust:\n");
78	tLoserTreeDisplaypTreeInfo;
79	printf("initialize local reducer completed!\n");
80	#endif
81
82	*pTree = pTreeInfo;	235,890✔
83	return 0;	235,890✔
84	}
85
86	void tMergeTreeDestroy(SMultiwayMergeTreeInfo** pTree) {	235,915✔
87	if (pTree == NULL \|\| *pTree == NULL) {	235,915!
88	return;	×
89	}
90
91	taosMemoryFreeClear(*pTree);	235,919!
92	}
93
94	int32_t tMergeTreeAdjust(SMultiwayMergeTreeInfo* pTree, int32_t idx) {	208,134,616✔
95	int32_t code = 0;	208,134,616✔
96	if (!(idx <= pTree->totalSources - 1 && idx >= pTree->numOfSources && pTree->totalSources >= 2)) {	208,134,616!
97	uError("losertree failed at: %s:%d", __func__, __LINE__);	×
98	return TSDB_CODE_INVALID_PARA;	×
99	}
100
101	if (pTree->totalSources == 2) {	208,622,945✔
102	pTree->pNode[0].index = 0;	48,495,173✔
103	pTree->pNode[1].index = 0;	48,495,173✔
104	return code;	48,495,173✔
105	}
106
107	int32_t parentId = idx >> 1;	160,127,772✔
108	STreeNode kLeaf = pTree->pNode[idx];	160,127,772✔
109
110	while (parentId > 0) {	555,595,493✔
111	STreeNode* pCur = &pTree->pNode[parentId];	389,185,378✔
112	if (pCur->index == -1) {	389,185,378✔
113	pTree->pNode[parentId] = kLeaf;	693,333✔
114	return code;	693,333✔
115	}
116
117	int32_t ret = pTree->comparFn(pCur, &kLeaf, pTree->param);	388,492,045✔
118	if (ret < 0) {	395,467,721✔
119	STreeNode t = pTree->pNode[parentId];	106,290,237✔
120	pTree->pNode[parentId] = kLeaf;	106,290,237✔
121	kLeaf = t;	106,290,237✔
122	}
123
124	parentId = parentId >> 1;	395,467,721✔
125	}
126
127	if (memcmp(&kLeaf, &pTree->pNode[1], sizeof(kLeaf)) != 0) {	166,410,115!
128	// winner cannot be identical to the loser, which is pTreeNode[1]
129	pTree->pNode[0] = kLeaf;	169,299,680✔
130	}
131	return code;	166,410,115✔
132	}
133
134	int32_t tMergeTreeRebuild(SMultiwayMergeTreeInfo* pTree) {	3,703✔
135	int32_t code = tMergeTreeInit(pTree);	3,703✔
136	if (TSDB_CODE_SUCCESS != code) {	3,703!
137	return code;	×
138	}
139	for (int32_t i = pTree->totalSources - 1; i >= pTree->numOfSources; i--) {	33,327✔
140	code = tMergeTreeAdjust(pTree, i);	29,624✔
141	if (TSDB_CODE_SUCCESS != code) {	29,624!
142	return code;	×
143	}
144	}
145	return TSDB_CODE_SUCCESS;	3,703✔
146	}
147
148	/*
149	* display whole loser tree on screen for debug purpose only.
150	*/
151	void tMergeTreePrint(const SMultiwayMergeTreeInfo* pTree) {	×
152	(void)printf("the value of loser tree:\t");	×
153	for (int32_t i = 0; i < pTree->totalSources; ++i) {	×
154	(void)printf("%d\t", pTree->pNode[i].index);	×
155	}
156
157	(void)printf("\n");	×
158	}	×

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