#4987

Committed 16 Mar 2026 12:26PM UTC coverage: 73.883% (+36.6%) from 37.305%

Build # #4987

Build Type

push

travis-ci

Committed by

web-flow

Commit Message

feat: support secure delete option. (#34591)

Coverage Stats

209 of 391 new or added lines in 24 files covered. (53.45%)

3062 existing lines in 140 files now uncovered.

261133 of 353439 relevant lines covered (73.88%)

121262425.02 hits per line

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

17.92

/tools/shell/src/shellTire.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 __USE_XOPEN

#include "os.h"
#include "shellTire.h"

// ----------- interface -------------

// create prefix search tree
STire* createTire(char type) {
  STire* tire = taosMemoryMalloc(sizeof(STire));
  memset(tire, 0, sizeof(STire));
  tire->ref = 1;  // init is 1
  tire->type = type;
  tire->root.d = (STireNode**)taosMemoryCalloc(CHAR_CNT, sizeof(STireNode*));
  return tire;
}

// free tire node
void freeTireNode(STireNode* node) {
  if (node == NULL) return;

  // nest free sub node on array d
  if (node->d) {
    for (int i = 0; i < CHAR_CNT; i++) {
      freeTireNode(node->d[i]);
    }
    taosMemoryFree(node->d);
  }

  // free self
  taosMemoryFree(node);
}

// destroy prefix search tree
void freeTire(STire* tire) {
  // free nodes
  for (int i = 0; i < CHAR_CNT; i++) {
    freeTireNode(tire->root.d[i]);
  }
  taosMemoryFree(tire->root.d);

  // free from list
  StrName* item = tire->head;
  while (item) {
    StrName* next = item->next;
    // free string
    taosMemoryFree(item->name);
    // free node
    taosMemoryFree(item);

    // move next
    item = next;
  }
  tire->head = tire->tail = NULL;

  // free tire
  taosMemoryFree(tire);
}

// insert a new word to list
bool insertToList(STire* tire, char* word) {
  StrName* p = (StrName*)taosMemoryMalloc(sizeof(StrName));
  p->name = taosStrdup(word);
  p->next = NULL;

  if (tire->head == NULL) {
    tire->head = p;
    tire->tail = p;
  } else {
    tire->tail->next = p;
    tire->tail = p;
  }

  return true;
}

// insert a new word to tree
bool insertToTree(STire* tire, char* word, int len) {
  int         m = 0;
  STireNode** nodes = tire->root.d;
  for (int i = 0; i < len; i++) {
    m = word[i] - FIRST_ASCII;
    if (m < 0 || m >= CHAR_CNT) {
      return false;
    }

    if (nodes[m] == NULL) {
      // no pointer
      STireNode* p = (STireNode*)taosMemoryMalloc(sizeof(STireNode));
      memset(p, 0, sizeof(STireNode));
      nodes[m] = p;
      if (i == len - 1) {
        // is end
        p->end = true;
        break;
      }
    }

    if (nodes[m]->d == NULL) {
      // malloc d
      nodes[m]->d = (STireNode**)taosMemoryCalloc(CHAR_CNT, sizeof(STireNode*));
    }

    // move to next node
    nodes = nodes[m]->d;
  }

  // add count
  tire->count += 1;
  return true;
}

// insert a new word
bool insertWord(STire* tire, char* word) {
  int len = strlen(word);
  if (len >= MAX_WORD_LEN) {
    return false;
  }

  switch (tire->type) {
    case TIRE_TREE:
      return insertToTree(tire, word, len);
    case TIRE_LIST:
      return insertToList(tire, word);
    default:
      break;
  }
  return false;
}

// delete one word from list
bool deleteFromList(STire* tire, char* word) {
  StrName* item = tire->head;
  while (item) {
    if (strcmp(item->name, word) == 0) {
      // found, reset empty to delete
      item->name[0] = 0;
    }

    // move next
    item = item->next;
  }
  return true;
}

// delete one word from tree
bool deleteFromTree(STire* tire, char* word, int len) {
  int  m = 0;
  bool del = false;

  STireNode** nodes = tire->root.d;
  for (int i = 0; i < len; i++) {
    m = word[i] - FIRST_ASCII;
    if (m < 0 || m >= CHAR_CNT) {
      return false;
    }

    if (nodes[m] == NULL) {
      // no found
      return false;
    } else {
      // not null
      if (i == len - 1) {
        // this is last, only set end false , not free node
        nodes[m]->end = false;
        del = true;
        break;
      }
    }

    if (nodes[m]->d == NULL) break;
    // move to next node
    nodes = nodes[m]->d;
  }

  // reduce count
  if (del) {
    tire->count -= 1;
  }

  return del;
}

// insert a new word
bool deleteWord(STire* tire, char* word) {
  int len = strlen(word);
  if (len >= MAX_WORD_LEN) {
    return false;
  }

  switch (tire->type) {
    case TIRE_TREE:
      return deleteFromTree(tire, word, len);
    case TIRE_LIST:
      return deleteFromList(tire, word);
    default:
      break;
  }
  return false;
}

void addWordToMatch(SMatch* match, char* word) {
  // malloc new
  SMatchNode* node = (SMatchNode*)taosMemoryMalloc(sizeof(SMatchNode));
  memset(node, 0, sizeof(SMatchNode));
  node->word = taosStrdup(word);

  // append to match
  if (match->head == NULL) {
    match->head = match->tail = node;
  } else {
    match->tail->next = node;
    match->tail = node;
  }
  match->count += 1;
}

// enum all words from node
void enumAllWords(STireNode** nodes, char* prefix, SMatch* match) {
  STireNode* c;
  char       word[MAX_WORD_LEN];
  int        len = strlen(prefix);
  for (int i = 0; i < CHAR_CNT; i++) {
    c = nodes[i];

    if (c == NULL) {
      // chain end node
      continue;
    } else {
      // combine word string
      memset(word, 0, tListLen(word));
      strncpy(word, prefix, len);
      word[len] = FIRST_ASCII + i;  // append current char

      // chain middle node
      if (c->end) {
        // have end flag
        addWordToMatch(match, word);
      }
      // nested call next layer
      if (c->d) enumAllWords(c->d, word, match);
    }
  }
}

// match prefix from list
void matchPrefixFromList(STire* tire, char* prefix, SMatch* match) {
  StrName* item = tire->head;
  int      len = strlen(prefix);
  while (item) {
    if (strncmp(item->name, prefix, len) == 0) {
      // prefix matched
      addWordToMatch(match, item->name);
    }

    // move next
    item = item->next;
  }
}

// match prefix words, if match is not NULL , put all item to match and return match
void matchPrefixFromTree(STire* tire, char* prefix, SMatch* match) {
  int        m = 0;
  STireNode* c = 0;
  int        len = strlen(prefix);
  if (len >= MAX_WORD_LEN) {
    return;
  }

  STireNode** nodes = tire->root.d;
  for (int i = 0; i < len; i++) {
    m = prefix[i] - FIRST_ASCII;
    if (m < 0 || m > CHAR_CNT) {
      return;
    }

    // match
    c = nodes[m];
    if (c == NULL) {
      // arrive end
      break;
    }

    // previous items already matched
    if (i == len - 1) {
      // prefix is match to end char
      if (c->d) enumAllWords(c->d, prefix, match);
    } else {
      // move to next node continue match
      if (c->d == NULL) break;
      nodes = c->d;
    }
  }
}

void matchPrefix(STire* tire, char* prefix, SMatch* match) {
  if (match == NULL) {
    return;
  }

  switch (tire->type) {
    case TIRE_TREE:
      matchPrefixFromTree(tire, prefix, match);
      break;
    case TIRE_LIST:
      matchPrefixFromList(tire, prefix, match);
      break;
    default:
      break;
  }
}

// get all items from tires tree
void enumFromList(STire* tire, SMatch* match) {
  StrName* item = tire->head;
  while (item) {
    if (item->name[0] != 0) {
      // not delete
      addWordToMatch(match, item->name);
    }

    // move next
    item = item->next;
  }
}

// get all items from tires tree
void enumFromTree(STire* tire, SMatch* match) {
  char       pre[2] = {0, 0};
  STireNode* c;

  // enum first layer
  for (int i = 0; i < CHAR_CNT; i++) {
    pre[0] = FIRST_ASCII + i;

    // each node
    c = tire->root.d[i];
    if (c == NULL) {
      // this branch no data
      continue;
    }

    // this branch have data
    if (c->end) {
      addWordToMatch(match, pre);
    } else {
      matchPrefix(tire, pre, match);
    }
  }
}

// get all items from tires tree
SMatch* enumAll(STire* tire) {
  SMatch* match = (SMatch*)taosMemoryMalloc(sizeof(SMatch));
  memset(match, 0, sizeof(SMatch));

  switch (tire->type) {
    case TIRE_TREE:
      enumFromTree(tire, match);
      break;
    case TIRE_LIST:
      enumFromList(tire, match);
      break;
    default:
      break;
  }

  // return if need
  if (match->count == 0) {
    freeMatch(match);
    match = NULL;
  }

  return match;
}

// free match result
void freeMatchNode(SMatchNode* node) {
  // first free next
  if (node->next) freeMatchNode(node->next);

  // second free self
  if (node->word) taosMemoryFree(node->word);
  taosMemoryFree(node);
}

// free match result
void freeMatch(SMatch* match) {
  // first free next
  if (match->head) {
    freeMatchNode(match->head);
  }

  // second free self
  taosMemoryFree(match);
}

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 __USE_XOPEN
17
18	#include "os.h"
19	#include "shellTire.h"
20
21	// ----------- interface -------------
22
23	// create prefix search tree
24	STire* createTire(char type) {	15,269,284✔
25	STire* tire = taosMemoryMalloc(sizeof(STire));	15,269,284✔
26	memset(tire, 0, sizeof(STire));	15,269,284✔
27	tire->ref = 1; // init is 1	15,269,284✔
28	tire->type = type;	15,269,284✔
29	tire->root.d = (STireNode*)taosMemoryCalloc(CHAR_CNT, sizeof(STireNode));	15,269,284✔
30	return tire;	15,269,284✔
31	}
32
33	// free tire node
34	void freeTireNode(STireNode* node) {	1,450,581,980✔
35	if (node == NULL) return;	1,450,581,980✔
36
37	// nest free sub node on array d
38	if (node->d) {	×
39	for (int i = 0; i < CHAR_CNT; i++) {	×
40	freeTireNode(node->d[i]);	×
41	}
42	taosMemoryFree(node->d);	×
43	}
44
45	// free self
46	taosMemoryFree(node);	×
47	}
48
49	// destroy prefix search tree
50	void freeTire(STire* tire) {	15,269,284✔
51	// free nodes
52	for (int i = 0; i < CHAR_CNT; i++) {	1,465,851,264✔
53	freeTireNode(tire->root.d[i]);	1,450,581,980✔
54	}
55	taosMemoryFree(tire->root.d);	15,269,284✔
56
57	// free from list
58	StrName* item = tire->head;	15,269,284✔
59	while (item) {	328,730,228✔
60	StrName* next = item->next;	313,460,944✔
61	// free string
62	taosMemoryFree(item->name);	313,460,944✔
63	// free node
64	taosMemoryFree(item);	313,460,944✔
65
66	// move next
67	item = next;	313,460,944✔
68	}
69	tire->head = tire->tail = NULL;	15,269,284✔
70
71	// free tire
72	taosMemoryFree(tire);	15,269,284✔
73	}	15,269,284✔
74
75	// insert a new word to list
76	bool insertToList(STire* tire, char* word) {	313,460,944✔
77	StrName* p = (StrName*)taosMemoryMalloc(sizeof(StrName));	313,460,944✔
78	p->name = taosStrdup(word);	313,460,944✔
79	p->next = NULL;	313,460,944✔
80
81	if (tire->head == NULL) {	313,460,944✔
82	tire->head = p;	15,269,284✔
83	tire->tail = p;	15,269,284✔
84	} else {
85	tire->tail->next = p;	298,191,660✔
86	tire->tail = p;	298,191,660✔
87	}
88
89	return true;	313,460,944✔
90	}
91
92	// insert a new word to tree
93	bool insertToTree(STire* tire, char* word, int len) {	×
94	int m = 0;	×
95	STireNode** nodes = tire->root.d;	×
96	for (int i = 0; i < len; i++) {	×
97	m = word[i] - FIRST_ASCII;	×
98	if (m < 0 \|\| m >= CHAR_CNT) {	×
99	return false;	×
100	}
101
102	if (nodes[m] == NULL) {	×
103	// no pointer
104	STireNode* p = (STireNode*)taosMemoryMalloc(sizeof(STireNode));	×
105	memset(p, 0, sizeof(STireNode));	×
106	nodes[m] = p;	×
107	if (i == len - 1) {	×
108	// is end
109	p->end = true;	×
110	break;	×
111	}
112	}
113
114	if (nodes[m]->d == NULL) {	×
115	// malloc d
116	nodes[m]->d = (STireNode*)taosMemoryCalloc(CHAR_CNT, sizeof(STireNode));	×
117	}
118
119	// move to next node
120	nodes = nodes[m]->d;	×
121	}
122
123	// add count
124	tire->count += 1;	×
125	return true;	×
126	}
127
128	// insert a new word
129	bool insertWord(STire* tire, char* word) {	313,460,944✔
130	int len = strlen(word);	313,460,944✔
131	if (len >= MAX_WORD_LEN) {	313,460,944✔
132	return false;	×
133	}
134
135	switch (tire->type) {	313,460,944✔
136	case TIRE_TREE:	×
137	return insertToTree(tire, word, len);	×
138	case TIRE_LIST:	313,460,944✔
139	return insertToList(tire, word);	313,460,944✔
140	default:	×
141	break;	×
142	}
143	return false;	×
144	}
145
146	// delete one word from list
147	bool deleteFromList(STire* tire, char* word) {	×
148	StrName* item = tire->head;	×
149	while (item) {	×
150	if (strcmp(item->name, word) == 0) {	×
151	// found, reset empty to delete
152	item->name[0] = 0;	×
153	}
154
155	// move next
156	item = item->next;	×
157	}
158	return true;	×
159	}
160
161	// delete one word from tree
162	bool deleteFromTree(STire* tire, char* word, int len) {	×
163	int m = 0;	×
164	bool del = false;	×
165
166	STireNode** nodes = tire->root.d;	×
167	for (int i = 0; i < len; i++) {	×
168	m = word[i] - FIRST_ASCII;	×
169	if (m < 0 \|\| m >= CHAR_CNT) {	×
170	return false;	×
171	}
172
173	if (nodes[m] == NULL) {	×
174	// no found
175	return false;	×
176	} else {
177	// not null
178	if (i == len - 1) {	×
179	// this is last, only set end false , not free node
180	nodes[m]->end = false;	×
181	del = true;	×
182	break;	×
183	}
184	}
185
186	if (nodes[m]->d == NULL) break;	×
187	// move to next node
188	nodes = nodes[m]->d;	×
189	}
190
191	// reduce count
192	if (del) {	×
193	tire->count -= 1;	×
194	}
195
196	return del;	×
197	}
198
199	// insert a new word
200	bool deleteWord(STire* tire, char* word) {	×
201	int len = strlen(word);	×
202	if (len >= MAX_WORD_LEN) {	×
203	return false;	×
204	}
205
206	switch (tire->type) {	×
207	case TIRE_TREE:	×
208	return deleteFromTree(tire, word, len);	×
209	case TIRE_LIST:	×
210	return deleteFromList(tire, word);	×
211	default:	×
212	break;	×
213	}
214	return false;	×
215	}
216
217	void addWordToMatch(SMatch* match, char* word) {	×
218	// malloc new
219	SMatchNode* node = (SMatchNode*)taosMemoryMalloc(sizeof(SMatchNode));	×
220	memset(node, 0, sizeof(SMatchNode));	×
221	node->word = taosStrdup(word);	×
222
223	// append to match
224	if (match->head == NULL) {	×
225	match->head = match->tail = node;	×
226	} else {
227	match->tail->next = node;	×
228	match->tail = node;	×
229	}
230	match->count += 1;	×
231	}	×
232
233	// enum all words from node
234	void enumAllWords(STireNode** nodes, char* prefix, SMatch* match) {	×
235	STireNode* c;
UNCOV 236	char word[MAX_WORD_LEN];	×
237	int len = strlen(prefix);	×
238	for (int i = 0; i < CHAR_CNT; i++) {	×
239	c = nodes[i];	×
240
241	if (c == NULL) {	×
242	// chain end node
243	continue;	×
244	} else {
245	// combine word string
246	memset(word, 0, tListLen(word));	×
247	strncpy(word, prefix, len);	×
248	word[len] = FIRST_ASCII + i; // append current char	×
249
250	// chain middle node
251	if (c->end) {	×
252	// have end flag
253	addWordToMatch(match, word);	×
254	}
255	// nested call next layer
256	if (c->d) enumAllWords(c->d, word, match);	×
257	}
258	}
259	}	×
260
261	// match prefix from list
262	void matchPrefixFromList(STire* tire, char* prefix, SMatch* match) {	×
263	StrName* item = tire->head;	×
264	int len = strlen(prefix);	×
265	while (item) {	×
266	if (strncmp(item->name, prefix, len) == 0) {	×
267	// prefix matched
268	addWordToMatch(match, item->name);	×
269	}
270
271	// move next
272	item = item->next;	×
273	}
274	}	×
275
276	// match prefix words, if match is not NULL , put all item to match and return match
277	void matchPrefixFromTree(STire* tire, char* prefix, SMatch* match) {	×
278	int m = 0;	×
279	STireNode* c = 0;	×
280	int len = strlen(prefix);	×
281	if (len >= MAX_WORD_LEN) {	×
282	return;	×
283	}
284
285	STireNode** nodes = tire->root.d;	×
286	for (int i = 0; i < len; i++) {	×
287	m = prefix[i] - FIRST_ASCII;	×
288	if (m < 0 \|\| m > CHAR_CNT) {	×
289	return;	×
290	}
291
292	// match
293	c = nodes[m];	×
294	if (c == NULL) {	×
295	// arrive end
296	break;	×
297	}
298
299	// previous items already matched
300	if (i == len - 1) {	×
301	// prefix is match to end char
302	if (c->d) enumAllWords(c->d, prefix, match);	×
303	} else {
304	// move to next node continue match
305	if (c->d == NULL) break;	×
306	nodes = c->d;	×
307	}
308	}
309	}
310
311	void matchPrefix(STire* tire, char* prefix, SMatch* match) {	×
312	if (match == NULL) {	×
313	return;	×
314	}
315
316	switch (tire->type) {	×
317	case TIRE_TREE:	×
318	matchPrefixFromTree(tire, prefix, match);	×
319	break;	×
320	case TIRE_LIST:	×
321	matchPrefixFromList(tire, prefix, match);	×
322	break;	×
323	default:	×
324	break;	×
325	}
326	}
327
328	// get all items from tires tree
329	void enumFromList(STire* tire, SMatch* match) {	×
330	StrName* item = tire->head;	×
331	while (item) {	×
332	if (item->name[0] != 0) {	×
333	// not delete
334	addWordToMatch(match, item->name);	×
335	}
336
337	// move next
338	item = item->next;	×
339	}
340	}	×
341
342	// get all items from tires tree
343	void enumFromTree(STire* tire, SMatch* match) {	×
344	char pre[2] = {0, 0};	×
345	STireNode* c;
346
347	// enum first layer
348	for (int i = 0; i < CHAR_CNT; i++) {	×
349	pre[0] = FIRST_ASCII + i;	×
350
351	// each node
352	c = tire->root.d[i];	×
353	if (c == NULL) {	×
354	// this branch no data
355	continue;	×
356	}
357
358	// this branch have data
359	if (c->end) {	×
360	addWordToMatch(match, pre);	×
361	} else {
362	matchPrefix(tire, pre, match);	×
363	}
364	}
365	}	×
366
367	// get all items from tires tree
368	SMatch* enumAll(STire* tire) {	×
369	SMatch* match = (SMatch*)taosMemoryMalloc(sizeof(SMatch));	×
370	memset(match, 0, sizeof(SMatch));	×
371
372	switch (tire->type) {	×
373	case TIRE_TREE:	×
374	enumFromTree(tire, match);	×
375	break;	×
376	case TIRE_LIST:	×
377	enumFromList(tire, match);	×
378	break;	×
379	default:	×
380	break;	×
381	}
382
383	// return if need
384	if (match->count == 0) {	×
385	freeMatch(match);	×
386	match = NULL;	×
387	}
388
389	return match;	×
390	}
391
392	// free match result
393	void freeMatchNode(SMatchNode* node) {	×
394	// first free next
395	if (node->next) freeMatchNode(node->next);	×
396
397	// second free self
398	if (node->word) taosMemoryFree(node->word);	×
399	taosMemoryFree(node);	×
400	}	×
401
402	// free match result
403	void freeMatch(SMatch* match) {	×
404	// first free next
405	if (match->head) {	×
406	freeMatchNode(match->head);	×
407	}
408
409	// second free self
410	taosMemoryFree(match);	×
411	}	×

taosdata / TDengine / #4987

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