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.

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)