From 1be6ec30336a318dd50f9d9a45c8066860ec07f2 Mon Sep 17 00:00:00 2001 From: Roland McGrath Date: Fri, 7 Jun 1996 04:36:10 +0000 Subject: Fri Jun 7 1996 05:29:32 Ulrich Drepper * 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 * Make-dist (sysdep_dirs): Skip CVS dirs. --- ChangeLog | 17 ++++++++++ Make-dist | 3 +- misc/lsearch.c | 58 +++++++++++++++++++++++++++++++++++ misc/search.h | 23 ++++++++++---- misc/tsearch.c | 22 +++++++------ sysdeps/unix/sysv/linux/i386/Makefile | 2 +- 6 files changed, 108 insertions(+), 17 deletions(-) create mode 100644 misc/lsearch.c diff --git a/ChangeLog b/ChangeLog index 062cc98792..48ff28c87b 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,20 @@ +Fri Jun 7 1996 05:29:32 Ulrich Drepper + + * 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 + + * Make-dist (sysdep_dirs): Skip CVS dirs. + Thu Jun 6 16:12:39 1996 Roland McGrath * malloc/Makefile (distribute): Change malloc/gmalloc-head.c to diff --git a/Make-dist b/Make-dist index bba703cb26..7aece5ee62 100644 --- a/Make-dist +++ b/Make-dist @@ -31,7 +31,8 @@ foo:=$(shell echo 'foobar=$(filter %.c %.S %.s %.h,$(distribute))'>&2) ifndef sysdep_dirs # Find all sysdep directories. -export sysdep_dirs := $(shell find $(..)sysdeps -type d ! -name RCS -print) +export sysdep_dirs := $(shell find $(..)sysdeps -type d \ + ! -name CVS ! -name RCS -print) else # Defined by the parent. sysdep_dirs := $(addprefix $(..),$(sysdep_dirs)) diff --git a/misc/lsearch.c b/misc/lsearch.c new file mode 100644 index 0000000000..f062a6882b --- /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 , 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 +#include + + +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 31c4f03a1f..5e237a2791 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 cb06b7d8c8..deff96c478 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) diff --git a/sysdeps/unix/sysv/linux/i386/Makefile b/sysdeps/unix/sysv/linux/i386/Makefile index bd345b6fc6..77c9ad3e85 100644 --- a/sysdeps/unix/sysv/linux/i386/Makefile +++ b/sysdeps/unix/sysv/linux/i386/Makefile @@ -1,4 +1,4 @@ ifeq ($(subdir), misc) sysdep_routines += ioperm iopl vm86 -headers += sys/perm.h sys/vm86.h +sysdep_headers += sys/perm.h sys/vm86.h endif -- cgit v1.2.3