Switch to upstream NetBSD tdelete/tfind/tsearch.
tdestroy is a GNU extension, so that stays.
Change-Id: Iedebaff25ea7e92b1ab1dd4440da12b67b99aa40
diff --git a/libc/Android.mk b/libc/Android.mk
index c20d29f..7b1aa99 100644
--- a/libc/Android.mk
+++ b/libc/Android.mk
@@ -293,12 +293,9 @@
bionic/sha1.c \
bionic/stubs.cpp \
bionic/system_properties.c \
- bionic/tdelete.c \
bionic/tdestroy.c \
bionic/time64.c \
- bionic/tfind.c \
bionic/thread_atexit.c \
- bionic/tsearch.c \
bionic/utime.c \
bionic/utmp.c \
netbsd/gethnamaddr.c \
@@ -338,6 +335,9 @@
libc_upstream_netbsd_src_files := \
upstream-netbsd/libc/gen/nice.c \
+ upstream-netbsd/libc/stdlib/tdelete.c \
+ upstream-netbsd/libc/stdlib/tfind.c \
+ upstream-netbsd/libc/stdlib/tsearch.c \
upstream-netbsd/libc/string/strxfrm.c \
# The following files are common, but must be compiled
diff --git a/libc/NOTICE b/libc/NOTICE
index d78b840..e22599c 100644
--- a/libc/NOTICE
+++ b/libc/NOTICE
@@ -483,8 +483,7 @@
-------------------------------------------------------------------
-Copyright (c) 1988, 1993
- The Regents of the University of California. All rights reserved.
+Copyright (c) 1997 Niklas Hallqvist. All rights reserved.
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions
@@ -494,21 +493,17 @@
2. Redistributions in binary form must reproduce the above copyright
notice, this list of conditions and the following disclaimer in the
documentation and/or other materials provided with the distribution.
-3. Neither the name of the University nor the names of its contributors
- may be used to endorse or promote products derived from this software
- without specific prior written permission.
-THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
-ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
-IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
-ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
-FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
-DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
-OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
-HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
-LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
-OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
-SUCH DAMAGE.
+THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-------------------------------------------------------------------
@@ -1850,19 +1845,40 @@
-------------------------------------------------------------------
-Copyright (C) 2012 The Android Open Source Project
+Copyright (c) 1991, 1993
+ The Regents of the University of California. All rights reserved.
+(c) UNIX System Laboratories, Inc.
+All or some portions of this file are derived from material licensed
+to the University of California by American Telephone and Telegraph
+Co. or Unix System Laboratories, Inc. and are reproduced herein with
+the permission of UNIX System Laboratories, Inc.
-Licensed 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
+This code is derived from software contributed to Berkeley by
+Hugh Smith at The University of Guelph.
- http://www.apache.org/licenses/LICENSE-2.0
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions
+are met:
+1. Redistributions of source code must retain the above copyright
+ notice, this list of conditions and the following disclaimer.
+2. Redistributions in binary form must reproduce the above copyright
+ notice, this list of conditions and the following disclaimer in the
+ documentation and/or other materials provided with the distribution.
+3. Neither the name of the University nor the names of its contributors
+ may be used to endorse or promote products derived from this software
+ without specific prior written permission.
-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.
+THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+SUCH DAMAGE.
-------------------------------------------------------------------
@@ -2953,40 +2969,19 @@
-------------------------------------------------------------------
-Copyright (c) 1991, 1993
- The Regents of the University of California. All rights reserved.
-(c) UNIX System Laboratories, Inc.
-All or some portions of this file are derived from material licensed
-to the University of California by American Telephone and Telegraph
-Co. or Unix System Laboratories, Inc. and are reproduced herein with
-the permission of UNIX System Laboratories, Inc.
+Copyright (C) 2012 The Android Open Source Project
-This code is derived from software contributed to Berkeley by
-Hugh Smith at The University of Guelph.
+Licensed 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
-Redistribution and use in source and binary forms, with or without
-modification, are permitted provided that the following conditions
-are met:
-1. Redistributions of source code must retain the above copyright
- notice, this list of conditions and the following disclaimer.
-2. Redistributions in binary form must reproduce the above copyright
- notice, this list of conditions and the following disclaimer in the
- documentation and/or other materials provided with the distribution.
-3. Neither the name of the University nor the names of its contributors
- may be used to endorse or promote products derived from this software
- without specific prior written permission.
+ http://www.apache.org/licenses/LICENSE-2.0
-THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
-ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
-IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
-ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
-FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
-DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
-OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
-HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
-LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
-OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
-SUCH DAMAGE.
+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.
-------------------------------------------------------------------
@@ -3487,7 +3482,8 @@
-------------------------------------------------------------------
-Copyright (c) 1997 Niklas Hallqvist. All rights reserved.
+Copyright (c) 1988, 1993
+ The Regents of the University of California. All rights reserved.
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions
@@ -3497,17 +3493,21 @@
2. Redistributions in binary form must reproduce the above copyright
notice, this list of conditions and the following disclaimer in the
documentation and/or other materials provided with the distribution.
+3. Neither the name of the University nor the names of its contributors
+ may be used to endorse or promote products derived from this software
+ without specific prior written permission.
-THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
-IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
-OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
-IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
-INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
-NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
-DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
-THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
-(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
-THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+SUCH DAMAGE.
-------------------------------------------------------------------
@@ -3559,22 +3559,6 @@
-------------------------------------------------------------------
-Copyright 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.
-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.
-
--------------------------------------------------------------------
-
Copyright (c) 1993
The Regents of the University of California. All rights reserved.
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/tdelete.c b/libc/upstream-netbsd/libc/stdlib/tdelete.c
similarity index 72%
rename from libc/bionic/tdelete.c
rename to libc/upstream-netbsd/libc/stdlib/tdelete.c
index b64b47a..84017dc 100644
--- a/libc/bionic/tdelete.c
+++ b/libc/upstream-netbsd/libc/stdlib/tdelete.c
@@ -1,4 +1,4 @@
-/* $NetBSD: tdelete.c,v 1.2 1999/09/16 11:45:37 lukem Exp $ */
+/* $NetBSD: tdelete.c,v 1.6 2012/06/25 22:32:45 abs Exp $ */
/*
* Tree search generalized from Knuth (6.2.2) Algorithm T just like
@@ -12,32 +12,27 @@
*/
#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 $");
+__RCSID("$NetBSD: tdelete.c,v 1.6 2012/06/25 22:32:45 abs 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 $");
+#include <assert.h>
#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
- */
+/* find a node with key "vkey" in tree "vrootp" */
void *
-tdelete(const void * __restrict vkey, void ** __restrict vrootp,
+tdelete(const void *vkey, void **vrootp,
int (*compar)(const void *, const void *))
{
node_t **rootp = (node_t **)vrootp;
node_t *p, *q, *r;
- int cmp;
+ int cmp;
+
+ _DIAGASSERT(vkey != NULL);
+ _DIAGASSERT(compar != NULL);
if (rootp == NULL || (p = *rootp) == NULL)
return NULL;
@@ -65,7 +60,8 @@
q->rlink = (*rootp)->rlink;
}
}
- free(*rootp); /* D4: Free node */
+ if (p != *rootp)
+ free(*rootp); /* D4: Free node */
*rootp = q; /* link parent to new node */
return p;
}
diff --git a/libc/bionic/tfind.c b/libc/upstream-netbsd/libc/stdlib/tfind.c
similarity index 62%
rename from libc/bionic/tfind.c
rename to libc/upstream-netbsd/libc/stdlib/tfind.c
index 7e2bb0c..fd3f362 100644
--- a/libc/bionic/tfind.c
+++ b/libc/upstream-netbsd/libc/stdlib/tfind.c
@@ -1,4 +1,4 @@
-/* $NetBSD: tfind.c,v 1.2 1999/09/16 11:45:37 lukem Exp $ */
+/* $NetBSD: tfind.c,v 1.7 2012/06/25 22:32:45 abs Exp $ */
/*
* Tree search generalized from Knuth (6.2.2) Algorithm T just like
@@ -12,25 +12,24 @@
*/
#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 $");
+__RCSID("$NetBSD: tfind.c,v 1.7 2012/06/25 22:32:45 abs 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 $");
+#include <assert.h>
#define _SEARCH_PRIVATE
#include <stdlib.h>
#include <search.h>
-/* find a node, or return 0 */
+/* find a node by key "vkey" in tree "vrootp", 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 *);
+tfind(const void *vkey, void * const *vrootp,
+ int (*compar)(const void *, const void *))
{
- node_t **rootp = (node_t **)vrootp;
+ node_t * const *rootp = (node_t * const*)vrootp;
+
+ _DIAGASSERT(vkey != NULL);
+ _DIAGASSERT(compar != NULL);
if (rootp == NULL)
return NULL;
diff --git a/libc/bionic/tsearch.c b/libc/upstream-netbsd/libc/stdlib/tsearch.c
similarity index 68%
rename from libc/bionic/tsearch.c
rename to libc/upstream-netbsd/libc/stdlib/tsearch.c
index 4270e6b..af2fe9c 100644
--- a/libc/bionic/tsearch.c
+++ b/libc/upstream-netbsd/libc/stdlib/tsearch.c
@@ -1,4 +1,4 @@
-/* $NetBSD: tsearch.c,v 1.3 1999/09/16 11:45:37 lukem Exp $ */
+/* $NetBSD: tsearch.c,v 1.7 2012/06/25 22:32:45 abs Exp $ */
/*
* Tree search generalized from Knuth (6.2.2) Algorithm T just like
@@ -12,27 +12,26 @@
*/
#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 $");
+__RCSID("$NetBSD: tsearch.c,v 1.7 2012/06/25 22:32:45 abs 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 $");
+#include <assert.h>
#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 *);
+tsearch(const void *vkey, void **vrootp,
+ int (*compar)(const void *, const void *))
{
node_t *q;
node_t **rootp = (node_t **)vrootp;
+ _DIAGASSERT(vkey != NULL);
+ _DIAGASSERT(compar != NULL);
+
if (rootp == NULL)
return NULL;
@@ -50,8 +49,7 @@
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->key = __UNCONST(vkey); /* initialize new node */
q->llink = q->rlink = NULL;
}
return q;