This is an automated email from the ASF dual-hosted git repository. xiaoxiang781216 pushed a commit to branch master in repository https://gitbox.apache.org/repos/asf/nuttx.git
commit 88427d505c440485f2cb67324237aa60bf276dfc Author: Marco Casaroli <[email protected]> AuthorDate: Tue Oct 20 16:23:49 2026 +0200 libs/libc/search: Add tsearch(), tfind(), tdelete() and twalk(). POSIX (XSI) <search.h> has binary search trees: tsearch() finds or adds a key, tfind() finds it, tdelete() removes it and twalk() visits all nodes. NuttX had only the hash table functions. Add them as an AVL tree, so the height stays below 1.44 log2(n + 2) for any order of keys, and tdestroy(), the GNU extension that frees a tree. The first member of a node is the key pointer, as POSIX requires. tdelete() replaces a node with two children by its in-order predecessor node, so the other nodes do not move and pointers to them stay valid. Insertion and deletion walk with a fixed path array, not recursion. Assisted-by: Claude Code:claude-opus-5-5 Signed-off-by: Marco Casaroli <[email protected]> --- include/search.h | 32 ++++++++ libs/libc/libc.csv | 5 ++ libs/libc/search/CMakeLists.txt | 10 ++- libs/libc/search/Make.defs | 1 + libs/libc/search/lib_tdelete.c | 125 ++++++++++++++++++++++++++++++ libs/libc/search/lib_tdestroy.c | 62 +++++++++++++++ libs/libc/search/lib_tfind.c | 67 ++++++++++++++++ libs/libc/search/lib_tsearch.c | 166 ++++++++++++++++++++++++++++++++++++++++ libs/libc/search/lib_twalk.c | 81 ++++++++++++++++++++ libs/libc/search/tsearch.h | 73 ++++++++++++++++++ 10 files changed, 621 insertions(+), 1 deletion(-) diff --git a/include/search.h b/include/search.h index 04b758bd620..82762abb804 100644 --- a/include/search.h +++ b/include/search.h @@ -45,6 +45,16 @@ struct hsearch_data CODE void (*free_entry)(FAR ENTRY *entry); }; +/* The order in which twalk() visits a node */ + +typedef enum +{ + preorder, + postorder, + endorder, + leaf +} VISIT; + /* This is the callback type used by hforeach() */ typedef CODE void (*hforeach_t)(FAR ENTRY *entry, FAR void *data); @@ -200,4 +210,26 @@ int hsearch_r(ENTRY, ACTION, FAR ENTRY **, FAR struct hsearch_data *); void hforeach_r(hforeach_t, FAR void *, FAR struct hsearch_data *); +/**************************************************************************** + * Name: tsearch, tfind, tdelete, twalk, tdestroy + * + * Description: + * Binary search trees (an AVL tree). tsearch() finds or adds a key, + * tfind() finds it, tdelete() removes it, twalk() visits all nodes and + * tdestroy() (a GNU extension) frees the tree. The first member of a + * node is the pointer to its key. + * + ****************************************************************************/ + +FAR void *tsearch(FAR const void *key, FAR void **rootp, + CODE int (*compar)(FAR const void *, FAR const void *)); +FAR void *tfind(FAR const void *key, FAR void * const *rootp, + CODE int (*compar)(FAR const void *, FAR const void *)); +FAR void *tdelete(FAR const void *key, FAR void **rootp, + CODE int (*compar)(FAR const void *, FAR const void *)); +void twalk(FAR const void *root, + CODE void (*action)(FAR const void *node, VISIT visit, + int depth)); +void tdestroy(FAR void *root, CODE void (*free_node)(FAR void *key)); + #endif /* __INCLUDE_SEARCH_H */ diff --git a/libs/libc/libc.csv b/libs/libc/libc.csv index 17080b6a087..d190764acb7 100644 --- a/libs/libc/libc.csv +++ b/libs/libc/libc.csv @@ -347,8 +347,11 @@ "tcflush","termios.h","","int","int","int" "tcgetattr","termios.h","","int","int","FAR struct termios *" "tcsetattr","termios.h","","int","int","int","FAR const struct termios *" +"tdelete","search.h","","FAR void *","FAR const void *","FAR void **","int(*)(FAR const void *,FAR const void *)" +"tdestroy","search.h","","void","FAR void *","void(*)(FAR void *)" "telldir","dirent.h","","off_t","FAR DIR *" "textdomain","libintl.h","defined(CONFIG_LIBC_LOCALE_GETTEXT)","FAR char *","FAR const char *" +"tfind","search.h","","FAR void *","FAR const void *","FAR void * const *","int(*)(FAR const void *,FAR const void *)" "thrd_exit","threads.h","!defined(CONFIG_DISABLE_PTHREAD)","noreturn","int" "time","time.h","","time_t","FAR time_t *" "tolower","ctype.h","","int","int" @@ -356,6 +359,8 @@ "towlower","wchar.h","","wint_t","wint_t" "towupper","wchar.h","","wint_t","wint_t" "truncate","unistd.h","!defined(CONFIG_DISABLE_MOUNTPOINT)","int","FAR const char *","off_t" +"tsearch","search.h","","FAR void *","FAR const void *","FAR void **","int(*)(FAR const void *,FAR const void *)" +"twalk","search.h","","void","FAR const void *","void(*)(FAR const void *,VISIT,int)" "uname","sys/utsname.h","","int","FAR struct utsname *" "ungetc","stdio.h","defined(CONFIG_FILE_STREAM)","int","int","FAR FILE *" "ungetwc","wchar.h","defined(CONFIG_FILE_STREAM)","wint_t","wint_t","FAR FILE *" diff --git a/libs/libc/search/CMakeLists.txt b/libs/libc/search/CMakeLists.txt index a1a309073f5..e1242e39921 100644 --- a/libs/libc/search/CMakeLists.txt +++ b/libs/libc/search/CMakeLists.txt @@ -20,6 +20,14 @@ # # ############################################################################## -set(SRCS hash_func.c hcreate.c hcreate_r.c) +set(SRCS + hash_func.c + hcreate.c + hcreate_r.c + lib_tsearch.c + lib_tfind.c + lib_tdelete.c + lib_twalk.c + lib_tdestroy.c) target_sources(c PRIVATE ${SRCS}) diff --git a/libs/libc/search/Make.defs b/libs/libc/search/Make.defs index 38f703120a8..7f8708beee4 100644 --- a/libs/libc/search/Make.defs +++ b/libs/libc/search/Make.defs @@ -23,6 +23,7 @@ # Add the search C files to the build CSRCS += hcreate_r.c hcreate.c hash_func.c +CSRCS += lib_tsearch.c lib_tfind.c lib_tdelete.c lib_twalk.c lib_tdestroy.c # Add the search directory to the build diff --git a/libs/libc/search/lib_tdelete.c b/libs/libc/search/lib_tdelete.c new file mode 100644 index 00000000000..68b139c0858 --- /dev/null +++ b/libs/libc/search/lib_tdelete.c @@ -0,0 +1,125 @@ +/**************************************************************************** + * libs/libc/search/lib_tdelete.c + * + * SPDX-License-Identifier: Apache-2.0 + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. The + * ASF licenses this file to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance with the + * License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT + * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the + * License for the specific language governing permissions and limitations + * under the License. + * + ****************************************************************************/ + +/**************************************************************************** + * Included Files + ****************************************************************************/ + +#include <search.h> + +#include "libc.h" +#include "search/tsearch.h" + +/**************************************************************************** + * Public Functions + ****************************************************************************/ + +/**************************************************************************** + * Name: tdelete + * + * Description: + * Remove the node of key from the tree at *rootp. The other nodes stay + * where they are in memory: a node with two children is replaced by its + * in-order predecessor node, the keys do not move. + * + * Returned Value: + * A pointer to the parent of the removed node, rootp if it was the + * root, or NULL if the tree has no such key. + * + ****************************************************************************/ + +FAR void *tdelete(FAR const void *key, FAR void **rootp, + CODE int (*compar)(FAR const void *, FAR const void *)) +{ + FAR struct tnode_s **path[TSEARCH_MAXHEIGHT + 1]; + FAR struct tnode_s **link; + FAR struct tnode_s *node; + FAR struct tnode_s *pred; + FAR void *parent; + int n = 0; + int k; + int c; + + if (rootp == NULL) + { + return NULL; + } + + link = (FAR struct tnode_s **)rootp; + path[n++] = link; + while (*link != NULL && (c = compar(key, (*link)->key)) != 0) + { + link = &(*link)->child[c > 0]; + path[n++] = link; + } + + node = *link; + if (node == NULL) + { + return NULL; + } + + k = n - 1; + parent = k > 0 ? (FAR void *)*path[k - 1] : (FAR void *)rootp; + + if (node->child[0] != NULL && node->child[1] != NULL) + { + /* Find the predecessor: the rightmost node of the left subtree */ + + link = &node->child[0]; + path[n++] = link; + while ((*link)->child[1] != NULL) + { + link = &(*link)->child[1]; + path[n++] = link; + } + + /* Unlink it and put it where the node was */ + + pred = *link; + *link = pred->child[0]; + pred->child[0] = node->child[0]; + pred->child[1] = node->child[1]; + pred->height = node->height; + *path[k] = pred; + + /* The path went through the removed node */ + + path[k + 1] = &pred->child[0]; + } + else + { + *link = node->child[node->child[0] == NULL]; + } + + lib_free(node); + + /* Rebalance the ancestors of the changed link, while their height + * changes. + */ + + for (n -= 2; n >= 0 && tsearch_balance(path[n]); n--) + { + } + + return parent; +} diff --git a/libs/libc/search/lib_tdestroy.c b/libs/libc/search/lib_tdestroy.c new file mode 100644 index 00000000000..2f719385434 --- /dev/null +++ b/libs/libc/search/lib_tdestroy.c @@ -0,0 +1,62 @@ +/**************************************************************************** + * libs/libc/search/lib_tdestroy.c + * + * SPDX-License-Identifier: Apache-2.0 + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. The + * ASF licenses this file to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance with the + * License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT + * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the + * License for the specific language governing permissions and limitations + * under the License. + * + ****************************************************************************/ + +/**************************************************************************** + * Included Files + ****************************************************************************/ + +#include <search.h> + +#include "libc.h" +#include "search/tsearch.h" + +/**************************************************************************** + * Public Functions + ****************************************************************************/ + +/**************************************************************************** + * Name: tdestroy + * + * Description: + * Free all nodes of the tree, and call free_node for the key of each + * (a GNU extension). + * + ****************************************************************************/ + +void tdestroy(FAR void *root, CODE void (*free_node)(FAR void *)) +{ + FAR struct tnode_s *node = root; + + if (node == NULL) + { + return; + } + + tdestroy(node->child[0], free_node); + tdestroy(node->child[1], free_node); + if (free_node != NULL) + { + free_node((FAR void *)node->key); + } + + lib_free(node); +} diff --git a/libs/libc/search/lib_tfind.c b/libs/libc/search/lib_tfind.c new file mode 100644 index 00000000000..bcec1abc9af --- /dev/null +++ b/libs/libc/search/lib_tfind.c @@ -0,0 +1,67 @@ +/**************************************************************************** + * libs/libc/search/lib_tfind.c + * + * SPDX-License-Identifier: Apache-2.0 + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. The + * ASF licenses this file to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance with the + * License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT + * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the + * License for the specific language governing permissions and limitations + * under the License. + * + ****************************************************************************/ + +/**************************************************************************** + * Included Files + ****************************************************************************/ + +#include <search.h> + +#include "search/tsearch.h" + +/**************************************************************************** + * Public Functions + ****************************************************************************/ + +/**************************************************************************** + * Name: tfind + * + * Description: + * Find the node of key in the tree at *rootp. + * + * Returned Value: + * A pointer to the node, or NULL if the tree has no such key. + * + ****************************************************************************/ + +FAR void *tfind(FAR const void *key, FAR void * const *rootp, + CODE int (*compar)(FAR const void *, FAR const void *)) +{ + FAR struct tnode_s *node; + int c; + + if (rootp == NULL) + { + return NULL; + } + + for (node = *rootp; node != NULL; node = node->child[c > 0]) + { + c = compar(key, node->key); + if (c == 0) + { + return node; + } + } + + return NULL; +} diff --git a/libs/libc/search/lib_tsearch.c b/libs/libc/search/lib_tsearch.c new file mode 100644 index 00000000000..530e9e374df --- /dev/null +++ b/libs/libc/search/lib_tsearch.c @@ -0,0 +1,166 @@ +/**************************************************************************** + * libs/libc/search/lib_tsearch.c + * + * SPDX-License-Identifier: Apache-2.0 + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. The + * ASF licenses this file to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance with the + * License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT + * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the + * License for the specific language governing permissions and limitations + * under the License. + * + ****************************************************************************/ + +/**************************************************************************** + * Included Files + ****************************************************************************/ + +#include <search.h> + +#include "libc.h" +#include "search/tsearch.h" + +/**************************************************************************** + * Private Functions + ****************************************************************************/ + +static int tsearch_height(FAR const struct tnode_s *node) +{ + return node != NULL ? node->height : 0; +} + +static void tsearch_update(FAR struct tnode_s *node) +{ + int h0 = tsearch_height(node->child[0]); + int h1 = tsearch_height(node->child[1]); + + node->height = (h0 > h1 ? h0 : h1) + 1; +} + +/**************************************************************************** + * Public Functions + ****************************************************************************/ + +/**************************************************************************** + * Name: tsearch_balance + ****************************************************************************/ + +int tsearch_balance(FAR struct tnode_s **link) +{ + FAR struct tnode_s *node = *link; + FAR struct tnode_s *heavy; + FAR struct tnode_s *inner; + int old = node->height; + int h0 = tsearch_height(node->child[0]); + int h1 = tsearch_height(node->child[1]); + int other; + int dir; + + if (h0 - h1 <= 1 && h1 - h0 <= 1) + { + tsearch_update(node); + return node->height != old; + } + + /* dir is the heavy side. An inner grandchild that is higher than the + * outer one needs a double rotation. + */ + + dir = h1 > h0; + other = !dir; + heavy = node->child[dir]; + inner = heavy->child[other]; + + if (tsearch_height(inner) > tsearch_height(heavy->child[dir])) + { + heavy->child[other] = inner->child[dir]; + node->child[dir] = inner->child[other]; + inner->child[dir] = heavy; + inner->child[other] = node; + tsearch_update(heavy); + tsearch_update(node); + tsearch_update(inner); + *link = inner; + } + else + { + node->child[dir] = inner; + heavy->child[other] = node; + tsearch_update(node); + tsearch_update(heavy); + *link = heavy; + } + + return (*link)->height != old; +} + +/**************************************************************************** + * Name: tsearch + * + * Description: + * Find the node of key in the tree at *rootp; add one if there is none. + * The tree is an AVL tree. + * + * Returned Value: + * A pointer to the node (its first member is the key pointer), or NULL + * if there is no memory or rootp is NULL. + * + ****************************************************************************/ + +FAR void *tsearch(FAR const void *key, FAR void **rootp, + CODE int (*compar)(FAR const void *, FAR const void *)) +{ + FAR struct tnode_s **path[TSEARCH_MAXHEIGHT + 1]; + FAR struct tnode_s **link; + FAR struct tnode_s *node; + int n = 0; + int c; + + if (rootp == NULL) + { + return NULL; + } + + link = (FAR struct tnode_s **)rootp; + path[n++] = link; + while (*link != NULL) + { + c = compar(key, (*link)->key); + if (c == 0) + { + return *link; + } + + link = &(*link)->child[c > 0]; + path[n++] = link; + } + + node = lib_malloc(sizeof(*node)); + if (node == NULL) + { + return NULL; + } + + node->key = key; + node->child[0] = NULL; + node->child[1] = NULL; + node->height = 1; + *link = node; + + /* The ancestors, from the parent up, while their height changes */ + + for (n -= 2; n >= 0 && tsearch_balance(path[n]); n--) + { + } + + return node; +} diff --git a/libs/libc/search/lib_twalk.c b/libs/libc/search/lib_twalk.c new file mode 100644 index 00000000000..ee21dc3e17a --- /dev/null +++ b/libs/libc/search/lib_twalk.c @@ -0,0 +1,81 @@ +/**************************************************************************** + * libs/libc/search/lib_twalk.c + * + * SPDX-License-Identifier: Apache-2.0 + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. The + * ASF licenses this file to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance with the + * License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT + * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the + * License for the specific language governing permissions and limitations + * under the License. + * + ****************************************************************************/ + +/**************************************************************************** + * Included Files + ****************************************************************************/ + +#include <search.h> + +#include "search/tsearch.h" + +/**************************************************************************** + * Private Functions + ****************************************************************************/ + +static void twalk_node(FAR const struct tnode_s *node, + CODE void (*action)(FAR const void *, VISIT, int), + int depth) +{ + if (node->child[0] == NULL && node->child[1] == NULL) + { + action(node, leaf, depth); + return; + } + + action(node, preorder, depth); + if (node->child[0] != NULL) + { + twalk_node(node->child[0], action, depth + 1); + } + + action(node, postorder, depth); + if (node->child[1] != NULL) + { + twalk_node(node->child[1], action, depth + 1); + } + + action(node, endorder, depth); +} + +/**************************************************************************** + * Public Functions + ****************************************************************************/ + +/**************************************************************************** + * Name: twalk + * + * Description: + * Call action for each node of the tree, depth first, left to right: + * preorder, postorder and endorder for a node with children, leaf for a + * node without. The depth of the root is 0. + * + ****************************************************************************/ + +void twalk(FAR const void *root, + CODE void (*action)(FAR const void *, VISIT, int)) +{ + if (root != NULL && action != NULL) + { + twalk_node(root, action, 0); + } +} diff --git a/libs/libc/search/tsearch.h b/libs/libc/search/tsearch.h new file mode 100644 index 00000000000..dc3bed26fa7 --- /dev/null +++ b/libs/libc/search/tsearch.h @@ -0,0 +1,73 @@ +/**************************************************************************** + * libs/libc/search/tsearch.h + * + * SPDX-License-Identifier: Apache-2.0 + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. The + * ASF licenses this file to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance with the + * License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT + * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the + * License for the specific language governing permissions and limitations + * under the License. + * + ****************************************************************************/ + +#ifndef __LIBS_LIBC_SEARCH_TSEARCH_H +#define __LIBS_LIBC_SEARCH_TSEARCH_H + +/**************************************************************************** + * Included Files + ****************************************************************************/ + +#include <nuttx/compiler.h> + +#include <search.h> + +/**************************************************************************** + * Pre-processor Definitions + ****************************************************************************/ + +/* The height of an AVL tree is less than 1.45 * log2(n + 2) */ + +#define TSEARCH_MAXHEIGHT (sizeof(FAR void *) * 8 * 3 / 2) + +/**************************************************************************** + * Public Types + ****************************************************************************/ + +/* A node of the tree. POSIX: the key pointer is the first member, so a + * pointer to a node is also a pointer to its key pointer. + */ + +struct tnode_s +{ + FAR const void *key; + FAR struct tnode_s *child[2]; + int height; +}; + +/**************************************************************************** + * Public Function Prototypes + ****************************************************************************/ + +/**************************************************************************** + * Name: tsearch_balance + * + * Description: + * Update the height of the subtree at *link and rotate it if its two + * sides differ by more than one. Return nonzero if the height of the + * subtree changed. + * + ****************************************************************************/ + +int tsearch_balance(FAR struct tnode_s **link); + +#endif /* __LIBS_LIBC_SEARCH_TSEARCH_H */
