New additions/bug fixes required/found when porting perf.
New functions:
tfind
tsearch
tdelete
twalk
tdestroy (GNU extension)
Bug fix: the current implementation for realpath would crash
if the second argument (resolved_path) is NULL.
New headers:
ar.h
search.h
Change-Id: Ib6c1e42fc186a6d597a6e5a9692b16acaa155804
diff --git a/libc/bionic/realpath.c b/libc/bionic/realpath.c
index 4cb847b..b909831 100644
--- a/libc/bionic/realpath.c
+++ b/libc/bionic/realpath.c
@@ -1,4 +1,3 @@
-/* $OpenBSD: realpath.c,v 1.13 2005/08/08 08:05:37 espie Exp $ */
/*
* Copyright (c) 2003 Constantin S. Svintsoff <kostik@iclub.nsu.ru>
*
@@ -27,6 +26,12 @@
* SUCH DAMAGE.
*/
+#if defined(LIBC_SCCS) && !defined(lint)
+static char sccsid[] = "@(#)realpath.c 8.1 (Berkeley) 2/16/94";
+#endif /* LIBC_SCCS and not lint */
+#include <sys/cdefs.h>
+__FBSDID("$FreeBSD: release/9.0.0/lib/libc/stdlib/realpath.c 217144 2011-01-08 11:04:30Z kib $");
+
#include <sys/param.h>
#include <sys/stat.h>
@@ -36,23 +41,36 @@
#include <unistd.h>
/*
- * char *realpath(const char *path, char resolved[PATH_MAX]);
- *
* Find the real name of path, by removing all ".", ".." and symlink
* components. Returns (resolved) on success, or (NULL) on failure,
* in which case the path which caused trouble is left in (resolved).
*/
char *
-realpath(const char *path, char resolved[PATH_MAX])
+realpath(const char * __restrict path, char * __restrict resolved)
{
struct stat sb;
char *p, *q, *s;
size_t left_len, resolved_len;
unsigned symlinks;
- int serrno, slen;
+ int m, serrno, slen;
char left[PATH_MAX], next_token[PATH_MAX], symlink[PATH_MAX];
+ if (path == NULL) {
+ errno = EINVAL;
+ return (NULL);
+ }
+ if (path[0] == '\0') {
+ errno = ENOENT;
+ return (NULL);
+ }
serrno = errno;
+ if (resolved == NULL) {
+ resolved = malloc(PATH_MAX);
+ if (resolved == NULL)
+ return (NULL);
+ m = 1;
+ } else
+ m = 0;
symlinks = 0;
if (path[0] == '/') {
resolved[0] = '/';
@@ -63,13 +81,20 @@
left_len = strlcpy(left, path + 1, sizeof(left));
} else {
if (getcwd(resolved, PATH_MAX) == NULL) {
- strlcpy(resolved, ".", PATH_MAX);
+ if (m)
+ free(resolved);
+ else {
+ resolved[0] = '.';
+ resolved[1] = '\0';
+ }
return (NULL);
}
resolved_len = strlen(resolved);
left_len = strlcpy(left, path, sizeof(left));
}
if (left_len >= sizeof(left) || resolved_len >= PATH_MAX) {
+ if (m)
+ free(resolved);
errno = ENAMETOOLONG;
return (NULL);
}
@@ -85,6 +110,8 @@
p = strchr(left, '/');
s = p ? p : left + left_len;
if (s - left >= sizeof(next_token)) {
+ if (m)
+ free(resolved);
errno = ENAMETOOLONG;
return (NULL);
}
@@ -95,6 +122,8 @@
memmove(left, s + 1, left_len + 1);
if (resolved[resolved_len - 1] != '/') {
if (resolved_len + 1 >= PATH_MAX) {
+ if (m)
+ free(resolved);
errno = ENAMETOOLONG;
return (NULL);
}
@@ -126,6 +155,8 @@
*/
resolved_len = strlcat(resolved, next_token, PATH_MAX);
if (resolved_len >= PATH_MAX) {
+ if (m)
+ free(resolved);
errno = ENAMETOOLONG;
return (NULL);
}
@@ -134,16 +165,23 @@
errno = serrno;
return (resolved);
}
+ if (m)
+ free(resolved);
return (NULL);
}
if (S_ISLNK(sb.st_mode)) {
if (symlinks++ > MAXSYMLINKS) {
+ if (m)
+ free(resolved);
errno = ELOOP;
return (NULL);
}
slen = readlink(resolved, symlink, sizeof(symlink) - 1);
- if (slen < 0)
+ if (slen < 0) {
+ if (m)
+ free(resolved);
return (NULL);
+ }
symlink[slen] = '\0';
if (symlink[0] == '/') {
resolved[1] = 0;
@@ -164,6 +202,8 @@
if (p != NULL) {
if (symlink[slen - 1] != '/') {
if (slen + 1 >= sizeof(symlink)) {
+ if (m)
+ free(resolved);
errno = ENAMETOOLONG;
return (NULL);
}
@@ -172,6 +212,8 @@
}
left_len = strlcat(symlink, left, sizeof(left));
if (left_len >= sizeof(left)) {
+ if (m)
+ free(resolved);
errno = ENAMETOOLONG;
return (NULL);
}
diff --git a/libc/bionic/tdelete.c b/libc/bionic/tdelete.c
new file mode 100644
index 0000000..b64b47a
--- /dev/null
+++ b/libc/bionic/tdelete.c
@@ -0,0 +1,71 @@
+/* $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
new file mode 100644
index 0000000..70b71f4
--- /dev/null
+++ b/libc/bionic/tdestroy.c
@@ -0,0 +1,33 @@
+/*
+ * 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.
+ */
+
+#define _SEARCH_PRIVATE
+#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);
+}
diff --git a/libc/bionic/tfind.c b/libc/bionic/tfind.c
new file mode 100644
index 0000000..7e2bb0c
--- /dev/null
+++ b/libc/bionic/tfind.c
@@ -0,0 +1,48 @@
+/* $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
new file mode 100644
index 0000000..4270e6b
--- /dev/null
+++ b/libc/bionic/tsearch.c
@@ -0,0 +1,58 @@
+/* $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;
+}