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;