#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

62.25

/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 ((*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,	1,496,666✔
45	void *buf) {
46	for (int32_t i = s + 1; i <= e; ++i) {	8,848,980✔
47	for (int32_t j = i; j > s; --j) {	8,540,924✔
48	if (comparFn(elePtrAt(src, size, j), elePtrAt(src, size, j - 1), param) < 0) {	8,237,056✔
49	doswap(elePtrAt(src, size, j), elePtrAt(src, size, j - 1), size, buf);	1,186,566✔
50	} else {
51	break;	7,048,446✔
52	}
53	}
54	}
55	}	1,494,622✔
56
57	static void tqsortImpl(void src, int32_t start, int32_t end, int64_t size, const void param,	×
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;	×
61	if (end - start + 1 <= THRESHOLD_SIZE) {	×
62	tInsertSort(src, size, start, end, param, comparFn, buf);	×
63	return;	×
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) {	×
149	char *buf = taosMemoryCalloc(1, size); // prepare the swap buffer	×
150	if (NULL == buf) {	×
151	return terrno;	×
152	}
153	tqsortImpl(src, 0, (int32_t)numOfElem - 1, (int32_t)size, param, comparFn, buf);	×
154	taosMemoryFreeClear(buf);	×
155	return 0;	×
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) {	146,834✔
180	const int32_t MAX_THRESH = 6;	146,834✔
181	char base_ptr = (char )src;	146,834✔
182
183	const size_t max_thresh = MAX_THRESH * size;	146,834✔
184
185	if (nelem == 0) return;	146,834!
186
187	if (nelem > MAX_THRESH) {	146,834✔
188	char *lo = base_ptr;	65,628✔
189	char hi = &lo[size (nelem - 1)];	65,628✔
190	stack_node stack[STACK_SIZE];
191	stack_node *top = stack;	65,628✔
192
193	PUSH(NULL, NULL);	65,628✔
194
UNCOV 195	while (STACK_NOT_EMPTY) {	×
196	char *left_ptr;
197	char *right_ptr;
198
199	char mid = lo + size ((hi - lo) / size >> 1);	10,995,163✔
200
201	if ((cmp)((void )mid, (void *)lo, arg) < 0) DOSWAP(mid, lo, size);	19,359,638✔
202	if ((cmp)((void )hi, (void *)mid, arg) < 0)	10,991,895✔
203	DOSWAP(mid, hi, size);	16,613,094✔
204	else
205	goto jump_over;	6,837,401✔
206	if ((cmp)((void )mid, (void *)lo, arg) < 0) DOSWAP(mid, lo, size);	9,212,877✔
207	jump_over:;	4,153,591✔
208
209	left_ptr = lo + size;	10,990,992✔
210	right_ptr = hi - size;	10,990,992✔
211	do {
212	while ((cmp)((void )left_ptr, (void *)mid, arg) < 0) left_ptr += size;	400,101,448✔
213
214	while ((cmp)((void )mid, (void *)right_ptr, arg) < 0) right_ptr -= size;	392,599,959✔
215
216	if (left_ptr < right_ptr) {	162,844,912!
217	DOSWAP(left_ptr, right_ptr, size);	654,805,382✔
218	if (mid == left_ptr)	163,595,221✔
219	mid = right_ptr;	4,257,775✔
220	else if (mid == right_ptr)	159,337,446✔
221	mid = left_ptr;	2,809,557✔
222	left_ptr += size;	163,595,221✔
223	right_ptr -= size;	163,595,221✔
UNCOV 224	} else if (left_ptr == right_ptr) {	×
225	left_ptr += size;	4,376,375✔
226	right_ptr -= size;	4,376,375✔
227	break;	4,376,375✔
228	}
229	} while (left_ptr <= right_ptr);	158,468,537!
230
UNCOV 231	if ((size_t)(right_ptr - lo) <= max_thresh) {	×
232	if ((size_t)(hi - left_ptr) <= max_thresh)	5,627,212✔
233	POP(lo, hi);	4,433,514✔
234	else
235	lo = left_ptr;	1,193,698✔
236	} else if ((size_t)(hi - left_ptr) <= max_thresh)	×
237	hi = right_ptr;	1,009,005✔
238	else if ((right_ptr - lo) > (hi - left_ptr)) {	×
239	PUSH(lo, right_ptr);	983,212✔
240	lo = left_ptr;	983,212✔
241	} else {
242	PUSH(left_ptr, hi);	×
243	hi = right_ptr;	×
244	}
245	}
246	}
247	#define min(x, y) ((x) < (y) ? (x) : (y))
248
249	{
250	char const end_ptr = &base_ptr[size (nelem - 1)];	×
251	char *tmp_ptr = base_ptr;	×
252	char *thresh = min(end_ptr, base_ptr + max_thresh);	×
253	char *run_ptr;
254
255	for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size)	×
256	if ((cmp)((void )run_ptr, (void *)tmp_ptr, arg) < 0) tmp_ptr = run_ptr;	504,732✔
257
258	if (tmp_ptr != base_ptr) DOSWAP(tmp_ptr, base_ptr, size);	×
259
260	run_ptr = base_ptr + size;	×
261	while ((run_ptr += size) <= end_ptr) {	44,885,386!
262	tmp_ptr = run_ptr - size;	56,652,363✔
263	while ((cmp)((void )run_ptr, (void *)tmp_ptr, arg) < 0) tmp_ptr -= size;	76,340,534✔
264
265	tmp_ptr += size;	56,236,631✔
266	if (tmp_ptr != run_ptr) {	56,236,631✔
267	char *trav;
268
269	trav = run_ptr + size;	10,969,299✔
270	while (--trav >= run_ptr) {	54,837,962✔
271	char c = *trav;	43,868,663✔
272	char hi, lo;
273
274	for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo) hi = lo;	122,854,778✔
275	*hi = c;	43,868,663✔
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) {	8,023,673✔
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;	8,023,673✔
290
291	lidx = 0;	7,251,431✔
292	ridx = nmemb - 1;	7,251,431✔
293	while (lidx <= ridx) {	17,355,183✔
294	midx = (lidx + ridx) / 2;	15,803,362✔
295	p = (uint8_t )base + size midx;	15,803,362✔
296
297	c = compar(key, p);	15,803,362✔
298	if (c == 0) {	15,802,205✔
299	if (flags == TD_GT) {	5,698,453!
300	lidx = midx + 1;	×
301	} else if (flags == TD_LT) {	5,698,453!
302	ridx = midx - 1;	×
303	} else {
304	break;	5,698,453✔
305	}
306	} else if (c < 0) {	10,103,752✔
307	ridx = midx - 1;	1,882,843✔
308	} else {
309	lidx = midx + 1;	8,220,909✔
310	}
311	}
312
313	if (flags == TD_EQ) {	7,250,274✔
314	return c ? NULL : p;	6,580,482✔
315	} else if (flags == TD_GE) {	669,792!
316	return (c <= 0) ? p : (midx + 1 < nmemb ? p + size : NULL);	×
317	} else if (flags == TD_LE) {	669,792✔
318	return (c >= 0) ? p : (midx > 0 ? p - size : NULL);	386,313✔
319	} else if (flags == TD_GT) {	283,479!
320	return (c < 0) ? p : (midx + 1 < nmemb ? p + size : NULL);	284,047✔
UNCOV 321	} else if (flags == TD_LT) {	×
322	return (c > 0) ? p : (midx > 0 ? p - size : NULL);	×
323	} else {
UNCOV 324	uError("Invalid bsearch flags:%d", flags);	×
325	return NULL;	×
326	}
327	}
328
329	int32_t taosheapadjust(void base, int32_t size, int32_t start, int32_t end, const void parcompar,	1,019,069✔
330	__ext_compar_fn_t compar, char *buf, bool maxroot) {
331	int32_t parent;
332	int32_t child;
333
334	char *tmp = NULL;	1,019,069✔
335	if (buf == NULL) {	1,019,069✔
336	tmp = taosMemoryMalloc(size);	234,931✔
337	if (NULL == tmp) {	235,043!
338	return terrno;	×
339	}
340	} else {
341	tmp = buf;	784,138✔
342	}
343
344	if (base && size > 0 && compar) {	1,019,181!
345	parent = start;	1,021,224✔
346	child = 2 * parent + 1;	1,021,224✔
347
348	if (maxroot) {	1,021,224✔
349	while (child <= end) {	511,756✔
350	if (child + 1 <= end &&	896,652✔
351	(*compar)(elePtrAt(base, size, child), elePtrAt(base, size, child + 1), parcompar) < 0) {	438,064✔
352	child++;	243,737✔
353	}
354
355	if ((*compar)(elePtrAt(base, size, parent), elePtrAt(base, size, child), parcompar) > 0) {	458,588✔
356	break;	289,018✔
357	}
358
359	doswap(elePtrAt(base, size, parent), elePtrAt(base, size, child), size, tmp);	170,205✔
360
361	parent = child;	170,205✔
362	child = 2 * parent + 1;	170,205✔
363	}
364	} else {
365	while (child <= end) {	1,048,766✔
366	if (child + 1 <= end &&	1,378,192✔
367	(*compar)(elePtrAt(base, size, child), elePtrAt(base, size, child + 1), parcompar) > 0) {	574,585✔
368	child++;	211,354✔
369	}
370
371	if ((*compar)(elePtrAt(base, size, parent), elePtrAt(base, size, child), parcompar) < 0) {	803,607✔
372	break;	432,094✔
373	}
374
375	doswap(elePtrAt(base, size, parent), elePtrAt(base, size, child), size, tmp);	369,093✔
376
377	parent = child;	369,093✔
378	child = 2 * parent + 1;	369,093✔
379	}
380	}
381	}
382
383	if (buf == NULL) {	1,012,370✔
384	taosMemoryFree(tmp);	236,203✔
385	}
386
387	return 0;	1,021,821✔
388	}
389
390	int32_t taosheapsort(void base, int32_t size, int32_t len, const void parcompar, __ext_compar_fn_t compar,	155,045✔
391	bool maxroot) {
392	int32_t i;
393
394	char *buf = taosMemoryCalloc(1, size);	155,045✔
395	if (buf == NULL) {	155,234!
396	return terrno;	×
397	}
398
399	if (base && size > 0) {	155,234!
400	for (i = len / 2 - 1; i >= 0; i--) {	940,358✔
401	int32_t code = taosheapadjust(base, size, i, len - 1, parcompar, compar, buf, maxroot);	785,934✔
402	if (code) {	785,083!
UNCOV 403	taosMemoryFree(buf);	×
404	return code;	×
405	}
406	}
407	}
408
409	taosMemoryFree(buf);	154,437✔
410	return 0;	154,999✔
411	}
412
413	static void taosMerge(void src, int32_t start, int32_t leftend, int32_t end, int64_t size, const void param,	1,492,671✔
414	__ext_compar_fn_t comparFn, void *tmp) {
415	int32_t leftSize = leftend - start + 1;	1,492,671✔
416	int32_t rightSize = end - leftend;	1,492,671✔
417
418	void *leftBuf = tmp;	1,492,671✔
419	void rightBuf = (char )tmp + (leftSize * size);	1,492,671✔
420
421	memcpy(leftBuf, elePtrAt(src, size, start), leftSize * size);	1,492,671✔
422	memcpy(rightBuf, elePtrAt(src, size, leftend + 1), rightSize * size);	1,492,671✔
423
424	int32_t i = 0, j = 0, k = start;	1,492,671✔
425
426	while (i < leftSize && j < rightSize) {	45,026,259✔
427	int32_t ret = comparFn(elePtrAt(leftBuf, size, i), elePtrAt(rightBuf, size, j), param);	43,681,567✔
428	if (ret <= 0) {	43,533,588✔
429	memcpy(elePtrAt(src, size, k), elePtrAt(leftBuf, size, i), size);	40,989,414✔
430	i++;	40,989,414✔
431	} else {
432	memcpy(elePtrAt(src, size, k), elePtrAt(rightBuf, size, j), size);	2,544,174✔
433	j++;	2,544,174✔
434	}
435	k++;	43,533,588✔
436	}
437
438	while (i < leftSize) {	1,453,168✔
439	memcpy(elePtrAt(src, size, k), elePtrAt(leftBuf, size, i), size);	108,476✔
440	i++;	108,476✔
441	k++;	108,476✔
442	}
443
444	while (j < rightSize) {	40,234,080✔
445	memcpy(elePtrAt(src, size, k), elePtrAt(rightBuf, size, j), size);	38,889,388✔
446	j++;	38,889,388✔
447	k++;	38,889,388✔
448	}
449	}	1,344,692✔
450
451	static int32_t taosMergeSortHelper(void src, int64_t numOfElem, int64_t size, const void param,	17,992✔
452	__ext_compar_fn_t comparFn) {
453	// short array sort, instead of merge sort process
454	const int32_t THRESHOLD_SIZE = 6;	17,992✔
455	char *buf = taosMemoryCalloc(1, size); // prepare the swap buffer	17,992✔
456	if (buf == NULL) {	17,992!
457	return terrno;	×
458	}
459
460	for (int32_t start = 0; start < numOfElem - 1; start += THRESHOLD_SIZE) {	1,513,118✔
461	int32_t end = (start + THRESHOLD_SIZE - 1) <= numOfElem - 1 ? (start + THRESHOLD_SIZE - 1) : numOfElem - 1;	1,495,397✔
462	tInsertSort(src, size, start, end, param, comparFn, buf);	1,495,397✔
463	}
464	taosMemoryFreeClear(buf);	17,721!
465
466	if (numOfElem > THRESHOLD_SIZE) {	17,721✔
467	int32_t currSize;
468	void tmp = taosMemoryMalloc(numOfElem size);	2,237✔
469	if (tmp == NULL) {	2,237!
470	return terrno;	×
471	}
472
473	for (currSize = THRESHOLD_SIZE; currSize <= numOfElem - 1; currSize = 2 * currSize) {	21,844✔
474	int32_t leftStart;
475	for (leftStart = 0; leftStart < numOfElem - 1; leftStart += 2 * currSize) {	1,513,686✔
476	int32_t leftend = leftStart + currSize - 1;	1,500,680✔
477	int32_t rightEnd =	1,500,680✔
478	(leftStart + 2 * currSize - 1 < numOfElem - 1) ? (leftStart + 2 * currSize - 1) : (numOfElem - 1);	1,500,680✔
479	if (leftend >= rightEnd) break;	1,500,680✔
480
481	taosMerge(src, leftStart, leftend, rightEnd, size, param, comparFn, tmp);	1,494,079✔
482	}
483	}
484
485	taosMemoryFreeClear(tmp);	1,268!
486	}
487	return 0;	16,752✔
488	}
489
490	int32_t msortHelper(const void p1, const void p2, const void *param) {	51,343,824✔
491	__compar_fn_t comparFn = param;	51,343,824✔
492	return comparFn(p1, p2);	51,343,824✔
493	}
494
495	int32_t taosMergeSort(void *src, int64_t numOfElem, int64_t size, __compar_fn_t comparFn) {	17,992✔
496	void *param = comparFn;	17,992✔
497	return taosMergeSortHelper(src, numOfElem, size, param, msortHelper);	17,992✔
498	}

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