aboutsummaryrefslogtreecommitdiff
path: root/misc
diff options
context:
space:
mode:
authorRoland McGrath <roland@gnu.org>1996-06-07 04:36:10 +0000
committerRoland McGrath <roland@gnu.org>1996-06-07 04:36:10 +0000
commit1be6ec30336a318dd50f9d9a45c8066860ec07f2 (patch)
tree8399c167a53cfe3ab9cdf27018730dda3c6a4d1b /misc
parentc035afc9605510b5437515b71e0603c12463c2e9 (diff)
downloadglibc-1be6ec30336a318dd50f9d9a45c8066860ec07f2.zip
glibc-1be6ec30336a318dd50f9d9a45c8066860ec07f2.tar.gz
glibc-1be6ec30336a318dd50f9d9a45c8066860ec07f2.tar.bz2
Fri Jun 7 1996 05:29:32 Ulrich Drepper <drepper@cygnus.com>cvs/libc-960607
* misc/lsearch.c: New file. Implementation of lfind and lsearch functions. * misc/search.h: Add prototype for functions from tsearch family with __ prefix. Correct prototype for lsearch: BASE parameter must not be const. * misc/tsearch.c: prepend all global function names with __ and make normal names weak aliases. Fri Jun 7 00:15:24 1996 Roland McGrath <roland@delasyd.gnu.ai.mit.edu> * Make-dist (sysdep_dirs): Skip CVS dirs.
Diffstat (limited to 'misc')
-rw-r--r--misc/lsearch.c58
-rw-r--r--misc/search.h23
-rw-r--r--misc/tsearch.c22
3 files changed, 88 insertions, 15 deletions
diff --git a/misc/lsearch.c b/misc/lsearch.c
new file mode 100644
index 0000000..f062a68
--- /dev/null
+++ b/misc/lsearch.c
@@ -0,0 +1,58 @@
+/* Linear search functions.
+Copyright (C) 1996 Free Software Foundation, Inc.
+This file is part of the GNU C Library.
+Contributed by Ulrich Drepper <drepper@cygnus.com>, 1996.
+
+The GNU C Library is free software; you can redistribute it and/or
+modify it under the terms of the GNU Library General Public License as
+published by the Free Software Foundation; either version 2 of the
+License, or (at your option) any later version.
+
+The GNU C Library is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+Library General Public License for more details.
+
+You should have received a copy of the GNU Library General Public
+License along with the GNU C Library; see the file COPYING.LIB. If
+not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+Boston, MA 02111-1307, USA. */
+
+#include <search.h>
+#include <string.h>
+
+
+void *
+lsearch (const void *key, void *base, size_t *nmemb, size_t size,
+ __compar_fn_t compar)
+{
+ void *result;
+
+ /* Try to find it. */
+ result = lfind (key, base, nmemb, size, compar);
+ if (result == NULL)
+ {
+ /* Not available. Insert at the end. */
+ memcpy (base + (*nmemb) * size, key, size);
+ ++(*nmemb);
+ }
+
+ return result;
+}
+
+
+void *
+lfind (const void *key, const void *base, size_t *nmemb, size_t size,
+ __compar_fn_t compar)
+{
+ const void *result = base;
+ size_t cnt = 0;
+
+ while (cnt < *nmemb && (*compar) (key, result) != 0)
+ {
+ result += size;
+ ++cnt;
+ }
+
+ return cnt < *nmemb ? (void *) result : NULL;
+}
diff --git a/misc/search.h b/misc/search.h
index 31c4f03..5e237a2 100644
--- a/misc/search.h
+++ b/misc/search.h
@@ -1,5 +1,5 @@
/* search.h -- declarations for System V style searching functions.
-Copyright (C) 1995 Free Software Foundation, Inc.
+Copyright (C) 1995, 1996 Free Software Foundation, Inc.
This file is part of the GNU C Library.
The GNU C Library is free software; you can redistribute it and/or
@@ -106,12 +106,18 @@ VISIT;
extern void *tsearch __P ((__const void * __key, void **__rootp,
__compar_fn_t compar));
+extern void *__tsearch __P ((__const void * __key, void **__rootp,
+ __compar_fn_t compar));
extern void *tfind __P ((__const void * __key, __const void ** __rootp,
__compar_fn_t compar));
+extern void *__tfind __P ((__const void * __key, __const void ** __rootp,
+ __compar_fn_t compar));
extern void *tdelete __P ((__const void * __key, void ** __rootp,
__compar_fn_t compar));
+extern void *__tdelete __P ((__const void * __key, void ** __rootp,
+ __compar_fn_t compar));
#ifndef __ACTION_FN_T
#define __ACTION_FN_T
@@ -122,14 +128,19 @@ typedef void (*__action_fn_t) __P ((__const void *__nodep,
extern void twalk __P ((__const void * __root, __action_fn_t action));
+extern void __twalk __P ((__const void * __root, __action_fn_t action));
+
-extern void * lfind __P ((__const void * __key, __const void * __base,
- size_t * __nmemb, size_t __size,
+/* Perform linear search for KEY by comparing by COMPAR in an array
+ [BASE,BASE+NMEMB*SIZE). */
+extern void * lfind __P ((__const void *__key, __const void *__base,
+ size_t *__nmemb, size_t __size,
__compar_fn_t __compar));
-extern void * lsearch __P ((__const void * __key, __const void * __base,
- size_t * __nmemb, size_t __size,
- __compar_fn_t __compar));
+/* Perform linear search for KEY by comparing by COMPAR function in
+ array [BASE,BASE+NMEMB*SIZE) and insert entry if not found. */
+extern void * lsearch __P ((__const void *__key, void *__base, size_t *__nmemb,
+ size_t __size, __compar_fn_t __compar));
__END_DECLS
diff --git a/misc/tsearch.c b/misc/tsearch.c
index cb06b7d..deff96c 100644
--- a/misc/tsearch.c
+++ b/misc/tsearch.c
@@ -1,4 +1,4 @@
-/* Copyright (C) 1995 Free Software Foundation, Inc.
+/* Copyright (C) 1995, 1996 Free Software Foundation, Inc.
This file is part of the GNU C Library.
The GNU C Library is free software; you can redistribute it and/or
@@ -18,11 +18,11 @@ Boston, MA 02111-1307, USA. */
/* 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. */
/*LINTLIBRARY*/
@@ -52,7 +52,7 @@ node **rootp; address of tree root
int (*compar)(); ordering function
*/
void *
-tsearch (key, vrootp, compar)
+__tsearch (key, vrootp, compar)
const void *key;
void **vrootp;
__compar_fn_t compar;
@@ -85,10 +85,11 @@ tsearch (key, vrootp, compar)
return q;
}
+weak_alias (__tsearch, tsearch)
void *
-tfind (key, vrootp, compar)
+__tfind (key, vrootp, compar)
const void *key;
const void **vrootp;
__compar_fn_t compar;
@@ -112,6 +113,7 @@ tfind (key, vrootp, compar)
}
return NULL;
}
+weak_alias (__tfind, tfind)
/* delete node with given key
@@ -120,7 +122,7 @@ node **rootp; address of the root of tree
int (*compar)(); comparison function
*/
void *
-tdelete (key, vrootp, compar)
+__tdelete (key, vrootp, compar)
const void *key;
void **vrootp;
__compar_fn_t compar;
@@ -168,6 +170,7 @@ tdelete (key, vrootp, compar)
*rootp = q; /* link parent to new node */
return p;
}
+weak_alias (__tfind, tfind)
/* Walk the nodes of a tree
@@ -198,13 +201,13 @@ trecurse (vroot, action, level)
}
-/* void twalk(root, action) Walk the nodes of a tree
+/* void twalk(root, action) Walk the nodes of a tree
node *root; Root of the tree to be walked
void (*action)(); Function to be called at each node
PTR
*/
void
-twalk (vroot, action)
+__twalk (vroot, action)
const void *vroot;
__action_fn_t action;
{
@@ -213,3 +216,4 @@ twalk (vroot, action)
if (root != NULL && action != NULL)
trecurse (root, action, 0);
}
+weak_alias (__twalk, twalk)