#5034

Committed 24 Apr 2026 11:25AM UTC coverage: 73.058%. Remained the same

Build # #5034

Build Type

push

travis-ci

Committed by

web-flow

Commit Message

merge: from main to 3.0 branch #35224

merge: from main to 3.0 branch[manual-only]

Coverage Stats

1336 of 1975 new or added lines in 48 files covered. (67.65%)

14149 existing lines in 164 files now uncovered.

275896 of 377640 relevant lines covered (73.06%)

132944440.29 hits per line

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

75.85

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

#define doswap(__left, __right, __size, __buf) \
  do {                                         \
    memcpy((__buf), (__left), (__size));       \
    memcpy((__left), (__right), (__size));     \
    memcpy((__right), (__buf), (__size));      \
  } while (0);

static void median(void *src, int64_t size, int64_t s, int64_t e, const void *param, __ext_compar_fn_t comparFn,
                   void *buf) {
  int32_t mid = ((int32_t)(e - s) >> 1u) + (int32_t)s;

  if (comparFn(elePtrAt(src, size, mid), elePtrAt(src, size, s), param) > 0) {
    doswap(elePtrAt(src, size, mid), elePtrAt(src, size, s), size, buf);
  }

  if (comparFn(elePtrAt(src, size, mid), elePtrAt(src, size, e), param) > 0) {
    doswap(elePtrAt(src, size, mid), elePtrAt(src, size, s), size, buf);
    doswap(elePtrAt(src, size, mid), elePtrAt(src, size, e), size, buf);
  } else if (comparFn(elePtrAt(src, size, s), elePtrAt(src, size, e), param) > 0) {
    doswap(elePtrAt(src, size, s), elePtrAt(src, size, e), size, buf);
  }

}

static void tInsertSort(void *src, int64_t size, int32_t s, int32_t e, const void *param, __ext_compar_fn_t comparFn,
                        void *buf) {
  for (int32_t i = s + 1; i <= e; ++i) {
    for (int32_t j = i; j > s; --j) {
      if (comparFn(elePtrAt(src, size, j), elePtrAt(src, size, j - 1), param) < 0) {
        doswap(elePtrAt(src, size, j), elePtrAt(src, size, j - 1), size, buf);
      } else {
        break;
      }
    }
  }
}

static void tqsortImpl(void *src, int32_t start, int32_t end, int64_t size, const void *param,
                       __ext_compar_fn_t comparFn, void *buf) {
  // short array sort, incur another sort procedure instead of quick sort process
  const int32_t THRESHOLD_SIZE = 6;
  if (end - start + 1 <= THRESHOLD_SIZE) {
    tInsertSort(src, size, start, end, param, comparFn, buf);
    return;
  }

  median(src, size, start, end, param, comparFn, buf);

  int32_t s = start, e = end;
  int32_t endRightS = end, startLeftS = start;

  while (s < e) {
    while (e > s) {
      int32_t ret = comparFn(elePtrAt(src, size, e), elePtrAt(src, size, s), param);
      if (ret < 0) {
        break;
      }

      // move the data that equals to pivotal value to the right end of the list
      if (ret == 0 && e != endRightS) {
        doswap(elePtrAt(src, size, e), elePtrAt(src, size, endRightS), size, buf);
        endRightS--;
      }

      e--;
    }

    if (e != s) {
      doswap(elePtrAt(src, size, e), elePtrAt(src, size, s), size, buf);
    }

    while (s < e) {
      int32_t ret = comparFn(elePtrAt(src, size, s), elePtrAt(src, size, e), param);
      if (ret > 0) {
        break;
      }

      if (ret == 0 && s != startLeftS) {
        doswap(elePtrAt(src, size, s), elePtrAt(src, size, startLeftS), size, buf);
        startLeftS++;
      }
      s++;
    }

    if (e != s) {
      doswap(elePtrAt(src, size, s), elePtrAt(src, size, e), size, buf);
    }
  }

  int32_t rightPartStart = e + 1;
  if (endRightS != end && e < end) {
    int32_t left = rightPartStart;
    int32_t right = end;

    while (right > endRightS && left <= endRightS) {
      doswap(elePtrAt(src, size, left), elePtrAt(src, size, right), size, buf);

      left++;
      right--;
    }

    rightPartStart += (end - endRightS);
  }

  int32_t leftPartEnd = e - 1;
  if (startLeftS != end && s > start) {
    int32_t left = start;
    int32_t right = leftPartEnd;

    while (left < startLeftS && right >= startLeftS) {
      doswap(elePtrAt(src, size, left), elePtrAt(src, size, right), size, buf);

      left++;
      right--;
    }

    leftPartEnd -= (startLeftS - start);
  }

  if (leftPartEnd > start) {
    tqsortImpl(src, start, leftPartEnd, size, param, comparFn, buf);
  }

  if (rightPartStart < end) {
    tqsortImpl(src, rightPartStart, end, size, param, comparFn, buf);
  }
}

int32_t taosqsort(void *src, int64_t numOfElem, int64_t size, const void *param, __ext_compar_fn_t comparFn) {
  char *buf = taosMemoryCalloc(1, size);  // prepare the swap buffer
  if (NULL == buf) {
    return terrno;
  }
  tqsortImpl(src, 0, (int32_t)numOfElem - 1, (int32_t)size, param, comparFn, buf);
  taosMemoryFreeClear(buf);
  return 0;
}

#define DOSWAP(a, b, size)        \
  do {                            \
    size_t __size = (size);       \
    char  *__a = (a), *__b = (b); \
    do {                          \
      char __tmp = *__a;          \
      *__a++ = *__b;              \
      *__b++ = __tmp;             \
    } while (--__size > 0);       \
  } while (0)

typedef struct {
  char *lo;
  char *hi;
} stack_node;

#define STACK_SIZE      (CHAR_BIT * sizeof(size_t))
#define PUSH(low, high) ((void)((top->lo = (low)), (top->hi = (high)), ++top))
#define POP(low, high)  ((void)(--top, (low = top->lo), (high = top->hi)))
#define STACK_NOT_EMPTY (stack < top)

void taosqsort_r(void *src, int64_t nelem, int64_t size, const void *arg, __ext_compar_fn_t cmp) {
  const int32_t MAX_THRESH = 6;
  char         *base_ptr = (char *)src;

  const size_t max_thresh = MAX_THRESH * size;

  if (nelem == 0) return;

  if (nelem > MAX_THRESH) {
    char       *lo = base_ptr;
    char       *hi = &lo[size * (nelem - 1)];
    stack_node  stack[STACK_SIZE];
    stack_node *top = stack;

    PUSH(NULL, NULL);

    while (STACK_NOT_EMPTY) {
      char *left_ptr;
      char *right_ptr;

      char *mid = lo + size * ((hi - lo) / size >> 1);

      if ((*cmp)((void *)mid, (void *)lo, arg) < 0) DOSWAP(mid, lo, size);
      if ((*cmp)((void *)hi, (void *)mid, arg) < 0)
        DOSWAP(mid, hi, size);
      else
        goto jump_over;
      if ((*cmp)((void *)mid, (void *)lo, arg) < 0) DOSWAP(mid, lo, size);
    jump_over:;

      left_ptr = lo + size;
      right_ptr = hi - size;
      do {
        while ((*cmp)((void *)left_ptr, (void *)mid, arg) < 0) left_ptr += size;

        while ((*cmp)((void *)mid, (void *)right_ptr, arg) < 0) right_ptr -= size;

        if (left_ptr < right_ptr) {
          DOSWAP(left_ptr, right_ptr, size);
          if (mid == left_ptr)
            mid = right_ptr;
          else if (mid == right_ptr)
            mid = left_ptr;
          left_ptr += size;
          right_ptr -= size;
        } else if (left_ptr == right_ptr) {
          left_ptr += size;
          right_ptr -= size;
          break;
        }
      } while (left_ptr <= right_ptr);

      if ((size_t)(right_ptr - lo) <= max_thresh) {
        if ((size_t)(hi - left_ptr) <= max_thresh)
          POP(lo, hi);
        else
          lo = left_ptr;
      } else if ((size_t)(hi - left_ptr) <= max_thresh)
        hi = right_ptr;
      else if ((right_ptr - lo) > (hi - left_ptr)) {
        PUSH(lo, right_ptr);
        lo = left_ptr;
      } else {
        PUSH(left_ptr, hi);
        hi = right_ptr;
      }
    }
  }
#define min(x, y) ((x) < (y) ? (x) : (y))

  {
    char *const end_ptr = &base_ptr[size * (nelem - 1)];
    char       *tmp_ptr = base_ptr;
    char       *thresh = min(end_ptr, base_ptr + max_thresh);
    char       *run_ptr;

    for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size)
      if ((*cmp)((void *)run_ptr, (void *)tmp_ptr, arg) < 0) tmp_ptr = run_ptr;

    if (tmp_ptr != base_ptr) DOSWAP(tmp_ptr, base_ptr, size);

    run_ptr = base_ptr + size;
    while ((run_ptr += size) <= end_ptr) {
      tmp_ptr = run_ptr - size;
      while ((tmp_ptr >= base_ptr) &&((*cmp)((void *)run_ptr, (void *)tmp_ptr, arg) < 0)) tmp_ptr -= size;

      tmp_ptr += size;
      if (tmp_ptr != run_ptr) {
        char *trav;

        trav = run_ptr + size;
        while (--trav >= run_ptr) {
          char  c = *trav;
          char *hi, *lo;

          for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo) *hi = *lo;
          *hi = c;
        }
      }
    }
  }
}

void *taosbsearch(const void *key, const void *base, int32_t nmemb, int32_t size, __compar_fn_t compar, int32_t flags) {
  uint8_t *p;
  int32_t  lidx;
  int32_t  ridx;
  int32_t  midx;
  int32_t  c;

  if (nmemb <= 0) return NULL;

  lidx = 0;
  ridx = nmemb - 1;
  while (lidx <= ridx) {
    midx = (lidx + ridx) / 2;
    p = (uint8_t *)base + size * midx;

    c = compar(key, p);
    if (c == 0) {
      if (flags == TD_GT) {
        lidx = midx + 1;
      } else if (flags == TD_LT) {
        ridx = midx - 1;
      } else {
        break;
      }
    } else if (c < 0) {
      ridx = midx - 1;
    } else {
      lidx = midx + 1;
    }
  }

  if (flags == TD_EQ) {
    return c ? NULL : p;
  } else if (flags == TD_GE) {
    return (c <= 0) ? p : (midx + 1 < nmemb ? p + size : NULL);
  } else if (flags == TD_LE) {
    return (c >= 0) ? p : (midx > 0 ? p - size : NULL);
  } else if (flags == TD_GT) {
    return (c < 0) ? p : (midx + 1 < nmemb ? p + size : NULL);
  } else if (flags == TD_LT) {
    return (c > 0) ? p : (midx > 0 ? p - size : NULL);
  } else {
    uError("Invalid bsearch flags:%d", flags);
    return NULL;
  }
}

int32_t taosheapadjust(void *base, int32_t size, int32_t start, int32_t end, const void *parcompar,
                       __ext_compar_fn_t compar, char *buf, bool maxroot) {
  int32_t parent;
  int32_t child;

  char *tmp = NULL;
  if (buf == NULL) {
    tmp = taosMemoryMalloc(size);
    if (NULL == tmp) {
      return terrno;
    }
  } else {
    tmp = buf;
  }

  if (base && size > 0 && compar) {
    parent = start;
    child = 2 * parent + 1;

    if (maxroot) {
      while (child <= end) {
        if (child + 1 <= end &&
            (*compar)(elePtrAt(base, size, child), elePtrAt(base, size, child + 1), parcompar) < 0) {
          child++;
        }

        if ((*compar)(elePtrAt(base, size, parent), elePtrAt(base, size, child), parcompar) > 0) {
          break;
        }

        doswap(elePtrAt(base, size, parent), elePtrAt(base, size, child), size, tmp);

        parent = child;
        child = 2 * parent + 1;
      }
    } else {
      while (child <= end) {
        if (child + 1 <= end &&
            (*compar)(elePtrAt(base, size, child), elePtrAt(base, size, child + 1), parcompar) > 0) {
          child++;
        }

        if ((*compar)(elePtrAt(base, size, parent), elePtrAt(base, size, child), parcompar) < 0) {
          break;
        }

        doswap(elePtrAt(base, size, parent), elePtrAt(base, size, child), size, tmp);

        parent = child;
        child = 2 * parent + 1;
      }
    }
  }

  if (buf == NULL) {
    taosMemoryFree(tmp);
  }

  return 0;
}

int32_t taosheapsort(void *base, int32_t size, int32_t len, const void *parcompar, __ext_compar_fn_t compar,
                     bool maxroot) {
  int32_t i;

  char *buf = taosMemoryCalloc(1, size);
  if (buf == NULL) {
    return terrno;
  }

  if (base && size > 0) {
    for (i = len / 2 - 1; i >= 0; i--) {
      int32_t code = taosheapadjust(base, size, i, len - 1, parcompar, compar, buf, maxroot);
      if (code) {
        taosMemoryFree(buf);
        return code;
      }
    }
  }

  taosMemoryFree(buf);
  return 0;
}

static void taosMerge(void *src, int32_t start, int32_t leftend, int32_t end, int64_t size, const void *param,
                      __ext_compar_fn_t comparFn, void *tmp) {
  int32_t leftSize = leftend - start + 1;
  int32_t rightSize = end - leftend;

  void *leftBuf = tmp;
  void *rightBuf = (char *)tmp + (leftSize * size);

  memcpy(leftBuf, elePtrAt(src, size, start), leftSize * size);
  memcpy(rightBuf, elePtrAt(src, size, leftend + 1), rightSize * size);

  int32_t i = 0, j = 0, k = start;

  while (i < leftSize && j < rightSize) {
    int32_t ret = comparFn(elePtrAt(leftBuf, size, i), elePtrAt(rightBuf, size, j), param);
    if (ret <= 0) {
      memcpy(elePtrAt(src, size, k), elePtrAt(leftBuf, size, i), size);
      i++;
    } else {
      memcpy(elePtrAt(src, size, k), elePtrAt(rightBuf, size, j), size);
      j++;
    }
    k++;
  }

  while (i < leftSize) {
    memcpy(elePtrAt(src, size, k), elePtrAt(leftBuf, size, i), size);
    i++;
    k++;
  }

  while (j < rightSize) {
    memcpy(elePtrAt(src, size, k), elePtrAt(rightBuf, size, j), size);
    j++;
    k++;
  }
}

static int32_t taosMergeSortHelper(void *src, int64_t numOfElem, int64_t size, const void *param,
                                   __ext_compar_fn_t comparFn) {
  // short array sort, instead of merge sort process
  const int32_t THRESHOLD_SIZE = 6;
  char         *buf = taosMemoryCalloc(1, size);  // prepare the swap buffer
  if (buf == NULL) {
    return terrno;
  }

  for (int32_t start = 0; start < numOfElem - 1; start += THRESHOLD_SIZE) {
    int32_t end = (start + THRESHOLD_SIZE - 1) <= numOfElem - 1 ? (start + THRESHOLD_SIZE - 1) : numOfElem - 1;
    tInsertSort(src, size, start, end, param, comparFn, buf);
  }
  taosMemoryFreeClear(buf);

  if (numOfElem > THRESHOLD_SIZE) {
    int32_t currSize;
    void   *tmp = taosMemoryMalloc(numOfElem * size);
    if (tmp == NULL) {
      return terrno;
    }

    for (currSize = THRESHOLD_SIZE; currSize <= numOfElem - 1; currSize = 2 * currSize) {
      int32_t leftStart;
      for (leftStart = 0; leftStart < numOfElem - 1; leftStart += 2 * currSize) {
        int32_t leftend = leftStart + currSize - 1;
        int32_t rightEnd =
            (leftStart + 2 * currSize - 1 < numOfElem - 1) ? (leftStart + 2 * currSize - 1) : (numOfElem - 1);
        if (leftend >= rightEnd) break;

        taosMerge(src, leftStart, leftend, rightEnd, size, param, comparFn, tmp);
      }
    }

    taosMemoryFreeClear(tmp);
  }
  return 0;
}

int32_t msortHelper(const void *p1, const void *p2, const void *param) {
  __compar_fn_t comparFn = param;
  return comparFn(p1, p2);
}

int32_t taosMergeSort(void *src, int64_t numOfElem, int64_t size, __compar_fn_t comparFn) {
  void *param = comparFn;
  return taosMergeSortHelper(src, numOfElem, size, param, msortHelper);
}

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 "talgo.h"
18	#include "tlog.h"
19
20	#define doswap(__left, __right, __size, __buf) \
21	do { \
22	memcpy((__buf), (__left), (__size)); \
23	memcpy((__left), (__right), (__size)); \
24	memcpy((__right), (__buf), (__size)); \
25	} while (0);
26
27	static void median(void src, int64_t size, int64_t s, int64_t e, const void param, __ext_compar_fn_t comparFn,	×
28	void *buf) {
29	int32_t mid = ((int32_t)(e - s) >> 1u) + (int32_t)s;	×
30
31	if (comparFn(elePtrAt(src, size, mid), elePtrAt(src, size, s), param) > 0) {	×
32	doswap(elePtrAt(src, size, mid), elePtrAt(src, size, s), size, buf);	×
33	}
34
35	if (comparFn(elePtrAt(src, size, mid), elePtrAt(src, size, e), param) > 0) {	×
36	doswap(elePtrAt(src, size, mid), elePtrAt(src, size, s), size, buf);	×
37	doswap(elePtrAt(src, size, mid), elePtrAt(src, size, e), size, buf);	×
38	} else if (comparFn(elePtrAt(src, size, s), elePtrAt(src, size, e), param) > 0) {	×
39	doswap(elePtrAt(src, size, s), elePtrAt(src, size, e), size, buf);	×
40	}
41
42	}	×
43
44	static void tInsertSort(void src, int64_t size, int32_t s, int32_t e, const void param, __ext_compar_fn_t comparFn,	43,465,676✔
45	void *buf) {
46	for (int32_t i = s + 1; i <= e; ++i) {	259,343,620✔
47	for (int32_t j = i; j > s; --j) {	504,271,920✔
48	if (comparFn(elePtrAt(src, size, j), elePtrAt(src, size, j - 1), param) < 0) {	446,269,036✔
49	doswap(elePtrAt(src, size, j), elePtrAt(src, size, j - 1), size, buf);	288,399,126✔
50	} else {
51	break;	157,875,060✔
52	}
53	}
54	}
55	}	43,484,602✔
56
57	static void tqsortImpl(void src, int32_t start, int32_t end, int64_t size, const void param,	5,533✔
58	__ext_compar_fn_t comparFn, void *buf) {
59	// short array sort, incur another sort procedure instead of quick sort process
60	const int32_t THRESHOLD_SIZE = 6;	5,533✔
61	if (end - start + 1 <= THRESHOLD_SIZE) {	5,533✔
62	tInsertSort(src, size, start, end, param, comparFn, buf);	5,533✔
63	return;	5,533✔
64	}
65
66	median(src, size, start, end, param, comparFn, buf);	×
67
68	int32_t s = start, e = end;	×
69	int32_t endRightS = end, startLeftS = start;	×
70
71	while (s < e) {	×
72	while (e > s) {	×
73	int32_t ret = comparFn(elePtrAt(src, size, e), elePtrAt(src, size, s), param);	×
74	if (ret < 0) {	×
75	break;	×
76	}
77
78	// move the data that equals to pivotal value to the right end of the list
79	if (ret == 0 && e != endRightS) {	×
80	doswap(elePtrAt(src, size, e), elePtrAt(src, size, endRightS), size, buf);	×
81	endRightS--;	×
82	}
83
84	e--;	×
85	}
86
87	if (e != s) {	×
88	doswap(elePtrAt(src, size, e), elePtrAt(src, size, s), size, buf);	×
89	}
90
91	while (s < e) {	×
92	int32_t ret = comparFn(elePtrAt(src, size, s), elePtrAt(src, size, e), param);	×
93	if (ret > 0) {	×
94	break;	×
95	}
96
97	if (ret == 0 && s != startLeftS) {	×
98	doswap(elePtrAt(src, size, s), elePtrAt(src, size, startLeftS), size, buf);	×
99	startLeftS++;	×
100	}
101	s++;	×
102	}
103
104	if (e != s) {	×
105	doswap(elePtrAt(src, size, s), elePtrAt(src, size, e), size, buf);	×
106	}
107	}
108
109	int32_t rightPartStart = e + 1;	×
110	if (endRightS != end && e < end) {	×
111	int32_t left = rightPartStart;	×
112	int32_t right = end;	×
113
114	while (right > endRightS && left <= endRightS) {	×
115	doswap(elePtrAt(src, size, left), elePtrAt(src, size, right), size, buf);	×
116
117	left++;	×
118	right--;	×
119	}
120
121	rightPartStart += (end - endRightS);	×
122	}
123
124	int32_t leftPartEnd = e - 1;	×
125	if (startLeftS != end && s > start) {	×
126	int32_t left = start;	×
127	int32_t right = leftPartEnd;	×
128
129	while (left < startLeftS && right >= startLeftS) {	×
130	doswap(elePtrAt(src, size, left), elePtrAt(src, size, right), size, buf);	×
131
132	left++;	×
133	right--;	×
134	}
135
136	leftPartEnd -= (startLeftS - start);	×
137	}
138
139	if (leftPartEnd > start) {	×
140	tqsortImpl(src, start, leftPartEnd, size, param, comparFn, buf);	×
141	}
142
143	if (rightPartStart < end) {	×
144	tqsortImpl(src, rightPartStart, end, size, param, comparFn, buf);	×
145	}
146	}
147
148	int32_t taosqsort(void src, int64_t numOfElem, int64_t size, const void param, __ext_compar_fn_t comparFn) {	5,533✔
149	char *buf = taosMemoryCalloc(1, size); // prepare the swap buffer	5,533✔
150	if (NULL == buf) {	5,533✔
151	return terrno;	×
152	}
153	tqsortImpl(src, 0, (int32_t)numOfElem - 1, (int32_t)size, param, comparFn, buf);	5,533✔
154	taosMemoryFreeClear(buf);	5,533✔
155	return 0;	5,533✔
156	}
157
158	#define DOSWAP(a, b, size) \
159	do { \
160	size_t __size = (size); \
161	char __a = (a), __b = (b); \
162	do { \
163	char __tmp = *__a; \
164	__a++ = __b; \
165	*__b++ = __tmp; \
166	} while (--__size > 0); \
167	} while (0)
168
169	typedef struct {
170	char *lo;
171	char *hi;
172	} stack_node;
173
174	#define STACK_SIZE (CHAR_BIT * sizeof(size_t))
175	#define PUSH(low, high) ((void)((top->lo = (low)), (top->hi = (high)), ++top))
176	#define POP(low, high) ((void)(--top, (low = top->lo), (high = top->hi)))
177	#define STACK_NOT_EMPTY (stack < top)
178
179	void taosqsort_r(void src, int64_t nelem, int64_t size, const void arg, __ext_compar_fn_t cmp) {	23,006,211✔
180	const int32_t MAX_THRESH = 6;	23,006,211✔
181	char base_ptr = (char )src;	23,006,211✔
182
183	const size_t max_thresh = MAX_THRESH * size;	23,006,211✔
184
185	if (nelem == 0) return;	23,006,211✔
186
187	if (nelem > MAX_THRESH) {	23,006,211✔
188	char *lo = base_ptr;	10,046,039✔
189	char hi = &lo[size (nelem - 1)];	10,046,039✔
190	stack_node stack[STACK_SIZE];	10,045,325✔
191	stack_node *top = stack;	10,045,527✔
192
193	PUSH(NULL, NULL);	10,045,527✔
194
195	while (STACK_NOT_EMPTY) {	2,147,483,647✔
196	char *left_ptr;
197	char *right_ptr;
198
199	char mid = lo + size ((hi - lo) / size >> 1);	2,147,483,647✔
200
201	if ((cmp)((void )mid, (void *)lo, arg) < 0) DOSWAP(mid, lo, size);	2,147,483,647✔
202	if ((cmp)((void )hi, (void *)mid, arg) < 0)	2,147,483,647✔
203	DOSWAP(mid, hi, size);	2,147,483,647✔
204	else
205	goto jump_over;	2,147,483,647✔
206	if ((cmp)((void )mid, (void *)lo, arg) < 0) DOSWAP(mid, lo, size);	1,545,219,673✔
207	jump_over:;	2,147,483,647✔
208
209	left_ptr = lo + size;	2,147,483,647✔
210	right_ptr = hi - size;	2,147,483,647✔
211	do {
212	while ((cmp)((void )left_ptr, (void *)mid, arg) < 0) left_ptr += size;	2,147,483,647✔
213
214	while ((cmp)((void )mid, (void *)right_ptr, arg) < 0) right_ptr -= size;	2,147,483,647✔
215
216	if (left_ptr < right_ptr) {	2,147,483,647✔
217	DOSWAP(left_ptr, right_ptr, size);	2,147,483,647✔
218	if (mid == left_ptr)	2,147,483,647✔
219	mid = right_ptr;	876,042,589✔
220	else if (mid == right_ptr)	2,147,483,647✔
221	mid = left_ptr;	476,207,716✔
222	left_ptr += size;	2,147,483,647✔
223	right_ptr -= size;	2,147,483,647✔
224	} else if (left_ptr == right_ptr) {	2,147,483,647✔
225	left_ptr += size;	2,147,483,647✔
226	right_ptr -= size;	2,147,483,647✔
227	break;	2,147,483,647✔
228	}
229	} while (left_ptr <= right_ptr);	2,147,483,647✔
230
231	if ((size_t)(right_ptr - lo) <= max_thresh) {	2,147,483,647✔
232	if ((size_t)(hi - left_ptr) <= max_thresh)	2,147,483,647✔
233	POP(lo, hi);	2,147,483,647✔
234	else
235	lo = left_ptr;	236,979,080✔
236	} else if ((size_t)(hi - left_ptr) <= max_thresh)	2,147,483,647✔
237	hi = right_ptr;	158,271,601✔
238	else if ((right_ptr - lo) > (hi - left_ptr)) {	2,147,483,647✔
239	PUSH(lo, right_ptr);	179,291,252✔
240	lo = left_ptr;	179,291,252✔
241	} else {
242	PUSH(left_ptr, hi);	2,062,910,977✔
243	hi = right_ptr;	2,062,889,580✔
244	}
245	}
246	}
247	#define min(x, y) ((x) < (y) ? (x) : (y))
248
249	{
250	char const end_ptr = &base_ptr[size (nelem - 1)];	23,006,211✔
251	char *tmp_ptr = base_ptr;	23,006,211✔
252	char *thresh = min(end_ptr, base_ptr + max_thresh);	23,006,211✔
253	char *run_ptr;
254
255	for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size)	102,404,791✔
256	if ((cmp)((void )run_ptr, (void *)tmp_ptr, arg) < 0) tmp_ptr = run_ptr;	79,397,251✔
257
258	if (tmp_ptr != base_ptr) DOSWAP(tmp_ptr, base_ptr, size);	57,233,765✔
259
260	run_ptr = base_ptr + size;	23,005,801✔
261	while ((run_ptr += size) <= end_ptr) {	2,147,483,647✔
262	tmp_ptr = run_ptr - size;	2,147,483,647✔
263	while ((tmp_ptr >= base_ptr) &&((cmp)((void )run_ptr, (void *)tmp_ptr, arg) < 0)) tmp_ptr -= size;	2,147,483,647✔
264
265	tmp_ptr += size;	2,147,483,647✔
266	if (tmp_ptr != run_ptr) {	2,147,483,647✔
267	char *trav;
268
269	trav = run_ptr + size;	1,545,741,427✔
270	while (--trav >= run_ptr) {	2,147,483,647✔
271	char c = *trav;	2,147,483,647✔
272	char hi, lo;
273
274	for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo) hi = lo;	2,147,483,647✔
275	*hi = c;	2,147,483,647✔
276	}
277	}
278	}
279	}
280	}
281
282	void taosbsearch(const void key, const void *base, int32_t nmemb, int32_t size, __compar_fn_t compar, int32_t flags) {	2,072,798,104✔
283	uint8_t *p;
284	int32_t lidx;
285	int32_t ridx;
286	int32_t midx;
287	int32_t c;
288
289	if (nmemb <= 0) return NULL;	2,072,798,104✔
290
291	lidx = 0;	1,971,036,416✔
292	ridx = nmemb - 1;	1,971,036,416✔
293	while (lidx <= ridx) {	2,147,483,647✔
294	midx = (lidx + ridx) / 2;	2,147,483,647✔
295	p = (uint8_t )base + size midx;	2,147,483,647✔
296
297	c = compar(key, p);	2,147,483,647✔
298	if (c == 0) {	2,147,483,647✔
299	if (flags == TD_GT) {	1,586,224,225✔
300	lidx = midx + 1;	4,162,653✔
301	} else if (flags == TD_LT) {	1,582,061,572✔
302	ridx = midx - 1;	3,030✔
303	} else {
304	break;	1,582,058,542✔
305	}
306	} else if (c < 0) {	2,145,723,695✔
307	ridx = midx - 1;	516,410,355✔
308	} else {
309	lidx = midx + 1;	1,629,313,340✔
310	}
311	}
312
313	if (flags == TD_EQ) {	1,971,253,527✔
314	return c ? NULL : p;	1,699,436,517✔
315	} else if (flags == TD_GE) {	271,817,010✔
316	return (c <= 0) ? p : (midx + 1 < nmemb ? p + size : NULL);	674,932✔
317	} else if (flags == TD_LE) {	271,142,078✔
318	return (c >= 0) ? p : (midx > 0 ? p - size : NULL);	221,274,617✔
319	} else if (flags == TD_GT) {	49,867,461✔
320	return (c < 0) ? p : (midx + 1 < nmemb ? p + size : NULL);	49,905,444✔
321	} else if (flags == TD_LT) {	31,551✔
322	return (c > 0) ? p : (midx > 0 ? p - size : NULL);	7,070✔
323	} else {
324	uError("Invalid bsearch flags:%d", flags);	30,113✔
325	return NULL;	×
326	}
327	}
328
329	int32_t taosheapadjust(void base, int32_t size, int32_t start, int32_t end, const void parcompar,	231,924,091✔
330	__ext_compar_fn_t compar, char *buf, bool maxroot) {
331	int32_t parent;
332	int32_t child;
333
334	char *tmp = NULL;	231,924,091✔
335	if (buf == NULL) {	231,924,091✔
336	tmp = taosMemoryMalloc(size);	38,828,457✔
337	if (NULL == tmp) {	38,823,943✔
338	return terrno;	×
339	}
340	} else {
341	tmp = buf;	193,095,634✔
342	}
343
344	if (base && size > 0 && compar) {	231,919,577✔
345	parent = start;	231,932,593✔
346	child = 2 * parent + 1;	231,932,593✔
347
348	if (maxroot) {	231,932,593✔
349	while (child <= end) {	122,762,906✔
350	if (child + 1 <= end &&	212,393,904✔
351	(*compar)(elePtrAt(base, size, child), elePtrAt(base, size, child + 1), parcompar) < 0) {	102,970,215✔
352	child++;	61,696,082✔
353	}
354
355	if ((*compar)(elePtrAt(base, size, parent), elePtrAt(base, size, child), parcompar) > 0) {	109,423,689✔
356	break;	75,287,318✔
357	}
358
359	doswap(elePtrAt(base, size, parent), elePtrAt(base, size, child), size, tmp);	34,162,320✔
360
361	parent = child;	34,125,249✔
362	child = 2 * parent + 1;	34,125,249✔
363	}
364	} else {
365	while (child <= end) {	212,843,376✔
366	if (child + 1 <= end &&	309,410,285✔
367	(*compar)(elePtrAt(base, size, child), elePtrAt(base, size, child + 1), parcompar) > 0) {	137,639,635✔
368	child++;	36,805,986✔
369	}
370
371	if ((*compar)(elePtrAt(base, size, parent), elePtrAt(base, size, child), parcompar) < 0) {	171,770,650✔
372	break;	102,302,072✔
373	}
374
375	doswap(elePtrAt(base, size, parent), elePtrAt(base, size, child), size, tmp);	69,519,308✔
376
377	parent = child;	69,548,440✔
378	child = 2 * parent + 1;	69,548,440✔
379	}
380	}
381	}
382
383	if (buf == NULL) {	232,012,339✔
384	taosMemoryFree(tmp);	38,826,473✔
385	}
386
387	return 0;	232,001,841✔
388	}
389
390	int32_t taosheapsort(void base, int32_t size, int32_t len, const void parcompar, __ext_compar_fn_t compar,	46,372,199✔
391	bool maxroot) {
392	int32_t i;
393
394	char *buf = taosMemoryCalloc(1, size);	46,372,199✔
395	if (buf == NULL) {	46,361,313✔
396	return terrno;	×
397	}
398
399	if (base && size > 0) {	46,361,313✔
400	for (i = len / 2 - 1; i >= 0; i--) {	239,546,941✔
401	int32_t code = taosheapadjust(base, size, i, len - 1, parcompar, compar, buf, maxroot);	193,099,047✔
402	if (code) {	193,184,293✔
UNCOV 403	taosMemoryFree(buf);	×
404	return code;	×
405	}
406	}
407	}
408
409	taosMemoryFree(buf);	46,447,004✔
410	return 0;	46,376,769✔
411	}
412
413	static void taosMerge(void src, int32_t start, int32_t leftend, int32_t end, int64_t size, const void param,	39,849,506✔
414	__ext_compar_fn_t comparFn, void *tmp) {
415	int32_t leftSize = leftend - start + 1;	39,849,506✔
416	int32_t rightSize = end - leftend;	39,849,506✔
417
418	void *leftBuf = tmp;	39,849,506✔
419	void rightBuf = (char )tmp + (leftSize * size);	39,849,506✔
420
421	memcpy(leftBuf, elePtrAt(src, size, start), leftSize * size);	39,849,578✔
422	memcpy(rightBuf, elePtrAt(src, size, leftend + 1), rightSize * size);	39,849,611✔
423
424	int32_t i = 0, j = 0, k = start;	39,825,216✔
425
426	while (i < leftSize && j < rightSize) {	2,147,483,647✔
427	int32_t ret = comparFn(elePtrAt(leftBuf, size, i), elePtrAt(rightBuf, size, j), param);	2,147,483,647✔
428	if (ret <= 0) {	2,147,483,647✔
429	memcpy(elePtrAt(src, size, k), elePtrAt(leftBuf, size, i), size);	1,981,808,255✔
430	i++;	1,981,944,813✔
431	} else {
432	memcpy(elePtrAt(src, size, k), elePtrAt(rightBuf, size, j), size);	1,775,391,970✔
433	j++;	1,775,273,344✔
434	}
435	k++;	2,147,483,647✔
436	}
437
438	while (i < leftSize) {	80,763,278✔
439	memcpy(elePtrAt(src, size, k), elePtrAt(leftBuf, size, i), size);	40,915,148✔
440	i++;	40,915,209✔
441	k++;	40,915,209✔
442	}
443
444	while (j < rightSize) {	110,729,642✔
445	memcpy(elePtrAt(src, size, k), elePtrAt(rightBuf, size, j), size);	70,880,346✔
446	j++;	70,881,512✔
447	k++;	70,881,512✔
448	}
449	}	39,849,296✔
450
451	static int32_t taosMergeSortHelper(void src, int64_t numOfElem, int64_t size, const void param,	3,615,766✔
452	__ext_compar_fn_t comparFn) {
453	// short array sort, instead of merge sort process
454	const int32_t THRESHOLD_SIZE = 6;	3,615,766✔
455	char *buf = taosMemoryCalloc(1, size); // prepare the swap buffer	3,615,766✔
456	if (buf == NULL) {	3,615,766✔
457	return terrno;	×
458	}
459
460	for (int32_t start = 0; start < numOfElem - 1; start += THRESHOLD_SIZE) {	47,076,007✔
461	int32_t end = (start + THRESHOLD_SIZE - 1) <= numOfElem - 1 ? (start + THRESHOLD_SIZE - 1) : numOfElem - 1;	43,460,251✔
462	tInsertSort(src, size, start, end, param, comparFn, buf);	43,460,251✔
463	}
464	taosMemoryFreeClear(buf);	3,615,756✔
465
466	if (numOfElem > THRESHOLD_SIZE) {	3,615,756✔
467	int32_t currSize;
468	void tmp = taosMemoryMalloc(numOfElem size);	463,104✔
469	if (tmp == NULL) {	463,104✔
470	return terrno;	×
471	}
472
473	for (currSize = THRESHOLD_SIZE; currSize <= numOfElem - 1; currSize = 2 * currSize) {	1,590,682✔
474	int32_t leftStart;
475	for (leftStart = 0; leftStart < numOfElem - 1; leftStart += 2 * currSize) {	40,976,872✔
476	int32_t leftend = leftStart + currSize - 1;	40,219,003✔
477	int32_t rightEnd =	40,219,003✔
478	(leftStart + 2 * currSize - 1 < numOfElem - 1) ? (leftStart + 2 * currSize - 1) : (numOfElem - 1);	40,219,003✔
479	if (leftend >= rightEnd) break;	40,219,003✔
480
481	taosMerge(src, leftStart, leftend, rightEnd, size, param, comparFn, tmp);	39,849,294✔
482	}
483	}
484
485	taosMemoryFreeClear(tmp);	462,351✔
486	}
487	return 0;	3,615,003✔
488	}
489
490	int32_t msortHelper(const void p1, const void p2, const void *param) {	2,147,483,647✔
491	__compar_fn_t comparFn = param;	2,147,483,647✔
492	return comparFn(p1, p2);	2,147,483,647✔
493	}
494
495	int32_t taosMergeSort(void *src, int64_t numOfElem, int64_t size, __compar_fn_t comparFn) {	3,615,766✔
496	void *param = comparFn;	3,615,766✔
497	return taosMergeSortHelper(src, numOfElem, size, param, msortHelper);	3,615,766✔
498	}

taosdata / TDengine / #5034

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