Switch to upstream NetBSD tdelete/tfind/tsearch.
tdestroy is a GNU extension, so that stays.
Change-Id: Iedebaff25ea7e92b1ab1dd4440da12b67b99aa40
diff --git a/libc/bionic/tdelete.c b/libc/bionic/tdelete.c
deleted file mode 100644
index b64b47a..0000000
--- a/libc/bionic/tdelete.c
+++ /dev/null
@@ -1,71 +0,0 @@
-/* $NetBSD: tdelete.c,v 1.2 1999/09/16 11:45:37 lukem Exp $ */
-
-/*
- * Tree search generalized from Knuth (6.2.2) Algorithm T just like
- * the AT&T man page says.
- *
- * The node_t structure is for internal use only, lint doesn't grok it.
- *
- * Written by reading the System V Interface Definition, not the code.
- *
- * Totally public domain.
- */
-
-#include <sys/cdefs.h>
-#if 0
-#if defined(LIBC_SCCS) && !defined(lint)
-__RCSID("$NetBSD: tdelete.c,v 1.2 1999/09/16 11:45:37 lukem Exp $");
-#endif /* LIBC_SCCS and not lint */
-#endif
-__FBSDID("$FreeBSD: release/9.0.0/lib/libc/stdlib/tdelete.c 108694 2003-01-05 02:43:18Z tjr $");
-
-#define _SEARCH_PRIVATE
-#include <search.h>
-#include <stdlib.h>
-
-
-/*
- * delete node with given key
- *
- * vkey: key to be deleted
- * vrootp: address of the root of the tree
- * compar: function to carry out node comparisons
- */
-void *
-tdelete(const void * __restrict vkey, void ** __restrict vrootp,
- int (*compar)(const void *, const void *))
-{
- node_t **rootp = (node_t **)vrootp;
- node_t *p, *q, *r;
- int cmp;
-
- if (rootp == NULL || (p = *rootp) == NULL)
- return NULL;
-
- while ((cmp = (*compar)(vkey, (*rootp)->key)) != 0) {
- p = *rootp;
- rootp = (cmp < 0) ?
- &(*rootp)->llink : /* follow llink branch */
- &(*rootp)->rlink; /* follow rlink branch */
- if (*rootp == NULL)
- return NULL; /* key not found */
- }
- r = (*rootp)->rlink; /* D1: */
- if ((q = (*rootp)->llink) == NULL) /* Left NULL? */
- q = r;
- else if (r != NULL) { /* Right link is NULL? */
- if (r->llink == NULL) { /* D2: Find successor */
- r->llink = q;
- q = r;
- } else { /* D3: Find NULL link */
- for (q = r->llink; q->llink != NULL; q = r->llink)
- r = q;
- r->llink = q->rlink;
- q->llink = (*rootp)->llink;
- q->rlink = (*rootp)->rlink;
- }
- }
- free(*rootp); /* D4: Free node */
- *rootp = q; /* link parent to new node */
- return p;
-}
diff --git a/libc/bionic/tdestroy.c b/libc/bionic/tdestroy.c
index 70b71f4..decde4d 100644
--- a/libc/bionic/tdestroy.c
+++ b/libc/bionic/tdestroy.c
@@ -1,5 +1,5 @@
/*
- * Copyright 2012, The Android Open Source Project
+ * Copyright (C) 2012 The Android Open Source Project
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
@@ -18,16 +18,19 @@
#include <search.h>
#include <stdlib.h>
-/* destroy a tree and free all allocated resources */
-void
-tdestroy(void *root, void (*destroy_func)(void *))
-{
- node_t *root_node = (node_t *) root;
- if (root_node == NULL) return;
- if (root_node->llink)
- tdestroy(root_node->llink, destroy_func);
- if (root_node->rlink)
- tdestroy(root_node->rlink, destroy_func);
- (*destroy_func)(root_node->key);
- free(root);
+// Destroy a tree and free all allocated resources.
+// This is a GNU extension, not available from NetBSD.
+void tdestroy(void* root, void (*destroy_func)(void*)) {
+ node_t* root_node = (node_t*) root;
+ if (root_node == NULL) {
+ return;
+ }
+ if (root_node->llink) {
+ tdestroy(root_node->llink, destroy_func);
+ }
+ if (root_node->rlink) {
+ tdestroy(root_node->rlink, destroy_func);
+ }
+ (*destroy_func)(root_node->key);
+ free(root);
}
diff --git a/libc/bionic/tfind.c b/libc/bionic/tfind.c
deleted file mode 100644
index 7e2bb0c..0000000
--- a/libc/bionic/tfind.c
+++ /dev/null
@@ -1,48 +0,0 @@
-/* $NetBSD: tfind.c,v 1.2 1999/09/16 11:45:37 lukem Exp $ */
-
-/*
- * Tree search generalized from Knuth (6.2.2) Algorithm T just like
- * the AT&T man page says.
- *
- * The node_t structure is for internal use only, lint doesn't grok it.
- *
- * Written by reading the System V Interface Definition, not the code.
- *
- * Totally public domain.
- */
-
-#include <sys/cdefs.h>
-#if 0
-#if defined(LIBC_SCCS) && !defined(lint)
-__RCSID("$NetBSD: tfind.c,v 1.2 1999/09/16 11:45:37 lukem Exp $");
-#endif /* LIBC_SCCS and not lint */
-#endif
-__FBSDID("$FreeBSD: release/9.0.0/lib/libc/stdlib/tfind.c 108694 2003-01-05 02:43:18Z tjr $");
-
-#define _SEARCH_PRIVATE
-#include <stdlib.h>
-#include <search.h>
-
-/* find a node, or return 0 */
-void *
-tfind(vkey, vrootp, compar)
- const void *vkey; /* key to be found */
- void * const *vrootp; /* address of the tree root */
- int (*compar)(const void *, const void *);
-{
- node_t **rootp = (node_t **)vrootp;
-
- if (rootp == NULL)
- return NULL;
-
- while (*rootp != NULL) { /* T1: */
- int r;
-
- if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */
- return *rootp; /* key found */
- rootp = (r < 0) ?
- &(*rootp)->llink : /* T3: follow left branch */
- &(*rootp)->rlink; /* T4: follow right branch */
- }
- return NULL;
-}
diff --git a/libc/bionic/tsearch.c b/libc/bionic/tsearch.c
deleted file mode 100644
index 4270e6b..0000000
--- a/libc/bionic/tsearch.c
+++ /dev/null
@@ -1,58 +0,0 @@
-/* $NetBSD: tsearch.c,v 1.3 1999/09/16 11:45:37 lukem Exp $ */
-
-/*
- * Tree search generalized from Knuth (6.2.2) Algorithm T just like
- * the AT&T man page says.
- *
- * The node_t structure is for internal use only, lint doesn't grok it.
- *
- * Written by reading the System V Interface Definition, not the code.
- *
- * Totally public domain.
- */
-
-#include <sys/cdefs.h>
-#if 0
-#if defined(LIBC_SCCS) && !defined(lint)
-__RCSID("$NetBSD: tsearch.c,v 1.3 1999/09/16 11:45:37 lukem Exp $");
-#endif /* LIBC_SCCS and not lint */
-#endif
-__FBSDID("$FreeBSD: release/9.0.0/lib/libc/stdlib/tsearch.c 108694 2003-01-05 02:43:18Z tjr $");
-
-#define _SEARCH_PRIVATE
-#include <search.h>
-#include <stdlib.h>
-
-/* find or insert datum into search tree */
-void *
-tsearch(vkey, vrootp, compar)
- const void *vkey; /* key to be located */
- void **vrootp; /* address of tree root */
- int (*compar)(const void *, const void *);
-{
- node_t *q;
- node_t **rootp = (node_t **)vrootp;
-
- if (rootp == NULL)
- return NULL;
-
- while (*rootp != NULL) { /* Knuth's T1: */
- int r;
-
- if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */
- return *rootp; /* we found it! */
-
- rootp = (r < 0) ?
- &(*rootp)->llink : /* T3: follow left branch */
- &(*rootp)->rlink; /* T4: follow right branch */
- }
-
- q = malloc(sizeof(node_t)); /* T5: key not found */
- if (q != 0) { /* make new node */
- *rootp = q; /* link new node to old */
- /* LINTED const castaway ok */
- q->key = (void *)vkey; /* initialize new node */
- q->llink = q->rlink = NULL;
- }
- return q;
-}