diff options
| author | Thomas Fitzsimmons <fitzsim@redhat.com> | 2002-06-20 23:51:40 +0400 |
|---|---|---|
| committer | Thomas Fitzsimmons <fitzsim@redhat.com> | 2002-06-20 23:51:40 +0400 |
| commit | a7b23a8f11b2e1f2ef333d2ed95d1c972acad12f (patch) | |
| tree | 26eb76cc430a851b89de107870b4f6b177311072 | |
| parent | c25ebbaf55dbef934d85522616d898eef37438e4 (diff) | |
* Makefile.am (LIB_OBJECTLISTS): Add
libc/search/objectlist.awk.in.
* libc/Makefile.am (SUBDIRS): Add search.
(SUBLIBS): Add search/libsearch.la.
* libc/configure.in (AC_OUTPUT): Add search/Makefile.
* libc/search: New directory.
* libc/search/Makefile.am: New file.
* libc/search/extern.h: New file.
* libc/search/hash.c: New file.
* libc/search/hash.h: New file.
* libc/search/hash_bigkey.c: New file.
* libc/search/hash_buf.c: New file.
* libc/search/hash_func.c: New file.
* libc/search/hash_log2.c: New file.
* libc/search/hash_page.c: New file.
* libc/search/hcreate.3: New file.
* libc/search/hcreate.c: New file.
* libc/search/hcreate.c~: New file.
* libc/search/hcreate_r.c: New file.
* libc/search/ndbm.c: New file.
* libc/search/page.h: New file.
* libc/search/tdelete.c: New file.
* libc/search/tdestroy.c: New file.
* libc/search/tfind.c: New file.
* libc/search/tsearch.3: New file.
* libc/search/tsearch.c: New file.
* libc/search/twalk.c: New file.
* libc/include/db.h: New file.
* libc/include/ndbm.h: New file.
* libc/include/search.h: New file.
* libc/include/sys/queue.h: New file.
* libc/include/sys/cdefs.h: New file.
* libc/include/sys/param.h
[__IEEE_LITTLE_ENDIAN,__IEEE_BIG_ENDIAN]: Set BYTE_ORDER to
LITTLE_ENDIAN or BIG_ENDIAN.
* libc/include/sys/errno.h (EFTYPE): New macro.
* libc/search/bsearch.c: Move from libc/stdlib.
* libc/search/qsort.c: Likewise.
* libc/stdlib/Makefile.am (LIB_SOURCES): Remove bsearch.c and
qsort.c.
(CHEWOUT_FILES): Remove bsearch.def and qsort.def.
* libc/stdlib/stdlib.tex: Remove references to bsearch and qsort.
40 files changed, 6621 insertions, 55 deletions
diff --git a/newlib/ChangeLog b/newlib/ChangeLog index e6df2dc6c..b0b4c7c3e 100644 --- a/newlib/ChangeLog +++ b/newlib/ChangeLog @@ -1,3 +1,48 @@ +2002-06-20 Thomas Fitzsimmons <fitzsim@redhat.com> + + * Makefile.am (LIB_OBJECTLISTS): Add + libc/search/objectlist.awk.in. + * libc/Makefile.am (SUBDIRS): Add search. + (SUBLIBS): Add search/libsearch.la. + * libc/configure.in (AC_OUTPUT): Add search/Makefile. + * libc/search: New directory. + * libc/search/Makefile.am: New file. + * libc/search/extern.h: New file. + * libc/search/hash.c: New file. + * libc/search/hash.h: New file. + * libc/search/hash_bigkey.c: New file. + * libc/search/hash_buf.c: New file. + * libc/search/hash_func.c: New file. + * libc/search/hash_log2.c: New file. + * libc/search/hash_page.c: New file. + * libc/search/hcreate.3: New file. + * libc/search/hcreate.c: New file. + * libc/search/hcreate.c~: New file. + * libc/search/hcreate_r.c: New file. + * libc/search/ndbm.c: New file. + * libc/search/page.h: New file. + * libc/search/tdelete.c: New file. + * libc/search/tdestroy.c: New file. + * libc/search/tfind.c: New file. + * libc/search/tsearch.3: New file. + * libc/search/tsearch.c: New file. + * libc/search/twalk.c: New file. + * libc/include/db.h: New file. + * libc/include/ndbm.h: New file. + * libc/include/search.h: New file. + * libc/include/sys/queue.h: New file. + * libc/include/sys/cdefs.h: New file. + * libc/include/sys/param.h + [__IEEE_LITTLE_ENDIAN,__IEEE_BIG_ENDIAN]: Set BYTE_ORDER to + LITTLE_ENDIAN or BIG_ENDIAN. + * libc/include/sys/errno.h (EFTYPE): New macro. + * libc/search/bsearch.c: Move from libc/stdlib. + * libc/search/qsort.c: Likewise. + * libc/stdlib/Makefile.am (LIB_SOURCES): Remove bsearch.c and + qsort.c. + (CHEWOUT_FILES): Remove bsearch.def and qsort.def. + * libc/stdlib/stdlib.tex: Remove references to bsearch and qsort. + 2002-06-19 Jeff Johnston <jjohnstn@redhat.com> * libc/sys/linux/Makefile.am: Add support for message queue routines, diff --git a/newlib/Makefile.am b/newlib/Makefile.am index 8fa905fa5..6f3a217d1 100644 --- a/newlib/Makefile.am +++ b/newlib/Makefile.am @@ -107,6 +107,7 @@ LIBC_OBJECTLISTS = \ libc/stdlib/objectlist.awk.in \ libc/time/objectlist.awk.in \ libc/ctype/objectlist.awk.in \ + libc/search/objectlist.awk.in \ libc/string/objectlist.awk.in \ libc/locale/objectlist.awk.in \ libc/misc/objectlist.awk.in \ diff --git a/newlib/Makefile.in b/newlib/Makefile.in index eeac4f5cc..a8ad97bf8 100644 --- a/newlib/Makefile.in +++ b/newlib/Makefile.in @@ -205,6 +205,7 @@ LIBC_OBJECTLISTS = \ libc/stdlib/objectlist.awk.in \ libc/time/objectlist.awk.in \ libc/ctype/objectlist.awk.in \ + libc/search/objectlist.awk.in \ libc/string/objectlist.awk.in \ libc/locale/objectlist.awk.in \ libc/misc/objectlist.awk.in \ diff --git a/newlib/libc/Makefile.am b/newlib/libc/Makefile.am index 67d32fe5e..7a22c0269 100644 --- a/newlib/libc/Makefile.am +++ b/newlib/libc/Makefile.am @@ -20,7 +20,7 @@ endif # The order of SUBDIRS is important for the integrated documentation. # Do not change the order without considering the doc impact. -SUBDIRS = argz stdlib ctype stdio string $(SIGNAL_SUBDIR) time locale sys reent \ +SUBDIRS = argz stdlib ctype search stdio string $(SIGNAL_SUBDIR) time locale sys reent \ $(extra_dir) errno misc machine $(UNIX_SUBDIR) $(POSIX_SUBDIR) $(SYSCALLS_SUBDIR) . noinst_DATA = $(CRT0) @@ -31,6 +31,7 @@ SUBLIBS = \ argz/libargz.$(aext) \ stdlib/libstdlib.$(aext) \ ctype/libctype.$(aext) \ + search/libsearch.$(aext) \ stdio/libstdio.$(aext) \ string/libstring.$(aext) \ $(LIBC_SIGNAL_LIB) \ @@ -51,6 +52,7 @@ SUBLIBS = \ argz/lib.$(aext) \ stdlib/lib.$(aext) \ ctype/lib.$(aext) \ + search/lib.$(aext) \ stdio/lib.$(aext) \ string/lib.$(aext) \ $(LIBC_SIGNAL_LIB) \ diff --git a/newlib/libc/Makefile.in b/newlib/libc/Makefile.in index 9952b6a0e..83de2b4ba 100644 --- a/newlib/libc/Makefile.in +++ b/newlib/libc/Makefile.in @@ -115,7 +115,7 @@ AUTOMAKE_OPTIONS = cygnus # The order of SUBDIRS is important for the integrated documentation. # Do not change the order without considering the doc impact. -SUBDIRS = argz stdlib ctype stdio string $(SIGNAL_SUBDIR) time locale sys reent \ +SUBDIRS = argz stdlib ctype search stdio string $(SIGNAL_SUBDIR) time locale sys reent \ $(extra_dir) errno misc machine $(UNIX_SUBDIR) $(POSIX_SUBDIR) $(SYSCALLS_SUBDIR) . @@ -126,6 +126,7 @@ noinst_DATA = $(CRT0) @USE_LIBTOOL_TRUE@ argz/libargz.$(aext) \ @USE_LIBTOOL_TRUE@ stdlib/libstdlib.$(aext) \ @USE_LIBTOOL_TRUE@ ctype/libctype.$(aext) \ +@USE_LIBTOOL_TRUE@ search/libsearch.$(aext) \ @USE_LIBTOOL_TRUE@ stdio/libstdio.$(aext) \ @USE_LIBTOOL_TRUE@ string/libstring.$(aext) \ @USE_LIBTOOL_TRUE@ $(LIBC_SIGNAL_LIB) \ @@ -144,6 +145,7 @@ noinst_DATA = $(CRT0) @USE_LIBTOOL_FALSE@ argz/lib.$(aext) \ @USE_LIBTOOL_FALSE@ stdlib/lib.$(aext) \ @USE_LIBTOOL_FALSE@ ctype/lib.$(aext) \ +@USE_LIBTOOL_FALSE@ search/lib.$(aext) \ @USE_LIBTOOL_FALSE@ stdio/lib.$(aext) \ @USE_LIBTOOL_FALSE@ string/lib.$(aext) \ @USE_LIBTOOL_FALSE@ $(LIBC_SIGNAL_LIB) \ @@ -206,10 +208,10 @@ LTLIBRARIES = $(noinst_LTLIBRARIES) @USE_LIBTOOL_TRUE@libc_la_DEPENDENCIES = argz/libargz.$(aext) \ @USE_LIBTOOL_TRUE@stdlib/libstdlib.$(aext) ctype/libctype.$(aext) \ -@USE_LIBTOOL_TRUE@stdio/libstdio.$(aext) string/libstring.$(aext) \ -@USE_LIBTOOL_TRUE@time/libtime.$(aext) locale/liblocale.$(aext) \ -@USE_LIBTOOL_TRUE@reent/libreent.$(aext) errno/liberrno.$(aext) \ -@USE_LIBTOOL_TRUE@misc/libmisc.$(aext) +@USE_LIBTOOL_TRUE@search/libsearch.$(aext) stdio/libstdio.$(aext) \ +@USE_LIBTOOL_TRUE@string/libstring.$(aext) time/libtime.$(aext) \ +@USE_LIBTOOL_TRUE@locale/liblocale.$(aext) reent/libreent.$(aext) \ +@USE_LIBTOOL_TRUE@errno/liberrno.$(aext) misc/libmisc.$(aext) @USE_LIBTOOL_TRUE@libc_la_OBJECTS = CFLAGS = @CFLAGS@ COMPILE = $(CC) $(DEFS) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) @@ -230,8 +232,8 @@ DISTFILES = $(DIST_COMMON) $(SOURCES) $(HEADERS) $(TEXINFOS) $(EXTRA_DIST) TAR = gtar GZIP_ENV = --best -DIST_SUBDIRS = argz stdlib ctype stdio string signal time locale sys \ -reent @extra_dir@ errno misc machine unix posix syscalls . +DIST_SUBDIRS = argz stdlib ctype search stdio string signal time locale \ +sys reent @extra_dir@ errno misc machine unix posix syscalls . SOURCES = libc.a.c $(libc_la_SOURCES) OBJECTS = libc.a.$(OBJEXT) $(libc_la_OBJECTS) diff --git a/newlib/libc/configure b/newlib/libc/configure index b6ffacf39..b068fd2ea 100755 --- a/newlib/libc/configure +++ b/newlib/libc/configure @@ -3143,7 +3143,7 @@ done ac_given_srcdir=$srcdir ac_given_INSTALL="$INSTALL" -trap 'rm -fr `echo "Makefile argz/Makefile ctype/Makefile errno/Makefile locale/Makefile misc/Makefile reent/Makefile stdio/Makefile stdlib/Makefile string/Makefile time/Makefile posix/Makefile signal/Makefile syscalls/Makefile unix/Makefile" | sed "s/:[^ ]*//g"` conftest*; exit 1' 1 2 15 +trap 'rm -fr `echo "Makefile argz/Makefile ctype/Makefile errno/Makefile locale/Makefile misc/Makefile reent/Makefile search/Makefile stdio/Makefile stdlib/Makefile string/Makefile time/Makefile posix/Makefile signal/Makefile syscalls/Makefile unix/Makefile" | sed "s/:[^ ]*//g"` conftest*; exit 1' 1 2 15 EOF cat >> $CONFIG_STATUS <<EOF @@ -3285,7 +3285,7 @@ EOF cat >> $CONFIG_STATUS <<EOF -CONFIG_FILES=\${CONFIG_FILES-"Makefile argz/Makefile ctype/Makefile errno/Makefile locale/Makefile misc/Makefile reent/Makefile stdio/Makefile stdlib/Makefile string/Makefile time/Makefile posix/Makefile signal/Makefile syscalls/Makefile unix/Makefile"} +CONFIG_FILES=\${CONFIG_FILES-"Makefile argz/Makefile ctype/Makefile errno/Makefile locale/Makefile misc/Makefile reent/Makefile search/Makefile stdio/Makefile stdlib/Makefile string/Makefile time/Makefile posix/Makefile signal/Makefile syscalls/Makefile unix/Makefile"} EOF cat >> $CONFIG_STATUS <<\EOF for ac_file in .. $CONFIG_FILES; do if test "x$ac_file" != x..; then diff --git a/newlib/libc/configure.in b/newlib/libc/configure.in index d03681d27..0e61b0902 100644 --- a/newlib/libc/configure.in +++ b/newlib/libc/configure.in @@ -110,4 +110,4 @@ fi AC_SUBST(LIBC_MACHINE_LIB) AC_SUBST(machine_dir) -AC_OUTPUT(Makefile argz/Makefile ctype/Makefile errno/Makefile locale/Makefile misc/Makefile reent/Makefile stdio/Makefile stdlib/Makefile string/Makefile time/Makefile posix/Makefile signal/Makefile syscalls/Makefile unix/Makefile) +AC_OUTPUT(Makefile argz/Makefile ctype/Makefile errno/Makefile locale/Makefile misc/Makefile reent/Makefile search/Makefile stdio/Makefile stdlib/Makefile string/Makefile time/Makefile posix/Makefile signal/Makefile syscalls/Makefile unix/Makefile) diff --git a/newlib/libc/include/db.h b/newlib/libc/include/db.h new file mode 100644 index 000000000..53f9d17ff --- /dev/null +++ b/newlib/libc/include/db.h @@ -0,0 +1,218 @@ +/*- + * Copyright (c) 1990, 1993, 1994 + * 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 + * 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. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed by the University of + * California, Berkeley and its contributors. + * 4. 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. + * + * @(#)db.h 8.7 (Berkeley) 6/16/94 + * $FreeBSD: src/include/db.h,v 1.5 2002/03/26 01:35:05 bde Exp $ + */ + +#ifndef _DB_H_ +#define _DB_H_ + +#include <sys/types.h> +#include <sys/cdefs.h> +#include <sys/config.h> + +#include <limits.h> + +#define RET_ERROR -1 /* Return values. */ +#define RET_SUCCESS 0 +#define RET_SPECIAL 1 + +#define MAX_PAGE_NUMBER 0xffffffff /* >= # of pages in a file */ +typedef __uint32_t pgno_t; +#define MAX_PAGE_OFFSET 65535 /* >= # of bytes in a page */ +typedef __uint16_t indx_t; +#define MAX_REC_NUMBER 0xffffffff /* >= # of records in a tree */ +typedef __uint32_t recno_t; + +/* Key/data structure -- a Data-Base Thang. */ +typedef struct { + void *data; /* data */ + size_t size; /* data length */ +} DBT; + +/* Routine flags. */ +#define R_CURSOR 1 /* del, put, seq */ +#define __R_UNUSED 2 /* UNUSED */ +#define R_FIRST 3 /* seq */ +#define R_IAFTER 4 /* put (RECNO) */ +#define R_IBEFORE 5 /* put (RECNO) */ +#define R_LAST 6 /* seq (BTREE, RECNO) */ +#define R_NEXT 7 /* seq */ +#define R_NOOVERWRITE 8 /* put */ +#define R_PREV 9 /* seq (BTREE, RECNO) */ +#define R_SETCURSOR 10 /* put (RECNO) */ +#define R_RECNOSYNC 11 /* sync (RECNO) */ + +typedef enum { DB_BTREE, DB_HASH, DB_RECNO } DBTYPE; + +/* + * !!! + * The following flags are included in the dbopen(3) call as part of the + * open(2) flags. In order to avoid conflicts with the open flags, start + * at the top of the 16 or 32-bit number space and work our way down. If + * the open flags were significantly expanded in the future, it could be + * a problem. Wish I'd left another flags word in the dbopen call. + * + * !!! + * None of this stuff is implemented yet. The only reason that it's here + * is so that the access methods can skip copying the key/data pair when + * the DB_LOCK flag isn't set. + */ +#if UINT_MAX > 65535 +#define DB_LOCK 0x20000000 /* Do locking. */ +#define DB_SHMEM 0x40000000 /* Use shared memory. */ +#define DB_TXN 0x80000000 /* Do transactions. */ +#else +#define DB_LOCK 0x2000 /* Do locking. */ +#define DB_SHMEM 0x4000 /* Use shared memory. */ +#define DB_TXN 0x8000 /* Do transactions. */ +#endif + +/* Access method description structure. */ +typedef struct __db { + DBTYPE type; /* Underlying db type. */ + int (*close)(struct __db *); + int (*del)(const struct __db *, const DBT *, u_int); + int (*get)(const struct __db *, const DBT *, DBT *, u_int); + int (*put)(const struct __db *, DBT *, const DBT *, u_int); + int (*seq)(const struct __db *, DBT *, DBT *, u_int); + int (*sync)(const struct __db *, u_int); + void *internal; /* Access method private. */ + int (*fd)(const struct __db *); +} DB; + +#define BTREEMAGIC 0x053162 +#define BTREEVERSION 3 + +/* Structure used to pass parameters to the btree routines. */ +typedef struct { +#define R_DUP 0x01 /* duplicate keys */ + u_long flags; + u_int cachesize; /* bytes to cache */ + int maxkeypage; /* maximum keys per page */ + int minkeypage; /* minimum keys per page */ + u_int psize; /* page size */ + int (*compare) /* comparison function */ + (const DBT *, const DBT *); + size_t (*prefix) /* prefix function */ + (const DBT *, const DBT *); + int lorder; /* byte order */ +} BTREEINFO; + +#define HASHMAGIC 0x061561 +#define HASHVERSION 2 + +/* Structure used to pass parameters to the hashing routines. */ +typedef struct { + u_int bsize; /* bucket size */ + u_int ffactor; /* fill factor */ + u_int nelem; /* number of elements */ + u_int cachesize; /* bytes to cache */ + __uint32_t /* hash function */ + (*hash)(const void *, size_t); + int lorder; /* byte order */ +} HASHINFO; + +/* Structure used to pass parameters to the record routines. */ +typedef struct { +#define R_FIXEDLEN 0x01 /* fixed-length records */ +#define R_NOKEY 0x02 /* key not required */ +#define R_SNAPSHOT 0x04 /* snapshot the input */ + u_long flags; + u_int cachesize; /* bytes to cache */ + u_int psize; /* page size */ + int lorder; /* byte order */ + size_t reclen; /* record length (fixed-length records) */ + u_char bval; /* delimiting byte (variable-length records */ + char *bfname; /* btree file name */ +} RECNOINFO; + +/* + * Little endian <==> big endian 32-bit swap macros. + * M_32_SWAP swap a memory location + * P_32_SWAP swap a referenced memory location + * P_32_COPY swap from one location to another + */ +#define M_32_SWAP(a) { \ + __uint32_t _tmp = a; \ + ((char *)&a)[0] = ((char *)&_tmp)[3]; \ + ((char *)&a)[1] = ((char *)&_tmp)[2]; \ + ((char *)&a)[2] = ((char *)&_tmp)[1]; \ + ((char *)&a)[3] = ((char *)&_tmp)[0]; \ +} +#define P_32_SWAP(a) { \ + __uint32_t _tmp = *(__uint32_t *)a; \ + ((char *)a)[0] = ((char *)&_tmp)[3]; \ + ((char *)a)[1] = ((char *)&_tmp)[2]; \ + ((char *)a)[2] = ((char *)&_tmp)[1]; \ + ((char *)a)[3] = ((char *)&_tmp)[0]; \ +} +#define P_32_COPY(a, b) { \ + ((char *)&(b))[0] = ((char *)&(a))[3]; \ + ((char *)&(b))[1] = ((char *)&(a))[2]; \ + ((char *)&(b))[2] = ((char *)&(a))[1]; \ + ((char *)&(b))[3] = ((char *)&(a))[0]; \ +} + +/* + * Little endian <==> big endian 16-bit swap macros. + * M_16_SWAP swap a memory location + * P_16_SWAP swap a referenced memory location + * P_16_COPY swap from one location to another + */ +#define M_16_SWAP(a) { \ + __uint16_t _tmp = a; \ + ((char *)&a)[0] = ((char *)&_tmp)[1]; \ + ((char *)&a)[1] = ((char *)&_tmp)[0]; \ +} +#define P_16_SWAP(a) { \ + __uint16_t _tmp = *(__uint16_t *)a; \ + ((char *)a)[0] = ((char *)&_tmp)[1]; \ + ((char *)a)[1] = ((char *)&_tmp)[0]; \ +} +#define P_16_COPY(a, b) { \ + ((char *)&(b))[0] = ((char *)&(a))[1]; \ + ((char *)&(b))[1] = ((char *)&(a))[0]; \ +} + +__BEGIN_DECLS +DB *dbopen(const char *, int, int, DBTYPE, const void *); + +#ifdef __DBINTERFACE_PRIVATE +DB *__bt_open(const char *, int, int, const BTREEINFO *, int); +DB *__hash_open(const char *, int, int, const HASHINFO *, int); +DB *__rec_open(const char *, int, int, const RECNOINFO *, int); +void __dbpanic(DB *dbp); +#endif +__END_DECLS +#endif /* !_DB_H_ */ diff --git a/newlib/libc/include/ndbm.h b/newlib/libc/include/ndbm.h new file mode 100644 index 000000000..1637cd903 --- /dev/null +++ b/newlib/libc/include/ndbm.h @@ -0,0 +1,80 @@ +/*- + * Copyright (c) 1990, 1993 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Margo Seltzer. + * + * 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. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed by the University of + * California, Berkeley and its contributors. + * 4. 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. + * + * @(#)ndbm.h 8.1 (Berkeley) 6/2/93 + * $FreeBSD: src/include/ndbm.h,v 1.4 2002/03/23 17:24:53 imp Exp $ + */ + +#ifndef _NDBM_H_ +#define _NDBM_H_ + +#include <db.h> + +/* Map dbm interface onto db(3). */ +#define DBM_RDONLY O_RDONLY + +/* Flags to dbm_store(). */ +#define DBM_INSERT 0 +#define DBM_REPLACE 1 + +/* + * The db(3) support for ndbm always appends this suffix to the + * file name to avoid overwriting the user's original database. + */ +#define DBM_SUFFIX ".db" + +typedef struct { + char *dptr; + int dsize; +} datum; + +typedef DB DBM; +#define dbm_pagfno(a) DBM_PAGFNO_NOT_AVAILABLE + +__BEGIN_DECLS +int dbm_clearerr(DBM *); +void dbm_close(DBM *); +int dbm_delete(DBM *, datum); +int dbm_error(DBM *); +datum dbm_fetch(DBM *, datum); +datum dbm_firstkey(DBM *); +long dbm_forder(DBM *, datum); +datum dbm_nextkey(DBM *); +DBM *dbm_open(const char *, int, int); +int dbm_store(DBM *, datum, datum, int); +int dbm_dirfno(DBM *); +__END_DECLS + +#endif /* !_NDBM_H_ */ diff --git a/newlib/libc/include/search.h b/newlib/libc/include/search.h new file mode 100644 index 000000000..c78ce1841 --- /dev/null +++ b/newlib/libc/include/search.h @@ -0,0 +1,59 @@ +/* $NetBSD: search.h,v 1.12 1999/02/22 10:34:28 christos Exp $ */ +/* $FreeBSD: src/include/search.h,v 1.4 2002/03/23 17:24:53 imp Exp $ */ + +/* + * Written by J.T. Conklin <jtc@netbsd.org> + * Public domain. + */ + +#ifndef _SEARCH_H_ +#define _SEARCH_H_ + +#include <sys/cdefs.h> +#include <machine/ansi.h> +#include <sys/types.h> + +typedef struct entry { + char *key; + void *data; +} ENTRY; + +typedef enum { + FIND, ENTER +} ACTION; + +typedef enum { + preorder, + postorder, + endorder, + leaf +} VISIT; + +#ifdef _SEARCH_PRIVATE +typedef struct node { + char *key; + struct node *llink, *rlink; +} node_t; +#endif + +struct hsearch_data +{ + struct internal_head *htable; + size_t htablesize; +}; + +__BEGIN_DECLS +int hcreate(size_t); +void hdestroy(void); +ENTRY *hsearch(ENTRY, ACTION); +int hcreate_r(size_t, struct hsearch_data *); +void hdestroy_r(struct hsearch_data *); +int hsearch_r(ENTRY, ACTION, ENTRY **, struct hsearch_data *); +void *tdelete(const void *, void **, int (*)(const void *, const void *)); +void tdestroy (void *, void (*)(void *)); +void *tfind(const void *, void **, int (*)(const void *, const void *)); +void *tsearch(const void *, void **, int (*)(const void *, const void *)); +void twalk(const void *, void (*)(const void *, VISIT, int)); +__END_DECLS + +#endif /* !_SEARCH_H_ */ diff --git a/newlib/libc/include/sys/cdefs.h b/newlib/libc/include/sys/cdefs.h new file mode 100644 index 000000000..f0b6a27b4 --- /dev/null +++ b/newlib/libc/include/sys/cdefs.h @@ -0,0 +1,123 @@ +/* libc/sys/linux/sys/cdefs.h - Helper macros for K&R vs. ANSI C compat. */ + +/* Written 2000 by Werner Almesberger */ + +/* + * Copyright (c) 1991, 1993 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Berkeley Software Design, Inc. + * + * 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. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed by the University of + * California, Berkeley and its contributors. + * 4. 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. + * + * @(#)cdefs.h 8.8 (Berkeley) 1/9/95 + * $FreeBSD: src/sys/sys/cdefs.h,v 1.54 2002/05/11 03:58:24 alfred Exp $ + */ + +#ifndef _SYS_CDEFS_H +#define _SYS_CDEFS_H + +#define __FBSDID(x) /* nothing */ +/* + * Note: the goal here is not compatibility to K&R C. Since we know that we + * have GCC which understands ANSI C perfectly well, we make use of this. + */ + +#define __P(args) args +#define __PMT(args) args +#define __const const +#define __signed signed +#define __volatile volatile +#define __DOTS , ... +#define __THROW + +#define __ptr_t void * +#define __long_double_t long double + +#define __attribute_malloc__ +#define __attribute_pure__ +#define __attribute_format_strfmon__(a,b) +#define __flexarr [0] + +#ifdef __cplusplus +# define __BEGIN_DECLS extern "C" { +# define __END_DECLS } +#else +# define __BEGIN_DECLS +# define __END_DECLS +#endif + +#ifndef __BOUNDED_POINTERS__ +# define __bounded /* nothing */ +# define __unbounded /* nothing */ +# define __ptrvalue /* nothing */ +#endif + +#ifdef __GNUC__ +#define __strong_reference(sym,aliassym) \ + extern __typeof (sym) aliassym __attribute__ ((__alias__ (#sym))); +#ifdef __ELF__ +#ifdef __STDC__ +#define __weak_reference(sym,alias) \ + __asm__(".weak " #alias); \ + __asm__(".equ " #alias ", " #sym) +#define __warn_references(sym,msg) \ + __asm__(".section .gnu.warning." #sym); \ + __asm__(".asciz \"" msg "\""); \ + __asm__(".previous") +#else +#define __weak_reference(sym,alias) \ + __asm__(".weak alias"); \ + __asm__(".equ alias, sym") +#define __warn_references(sym,msg) \ + __asm__(".section .gnu.warning.sym"); \ + __asm__(".asciz \"msg\""); \ + __asm__(".previous") +#endif /* __STDC__ */ +#else /* !__ELF__ */ +#ifdef __STDC__ +#define __weak_reference(sym,alias) \ + __asm__(".stabs \"_" #alias "\",11,0,0,0"); \ + __asm__(".stabs \"_" #sym "\",1,0,0,0") +#define __warn_references(sym,msg) \ + __asm__(".stabs \"" msg "\",30,0,0,0"); \ + __asm__(".stabs \"_" #sym "\",1,0,0,0") +#else +#define __weak_reference(sym,alias) \ + __asm__(".stabs \"_/**/alias\",11,0,0,0"); \ + __asm__(".stabs \"_/**/sym\",1,0,0,0") +#define __warn_references(sym,msg) \ + __asm__(".stabs msg,30,0,0,0"); \ + __asm__(".stabs \"_/**/sym\",1,0,0,0") +#endif /* __STDC__ */ +#endif /* __ELF__ */ +#endif /* __GNUC__ */ + +#endif /* _SYS_CDEFS_H */ diff --git a/newlib/libc/include/sys/errno.h b/newlib/libc/include/sys/errno.h index 26b56925e..17a5611cb 100644 --- a/newlib/libc/include/sys/errno.h +++ b/newlib/libc/include/sys/errno.h @@ -96,6 +96,7 @@ extern __IMPORT int sys_nerr; #define ELBIN 75 /* Inode is remote (not really error) */ #define EDOTDOT 76 /* Cross mount point (not really error) */ #define EBADMSG 77 /* Trying to read unreadable message */ +#define EFTYPE 79 /* Inappropriate file type or format */ #define ENOTUNIQ 80 /* Given log. name not unique */ #define EBADFD 81 /* f.d. invalid for this operation */ #define EREMCHG 82 /* Remote address changed */ diff --git a/newlib/libc/include/sys/param.h b/newlib/libc/include/sys/param.h index 3470ef5d0..edb9639cd 100644 --- a/newlib/libc/include/sys/param.h +++ b/newlib/libc/include/sys/param.h @@ -5,14 +5,27 @@ #ifndef _SYS_PARAM_H # define _SYS_PARAM_H +#include <sys/config.h> + # define HZ (60) # define NOFILE (60) # define PATHSIZE (1024) -#ifdef __i386__ #define BIG_ENDIAN 4321 #define LITTLE_ENDIAN 1234 + +#ifdef __IEEE_LITTLE_ENDIAN +#define BYTE_ORDER LITTLE_ENDIAN +#endif + +#ifdef __IEEE_BIG_ENDIAN +#define BYTE_ORDER BIG_ENDIAN +#endif + +#ifdef __i386__ +#ifndef BYTE_ORDER #define BYTE_ORDER LITTLE_ENDIAN #endif +#endif #endif diff --git a/newlib/libc/include/sys/queue.h b/newlib/libc/include/sys/queue.h new file mode 100644 index 000000000..af637ca03 --- /dev/null +++ b/newlib/libc/include/sys/queue.h @@ -0,0 +1,471 @@ +/* + * Copyright (c) 1991, 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 + * 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. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed by the University of + * California, Berkeley and its contributors. + * 4. 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. + * + * @(#)queue.h 8.5 (Berkeley) 8/20/94 + * $FreeBSD: src/sys/sys/queue.h,v 1.48 2002/04/17 14:00:37 tmm Exp $ + */ + +#ifndef _SYS_QUEUE_H_ +#define _SYS_QUEUE_H_ + +#include <machine/ansi.h> /* for __offsetof */ + +/* + * This file defines four types of data structures: singly-linked lists, + * singly-linked tail queues, lists and tail queues. + * + * A singly-linked list is headed by a single forward pointer. The elements + * are singly linked for minimum space and pointer manipulation overhead at + * the expense of O(n) removal for arbitrary elements. New elements can be + * added to the list after an existing element or at the head of the list. + * Elements being removed from the head of the list should use the explicit + * macro for this purpose for optimum efficiency. A singly-linked list may + * only be traversed in the forward direction. Singly-linked lists are ideal + * for applications with large datasets and few or no removals or for + * implementing a LIFO queue. + * + * A singly-linked tail queue is headed by a pair of pointers, one to the + * head of the list and the other to the tail of the list. The elements are + * singly linked for minimum space and pointer manipulation overhead at the + * expense of O(n) removal for arbitrary elements. New elements can be added + * to the list after an existing element, at the head of the list, or at the + * end of the list. Elements being removed from the head of the tail queue + * should use the explicit macro for this purpose for optimum efficiency. + * A singly-linked tail queue may only be traversed in the forward direction. + * Singly-linked tail queues are ideal for applications with large datasets + * and few or no removals or for implementing a FIFO queue. + * + * A list is headed by a single forward pointer (or an array of forward + * pointers for a hash table header). The elements are doubly linked + * so that an arbitrary element can be removed without a need to + * traverse the list. New elements can be added to the list before + * or after an existing element or at the head of the list. A list + * may only be traversed in the forward direction. + * + * A tail queue is headed by a pair of pointers, one to the head of the + * list and the other to the tail of the list. The elements are doubly + * linked so that an arbitrary element can be removed without a need to + * traverse the list. New elements can be added to the list before or + * after an existing element, at the head of the list, or at the end of + * the list. A tail queue may be traversed in either direction. + * + * For details on the use of these macros, see the queue(3) manual page. + * + * + * SLIST LIST STAILQ TAILQ + * _HEAD + + + + + * _HEAD_INITIALIZER + + + + + * _ENTRY + + + + + * _INIT + + + + + * _EMPTY + + + + + * _FIRST + + + + + * _NEXT + + + + + * _PREV - - - + + * _LAST - - + + + * _FOREACH + + + + + * _FOREACH_REVERSE - - - + + * _INSERT_HEAD + + + + + * _INSERT_BEFORE - + - + + * _INSERT_AFTER + + + + + * _INSERT_TAIL - - + + + * _CONCAT - - + + + * _REMOVE_HEAD + - + - + * _REMOVE + + + + + * + */ + +/* + * Singly-linked List declarations. + */ +#define SLIST_HEAD(name, type) \ +struct name { \ + struct type *slh_first; /* first element */ \ +} + +#define SLIST_HEAD_INITIALIZER(head) \ + { NULL } + +#define SLIST_ENTRY(type) \ +struct { \ + struct type *sle_next; /* next element */ \ +} + +/* + * Singly-linked List functions. + */ +#define SLIST_EMPTY(head) ((head)->slh_first == NULL) + +#define SLIST_FIRST(head) ((head)->slh_first) + +#define SLIST_FOREACH(var, head, field) \ + for ((var) = SLIST_FIRST((head)); \ + (var); \ + (var) = SLIST_NEXT((var), field)) + +#define SLIST_INIT(head) do { \ + SLIST_FIRST((head)) = NULL; \ +} while (0) + +#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \ + SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \ + SLIST_NEXT((slistelm), field) = (elm); \ +} while (0) + +#define SLIST_INSERT_HEAD(head, elm, field) do { \ + SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \ + SLIST_FIRST((head)) = (elm); \ +} while (0) + +#define SLIST_NEXT(elm, field) ((elm)->field.sle_next) + +#define SLIST_REMOVE(head, elm, type, field) do { \ + if (SLIST_FIRST((head)) == (elm)) { \ + SLIST_REMOVE_HEAD((head), field); \ + } \ + else { \ + struct type *curelm = SLIST_FIRST((head)); \ + while (SLIST_NEXT(curelm, field) != (elm)) \ + curelm = SLIST_NEXT(curelm, field); \ + SLIST_NEXT(curelm, field) = \ + SLIST_NEXT(SLIST_NEXT(curelm, field), field); \ + } \ +} while (0) + +#define SLIST_REMOVE_HEAD(head, field) do { \ + SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \ +} while (0) + +/* + * Singly-linked Tail queue declarations. + */ +#define STAILQ_HEAD(name, type) \ +struct name { \ + struct type *stqh_first;/* first element */ \ + struct type **stqh_last;/* addr of last next element */ \ +} + +#define STAILQ_HEAD_INITIALIZER(head) \ + { NULL, &(head).stqh_first } + +#define STAILQ_ENTRY(type) \ +struct { \ + struct type *stqe_next; /* next element */ \ +} + +/* + * Singly-linked Tail queue functions. + */ +#define STAILQ_CONCAT(head1, head2) do { \ + if (!STAILQ_EMPTY((head2))) { \ + *(head1)->stqh_last = (head2)->stqh_first; \ + (head1)->stqh_last = (head2)->stqh_last; \ + STAILQ_INIT((head2)); \ + } \ +} while (0) + +#define STAILQ_EMPTY(head) ((head)->stqh_first == NULL) + +#define STAILQ_FIRST(head) ((head)->stqh_first) + +#define STAILQ_FOREACH(var, head, field) \ + for((var) = STAILQ_FIRST((head)); \ + (var); \ + (var) = STAILQ_NEXT((var), field)) + +#define STAILQ_INIT(head) do { \ + STAILQ_FIRST((head)) = NULL; \ + (head)->stqh_last = &STAILQ_FIRST((head)); \ +} while (0) + +#define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \ + if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\ + (head)->stqh_last = &STAILQ_NEXT((elm), field); \ + STAILQ_NEXT((tqelm), field) = (elm); \ +} while (0) + +#define STAILQ_INSERT_HEAD(head, elm, field) do { \ + if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \ + (head)->stqh_last = &STAILQ_NEXT((elm), field); \ + STAILQ_FIRST((head)) = (elm); \ +} while (0) + +#define STAILQ_INSERT_TAIL(head, elm, field) do { \ + STAILQ_NEXT((elm), field) = NULL; \ + *(head)->stqh_last = (elm); \ + (head)->stqh_last = &STAILQ_NEXT((elm), field); \ +} while (0) + +#define STAILQ_LAST(head, type, field) \ + (STAILQ_EMPTY((head)) ? \ + NULL : \ + ((struct type *) \ + ((char *)((head)->stqh_last) - __offsetof(struct type, field)))) + +#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) + +#define STAILQ_REMOVE(head, elm, type, field) do { \ + if (STAILQ_FIRST((head)) == (elm)) { \ + STAILQ_REMOVE_HEAD((head), field); \ + } \ + else { \ + struct type *curelm = STAILQ_FIRST((head)); \ + while (STAILQ_NEXT(curelm, field) != (elm)) \ + curelm = STAILQ_NEXT(curelm, field); \ + if ((STAILQ_NEXT(curelm, field) = \ + STAILQ_NEXT(STAILQ_NEXT(curelm, field), field)) == NULL)\ + (head)->stqh_last = &STAILQ_NEXT((curelm), field);\ + } \ +} while (0) + +#define STAILQ_REMOVE_HEAD(head, field) do { \ + if ((STAILQ_FIRST((head)) = \ + STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \ + (head)->stqh_last = &STAILQ_FIRST((head)); \ +} while (0) + +#define STAILQ_REMOVE_HEAD_UNTIL(head, elm, field) do { \ + if ((STAILQ_FIRST((head)) = STAILQ_NEXT((elm), field)) == NULL) \ + (head)->stqh_last = &STAILQ_FIRST((head)); \ +} while (0) + +/* + * List declarations. + */ +#define LIST_HEAD(name, type) \ +struct name { \ + struct type *lh_first; /* first element */ \ +} + +#define LIST_HEAD_INITIALIZER(head) \ + { NULL } + +#define LIST_ENTRY(type) \ +struct { \ + struct type *le_next; /* next element */ \ + struct type **le_prev; /* address of previous next element */ \ +} + +/* + * List functions. + */ + +#define LIST_EMPTY(head) ((head)->lh_first == NULL) + +#define LIST_FIRST(head) ((head)->lh_first) + +#define LIST_FOREACH(var, head, field) \ + for ((var) = LIST_FIRST((head)); \ + (var); \ + (var) = LIST_NEXT((var), field)) + +#define LIST_INIT(head) do { \ + LIST_FIRST((head)) = NULL; \ +} while (0) + +#define LIST_INSERT_AFTER(listelm, elm, field) do { \ + if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\ + LIST_NEXT((listelm), field)->field.le_prev = \ + &LIST_NEXT((elm), field); \ + LIST_NEXT((listelm), field) = (elm); \ + (elm)->field.le_prev = &LIST_NEXT((listelm), field); \ +} while (0) + +#define LIST_INSERT_BEFORE(listelm, elm, field) do { \ + (elm)->field.le_prev = (listelm)->field.le_prev; \ + LIST_NEXT((elm), field) = (listelm); \ + *(listelm)->field.le_prev = (elm); \ + (listelm)->field.le_prev = &LIST_NEXT((elm), field); \ +} while (0) + +#define LIST_INSERT_HEAD(head, elm, field) do { \ + if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \ + LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\ + LIST_FIRST((head)) = (elm); \ + (elm)->field.le_prev = &LIST_FIRST((head)); \ +} while (0) + +#define LIST_NEXT(elm, field) ((elm)->field.le_next) + +#define LIST_REMOVE(elm, field) do { \ + if (LIST_NEXT((elm), field) != NULL) \ + LIST_NEXT((elm), field)->field.le_prev = \ + (elm)->field.le_prev; \ + *(elm)->field.le_prev = LIST_NEXT((elm), field); \ +} while (0) + +/* + * Tail queue declarations. + */ +#define TAILQ_HEAD(name, type) \ +struct name { \ + struct type *tqh_first; /* first element */ \ + struct type **tqh_last; /* addr of last next element */ \ +} + +#define TAILQ_HEAD_INITIALIZER(head) \ + { NULL, &(head).tqh_first } + +#define TAILQ_ENTRY(type) \ +struct { \ + struct type *tqe_next; /* next element */ \ + struct type **tqe_prev; /* address of previous next element */ \ +} + +/* + * Tail queue functions. + */ +#define TAILQ_CONCAT(head1, head2, field) do { \ + if (!TAILQ_EMPTY(head2)) { \ + *(head1)->tqh_last = (head2)->tqh_first; \ + (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \ + (head1)->tqh_last = (head2)->tqh_last; \ + TAILQ_INIT((head2)); \ + } \ +} while (0) + +#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL) + +#define TAILQ_FIRST(head) ((head)->tqh_first) + +#define TAILQ_FOREACH(var, head, field) \ + for ((var) = TAILQ_FIRST((head)); \ + (var); \ + (var) = TAILQ_NEXT((var), field)) + +#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ + for ((var) = TAILQ_LAST((head), headname); \ + (var); \ + (var) = TAILQ_PREV((var), headname, field)) + +#define TAILQ_INIT(head) do { \ + TAILQ_FIRST((head)) = NULL; \ + (head)->tqh_last = &TAILQ_FIRST((head)); \ +} while (0) + +#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ + if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\ + TAILQ_NEXT((elm), field)->field.tqe_prev = \ + &TAILQ_NEXT((elm), field); \ + else \ + (head)->tqh_last = &TAILQ_NEXT((elm), field); \ + TAILQ_NEXT((listelm), field) = (elm); \ + (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \ +} while (0) + +#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ + (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ + TAILQ_NEXT((elm), field) = (listelm); \ + *(listelm)->field.tqe_prev = (elm); \ + (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \ +} while (0) + +#define TAILQ_INSERT_HEAD(head, elm, field) do { \ + if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \ + TAILQ_FIRST((head))->field.tqe_prev = \ + &TAILQ_NEXT((elm), field); \ + else \ + (head)->tqh_last = &TAILQ_NEXT((elm), field); \ + TAILQ_FIRST((head)) = (elm); \ + (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \ +} while (0) + +#define TAILQ_INSERT_TAIL(head, elm, field) do { \ + TAILQ_NEXT((elm), field) = NULL; \ + (elm)->field.tqe_prev = (head)->tqh_last; \ + *(head)->tqh_last = (elm); \ + (head)->tqh_last = &TAILQ_NEXT((elm), field); \ +} while (0) + +#define TAILQ_LAST(head, headname) \ + (*(((struct headname *)((head)->tqh_last))->tqh_last)) + +#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) + +#define TAILQ_PREV(elm, headname, field) \ + (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) + +#define TAILQ_REMOVE(head, elm, field) do { \ + if ((TAILQ_NEXT((elm), field)) != NULL) \ + TAILQ_NEXT((elm), field)->field.tqe_prev = \ + (elm)->field.tqe_prev; \ + else \ + (head)->tqh_last = (elm)->field.tqe_prev; \ + *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \ +} while (0) + + +#ifdef _KERNEL + +/* + * XXX insque() and remque() are an old way of handling certain queues. + * They bogusly assumes that all queue heads look alike. + */ + +struct quehead { + struct quehead *qh_link; + struct quehead *qh_rlink; +}; + +#ifdef __GNUC__ + +static __inline void +insque(void *a, void *b) +{ + struct quehead *element = (struct quehead *)a, + *head = (struct quehead *)b; + + element->qh_link = head->qh_link; + element->qh_rlink = head; + head->qh_link = element; + element->qh_link->qh_rlink = element; +} + +static __inline void +remque(void *a) +{ + struct quehead *element = (struct quehead *)a; + + element->qh_link->qh_rlink = element->qh_rlink; + element->qh_rlink->qh_link = element->qh_link; + element->qh_rlink = 0; +} + +#else /* !__GNUC__ */ + +void insque(void *a, void *b); +void remque(void *a); + +#endif /* __GNUC__ */ + +#endif /* _KERNEL */ + +#endif /* !_SYS_QUEUE_H_ */ diff --git a/newlib/libc/search/Makefile.am b/newlib/libc/search/Makefile.am new file mode 100644 index 000000000..cfa193ad4 --- /dev/null +++ b/newlib/libc/search/Makefile.am @@ -0,0 +1,40 @@ +## Process this file with automake to generate Makefile.in + +AUTOMAKE_OPTIONS = cygnus + +INCLUDES = $(NEWLIB_CFLAGS) $(CROSS_CFLAGS) $(TARGET_CFLAGS) + +LIB_SOURCES = \ + bsearch.c \ + extern.h \ + hash.c \ + hash.h \ + hash_bigkey.c \ + hash_buf.c \ + hash_func.c \ + hash_log2.c \ + hash_page.c \ + hcreate.c \ + hcreate_r.c \ + ndbm.c \ + page.h \ + qsort.c \ + tdelete.c \ + tdestroy.c \ + tfind.c \ + tsearch.c \ + twalk.c + +libsearch_la_LDFLAGS = -Xcompiler -nostdlib + +if USE_LIBTOOL +noinst_LTLIBRARIES = libsearch.la +libsearch_la_SOURCES = $(LIB_SOURCES) +noinst_DATA = objectlist.awk.in +else +noinst_LIBRARIES = lib.a +lib_a_SOURCES = $(LIB_SOURCES) +noinst_DATA = +endif # USE_LIBTOOL + +include $(srcdir)/../../Makefile.shared diff --git a/newlib/libc/search/Makefile.in b/newlib/libc/search/Makefile.in new file mode 100644 index 000000000..3c6b23876 --- /dev/null +++ b/newlib/libc/search/Makefile.in @@ -0,0 +1,396 @@ +# Makefile.in generated automatically by automake 1.4 from Makefile.am + +# Copyright (C) 1994, 1995-8, 1999 Free Software Foundation, Inc. +# This Makefile.in is free software; the Free Software Foundation +# gives unlimited permission to copy and/or distribute it, +# with or without modifications, as long as this notice is preserved. + +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY, to the extent permitted by law; without +# even the implied warranty of MERCHANTABILITY or FITNESS FOR A +# PARTICULAR PURPOSE. + + + +SHELL = @SHELL@ + +srcdir = @srcdir@ +top_srcdir = @top_srcdir@ +VPATH = @srcdir@ +prefix = @prefix@ +exec_prefix = @exec_prefix@ + +bindir = @bindir@ +sbindir = @sbindir@ +libexecdir = @libexecdir@ +datadir = @datadir@ +sysconfdir = @sysconfdir@ +sharedstatedir = @sharedstatedir@ +localstatedir = @localstatedir@ +libdir = @libdir@ +infodir = @infodir@ +mandir = @mandir@ +includedir = @includedir@ +oldincludedir = /usr/include + +DESTDIR = + +pkgdatadir = $(datadir)/@PACKAGE@ +pkglibdir = $(libdir)/@PACKAGE@ +pkgincludedir = $(includedir)/@PACKAGE@ + +top_builddir = .. + +ACLOCAL = @ACLOCAL@ +AUTOCONF = @AUTOCONF@ +AUTOMAKE = @AUTOMAKE@ +AUTOHEADER = @AUTOHEADER@ + +INSTALL = @INSTALL@ +INSTALL_PROGRAM = @INSTALL_PROGRAM@ $(AM_INSTALL_PROGRAM_FLAGS) +INSTALL_DATA = @INSTALL_DATA@ +INSTALL_SCRIPT = @INSTALL_SCRIPT@ +transform = @program_transform_name@ + +NORMAL_INSTALL = : +PRE_INSTALL = : +POST_INSTALL = : +NORMAL_UNINSTALL = : +PRE_UNINSTALL = : +POST_UNINSTALL = : +build_alias = @build_alias@ +build_triplet = @build@ +host_alias = @host_alias@ +host_triplet = @host@ +target_alias = @target_alias@ +target_triplet = @target@ +AR = @AR@ +AS = @AS@ +CC = @CC@ +CPP = @CPP@ +CRT0 = @CRT0@ +CXX = @CXX@ +CXXCPP = @CXXCPP@ +DLLTOOL = @DLLTOOL@ +EXEEXT = @EXEEXT@ +GCJ = @GCJ@ +GCJFLAGS = @GCJFLAGS@ +LDFLAGS = @LDFLAGS@ +LIBC_EXTRA_DEF = @LIBC_EXTRA_DEF@ +LIBC_EXTRA_LIB = @LIBC_EXTRA_LIB@ +LIBC_MACHINE_LIB = @LIBC_MACHINE_LIB@ +LIBC_POSIX_LIB = @LIBC_POSIX_LIB@ +LIBC_SIGNAL_DEF = @LIBC_SIGNAL_DEF@ +LIBC_SIGNAL_LIB = @LIBC_SIGNAL_LIB@ +LIBC_SYSCALL_LIB = @LIBC_SYSCALL_LIB@ +LIBC_SYS_LIB = @LIBC_SYS_LIB@ +LIBC_UNIX_LIB = @LIBC_UNIX_LIB@ +LIBTOOL = @LIBTOOL@ +LN_S = @LN_S@ +MAINT = @MAINT@ +MAKEINFO = @MAKEINFO@ +NEWLIB_CFLAGS = @NEWLIB_CFLAGS@ +OBJDUMP = @OBJDUMP@ +OBJEXT = @OBJEXT@ +PACKAGE = @PACKAGE@ +RANLIB = @RANLIB@ +STRIP = @STRIP@ +VERSION = @VERSION@ +aext = @aext@ +extra_dir = @extra_dir@ +libm_machine_dir = @libm_machine_dir@ +machine_dir = @machine_dir@ +newlib_basedir = @newlib_basedir@ +oext = @oext@ +sys_dir = @sys_dir@ + +AUTOMAKE_OPTIONS = cygnus + +INCLUDES = $(NEWLIB_CFLAGS) $(CROSS_CFLAGS) $(TARGET_CFLAGS) + +LIB_SOURCES = \ + bsearch.c \ + extern.h \ + hash.c \ + hash.h \ + hash_bigkey.c \ + hash_buf.c \ + hash_func.c \ + hash_log2.c \ + hash_page.c \ + hcreate.c \ + hcreate_r.c \ + ndbm.c \ + page.h \ + qsort.c \ + tdelete.c \ + tdestroy.c \ + tfind.c \ + tsearch.c \ + twalk.c + + +libsearch_la_LDFLAGS = -Xcompiler -nostdlib + +@USE_LIBTOOL_TRUE@noinst_LTLIBRARIES = @USE_LIBTOOL_TRUE@libsearch.la +@USE_LIBTOOL_TRUE@libsearch_la_SOURCES = @USE_LIBTOOL_TRUE@$(LIB_SOURCES) +@USE_LIBTOOL_TRUE@noinst_DATA = @USE_LIBTOOL_TRUE@objectlist.awk.in +@USE_LIBTOOL_FALSE@noinst_DATA = +@USE_LIBTOOL_FALSE@noinst_LIBRARIES = @USE_LIBTOOL_FALSE@lib.a +@USE_LIBTOOL_FALSE@lib_a_SOURCES = @USE_LIBTOOL_FALSE@$(LIB_SOURCES) +mkinstalldirs = $(SHELL) $(top_srcdir)/../../mkinstalldirs +CONFIG_CLEAN_FILES = +LIBRARIES = $(noinst_LIBRARIES) + + +DEFS = @DEFS@ -I. -I$(srcdir) +CPPFLAGS = @CPPFLAGS@ +LIBS = @LIBS@ +lib_a_LIBADD = +@USE_LIBTOOL_FALSE@lib_a_OBJECTS = bsearch.$(OBJEXT) hash.$(OBJEXT) \ +@USE_LIBTOOL_FALSE@hash_bigkey.$(OBJEXT) hash_buf.$(OBJEXT) \ +@USE_LIBTOOL_FALSE@hash_func.$(OBJEXT) hash_log2.$(OBJEXT) \ +@USE_LIBTOOL_FALSE@hash_page.$(OBJEXT) hcreate.$(OBJEXT) \ +@USE_LIBTOOL_FALSE@hcreate_r.$(OBJEXT) ndbm.$(OBJEXT) qsort.$(OBJEXT) \ +@USE_LIBTOOL_FALSE@tdelete.$(OBJEXT) tdestroy.$(OBJEXT) tfind.$(OBJEXT) \ +@USE_LIBTOOL_FALSE@tsearch.$(OBJEXT) twalk.$(OBJEXT) +LTLIBRARIES = $(noinst_LTLIBRARIES) + +libsearch_la_LIBADD = +@USE_LIBTOOL_TRUE@libsearch_la_OBJECTS = bsearch.lo hash.lo \ +@USE_LIBTOOL_TRUE@hash_bigkey.lo hash_buf.lo hash_func.lo hash_log2.lo \ +@USE_LIBTOOL_TRUE@hash_page.lo hcreate.lo hcreate_r.lo ndbm.lo qsort.lo \ +@USE_LIBTOOL_TRUE@tdelete.lo tdestroy.lo tfind.lo tsearch.lo twalk.lo +CFLAGS = @CFLAGS@ +COMPILE = $(CC) $(DEFS) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) +LTCOMPILE = $(LIBTOOL) --mode=compile $(CC) $(DEFS) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) +CCLD = $(CC) +LINK = $(LIBTOOL) --mode=link $(CCLD) $(AM_CFLAGS) $(CFLAGS) $(LDFLAGS) -o $@ +DATA = $(noinst_DATA) + +DIST_COMMON = Makefile.am Makefile.in + + +DISTFILES = $(DIST_COMMON) $(SOURCES) $(HEADERS) $(TEXINFOS) $(EXTRA_DIST) + +TAR = gtar +GZIP_ENV = --best +SOURCES = $(lib_a_SOURCES) $(libsearch_la_SOURCES) +OBJECTS = $(lib_a_OBJECTS) $(libsearch_la_OBJECTS) + +all: all-redirect +.SUFFIXES: +.SUFFIXES: .S .c .lo .o .obj .s +$(srcdir)/Makefile.in: @MAINTAINER_MODE_TRUE@ Makefile.am $(top_srcdir)/configure.in $(ACLOCAL_M4) $(srcdir)/../../Makefile.shared + cd $(top_srcdir) && $(AUTOMAKE) --cygnus search/Makefile + +Makefile: $(srcdir)/Makefile.in $(top_builddir)/config.status + cd $(top_builddir) \ + && CONFIG_FILES=$(subdir)/$@ CONFIG_HEADERS= $(SHELL) ./config.status + + +mostlyclean-noinstLIBRARIES: + +clean-noinstLIBRARIES: + -test -z "$(noinst_LIBRARIES)" || rm -f $(noinst_LIBRARIES) + +distclean-noinstLIBRARIES: + +maintainer-clean-noinstLIBRARIES: + +.c.o: + $(COMPILE) -c $< + +# FIXME: We should only use cygpath when building on Windows, +# and only if it is available. +.c.obj: + $(COMPILE) -c `cygpath -w $<` + +.s.o: + $(COMPILE) -c $< + +.S.o: + $(COMPILE) -c $< + +mostlyclean-compile: + -rm -f *.o core *.core + -rm -f *.$(OBJEXT) + +clean-compile: + +distclean-compile: + -rm -f *.tab.c + +maintainer-clean-compile: + +.c.lo: + $(LIBTOOL) --mode=compile $(COMPILE) -c $< + +.s.lo: + $(LIBTOOL) --mode=compile $(COMPILE) -c $< + +.S.lo: + $(LIBTOOL) --mode=compile $(COMPILE) -c $< + +mostlyclean-libtool: + -rm -f *.lo + +clean-libtool: + -rm -rf .libs _libs + +distclean-libtool: + +maintainer-clean-libtool: + +lib.a: $(lib_a_OBJECTS) $(lib_a_DEPENDENCIES) + -rm -f lib.a + $(AR) cru lib.a $(lib_a_OBJECTS) $(lib_a_LIBADD) + $(RANLIB) lib.a + +mostlyclean-noinstLTLIBRARIES: + +clean-noinstLTLIBRARIES: + -test -z "$(noinst_LTLIBRARIES)" || rm -f $(noinst_LTLIBRARIES) + +distclean-noinstLTLIBRARIES: + +maintainer-clean-noinstLTLIBRARIES: + +libsearch.la: $(libsearch_la_OBJECTS) $(libsearch_la_DEPENDENCIES) + $(LINK) $(libsearch_la_LDFLAGS) $(libsearch_la_OBJECTS) $(libsearch_la_LIBADD) $(LIBS) + +tags: TAGS + +ID: $(HEADERS) $(SOURCES) $(LISP) + list='$(SOURCES) $(HEADERS)'; \ + unique=`for i in $$list; do echo $$i; done | \ + awk ' { files[$$0] = 1; } \ + END { for (i in files) print i; }'`; \ + here=`pwd` && cd $(srcdir) \ + && mkid -f$$here/ID $$unique $(LISP) + +TAGS: $(HEADERS) $(SOURCES) $(TAGS_DEPENDENCIES) $(LISP) + tags=; \ + here=`pwd`; \ + list='$(SOURCES) $(HEADERS)'; \ + unique=`for i in $$list; do echo $$i; done | \ + awk ' { files[$$0] = 1; } \ + END { for (i in files) print i; }'`; \ + test -z "$(ETAGS_ARGS)$$unique$(LISP)$$tags" \ + || (cd $(srcdir) && etags $(ETAGS_ARGS) $$tags $$unique $(LISP) -o $$here/TAGS) + +mostlyclean-tags: + +clean-tags: + +distclean-tags: + -rm -f TAGS ID + +maintainer-clean-tags: + +distdir = $(top_builddir)/$(PACKAGE)-$(VERSION)/$(subdir) + +subdir = search + +distdir: $(DISTFILES) + @for file in $(DISTFILES); do \ + if test -f $$file; then d=.; else d=$(srcdir); fi; \ + if test -d $$d/$$file; then \ + cp -pr $$d/$$file $(distdir)/$$file; \ + else \ + test -f $(distdir)/$$file \ + || ln $$d/$$file $(distdir)/$$file 2> /dev/null \ + || cp -p $$d/$$file $(distdir)/$$file || :; \ + fi; \ + done +info-am: +info: info-am +dvi-am: +dvi: dvi-am +check-am: +check: check-am +installcheck-am: +installcheck: installcheck-am +install-info-am: +install-info: install-info-am +install-exec-am: +install-exec: install-exec-am + +install-data-am: +install-data: install-data-am + +install-am: all-am + @$(MAKE) $(AM_MAKEFLAGS) install-exec-am install-data-am +install: install-am +uninstall-am: +uninstall: uninstall-am +all-am: Makefile $(LIBRARIES) $(LTLIBRARIES) $(DATA) +all-redirect: all-am +install-strip: + $(MAKE) $(AM_MAKEFLAGS) AM_INSTALL_PROGRAM_FLAGS=-s install +installdirs: + + +mostlyclean-generic: + +clean-generic: + +distclean-generic: + -rm -f Makefile $(CONFIG_CLEAN_FILES) + -rm -f config.cache config.log stamp-h stamp-h[0-9]* + +maintainer-clean-generic: +mostlyclean-am: mostlyclean-noinstLIBRARIES mostlyclean-compile \ + mostlyclean-libtool mostlyclean-noinstLTLIBRARIES \ + mostlyclean-tags mostlyclean-generic + +mostlyclean: mostlyclean-am + +clean-am: clean-noinstLIBRARIES clean-compile clean-libtool \ + clean-noinstLTLIBRARIES clean-tags clean-generic \ + mostlyclean-am + +clean: clean-am + +distclean-am: distclean-noinstLIBRARIES distclean-compile \ + distclean-libtool distclean-noinstLTLIBRARIES \ + distclean-tags distclean-generic clean-am + -rm -f libtool + +distclean: distclean-am + +maintainer-clean-am: maintainer-clean-noinstLIBRARIES \ + maintainer-clean-compile maintainer-clean-libtool \ + maintainer-clean-noinstLTLIBRARIES \ + maintainer-clean-tags maintainer-clean-generic \ + distclean-am + @echo "This command is intended for maintainers to use;" + @echo "it deletes files that may require special tools to rebuild." + +maintainer-clean: maintainer-clean-am + +.PHONY: mostlyclean-noinstLIBRARIES distclean-noinstLIBRARIES \ +clean-noinstLIBRARIES maintainer-clean-noinstLIBRARIES \ +mostlyclean-compile distclean-compile clean-compile \ +maintainer-clean-compile mostlyclean-libtool distclean-libtool \ +clean-libtool maintainer-clean-libtool mostlyclean-noinstLTLIBRARIES \ +distclean-noinstLTLIBRARIES clean-noinstLTLIBRARIES \ +maintainer-clean-noinstLTLIBRARIES tags mostlyclean-tags distclean-tags \ +clean-tags maintainer-clean-tags distdir info-am info dvi-am dvi check \ +check-am installcheck-am installcheck install-info-am install-info \ +install-exec-am install-exec install-data-am install-data install-am \ +install uninstall-am uninstall all-redirect all-am all installdirs \ +mostlyclean-generic distclean-generic clean-generic \ +maintainer-clean-generic clean mostlyclean distclean maintainer-clean + + +objectlist.awk.in: $(noinst_LTLIBRARIES) + -rm -f objectlist.awk.in + for i in `ls *.lo` ; \ + do \ + echo $$i `pwd`/$$i >> objectlist.awk.in ; \ + done + +# Tell versions [3.59,3.63) of GNU make to not export all variables. +# Otherwise a system limit (for SysV at least) may be exceeded. +.NOEXPORT: diff --git a/newlib/libc/search/bsearch.c b/newlib/libc/search/bsearch.c new file mode 100644 index 000000000..b9539aa3b --- /dev/null +++ b/newlib/libc/search/bsearch.c @@ -0,0 +1,100 @@ +/* + * bsearch.c + * Original Author: G. Haley + * Rewritten by: G. Noer + * + * Searches an array of nmemb members, the initial member of which is pointed + * to by base, for a member that matches the object pointed to by key. The + * contents of the array shall be in ascending order according to a comparison + * function pointed to by compar. The function shall return an integer less + * than, equal to or greater than zero if the first argument is considered to be + * respectively less than, equal to or greater than the second. Returns a + * pointer to the matching member of the array, or a null pointer if no match + * is found. + */ + +/* +FUNCTION +<<bsearch>>---binary search + +INDEX + bsearch + +ANSI_SYNOPSIS + #include <stdlib.h> + void *bsearch(const void *<[key]>, const void *<[base]>, + size_t <[nmemb]>, size_t <[size]>, + int (*<[compar]>)(const void *, const void *)); + +TRAD_SYNOPSIS + #include <stdlib.h> + char *bsearch(<[key]>, <[base]>, <[nmemb]>, <[size]>, <[compar]>) + char *<[key]>; + char *<[base]>; + size_t <[nmemb]>, <[size]>; + int (*<[compar]>)(); + +DESCRIPTION +<<bsearch>> searches an array beginning at <[base]> for any element +that matches <[key]>, using binary search. <[nmemb]> is the element +count of the array; <[size]> is the size of each element. + +The array must be sorted in ascending order with respect to the +comparison function <[compar]> (which you supply as the last argument of +<<bsearch>>). + +You must define the comparison function <<(*<[compar]>)>> to have two +arguments; its result must be negative if the first argument is +less than the second, zero if the two arguments match, and +positive if the first argument is greater than the second (where +``less than'' and ``greater than'' refer to whatever arbitrary +ordering is appropriate). + +RETURNS +Returns a pointer to an element of <[array]> that matches <[key]>. If +more than one matching element is available, the result may point to +any of them. + +PORTABILITY +<<bsearch>> is ANSI. + +No supporting OS subroutines are required. +*/ + +#include <stdlib.h> + +_PTR +_DEFUN (bsearch, (key, base, nmemb, size, compar), + _CONST _PTR key _AND + _CONST _PTR base _AND + size_t nmemb _AND + size_t size _AND + int _EXFUN ((*compar), (const _PTR, const _PTR))) +{ + _PTR current; + size_t lower = 0; + size_t upper = nmemb; + size_t index; + int result; + + if (nmemb == 0 || size == 0) + return NULL; + + while (lower < upper) + { + index = (lower + upper) / 2; + current = (_PTR) (((char *) base) + (index * size)); + + result = compar (key, current); + + if (result < 0) + upper = index; + else if (result > 0) + lower = index + 1; + else + return current; + } + + return NULL; +} + diff --git a/newlib/libc/search/extern.h b/newlib/libc/search/extern.h new file mode 100644 index 000000000..666a6e5bf --- /dev/null +++ b/newlib/libc/search/extern.h @@ -0,0 +1,66 @@ +/*- + * Copyright (c) 1991, 1993, 1994 + * 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 + * 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. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed by the University of + * California, Berkeley and its contributors. + * 4. 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. + * + * @(#)extern.h 8.4 (Berkeley) 6/16/94 + * $FreeBSD: src/lib/libc/db/hash/extern.h,v 1.3 2002/03/22 09:18:22 obrien Exp $ + */ + +BUFHEAD *__add_ovflpage(HTAB *, BUFHEAD *); +int __addel(HTAB *, BUFHEAD *, const DBT *, const DBT *); +int __big_delete(HTAB *, BUFHEAD *); +int __big_insert(HTAB *, BUFHEAD *, const DBT *, const DBT *); +int __big_keydata(HTAB *, BUFHEAD *, DBT *, DBT *, int); +int __big_return(HTAB *, BUFHEAD *, int, DBT *, int); +int __big_split(HTAB *, BUFHEAD *, BUFHEAD *, BUFHEAD *, + int, __uint32_t, SPLIT_RETURN *); +int __buf_free(HTAB *, int, int); +void __buf_init(HTAB *, int); +__uint32_t __call_hash(HTAB *, char *, int); +int __delpair(HTAB *, BUFHEAD *, int); +int __expand_table(HTAB *); +int __find_bigpair(HTAB *, BUFHEAD *, int, char *, int); +__uint16_t __find_last_page(HTAB *, BUFHEAD **); +void __free_ovflpage(HTAB *, BUFHEAD *); +BUFHEAD *__get_buf(HTAB *, __uint32_t, BUFHEAD *, int); +int __get_page(HTAB *, char *, __uint32_t, int, int, int); +int __ibitmap(HTAB *, int, int, int); +__uint32_t __log2(__uint32_t); +int __put_page(HTAB *, char *, __uint32_t, int, int); +void __reclaim_buf(HTAB *, BUFHEAD *); +int __split_page(HTAB *, __uint32_t, __uint32_t); + +/* Default hash routine. */ +extern __uint32_t (*__default_hash)(const void *, size_t); + +#ifdef HASH_STATISTICS +extern int hash_accesses, hash_collisions, hash_expansions, hash_overflows; +#endif diff --git a/newlib/libc/search/hash.c b/newlib/libc/search/hash.c new file mode 100644 index 000000000..498ee3fcc --- /dev/null +++ b/newlib/libc/search/hash.c @@ -0,0 +1,1004 @@ +/*- + * Copyright (c) 1990, 1993, 1994 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Margo Seltzer. + * + * 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. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed by the University of + * California, Berkeley and its contributors. + * 4. 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. + */ + +#include <sys/param.h> +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)hash.c 8.9 (Berkeley) 6/16/94"; +#endif /* LIBC_SCCS and not lint */ +#include <sys/cdefs.h> +#include <sys/types.h> + +#include <sys/stat.h> + +#include <errno.h> +#include <fcntl.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <unistd.h> +#ifdef DEBUG +#include <assert.h> +#endif + +#include <db.h> +#include "hash.h" +#include "page.h" +#include "extern.h" + +static int alloc_segs(HTAB *, int); +static int flush_meta(HTAB *); +static int hash_access(HTAB *, ACTION, DBT *, DBT *); +static int hash_close(DB *); +static int hash_delete(const DB *, const DBT *, __uint32_t); +static int hash_fd(const DB *); +static int hash_get(const DB *, const DBT *, DBT *, __uint32_t); +static int hash_put(const DB *, DBT *, const DBT *, __uint32_t); +static void *hash_realloc(SEGMENT **, int, int); +static int hash_seq(const DB *, DBT *, DBT *, __uint32_t); +static int hash_sync(const DB *, __uint32_t); +static int hdestroy(HTAB *); +static HTAB *init_hash(HTAB *, const char *, HASHINFO *); +static int init_htab(HTAB *, int); +#ifdef _IEEE_LITTLE_ENDIAN +static void swap_header(HTAB *); +static void swap_header_copy(HASHHDR *, HASHHDR *); +#endif + +/* Fast arithmetic, relying on powers of 2, */ +#define MOD(x, y) ((x) & ((y) - 1)) + +#define RETURN_ERROR(ERR, LOC) { save_errno = ERR; goto LOC; } + +/* Return values */ +#define SUCCESS (0) +#define ERROR (-1) +#define ABNORMAL (1) + +#ifdef HASH_STATISTICS +int hash_accesses, hash_collisions, hash_expansions, hash_overflows; +#endif + +/************************** INTERFACE ROUTINES ***************************/ +/* OPEN/CLOSE */ + +extern DB * +__hash_open(file, flags, mode, info, dflags) + const char *file; + int flags, mode, dflags; + const HASHINFO *info; /* Special directives for create */ +{ + HTAB *hashp; + struct stat statbuf; + DB *dbp; + int bpages, hdrsize, new_table, nsegs, save_errno; + + if ((flags & O_ACCMODE) == O_WRONLY) { + errno = EINVAL; + return (NULL); + } + + if (!(hashp = (HTAB *)calloc(1, sizeof(HTAB)))) + return (NULL); + hashp->fp = -1; + + /* + * Even if user wants write only, we need to be able to read + * the actual file, so we need to open it read/write. But, the + * field in the hashp structure needs to be accurate so that + * we can check accesses. + */ + hashp->flags = flags; + + new_table = 0; + if (!file || (flags & O_TRUNC) || + (stat(file, &statbuf) && (errno == ENOENT))) { + if (errno == ENOENT) + errno = 0; /* Just in case someone looks at errno */ + new_table = 1; + } + if (file) { + if ((hashp->fp = open(file, flags, mode)) == -1) + RETURN_ERROR(errno, error0); + + /* if the .db file is empty, and we had permission to create + a new .db file, then reinitialize the database */ + if ((flags & O_CREAT) && + fstat(hashp->fp, &statbuf) == 0 && statbuf.st_size == 0) + new_table = 1; + + (void)fcntl(hashp->fp, F_SETFD, 1); + } + if (new_table) { + if (!(hashp = init_hash(hashp, file, (HASHINFO *)info))) + RETURN_ERROR(errno, error1); + } else { + /* Table already exists */ + if (info && info->hash) + hashp->hash = info->hash; + else + hashp->hash = __default_hash; + + hdrsize = read(hashp->fp, &hashp->hdr, sizeof(HASHHDR)); +#ifdef _IEEE_LITTLE_ENDIAN + swap_header(hashp); +#endif + if (hdrsize == -1) + RETURN_ERROR(errno, error1); + if (hdrsize != sizeof(HASHHDR)) + RETURN_ERROR(EFTYPE, error1); + /* Verify file type, versions and hash function */ + if (hashp->MAGIC != HASHMAGIC) + RETURN_ERROR(EFTYPE, error1); +#define OLDHASHVERSION 1 + if (hashp->HASH_VERSION != HASHVERSION && + hashp->HASH_VERSION != OLDHASHVERSION) + RETURN_ERROR(EFTYPE, error1); + if (hashp->hash(CHARKEY, sizeof(CHARKEY)) != hashp->H_CHARKEY) + RETURN_ERROR(EFTYPE, error1); + /* + * Figure out how many segments we need. Max_Bucket is the + * maximum bucket number, so the number of buckets is + * max_bucket + 1. + */ + nsegs = (hashp->MAX_BUCKET + 1 + hashp->SGSIZE - 1) / + hashp->SGSIZE; + hashp->nsegs = 0; + if (alloc_segs(hashp, nsegs)) + /* + * If alloc_segs fails, table will have been destroyed + * and errno will have been set. + */ + return (NULL); + /* Read in bitmaps */ + bpages = (hashp->SPARES[hashp->OVFL_POINT] + + (hashp->BSIZE << BYTE_SHIFT) - 1) >> + (hashp->BSHIFT + BYTE_SHIFT); + + hashp->nmaps = bpages; + (void)memset(&hashp->mapp[0], 0, bpages * sizeof(__uint32_t *)); + } + + /* Initialize Buffer Manager */ + if (info && info->cachesize) + __buf_init(hashp, info->cachesize); + else + __buf_init(hashp, DEF_BUFSIZE); + + hashp->new_file = new_table; + hashp->save_file = file && (hashp->flags & O_RDWR); + hashp->cbucket = -1; + if (!(dbp = (DB *)malloc(sizeof(DB)))) { + save_errno = errno; + hdestroy(hashp); + errno = save_errno; + return (NULL); + } + dbp->internal = hashp; + dbp->close = hash_close; + dbp->del = hash_delete; + dbp->fd = hash_fd; + dbp->get = hash_get; + dbp->put = hash_put; + dbp->seq = hash_seq; + dbp->sync = hash_sync; + dbp->type = DB_HASH; + +#ifdef DEBUG + (void)fprintf(stderr, +"%s\n%s%x\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%x\n%s%x\n%s%d\n%s%d\n", + "init_htab:", + "TABLE POINTER ", hashp, + "BUCKET SIZE ", hashp->BSIZE, + "BUCKET SHIFT ", hashp->BSHIFT, + "DIRECTORY SIZE ", hashp->DSIZE, + "SEGMENT SIZE ", hashp->SGSIZE, + "SEGMENT SHIFT ", hashp->SSHIFT, + "FILL FACTOR ", hashp->FFACTOR, + "MAX BUCKET ", hashp->MAX_BUCKET, + "OVFL POINT ", hashp->OVFL_POINT, + "LAST FREED ", hashp->LAST_FREED, + "HIGH MASK ", hashp->HIGH_MASK, + "LOW MASK ", hashp->LOW_MASK, + "NSEGS ", hashp->nsegs, + "NKEYS ", hashp->NKEYS); +#endif +#ifdef HASH_STATISTICS + hash_overflows = hash_accesses = hash_collisions = hash_expansions = 0; +#endif + return (dbp); + +error1: + if (hashp != NULL) + (void)close(hashp->fp); + +error0: + free(hashp); + errno = save_errno; + return (NULL); +} + +static int +hash_close(dbp) + DB *dbp; +{ + HTAB *hashp; + int retval; + + if (!dbp) + return (ERROR); + + hashp = (HTAB *)dbp->internal; + retval = hdestroy(hashp); + free(dbp); + return (retval); +} + +static int +hash_fd(dbp) + const DB *dbp; +{ + HTAB *hashp; + + if (!dbp) + return (ERROR); + + hashp = (HTAB *)dbp->internal; + if (hashp->fp == -1) { + errno = ENOENT; + return (-1); + } + return (hashp->fp); +} + +/************************** LOCAL CREATION ROUTINES **********************/ +static HTAB * +init_hash(hashp, file, info) + HTAB *hashp; + const char *file; + HASHINFO *info; +{ + struct stat statbuf; + int nelem; + + nelem = 1; + hashp->NKEYS = 0; + hashp->LORDER = BYTE_ORDER; + hashp->BSIZE = DEF_BUCKET_SIZE; + hashp->BSHIFT = DEF_BUCKET_SHIFT; + hashp->SGSIZE = DEF_SEGSIZE; + hashp->SSHIFT = DEF_SEGSIZE_SHIFT; + hashp->DSIZE = DEF_DIRSIZE; + hashp->FFACTOR = DEF_FFACTOR; + hashp->hash = __default_hash; + memset(hashp->SPARES, 0, sizeof(hashp->SPARES)); + memset(hashp->BITMAPS, 0, sizeof (hashp->BITMAPS)); + + /* Fix bucket size to be optimal for file system */ + if (file != NULL) { + if (stat(file, &statbuf)) + return (NULL); + hashp->BSIZE = statbuf.st_blksize; + hashp->BSHIFT = __log2(hashp->BSIZE); + } + + if (info) { + if (info->bsize) { + /* Round pagesize up to power of 2 */ + hashp->BSHIFT = __log2(info->bsize); + hashp->BSIZE = 1 << hashp->BSHIFT; + if (hashp->BSIZE > MAX_BSIZE) { + errno = EINVAL; + return (NULL); + } + } + if (info->ffactor) + hashp->FFACTOR = info->ffactor; + if (info->hash) + hashp->hash = info->hash; + if (info->nelem) + nelem = info->nelem; + if (info->lorder) { + if (info->lorder != BIG_ENDIAN && + info->lorder != LITTLE_ENDIAN) { + errno = EINVAL; + return (NULL); + } + hashp->LORDER = info->lorder; + } + } + /* init_htab should destroy the table and set errno if it fails */ + if (init_htab(hashp, nelem)) + return (NULL); + else + return (hashp); +} +/* + * This calls alloc_segs which may run out of memory. Alloc_segs will destroy + * the table and set errno, so we just pass the error information along. + * + * Returns 0 on No Error + */ +static int +init_htab(hashp, nelem) + HTAB *hashp; + int nelem; +{ + int nbuckets, nsegs; + int l2; + + /* + * Divide number of elements by the fill factor and determine a + * desired number of buckets. Allocate space for the next greater + * power of two number of buckets. + */ + nelem = (nelem - 1) / hashp->FFACTOR + 1; + + l2 = __log2(MAX(nelem, 2)); + nbuckets = 1 << l2; + + hashp->SPARES[l2] = l2 + 1; + hashp->SPARES[l2 + 1] = l2 + 1; + hashp->OVFL_POINT = l2; + hashp->LAST_FREED = 2; + + /* First bitmap page is at: splitpoint l2 page offset 1 */ + if (__ibitmap(hashp, OADDR_OF(l2, 1), l2 + 1, 0)) + return (-1); + + hashp->MAX_BUCKET = hashp->LOW_MASK = nbuckets - 1; + hashp->HIGH_MASK = (nbuckets << 1) - 1; + hashp->HDRPAGES = ((MAX(sizeof(HASHHDR), MINHDRSIZE) - 1) >> + hashp->BSHIFT) + 1; + + nsegs = (nbuckets - 1) / hashp->SGSIZE + 1; + nsegs = 1 << __log2(nsegs); + + if (nsegs > hashp->DSIZE) + hashp->DSIZE = nsegs; + return (alloc_segs(hashp, nsegs)); +} + +/********************** DESTROY/CLOSE ROUTINES ************************/ + +/* + * Flushes any changes to the file if necessary and destroys the hashp + * structure, freeing all allocated space. + */ +static int +hdestroy(hashp) + HTAB *hashp; +{ + int i, save_errno; + + save_errno = 0; + +#ifdef HASH_STATISTICS + (void)fprintf(stderr, "hdestroy: accesses %ld collisions %ld\n", + hash_accesses, hash_collisions); + (void)fprintf(stderr, "hdestroy: expansions %ld\n", + hash_expansions); + (void)fprintf(stderr, "hdestroy: overflows %ld\n", + hash_overflows); + (void)fprintf(stderr, "keys %ld maxp %d segmentcount %d\n", + hashp->NKEYS, hashp->MAX_BUCKET, hashp->nsegs); + + for (i = 0; i < NCACHED; i++) + (void)fprintf(stderr, + "spares[%d] = %d\n", i, hashp->SPARES[i]); +#endif + /* + * Call on buffer manager to free buffers, and if required, + * write them to disk. + */ + if (__buf_free(hashp, 1, hashp->save_file)) + save_errno = errno; + if (hashp->dir) { + free(*hashp->dir); /* Free initial segments */ + /* Free extra segments */ + while (hashp->exsegs--) + free(hashp->dir[--hashp->nsegs]); + free(hashp->dir); + } + if (flush_meta(hashp) && !save_errno) + save_errno = errno; + /* Free Bigmaps */ + for (i = 0; i < hashp->nmaps; i++) + if (hashp->mapp[i]) + free(hashp->mapp[i]); + + if (hashp->fp != -1) + (void)close(hashp->fp); + + free(hashp); + + if (save_errno) { + errno = save_errno; + return (ERROR); + } + return (SUCCESS); +} +/* + * Write modified pages to disk + * + * Returns: + * 0 == OK + * -1 ERROR + */ +static int +hash_sync(dbp, flags) + const DB *dbp; + __uint32_t flags; +{ + HTAB *hashp; + + if (flags != 0) { + errno = EINVAL; + return (ERROR); + } + + if (!dbp) + return (ERROR); + + hashp = (HTAB *)dbp->internal; + if (!hashp->save_file) + return (0); + if (__buf_free(hashp, 0, 1) || flush_meta(hashp)) + return (ERROR); + hashp->new_file = 0; + return (0); +} + +/* + * Returns: + * 0 == OK + * -1 indicates that errno should be set + */ +static int +flush_meta(hashp) + HTAB *hashp; +{ + HASHHDR *whdrp; +#ifdef _IEEE_LITTLE_ENDIAN + HASHHDR whdr; +#endif + int fp, i, wsize; + + if (!hashp->save_file) + return (0); + hashp->MAGIC = HASHMAGIC; + hashp->HASH_VERSION = HASHVERSION; + hashp->H_CHARKEY = hashp->hash(CHARKEY, sizeof(CHARKEY)); + + fp = hashp->fp; + whdrp = &hashp->hdr; +#ifdef _IEEE_LITTLE_ENDIAN + whdrp = &whdr; + swap_header_copy(&hashp->hdr, whdrp); +#endif + if ((lseek(fp, (off_t)0, SEEK_SET) == -1) || + ((wsize = write(fp, whdrp, sizeof(HASHHDR))) == -1)) + return (-1); + else + if (wsize != sizeof(HASHHDR)) { + errno = EFTYPE; + hashp->error = errno; + return (-1); + } + for (i = 0; i < NCACHED; i++) + if (hashp->mapp[i]) + if (__put_page(hashp, (char *)hashp->mapp[i], + hashp->BITMAPS[i], 0, 1)) + return (-1); + return (0); +} + +/*******************************SEARCH ROUTINES *****************************/ +/* + * All the access routines return + * + * Returns: + * 0 on SUCCESS + * 1 to indicate an external ERROR (i.e. key not found, etc) + * -1 to indicate an internal ERROR (i.e. out of memory, etc) + */ +static int +hash_get(dbp, key, data, flag) + const DB *dbp; + const DBT *key; + DBT *data; + __uint32_t flag; +{ + HTAB *hashp; + + hashp = (HTAB *)dbp->internal; + if (flag) { + hashp->error = errno = EINVAL; + return (ERROR); + } + return (hash_access(hashp, HASH_GET, (DBT *)key, data)); +} + +static int +hash_put(dbp, key, data, flag) + const DB *dbp; + DBT *key; + const DBT *data; + __uint32_t flag; +{ + HTAB *hashp; + + hashp = (HTAB *)dbp->internal; + if (flag && flag != R_NOOVERWRITE) { + hashp->error = EINVAL; + errno = EINVAL; + return (ERROR); + } + if ((hashp->flags & O_ACCMODE) == O_RDONLY) { + hashp->error = errno = EPERM; + return (ERROR); + } + return (hash_access(hashp, flag == R_NOOVERWRITE ? + HASH_PUTNEW : HASH_PUT, (DBT *)key, (DBT *)data)); +} + +static int +hash_delete(dbp, key, flag) + const DB *dbp; + const DBT *key; + __uint32_t flag; /* Ignored */ +{ + HTAB *hashp; + + hashp = (HTAB *)dbp->internal; + if (flag && flag != R_CURSOR) { + hashp->error = errno = EINVAL; + return (ERROR); + } + if ((hashp->flags & O_ACCMODE) == O_RDONLY) { + hashp->error = errno = EPERM; + return (ERROR); + } + return (hash_access(hashp, HASH_DELETE, (DBT *)key, NULL)); +} + +/* + * Assume that hashp has been set in wrapper routine. + */ +static int +hash_access(hashp, action, key, val) + HTAB *hashp; + ACTION action; + DBT *key, *val; +{ + BUFHEAD *rbufp; + BUFHEAD *bufp, *save_bufp; + __uint16_t *bp; + int n, ndx, off, size; + char *kp; + __uint16_t pageno; + +#ifdef HASH_STATISTICS + hash_accesses++; +#endif + + off = hashp->BSIZE; + size = key->size; + kp = (char *)key->data; + rbufp = __get_buf(hashp, __call_hash(hashp, kp, size), NULL, 0); + if (!rbufp) + return (ERROR); + save_bufp = rbufp; + + /* Pin the bucket chain */ + rbufp->flags |= BUF_PIN; + for (bp = (__uint16_t *)rbufp->page, n = *bp++, ndx = 1; ndx < n;) + if (bp[1] >= REAL_KEY) { + /* Real key/data pair */ + if (size == off - *bp && + memcmp(kp, rbufp->page + *bp, size) == 0) + goto found; + off = bp[1]; +#ifdef HASH_STATISTICS + hash_collisions++; +#endif + bp += 2; + ndx += 2; + } else if (bp[1] == OVFLPAGE) { + rbufp = __get_buf(hashp, *bp, rbufp, 0); + if (!rbufp) { + save_bufp->flags &= ~BUF_PIN; + return (ERROR); + } + /* FOR LOOP INIT */ + bp = (__uint16_t *)rbufp->page; + n = *bp++; + ndx = 1; + off = hashp->BSIZE; + } else if (bp[1] < REAL_KEY) { + if ((ndx = + __find_bigpair(hashp, rbufp, ndx, kp, size)) > 0) + goto found; + if (ndx == -2) { + bufp = rbufp; + if (!(pageno = + __find_last_page(hashp, &bufp))) { + ndx = 0; + rbufp = bufp; + break; /* FOR */ + } + rbufp = __get_buf(hashp, pageno, bufp, 0); + if (!rbufp) { + save_bufp->flags &= ~BUF_PIN; + return (ERROR); + } + /* FOR LOOP INIT */ + bp = (__uint16_t *)rbufp->page; + n = *bp++; + ndx = 1; + off = hashp->BSIZE; + } else { + save_bufp->flags &= ~BUF_PIN; + return (ERROR); + } + } + + /* Not found */ + switch (action) { + case HASH_PUT: + case HASH_PUTNEW: + if (__addel(hashp, rbufp, key, val)) { + save_bufp->flags &= ~BUF_PIN; + return (ERROR); + } else { + save_bufp->flags &= ~BUF_PIN; + return (SUCCESS); + } + case HASH_GET: + case HASH_DELETE: + default: + save_bufp->flags &= ~BUF_PIN; + return (ABNORMAL); + } + +found: + switch (action) { + case HASH_PUTNEW: + save_bufp->flags &= ~BUF_PIN; + return (ABNORMAL); + case HASH_GET: + bp = (__uint16_t *)rbufp->page; + if (bp[ndx + 1] < REAL_KEY) { + if (__big_return(hashp, rbufp, ndx, val, 0)) + return (ERROR); + } else { + val->data = (u_char *)rbufp->page + (int)bp[ndx + 1]; + val->size = bp[ndx] - bp[ndx + 1]; + } + break; + case HASH_PUT: + if ((__delpair(hashp, rbufp, ndx)) || + (__addel(hashp, rbufp, key, val))) { + save_bufp->flags &= ~BUF_PIN; + return (ERROR); + } + break; + case HASH_DELETE: + if (__delpair(hashp, rbufp, ndx)) + return (ERROR); + break; + default: + abort(); + } + save_bufp->flags &= ~BUF_PIN; + return (SUCCESS); +} + +static int +hash_seq(dbp, key, data, flag) + const DB *dbp; + DBT *key, *data; + __uint32_t flag; +{ + __uint32_t bucket; + BUFHEAD *bufp; + HTAB *hashp; + __uint16_t *bp, ndx; + + hashp = (HTAB *)dbp->internal; + if (flag && flag != R_FIRST && flag != R_NEXT) { + hashp->error = errno = EINVAL; + return (ERROR); + } +#ifdef HASH_STATISTICS + hash_accesses++; +#endif + if ((hashp->cbucket < 0) || (flag == R_FIRST)) { + hashp->cbucket = 0; + hashp->cndx = 1; + hashp->cpage = NULL; + } + + for (bp = NULL; !bp || !bp[0]; ) { + if (!(bufp = hashp->cpage)) { + for (bucket = hashp->cbucket; + bucket <= hashp->MAX_BUCKET; + bucket++, hashp->cndx = 1) { + bufp = __get_buf(hashp, bucket, NULL, 0); + if (!bufp) + return (ERROR); + hashp->cpage = bufp; + bp = (__uint16_t *)bufp->page; + if (bp[0]) + break; + } + hashp->cbucket = bucket; + if (hashp->cbucket > hashp->MAX_BUCKET) { + hashp->cbucket = -1; + return (ABNORMAL); + } + } else + bp = (__uint16_t *)hashp->cpage->page; + +#ifdef DEBUG + assert(bp); + assert(bufp); +#endif + while (bp[hashp->cndx + 1] == OVFLPAGE) { + bufp = hashp->cpage = + __get_buf(hashp, bp[hashp->cndx], bufp, 0); + if (!bufp) + return (ERROR); + bp = (__uint16_t *)(bufp->page); + hashp->cndx = 1; + } + if (!bp[0]) { + hashp->cpage = NULL; + ++hashp->cbucket; + } + } + ndx = hashp->cndx; + if (bp[ndx + 1] < REAL_KEY) { + if (__big_keydata(hashp, bufp, key, data, 1)) + return (ERROR); + } else { + key->data = (u_char *)hashp->cpage->page + bp[ndx]; + key->size = (ndx > 1 ? bp[ndx - 1] : hashp->BSIZE) - bp[ndx]; + data->data = (u_char *)hashp->cpage->page + bp[ndx + 1]; + data->size = bp[ndx] - bp[ndx + 1]; + ndx += 2; + if (ndx > bp[0]) { + hashp->cpage = NULL; + hashp->cbucket++; + hashp->cndx = 1; + } else + hashp->cndx = ndx; + } + return (SUCCESS); +} + +/********************************* UTILITIES ************************/ + +/* + * Returns: + * 0 ==> OK + * -1 ==> Error + */ +extern int +__expand_table(hashp) + HTAB *hashp; +{ + __uint32_t old_bucket, new_bucket; + int dirsize, new_segnum, spare_ndx; + +#ifdef HASH_STATISTICS + hash_expansions++; +#endif + new_bucket = ++hashp->MAX_BUCKET; + old_bucket = (hashp->MAX_BUCKET & hashp->LOW_MASK); + + new_segnum = new_bucket >> hashp->SSHIFT; + + /* Check if we need a new segment */ + if (new_segnum >= hashp->nsegs) { + /* Check if we need to expand directory */ + if (new_segnum >= hashp->DSIZE) { + /* Reallocate directory */ + dirsize = hashp->DSIZE * sizeof(SEGMENT *); + if (!hash_realloc(&hashp->dir, dirsize, dirsize << 1)) + return (-1); + hashp->DSIZE = dirsize << 1; + } + if ((hashp->dir[new_segnum] = + (SEGMENT)calloc(hashp->SGSIZE, sizeof(SEGMENT))) == NULL) + return (-1); + hashp->exsegs++; + hashp->nsegs++; + } + /* + * If the split point is increasing (MAX_BUCKET's log base 2 + * * increases), we need to copy the current contents of the spare + * split bucket to the next bucket. + */ + spare_ndx = __log2(hashp->MAX_BUCKET + 1); + if (spare_ndx > hashp->OVFL_POINT) { + hashp->SPARES[spare_ndx] = hashp->SPARES[hashp->OVFL_POINT]; + hashp->OVFL_POINT = spare_ndx; + } + + if (new_bucket > hashp->HIGH_MASK) { + /* Starting a new doubling */ + hashp->LOW_MASK = hashp->HIGH_MASK; + hashp->HIGH_MASK = new_bucket | hashp->LOW_MASK; + } + /* Relocate records to the new bucket */ + return (__split_page(hashp, old_bucket, new_bucket)); +} + +/* + * If realloc guarantees that the pointer is not destroyed if the realloc + * fails, then this routine can go away. + */ +static void * +hash_realloc(p_ptr, oldsize, newsize) + SEGMENT **p_ptr; + int oldsize, newsize; +{ + void *p; + + if ( (p = malloc(newsize)) ) { + memmove(p, *p_ptr, oldsize); + memset((char *)p + oldsize, 0, newsize - oldsize); + free(*p_ptr); + *p_ptr = p; + } + return (p); +} + +extern __uint32_t +__call_hash(hashp, k, len) + HTAB *hashp; + char *k; + int len; +{ + int n, bucket; + + n = hashp->hash(k, len); + bucket = n & hashp->HIGH_MASK; + if (bucket > hashp->MAX_BUCKET) + bucket = bucket & hashp->LOW_MASK; + return (bucket); +} + +/* + * Allocate segment table. On error, destroy the table and set errno. + * + * Returns 0 on success + */ +static int +alloc_segs(hashp, nsegs) + HTAB *hashp; + int nsegs; +{ + int i; + SEGMENT store; + + int save_errno; + + if ((hashp->dir = + (SEGMENT *)calloc(hashp->DSIZE, sizeof(SEGMENT *))) == NULL) { + save_errno = errno; + (void)hdestroy(hashp); + errno = save_errno; + return (-1); + } + /* Allocate segments */ + if ((store = + (SEGMENT)calloc(nsegs << hashp->SSHIFT, sizeof(SEGMENT))) == NULL) { + save_errno = errno; + (void)hdestroy(hashp); + errno = save_errno; + return (-1); + } + for (i = 0; i < nsegs; i++, hashp->nsegs++) + hashp->dir[i] = &store[i << hashp->SSHIFT]; + return (0); +} + +#ifdef _IEEE_LITTLE_ENDIAN +/* + * Hashp->hdr needs to be byteswapped. + */ +static void +swap_header_copy(srcp, destp) + HASHHDR *srcp, *destp; +{ + int i; + + P_32_COPY(srcp->magic, destp->magic); + P_32_COPY(srcp->version, destp->version); + P_32_COPY(srcp->lorder, destp->lorder); + P_32_COPY(srcp->bsize, destp->bsize); + P_32_COPY(srcp->bshift, destp->bshift); + P_32_COPY(srcp->dsize, destp->dsize); + P_32_COPY(srcp->ssize, destp->ssize); + P_32_COPY(srcp->sshift, destp->sshift); + P_32_COPY(srcp->ovfl_point, destp->ovfl_point); + P_32_COPY(srcp->last_freed, destp->last_freed); + P_32_COPY(srcp->max_bucket, destp->max_bucket); + P_32_COPY(srcp->high_mask, destp->high_mask); + P_32_COPY(srcp->low_mask, destp->low_mask); + P_32_COPY(srcp->ffactor, destp->ffactor); + P_32_COPY(srcp->nkeys, destp->nkeys); + P_32_COPY(srcp->hdrpages, destp->hdrpages); + P_32_COPY(srcp->h_charkey, destp->h_charkey); + for (i = 0; i < NCACHED; i++) { + P_32_COPY(srcp->spares[i], destp->spares[i]); + P_16_COPY(srcp->bitmaps[i], destp->bitmaps[i]); + } +} + +static void +swap_header(hashp) + HTAB *hashp; +{ + HASHHDR *hdrp; + int i; + + hdrp = &hashp->hdr; + + M_32_SWAP(hdrp->magic); + M_32_SWAP(hdrp->version); + M_32_SWAP(hdrp->lorder); + M_32_SWAP(hdrp->bsize); + M_32_SWAP(hdrp->bshift); + M_32_SWAP(hdrp->dsize); + M_32_SWAP(hdrp->ssize); + M_32_SWAP(hdrp->sshift); + M_32_SWAP(hdrp->ovfl_point); + M_32_SWAP(hdrp->last_freed); + M_32_SWAP(hdrp->max_bucket); + M_32_SWAP(hdrp->high_mask); + M_32_SWAP(hdrp->low_mask); + M_32_SWAP(hdrp->ffactor); + M_32_SWAP(hdrp->nkeys); + M_32_SWAP(hdrp->hdrpages); + M_32_SWAP(hdrp->h_charkey); + for (i = 0; i < NCACHED; i++) { + M_32_SWAP(hdrp->spares[i]); + M_16_SWAP(hdrp->bitmaps[i]); + } +} +#endif diff --git a/newlib/libc/search/hash.h b/newlib/libc/search/hash.h new file mode 100644 index 000000000..fa715c1eb --- /dev/null +++ b/newlib/libc/search/hash.h @@ -0,0 +1,294 @@ +/*- + * Copyright (c) 1990, 1993, 1994 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Margo Seltzer. + * + * 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. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed by the University of + * California, Berkeley and its contributors. + * 4. 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. + * + * @(#)hash.h 8.3 (Berkeley) 5/31/94 + * $FreeBSD: src/lib/libc/db/hash/hash.h,v 1.6 2002/03/21 22:46:26 obrien Exp $ + */ + +/* Operations */ +typedef enum { + HASH_GET, HASH_PUT, HASH_PUTNEW, HASH_DELETE, HASH_FIRST, HASH_NEXT +} ACTION; + +/* Buffer Management structures */ +typedef struct _bufhead BUFHEAD; + +struct _bufhead { + BUFHEAD *prev; /* LRU links */ + BUFHEAD *next; /* LRU links */ + BUFHEAD *ovfl; /* Overflow page buffer header */ + __uint32_t addr; /* Address of this page */ + char *page; /* Actual page data */ + char flags; +#define BUF_MOD 0x0001 +#define BUF_DISK 0x0002 +#define BUF_BUCKET 0x0004 +#define BUF_PIN 0x0008 +}; + +#define IS_BUCKET(X) ((X) & BUF_BUCKET) + +typedef BUFHEAD **SEGMENT; + +/* Hash Table Information */ +typedef struct hashhdr { /* Disk resident portion */ + int magic; /* Magic NO for hash tables */ + int version; /* Version ID */ + __uint32_t lorder; /* Byte Order */ + int bsize; /* Bucket/Page Size */ + int bshift; /* Bucket shift */ + int dsize; /* Directory Size */ + int ssize; /* Segment Size */ + int sshift; /* Segment shift */ + int ovfl_point; /* Where overflow pages are being + * allocated */ + int last_freed; /* Last overflow page freed */ + int max_bucket; /* ID of Maximum bucket in use */ + int high_mask; /* Mask to modulo into entire table */ + int low_mask; /* Mask to modulo into lower half of + * table */ + int ffactor; /* Fill factor */ + int nkeys; /* Number of keys in hash table */ + int hdrpages; /* Size of table header */ + int h_charkey; /* value of hash(CHARKEY) */ +#define NCACHED 32 /* number of bit maps and spare + * points */ + int spares[NCACHED];/* spare pages for overflow */ + __uint16_t bitmaps[NCACHED]; /* address of overflow page + * bitmaps */ +} HASHHDR; + +typedef struct htab { /* Memory resident data structure */ + HASHHDR hdr; /* Header */ + int nsegs; /* Number of allocated segments */ + int exsegs; /* Number of extra allocated + * segments */ + __uint32_t /* Hash function */ + (*hash)(const void *, size_t); + int flags; /* Flag values */ + int fp; /* File pointer */ + char *tmp_buf; /* Temporary Buffer for BIG data */ + char *tmp_key; /* Temporary Buffer for BIG keys */ + BUFHEAD *cpage; /* Current page */ + int cbucket; /* Current bucket */ + int cndx; /* Index of next item on cpage */ + int error; /* Error Number -- for DBM + * compatibility */ + int new_file; /* Indicates if fd is backing store + * or no */ + int save_file; /* Indicates whether we need to flush + * file at + * exit */ + __uint32_t *mapp[NCACHED]; /* Pointers to page maps */ + int nmaps; /* Initial number of bitmaps */ + int nbufs; /* Number of buffers left to + * allocate */ + BUFHEAD bufhead; /* Header of buffer lru list */ + SEGMENT *dir; /* Hash Bucket directory */ +} HTAB; + +/* + * Constants + */ +#define MAX_BSIZE 65536 /* 2^16 */ +#define MIN_BUFFERS 6 +#define MINHDRSIZE 512 +#define DEF_BUFSIZE 65536 /* 64 K */ +#define DEF_BUCKET_SIZE 4096 +#define DEF_BUCKET_SHIFT 12 /* log2(BUCKET) */ +#define DEF_SEGSIZE 256 +#define DEF_SEGSIZE_SHIFT 8 /* log2(SEGSIZE) */ +#define DEF_DIRSIZE 256 +#define DEF_FFACTOR 65536 +#define MIN_FFACTOR 4 +#define SPLTMAX 8 +#define CHARKEY "%$sniglet^&" +#define NUMKEY 1038583 +#define BYTE_SHIFT 3 +#define INT_TO_BYTE 2 +#define INT_BYTE_SHIFT 5 +#define ALL_SET ((__uint32_t)0xFFFFFFFF) +#define ALL_CLEAR 0 + +#define PTROF(X) ((BUFHEAD *)((ptrdiff_t)(X)&~0x3)) +#define ISMOD(X) ((__uint32_t)(ptrdiff_t)(X)&0x1) +#define DOMOD(X) ((X) = (char *)((ptrdiff_t)(X)|0x1)) +#define ISDISK(X) ((__uint32_t)(ptrdiff_t)(X)&0x2) +#define DODISK(X) ((X) = (char *)((ptrdiff_t)(X)|0x2)) + +#define BITS_PER_MAP 32 + +/* Given the address of the beginning of a big map, clear/set the nth bit */ +#define CLRBIT(A, N) ((A)[(N)/BITS_PER_MAP] &= ~(1<<((N)%BITS_PER_MAP))) +#define SETBIT(A, N) ((A)[(N)/BITS_PER_MAP] |= (1<<((N)%BITS_PER_MAP))) +#define ISSET(A, N) ((A)[(N)/BITS_PER_MAP] & (1<<((N)%BITS_PER_MAP))) + +/* Overflow management */ +/* + * Overflow page numbers are allocated per split point. At each doubling of + * the table, we can allocate extra pages. So, an overflow page number has + * the top 5 bits indicate which split point and the lower 11 bits indicate + * which page at that split point is indicated (pages within split points are + * numberered starting with 1). + */ + +#define SPLITSHIFT 11 +#define SPLITMASK 0x7FF +#define SPLITNUM(N) (((__uint32_t)(N)) >> SPLITSHIFT) +#define OPAGENUM(N) ((N) & SPLITMASK) +#define OADDR_OF(S,O) ((__uint32_t)((__uint32_t)(S) << SPLITSHIFT) + (O)) + +#define BUCKET_TO_PAGE(B) \ + (B) + hashp->HDRPAGES + ((B) ? hashp->SPARES[__log2((B)+1)-1] : 0) +#define OADDR_TO_PAGE(B) \ + BUCKET_TO_PAGE ( (1 << SPLITNUM((B))) -1 ) + OPAGENUM((B)); + +/* + * page.h contains a detailed description of the page format. + * + * Normally, keys and data are accessed from offset tables in the top of + * each page which point to the beginning of the key and data. There are + * four flag values which may be stored in these offset tables which indicate + * the following: + * + * + * OVFLPAGE Rather than a key data pair, this pair contains + * the address of an overflow page. The format of + * the pair is: + * OVERFLOW_PAGE_NUMBER OVFLPAGE + * + * PARTIAL_KEY This must be the first key/data pair on a page + * and implies that page contains only a partial key. + * That is, the key is too big to fit on a single page + * so it starts on this page and continues on the next. + * The format of the page is: + * KEY_OFF PARTIAL_KEY OVFL_PAGENO OVFLPAGE + * + * KEY_OFF -- offset of the beginning of the key + * PARTIAL_KEY -- 1 + * OVFL_PAGENO - page number of the next overflow page + * OVFLPAGE -- 0 + * + * FULL_KEY This must be the first key/data pair on the page. It + * is used in two cases. + * + * Case 1: + * There is a complete key on the page but no data + * (because it wouldn't fit). The next page contains + * the data. + * + * Page format it: + * KEY_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE + * + * KEY_OFF -- offset of the beginning of the key + * FULL_KEY -- 2 + * OVFL_PAGENO - page number of the next overflow page + * OVFLPAGE -- 0 + * + * Case 2: + * This page contains no key, but part of a large + * data field, which is continued on the next page. + * + * Page format it: + * DATA_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE + * + * KEY_OFF -- offset of the beginning of the data on + * this page + * FULL_KEY -- 2 + * OVFL_PAGENO - page number of the next overflow page + * OVFLPAGE -- 0 + * + * FULL_KEY_DATA + * This must be the first key/data pair on the page. + * There are two cases: + * + * Case 1: + * This page contains a key and the beginning of the + * data field, but the data field is continued on the + * next page. + * + * Page format is: + * KEY_OFF FULL_KEY_DATA OVFL_PAGENO DATA_OFF + * + * KEY_OFF -- offset of the beginning of the key + * FULL_KEY_DATA -- 3 + * OVFL_PAGENO - page number of the next overflow page + * DATA_OFF -- offset of the beginning of the data + * + * Case 2: + * This page contains the last page of a big data pair. + * There is no key, only the tail end of the data + * on this page. + * + * Page format is: + * DATA_OFF FULL_KEY_DATA <OVFL_PAGENO> <OVFLPAGE> + * + * DATA_OFF -- offset of the beginning of the data on + * this page + * FULL_KEY_DATA -- 3 + * OVFL_PAGENO - page number of the next overflow page + * OVFLPAGE -- 0 + * + * OVFL_PAGENO and OVFLPAGE are optional (they are + * not present if there is no next page). + */ + +#define OVFLPAGE 0 +#define PARTIAL_KEY 1 +#define FULL_KEY 2 +#define FULL_KEY_DATA 3 +#define REAL_KEY 4 + +/* Short hands for accessing structure */ +#define BSIZE hdr.bsize +#define BSHIFT hdr.bshift +#define DSIZE hdr.dsize +#define SGSIZE hdr.ssize +#define SSHIFT hdr.sshift +#define LORDER hdr.lorder +#define OVFL_POINT hdr.ovfl_point +#define LAST_FREED hdr.last_freed +#define MAX_BUCKET hdr.max_bucket +#define FFACTOR hdr.ffactor +#define HIGH_MASK hdr.high_mask +#define LOW_MASK hdr.low_mask +#define NKEYS hdr.nkeys +#define HDRPAGES hdr.hdrpages +#define SPARES hdr.spares +#define BITMAPS hdr.bitmaps +#define HASH_VERSION hdr.version +#define MAGIC hdr.magic +#define NEXT_FREE hdr.next_free +#define H_CHARKEY hdr.h_charkey diff --git a/newlib/libc/search/hash_bigkey.c b/newlib/libc/search/hash_bigkey.c new file mode 100644 index 000000000..8f8c58d10 --- /dev/null +++ b/newlib/libc/search/hash_bigkey.c @@ -0,0 +1,669 @@ +/*- + * Copyright (c) 1990, 1993, 1994 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Margo Seltzer. + * + * 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. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed by the University of + * California, Berkeley and its contributors. + * 4. 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. + */ + +#include <sys/param.h> +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)hash_bigkey.c 8.3 (Berkeley) 5/31/94"; +#endif /* LIBC_SCCS and not lint */ +#include <sys/cdefs.h> + +/* + * PACKAGE: hash + * DESCRIPTION: + * Big key/data handling for the hashing package. + * + * ROUTINES: + * External + * __big_keydata + * __big_split + * __big_insert + * __big_return + * __big_delete + * __find_last_page + * Internal + * collect_key + * collect_data + */ + +#include <sys/param.h> + +#include <errno.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#ifdef DEBUG +#include <assert.h> +#endif + +#include <db.h> +#include "hash.h" +#include "page.h" +#include "extern.h" + +static int collect_key(HTAB *, BUFHEAD *, int, DBT *, int); +static int collect_data(HTAB *, BUFHEAD *, int, int); + +/* + * Big_insert + * + * You need to do an insert and the key/data pair is too big + * + * Returns: + * 0 ==> OK + *-1 ==> ERROR + */ +extern int +__big_insert(hashp, bufp, key, val) + HTAB *hashp; + BUFHEAD *bufp; + const DBT *key, *val; +{ + __uint16_t *p; + int key_size, n, val_size; + __uint16_t space, move_bytes, off; + char *cp, *key_data, *val_data; + + cp = bufp->page; /* Character pointer of p. */ + p = (__uint16_t *)cp; + + key_data = (char *)key->data; + key_size = key->size; + val_data = (char *)val->data; + val_size = val->size; + + /* First move the Key */ + for (space = FREESPACE(p) - BIGOVERHEAD; key_size; + space = FREESPACE(p) - BIGOVERHEAD) { + move_bytes = MIN(space, key_size); + off = OFFSET(p) - move_bytes; + memmove(cp + off, key_data, move_bytes); + key_size -= move_bytes; + key_data += move_bytes; + n = p[0]; + p[++n] = off; + p[0] = ++n; + FREESPACE(p) = off - PAGE_META(n); + OFFSET(p) = off; + p[n] = PARTIAL_KEY; + bufp = __add_ovflpage(hashp, bufp); + if (!bufp) + return (-1); + n = p[0]; + if (!key_size) + if (FREESPACE(p)) { + move_bytes = MIN(FREESPACE(p), val_size); + off = OFFSET(p) - move_bytes; + p[n] = off; + memmove(cp + off, val_data, move_bytes); + val_data += move_bytes; + val_size -= move_bytes; + p[n - 2] = FULL_KEY_DATA; + FREESPACE(p) = FREESPACE(p) - move_bytes; + OFFSET(p) = off; + } else + p[n - 2] = FULL_KEY; + p = (__uint16_t *)bufp->page; + cp = bufp->page; + bufp->flags |= BUF_MOD; + } + + /* Now move the data */ + for (space = FREESPACE(p) - BIGOVERHEAD; val_size; + space = FREESPACE(p) - BIGOVERHEAD) { + move_bytes = MIN(space, val_size); + /* + * Here's the hack to make sure that if the data ends on the + * same page as the key ends, FREESPACE is at least one. + */ + if (space == val_size && val_size == val->size) + move_bytes--; + off = OFFSET(p) - move_bytes; + memmove(cp + off, val_data, move_bytes); + val_size -= move_bytes; + val_data += move_bytes; + n = p[0]; + p[++n] = off; + p[0] = ++n; + FREESPACE(p) = off - PAGE_META(n); + OFFSET(p) = off; + if (val_size) { + p[n] = FULL_KEY; + bufp = __add_ovflpage(hashp, bufp); + if (!bufp) + return (-1); + cp = bufp->page; + p = (__uint16_t *)cp; + } else + p[n] = FULL_KEY_DATA; + bufp->flags |= BUF_MOD; + } + return (0); +} + +/* + * Called when bufp's page contains a partial key (index should be 1) + * + * All pages in the big key/data pair except bufp are freed. We cannot + * free bufp because the page pointing to it is lost and we can't get rid + * of its pointer. + * + * Returns: + * 0 => OK + *-1 => ERROR + */ +extern int +__big_delete(hashp, bufp) + HTAB *hashp; + BUFHEAD *bufp; +{ + BUFHEAD *last_bfp, *rbufp; + __uint16_t *bp, pageno; + int key_done, n; + + rbufp = bufp; + last_bfp = NULL; + bp = (__uint16_t *)bufp->page; + pageno = 0; + key_done = 0; + + while (!key_done || (bp[2] != FULL_KEY_DATA)) { + if (bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA) + key_done = 1; + + /* + * If there is freespace left on a FULL_KEY_DATA page, then + * the data is short and fits entirely on this page, and this + * is the last page. + */ + if (bp[2] == FULL_KEY_DATA && FREESPACE(bp)) + break; + pageno = bp[bp[0] - 1]; + rbufp->flags |= BUF_MOD; + rbufp = __get_buf(hashp, pageno, rbufp, 0); + if (last_bfp) + __free_ovflpage(hashp, last_bfp); + last_bfp = rbufp; + if (!rbufp) + return (-1); /* Error. */ + bp = (__uint16_t *)rbufp->page; + } + + /* + * If we get here then rbufp points to the last page of the big + * key/data pair. Bufp points to the first one -- it should now be + * empty pointing to the next page after this pair. Can't free it + * because we don't have the page pointing to it. + */ + + /* This is information from the last page of the pair. */ + n = bp[0]; + pageno = bp[n - 1]; + + /* Now, bp is the first page of the pair. */ + bp = (__uint16_t *)bufp->page; + if (n > 2) { + /* There is an overflow page. */ + bp[1] = pageno; + bp[2] = OVFLPAGE; + bufp->ovfl = rbufp->ovfl; + } else + /* This is the last page. */ + bufp->ovfl = NULL; + n -= 2; + bp[0] = n; + FREESPACE(bp) = hashp->BSIZE - PAGE_META(n); + OFFSET(bp) = hashp->BSIZE - 1; + + bufp->flags |= BUF_MOD; + if (rbufp) + __free_ovflpage(hashp, rbufp); + if (last_bfp != rbufp) + __free_ovflpage(hashp, last_bfp); + + hashp->NKEYS--; + return (0); +} +/* + * Returns: + * 0 = key not found + * -1 = get next overflow page + * -2 means key not found and this is big key/data + * -3 error + */ +extern int +__find_bigpair(hashp, bufp, ndx, key, size) + HTAB *hashp; + BUFHEAD *bufp; + int ndx; + char *key; + int size; +{ + __uint16_t *bp; + char *p; + int ksize; + __uint16_t bytes; + char *kkey; + + bp = (__uint16_t *)bufp->page; + p = bufp->page; + ksize = size; + kkey = key; + + for (bytes = hashp->BSIZE - bp[ndx]; + bytes <= size && bp[ndx + 1] == PARTIAL_KEY; + bytes = hashp->BSIZE - bp[ndx]) { + if (memcmp(p + bp[ndx], kkey, bytes)) + return (-2); + kkey += bytes; + ksize -= bytes; + bufp = __get_buf(hashp, bp[ndx + 2], bufp, 0); + if (!bufp) + return (-3); + p = bufp->page; + bp = (__uint16_t *)p; + ndx = 1; + } + + if (bytes != ksize || memcmp(p + bp[ndx], kkey, bytes)) { +#ifdef HASH_STATISTICS + ++hash_collisions; +#endif + return (-2); + } else + return (ndx); +} + +/* + * Given the buffer pointer of the first overflow page of a big pair, + * find the end of the big pair + * + * This will set bpp to the buffer header of the last page of the big pair. + * It will return the pageno of the overflow page following the last page + * of the pair; 0 if there isn't any (i.e. big pair is the last key in the + * bucket) + */ +extern __uint16_t +__find_last_page(hashp, bpp) + HTAB *hashp; + BUFHEAD **bpp; +{ + BUFHEAD *bufp; + __uint16_t *bp, pageno; + int n; + + bufp = *bpp; + bp = (__uint16_t *)bufp->page; + for (;;) { + n = bp[0]; + + /* + * This is the last page if: the tag is FULL_KEY_DATA and + * either only 2 entries OVFLPAGE marker is explicit there + * is freespace on the page. + */ + if (bp[2] == FULL_KEY_DATA && + ((n == 2) || (bp[n] == OVFLPAGE) || (FREESPACE(bp)))) + break; + + pageno = bp[n - 1]; + bufp = __get_buf(hashp, pageno, bufp, 0); + if (!bufp) + return (0); /* Need to indicate an error! */ + bp = (__uint16_t *)bufp->page; + } + + *bpp = bufp; + if (bp[0] > 2) + return (bp[3]); + else + return (0); +} + +/* + * Return the data for the key/data pair that begins on this page at this + * index (index should always be 1). + */ +extern int +__big_return(hashp, bufp, ndx, val, set_current) + HTAB *hashp; + BUFHEAD *bufp; + int ndx; + DBT *val; + int set_current; +{ + BUFHEAD *save_p; + __uint16_t *bp, len, off, save_addr; + char *tp; + + bp = (__uint16_t *)bufp->page; + while (bp[ndx + 1] == PARTIAL_KEY) { + bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0); + if (!bufp) + return (-1); + bp = (__uint16_t *)bufp->page; + ndx = 1; + } + + if (bp[ndx + 1] == FULL_KEY) { + bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0); + if (!bufp) + return (-1); + bp = (__uint16_t *)bufp->page; + save_p = bufp; + save_addr = save_p->addr; + off = bp[1]; + len = 0; + } else + if (!FREESPACE(bp)) { + /* + * This is a hack. We can't distinguish between + * FULL_KEY_DATA that contains complete data or + * incomplete data, so we require that if the data + * is complete, there is at least 1 byte of free + * space left. + */ + off = bp[bp[0]]; + len = bp[1] - off; + save_p = bufp; + save_addr = bufp->addr; + bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0); + if (!bufp) + return (-1); + bp = (__uint16_t *)bufp->page; + } else { + /* The data is all on one page. */ + tp = (char *)bp; + off = bp[bp[0]]; + val->data = (u_char *)tp + off; + val->size = bp[1] - off; + if (set_current) { + if (bp[0] == 2) { /* No more buckets in + * chain */ + hashp->cpage = NULL; + hashp->cbucket++; + hashp->cndx = 1; + } else { + hashp->cpage = __get_buf(hashp, + bp[bp[0] - 1], bufp, 0); + if (!hashp->cpage) + return (-1); + hashp->cndx = 1; + if (!((__uint16_t *) + hashp->cpage->page)[0]) { + hashp->cbucket++; + hashp->cpage = NULL; + } + } + } + return (0); + } + + val->size = collect_data(hashp, bufp, (int)len, set_current); + if (val->size == -1) + return (-1); + if (save_p->addr != save_addr) { + /* We are pretty short on buffers. */ + errno = EINVAL; /* OUT OF BUFFERS */ + return (-1); + } + memmove(hashp->tmp_buf, (save_p->page) + off, len); + val->data = (u_char *)hashp->tmp_buf; + return (0); +} +/* + * Count how big the total datasize is by recursing through the pages. Then + * allocate a buffer and copy the data as you recurse up. + */ +static int +collect_data(hashp, bufp, len, set) + HTAB *hashp; + BUFHEAD *bufp; + int len, set; +{ + __uint16_t *bp; + char *p; + BUFHEAD *xbp; + __uint16_t save_addr; + int mylen, totlen; + + p = bufp->page; + bp = (__uint16_t *)p; + mylen = hashp->BSIZE - bp[1]; + save_addr = bufp->addr; + + if (bp[2] == FULL_KEY_DATA) { /* End of Data */ + totlen = len + mylen; + if (hashp->tmp_buf) + free(hashp->tmp_buf); + if ((hashp->tmp_buf = (char *)malloc(totlen)) == NULL) + return (-1); + if (set) { + hashp->cndx = 1; + if (bp[0] == 2) { /* No more buckets in chain */ + hashp->cpage = NULL; + hashp->cbucket++; + } else { + hashp->cpage = + __get_buf(hashp, bp[bp[0] - 1], bufp, 0); + if (!hashp->cpage) + return (-1); + else if (!((__uint16_t *)hashp->cpage->page)[0]) { + hashp->cbucket++; + hashp->cpage = NULL; + } + } + } + } else { + xbp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0); + if (!xbp || ((totlen = + collect_data(hashp, xbp, len + mylen, set)) < 1)) + return (-1); + } + if (bufp->addr != save_addr) { + errno = EINVAL; /* Out of buffers. */ + return (-1); + } + memmove(&hashp->tmp_buf[len], (bufp->page) + bp[1], mylen); + return (totlen); +} + +/* + * Fill in the key and data for this big pair. + */ +extern int +__big_keydata(hashp, bufp, key, val, set) + HTAB *hashp; + BUFHEAD *bufp; + DBT *key, *val; + int set; +{ + key->size = collect_key(hashp, bufp, 0, val, set); + if (key->size == -1) + return (-1); + key->data = (u_char *)hashp->tmp_key; + return (0); +} + +/* + * Count how big the total key size is by recursing through the pages. Then + * collect the data, allocate a buffer and copy the key as you recurse up. + */ +static int +collect_key(hashp, bufp, len, val, set) + HTAB *hashp; + BUFHEAD *bufp; + int len; + DBT *val; + int set; +{ + BUFHEAD *xbp; + char *p; + int mylen, totlen; + __uint16_t *bp, save_addr; + + p = bufp->page; + bp = (__uint16_t *)p; + mylen = hashp->BSIZE - bp[1]; + + save_addr = bufp->addr; + totlen = len + mylen; + if (bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA) { /* End of Key. */ + if (hashp->tmp_key != NULL) + free(hashp->tmp_key); + if ((hashp->tmp_key = (char *)malloc(totlen)) == NULL) + return (-1); + if (__big_return(hashp, bufp, 1, val, set)) + return (-1); + } else { + xbp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0); + if (!xbp || ((totlen = + collect_key(hashp, xbp, totlen, val, set)) < 1)) + return (-1); + } + if (bufp->addr != save_addr) { + errno = EINVAL; /* MIS -- OUT OF BUFFERS */ + return (-1); + } + memmove(&hashp->tmp_key[len], (bufp->page) + bp[1], mylen); + return (totlen); +} + +/* + * Returns: + * 0 => OK + * -1 => error + */ +extern int +__big_split(hashp, op, np, big_keyp, addr, obucket, ret) + HTAB *hashp; + BUFHEAD *op; /* Pointer to where to put keys that go in old bucket */ + BUFHEAD *np; /* Pointer to new bucket page */ + /* Pointer to first page containing the big key/data */ + BUFHEAD *big_keyp; + int addr; /* Address of big_keyp */ + __uint32_t obucket;/* Old Bucket */ + SPLIT_RETURN *ret; +{ + BUFHEAD *tmpp; + __uint16_t *tp; + BUFHEAD *bp; + DBT key, val; + __uint32_t change; + __uint16_t free_space, n, off; + + bp = big_keyp; + + /* Now figure out where the big key/data goes */ + if (__big_keydata(hashp, big_keyp, &key, &val, 0)) + return (-1); + change = (__call_hash(hashp, key.data, key.size) != obucket); + + if ( (ret->next_addr = __find_last_page(hashp, &big_keyp)) ) { + if (!(ret->nextp = + __get_buf(hashp, ret->next_addr, big_keyp, 0))) + return (-1);; + } else + ret->nextp = NULL; + + /* Now make one of np/op point to the big key/data pair */ +#ifdef DEBUG + assert(np->ovfl == NULL); +#endif + if (change) + tmpp = np; + else + tmpp = op; + + tmpp->flags |= BUF_MOD; +#ifdef DEBUG1 + (void)fprintf(stderr, + "BIG_SPLIT: %d->ovfl was %d is now %d\n", tmpp->addr, + (tmpp->ovfl ? tmpp->ovfl->addr : 0), (bp ? bp->addr : 0)); +#endif + tmpp->ovfl = bp; /* one of op/np point to big_keyp */ + tp = (__uint16_t *)tmpp->page; +#ifdef DEBUG + assert(FREESPACE(tp) >= OVFLSIZE); +#endif + n = tp[0]; + off = OFFSET(tp); + free_space = FREESPACE(tp); + tp[++n] = (__uint16_t)addr; + tp[++n] = OVFLPAGE; + tp[0] = n; + OFFSET(tp) = off; + FREESPACE(tp) = free_space - OVFLSIZE; + + /* + * Finally, set the new and old return values. BIG_KEYP contains a + * pointer to the last page of the big key_data pair. Make sure that + * big_keyp has no following page (2 elements) or create an empty + * following page. + */ + + ret->newp = np; + ret->oldp = op; + + tp = (__uint16_t *)big_keyp->page; + big_keyp->flags |= BUF_MOD; + if (tp[0] > 2) { + /* + * There may be either one or two offsets on this page. If + * there is one, then the overflow page is linked on normally + * and tp[4] is OVFLPAGE. If there are two, tp[4] contains + * the second offset and needs to get stuffed in after the + * next overflow page is added. + */ + n = tp[4]; + free_space = FREESPACE(tp); + off = OFFSET(tp); + tp[0] -= 2; + FREESPACE(tp) = free_space + OVFLSIZE; + OFFSET(tp) = off; + tmpp = __add_ovflpage(hashp, big_keyp); + if (!tmpp) + return (-1); + tp[4] = n; + } else + tmpp = big_keyp; + + if (change) + ret->newp = tmpp; + else + ret->oldp = tmpp; + return (0); +} diff --git a/newlib/libc/search/hash_buf.c b/newlib/libc/search/hash_buf.c new file mode 100644 index 000000000..33cdb7c20 --- /dev/null +++ b/newlib/libc/search/hash_buf.c @@ -0,0 +1,356 @@ +/*- + * Copyright (c) 1990, 1993, 1994 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Margo Seltzer. + * + * 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. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed by the University of + * California, Berkeley and its contributors. + * 4. 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. + */ + +#include <sys/param.h> +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)hash_buf.c 8.5 (Berkeley) 7/15/94"; +#endif /* LIBC_SCCS and not lint */ +#include <sys/cdefs.h> + +/* + * PACKAGE: hash + * + * DESCRIPTION: + * Contains buffer management + * + * ROUTINES: + * External + * __buf_init + * __get_buf + * __buf_free + * __reclaim_buf + * Internal + * newbuf + */ + +#include <sys/param.h> + +#include <stddef.h> +#include <stdio.h> +#include <stdlib.h> + +#ifdef DEBUG +#include <assert.h> +#endif + +#include <db.h> +#include "hash.h" +#include "page.h" +#include "extern.h" + +static BUFHEAD *newbuf(HTAB *, __uint32_t, BUFHEAD *); + +/* Unlink B from its place in the lru */ +#define BUF_REMOVE(B) { \ + (B)->prev->next = (B)->next; \ + (B)->next->prev = (B)->prev; \ +} + +/* Insert B after P */ +#define BUF_INSERT(B, P) { \ + (B)->next = (P)->next; \ + (B)->prev = (P); \ + (P)->next = (B); \ + (B)->next->prev = (B); \ +} + +#define MRU hashp->bufhead.next +#define LRU hashp->bufhead.prev + +#define MRU_INSERT(B) BUF_INSERT((B), &hashp->bufhead) +#define LRU_INSERT(B) BUF_INSERT((B), LRU) + +/* + * We are looking for a buffer with address "addr". If prev_bp is NULL, then + * address is a bucket index. If prev_bp is not NULL, then it points to the + * page previous to an overflow page that we are trying to find. + * + * CAVEAT: The buffer header accessed via prev_bp's ovfl field may no longer + * be valid. Therefore, you must always verify that its address matches the + * address you are seeking. + */ +extern BUFHEAD * +__get_buf(hashp, addr, prev_bp, newpage) + HTAB *hashp; + __uint32_t addr; + BUFHEAD *prev_bp; + int newpage; /* If prev_bp set, indicates a new overflow page. */ +{ + BUFHEAD *bp; + __uint32_t is_disk_mask; + int is_disk, segment_ndx; + SEGMENT segp; + + is_disk = 0; + is_disk_mask = 0; + if (prev_bp) { + bp = prev_bp->ovfl; + if (!bp || (bp->addr != addr)) + bp = NULL; + if (!newpage) + is_disk = BUF_DISK; + } else { + /* Grab buffer out of directory */ + segment_ndx = addr & (hashp->SGSIZE - 1); + + /* valid segment ensured by __call_hash() */ + segp = hashp->dir[addr >> hashp->SSHIFT]; +#ifdef DEBUG + assert(segp != NULL); +#endif + bp = PTROF(segp[segment_ndx]); + is_disk_mask = ISDISK(segp[segment_ndx]); + is_disk = is_disk_mask || !hashp->new_file; + } + + if (!bp) { + bp = newbuf(hashp, addr, prev_bp); + if (!bp || + __get_page(hashp, bp->page, addr, !prev_bp, is_disk, 0)) + return (NULL); + if (!prev_bp) + segp[segment_ndx] = + (BUFHEAD *)((ptrdiff_t)bp | is_disk_mask); + } else { + BUF_REMOVE(bp); + MRU_INSERT(bp); + } + return (bp); +} + +/* + * We need a buffer for this page. Either allocate one, or evict a resident + * one (if we have as many buffers as we're allowed) and put this one in. + * + * If newbuf finds an error (returning NULL), it also sets errno. + */ +static BUFHEAD * +newbuf(hashp, addr, prev_bp) + HTAB *hashp; + __uint32_t addr; + BUFHEAD *prev_bp; +{ + BUFHEAD *bp; /* The buffer we're going to use */ + BUFHEAD *xbp; /* Temp pointer */ + BUFHEAD *next_xbp; + SEGMENT segp; + int segment_ndx; + __uint16_t oaddr, *shortp; + + oaddr = 0; + bp = LRU; + /* + * If LRU buffer is pinned, the buffer pool is too small. We need to + * allocate more buffers. + */ + if (hashp->nbufs || (bp->flags & BUF_PIN)) { + /* Allocate a new one */ + if ((bp = (BUFHEAD *)malloc(sizeof(BUFHEAD))) == NULL) + return (NULL); +#ifdef PURIFY + memset(bp, 0xff, sizeof(BUFHEAD)); +#endif + if ((bp->page = (char *)malloc(hashp->BSIZE)) == NULL) { + free(bp); + return (NULL); + } +#ifdef PURIFY + memset(bp->page, 0xff, hashp->BSIZE); +#endif + if (hashp->nbufs) + hashp->nbufs--; + } else { + /* Kick someone out */ + BUF_REMOVE(bp); + /* + * If this is an overflow page with addr 0, it's already been + * flushed back in an overflow chain and initialized. + */ + if ((bp->addr != 0) || (bp->flags & BUF_BUCKET)) { + /* + * Set oaddr before __put_page so that you get it + * before bytes are swapped. + */ + shortp = (__uint16_t *)bp->page; + if (shortp[0]) + oaddr = shortp[shortp[0] - 1]; + if ((bp->flags & BUF_MOD) && __put_page(hashp, bp->page, + bp->addr, (int)IS_BUCKET(bp->flags), 0)) + return (NULL); + /* + * Update the pointer to this page (i.e. invalidate it). + * + * If this is a new file (i.e. we created it at open + * time), make sure that we mark pages which have been + * written to disk so we retrieve them from disk later, + * rather than allocating new pages. + */ + if (IS_BUCKET(bp->flags)) { + segment_ndx = bp->addr & (hashp->SGSIZE - 1); + segp = hashp->dir[bp->addr >> hashp->SSHIFT]; +#ifdef DEBUG + assert(segp != NULL); +#endif + + if (hashp->new_file && + ((bp->flags & BUF_MOD) || + ISDISK(segp[segment_ndx]))) + segp[segment_ndx] = (BUFHEAD *)BUF_DISK; + else + segp[segment_ndx] = NULL; + } + /* + * Since overflow pages can only be access by means of + * their bucket, free overflow pages associated with + * this bucket. + */ + for (xbp = bp; xbp->ovfl;) { + next_xbp = xbp->ovfl; + xbp->ovfl = 0; + xbp = next_xbp; + + /* Check that ovfl pointer is up date. */ + if (IS_BUCKET(xbp->flags) || + (oaddr != xbp->addr)) + break; + + shortp = (__uint16_t *)xbp->page; + if (shortp[0]) + /* set before __put_page */ + oaddr = shortp[shortp[0] - 1]; + if ((xbp->flags & BUF_MOD) && __put_page(hashp, + xbp->page, xbp->addr, 0, 0)) + return (NULL); + xbp->addr = 0; + xbp->flags = 0; + BUF_REMOVE(xbp); + LRU_INSERT(xbp); + } + } + } + + /* Now assign this buffer */ + bp->addr = addr; +#ifdef DEBUG1 + (void)fprintf(stderr, "NEWBUF1: %d->ovfl was %d is now %d\n", + bp->addr, (bp->ovfl ? bp->ovfl->addr : 0), 0); +#endif + bp->ovfl = NULL; + if (prev_bp) { + /* + * If prev_bp is set, this is an overflow page, hook it in to + * the buffer overflow links. + */ +#ifdef DEBUG1 + (void)fprintf(stderr, "NEWBUF2: %d->ovfl was %d is now %d\n", + prev_bp->addr, (prev_bp->ovfl ? bp->ovfl->addr : 0), + (bp ? bp->addr : 0)); +#endif + prev_bp->ovfl = bp; + bp->flags = 0; + } else + bp->flags = BUF_BUCKET; + MRU_INSERT(bp); + return (bp); +} + +extern void +__buf_init(hashp, nbytes) + HTAB *hashp; + int nbytes; +{ + BUFHEAD *bfp; + int npages; + + bfp = &(hashp->bufhead); + npages = (nbytes + hashp->BSIZE - 1) >> hashp->BSHIFT; + npages = MAX(npages, MIN_BUFFERS); + + hashp->nbufs = npages; + bfp->next = bfp; + bfp->prev = bfp; + /* + * This space is calloc'd so these are already null. + * + * bfp->ovfl = NULL; + * bfp->flags = 0; + * bfp->page = NULL; + * bfp->addr = 0; + */ +} + +extern int +__buf_free(hashp, do_free, to_disk) + HTAB *hashp; + int do_free, to_disk; +{ + BUFHEAD *bp; + + /* Need to make sure that buffer manager has been initialized */ + if (!LRU) + return (0); + for (bp = LRU; bp != &hashp->bufhead;) { + /* Check that the buffer is valid */ + if (bp->addr || IS_BUCKET(bp->flags)) { + if (to_disk && (bp->flags & BUF_MOD) && + __put_page(hashp, bp->page, + bp->addr, IS_BUCKET(bp->flags), 0)) + return (-1); + } + /* Check if we are freeing stuff */ + if (do_free) { + if (bp->page) + free(bp->page); + BUF_REMOVE(bp); + free(bp); + bp = LRU; + } else + bp = bp->prev; + } + return (0); +} + +extern void +__reclaim_buf(hashp, bp) + HTAB *hashp; + BUFHEAD *bp; +{ + bp->ovfl = 0; + bp->addr = 0; + bp->flags = 0; + BUF_REMOVE(bp); + LRU_INSERT(bp); +} diff --git a/newlib/libc/search/hash_func.c b/newlib/libc/search/hash_func.c new file mode 100644 index 000000000..deeb21e60 --- /dev/null +++ b/newlib/libc/search/hash_func.c @@ -0,0 +1,212 @@ +/*- + * Copyright (c) 1990, 1993 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Margo Seltzer. + * + * 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. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed by the University of + * California, Berkeley and its contributors. + * 4. 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. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)hash_func.c 8.2 (Berkeley) 2/21/94"; +#endif /* LIBC_SCCS and not lint */ +#include <sys/cdefs.h> +#include <sys/types.h> + +#include <db.h> +#include "hash.h" +#include "page.h" +#include "extern.h" + +static __uint32_t hash1(const void *, size_t); +static __uint32_t hash2(const void *, size_t); +static __uint32_t hash3(const void *, size_t); +static __uint32_t hash4(const void *, size_t); + +/* Global default hash function */ +__uint32_t (*__default_hash)(const void *, size_t) = hash4; + +/* + * HASH FUNCTIONS + * + * Assume that we've already split the bucket to which this key hashes, + * calculate that bucket, and check that in fact we did already split it. + * + * This came from ejb's hsearch. + */ + +#define PRIME1 37 +#define PRIME2 1048583 + +static __uint32_t +hash1(keyarg, len) + const void *keyarg; + size_t len; +{ + const u_char *key; + __uint32_t h; + + /* Convert string to integer */ + for (key = keyarg, h = 0; len--;) + h = h * PRIME1 ^ (*key++ - ' '); + h %= PRIME2; + return (h); +} + +/* + * Phong's linear congruential hash + */ +#define dcharhash(h, c) ((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c)) + +static __uint32_t +hash2(keyarg, len) + const void *keyarg; + size_t len; +{ + const u_char *e, *key; + __uint32_t h; + u_char c; + + key = keyarg; + e = key + len; + for (h = 0; key != e;) { + c = *key++; + if (!c && key > e) + break; + dcharhash(h, c); + } + return (h); +} + +/* + * This is INCREDIBLY ugly, but fast. We break the string up into 8 byte + * units. On the first time through the loop we get the "leftover bytes" + * (strlen % 8). On every other iteration, we perform 8 HASHC's so we handle + * all 8 bytes. Essentially, this saves us 7 cmp & branch instructions. If + * this routine is heavily used enough, it's worth the ugly coding. + * + * OZ's original sdbm hash + */ +static __uint32_t +hash3(keyarg, len) + const void *keyarg; + size_t len; +{ + const u_char *key; + size_t loop; + __uint32_t h; + +#define HASHC h = *key++ + 65599 * h + + h = 0; + key = keyarg; + if (len > 0) { + loop = (len + 8 - 1) >> 3; + + switch (len & (8 - 1)) { + case 0: + do { + HASHC; + /* FALLTHROUGH */ + case 7: + HASHC; + /* FALLTHROUGH */ + case 6: + HASHC; + /* FALLTHROUGH */ + case 5: + HASHC; + /* FALLTHROUGH */ + case 4: + HASHC; + /* FALLTHROUGH */ + case 3: + HASHC; + /* FALLTHROUGH */ + case 2: + HASHC; + /* FALLTHROUGH */ + case 1: + HASHC; + } while (--loop); + } + } + return (h); +} + +/* Hash function from Chris Torek. */ +static __uint32_t +hash4(keyarg, len) + const void *keyarg; + size_t len; +{ + const u_char *key; + size_t loop; + __uint32_t h; + +#define HASH4a h = (h << 5) - h + *key++; +#define HASH4b h = (h << 5) + h + *key++; +#define HASH4 HASH4b + + h = 0; + key = keyarg; + if (len > 0) { + loop = (len + 8 - 1) >> 3; + + switch (len & (8 - 1)) { + case 0: + do { + HASH4; + /* FALLTHROUGH */ + case 7: + HASH4; + /* FALLTHROUGH */ + case 6: + HASH4; + /* FALLTHROUGH */ + case 5: + HASH4; + /* FALLTHROUGH */ + case 4: + HASH4; + /* FALLTHROUGH */ + case 3: + HASH4; + /* FALLTHROUGH */ + case 2: + HASH4; + /* FALLTHROUGH */ + case 1: + HASH4; + } while (--loop); + } + } + return (h); +} diff --git a/newlib/libc/search/hash_log2.c b/newlib/libc/search/hash_log2.c new file mode 100644 index 000000000..bbcddb0c7 --- /dev/null +++ b/newlib/libc/search/hash_log2.c @@ -0,0 +1,55 @@ +/*- + * Copyright (c) 1990, 1993, 1994 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Margo Seltzer. + * + * 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. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed by the University of + * California, Berkeley and its contributors. + * 4. 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. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)hash_log2.c 8.2 (Berkeley) 5/31/94"; +#endif /* LIBC_SCCS and not lint */ +#include <sys/cdefs.h> + +#include <sys/types.h> + +#include <db.h> + +__uint32_t +__log2(num) + __uint32_t num; +{ + __uint32_t i, limit; + + limit = 1; + for (i = 0; limit < num; limit = limit << 1, i++); + return (i); +} diff --git a/newlib/libc/search/hash_page.c b/newlib/libc/search/hash_page.c new file mode 100644 index 000000000..a92dfa6e7 --- /dev/null +++ b/newlib/libc/search/hash_page.c @@ -0,0 +1,946 @@ +/*- + * Copyright (c) 1990, 1993, 1994 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Margo Seltzer. + * + * 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. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed by the University of + * California, Berkeley and its contributors. + * 4. 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. + */ + +#include <sys/param.h> +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)hash_page.c 8.7 (Berkeley) 8/16/94"; +#endif /* LIBC_SCCS and not lint */ +#include <sys/cdefs.h> + +/* + * PACKAGE: hashing + * + * DESCRIPTION: + * Page manipulation for hashing package. + * + * ROUTINES: + * + * External + * __get_page + * __add_ovflpage + * Internal + * overflow_page + * open_temp + */ + +#include <sys/types.h> + +#include <errno.h> +#include <fcntl.h> +#include <signal.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <unistd.h> +#ifdef DEBUG +#include <assert.h> +#endif + +#include <db.h> +#include "hash.h" +#include "page.h" +#include "extern.h" + +static __uint32_t *fetch_bitmap(HTAB *, int); +static __uint32_t first_free(__uint32_t); +static int open_temp(HTAB *); +static __uint16_t overflow_page(HTAB *); +static void putpair(char *, const DBT *, const DBT *); +static void squeeze_key(__uint16_t *, const DBT *, const DBT *); +static int ugly_split +(HTAB *, __uint32_t, BUFHEAD *, BUFHEAD *, int, int); + +#define PAGE_INIT(P) { \ + ((__uint16_t *)(P))[0] = 0; \ + ((__uint16_t *)(P))[1] = hashp->BSIZE - 3 * sizeof(__uint16_t); \ + ((__uint16_t *)(P))[2] = hashp->BSIZE; \ +} + +/* + * This is called AFTER we have verified that there is room on the page for + * the pair (PAIRFITS has returned true) so we go right ahead and start moving + * stuff on. + */ +static void +putpair(p, key, val) + char *p; + const DBT *key, *val; +{ + __uint16_t *bp, n, off; + + bp = (__uint16_t *)p; + + /* Enter the key first. */ + n = bp[0]; + + off = OFFSET(bp) - key->size; + memmove(p + off, key->data, key->size); + bp[++n] = off; + + /* Now the data. */ + off -= val->size; + memmove(p + off, val->data, val->size); + bp[++n] = off; + + /* Adjust page info. */ + bp[0] = n; + bp[n + 1] = off - ((n + 3) * sizeof(__uint16_t)); + bp[n + 2] = off; +} + +/* + * Returns: + * 0 OK + * -1 error + */ +extern int +__delpair(hashp, bufp, ndx) + HTAB *hashp; + BUFHEAD *bufp; + int ndx; +{ + __uint16_t *bp, newoff; + int n; + __uint16_t pairlen; + + bp = (__uint16_t *)bufp->page; + n = bp[0]; + + if (bp[ndx + 1] < REAL_KEY) + return (__big_delete(hashp, bufp)); + if (ndx != 1) + newoff = bp[ndx - 1]; + else + newoff = hashp->BSIZE; + pairlen = newoff - bp[ndx + 1]; + + if (ndx != (n - 1)) { + /* Hard Case -- need to shuffle keys */ + int i; + char *src = bufp->page + (int)OFFSET(bp); + char *dst = src + (int)pairlen; + memmove(dst, src, bp[ndx + 1] - OFFSET(bp)); + + /* Now adjust the pointers */ + for (i = ndx + 2; i <= n; i += 2) { + if (bp[i + 1] == OVFLPAGE) { + bp[i - 2] = bp[i]; + bp[i - 1] = bp[i + 1]; + } else { + bp[i - 2] = bp[i] + pairlen; + bp[i - 1] = bp[i + 1] + pairlen; + } + } + } + /* Finally adjust the page data */ + bp[n] = OFFSET(bp) + pairlen; + bp[n - 1] = bp[n + 1] + pairlen + 2 * sizeof(__uint16_t); + bp[0] = n - 2; + hashp->NKEYS--; + + bufp->flags |= BUF_MOD; + return (0); +} +/* + * Returns: + * 0 ==> OK + * -1 ==> Error + */ +extern int +__split_page(hashp, obucket, nbucket) + HTAB *hashp; + __uint32_t obucket, nbucket; +{ + BUFHEAD *new_bufp, *old_bufp; + __uint16_t *ino; + char *np; + DBT key, val; + int n, ndx, retval; + __uint16_t copyto, diff, off, moved; + char *op; + + copyto = (__uint16_t)hashp->BSIZE; + off = (__uint16_t)hashp->BSIZE; + old_bufp = __get_buf(hashp, obucket, NULL, 0); + if (old_bufp == NULL) + return (-1); + new_bufp = __get_buf(hashp, nbucket, NULL, 0); + if (new_bufp == NULL) + return (-1); + + old_bufp->flags |= (BUF_MOD | BUF_PIN); + new_bufp->flags |= (BUF_MOD | BUF_PIN); + + ino = (__uint16_t *)(op = old_bufp->page); + np = new_bufp->page; + + moved = 0; + + for (n = 1, ndx = 1; n < ino[0]; n += 2) { + if (ino[n + 1] < REAL_KEY) { + retval = ugly_split(hashp, obucket, old_bufp, new_bufp, + (int)copyto, (int)moved); + old_bufp->flags &= ~BUF_PIN; + new_bufp->flags &= ~BUF_PIN; + return (retval); + + } + key.data = (u_char *)op + ino[n]; + key.size = off - ino[n]; + + if (__call_hash(hashp, key.data, key.size) == obucket) { + /* Don't switch page */ + diff = copyto - off; + if (diff) { + copyto = ino[n + 1] + diff; + memmove(op + copyto, op + ino[n + 1], + off - ino[n + 1]); + ino[ndx] = copyto + ino[n] - ino[n + 1]; + ino[ndx + 1] = copyto; + } else + copyto = ino[n + 1]; + ndx += 2; + } else { + /* Switch page */ + val.data = (u_char *)op + ino[n + 1]; + val.size = ino[n] - ino[n + 1]; + putpair(np, &key, &val); + moved += 2; + } + + off = ino[n + 1]; + } + + /* Now clean up the page */ + ino[0] -= moved; + FREESPACE(ino) = copyto - sizeof(__uint16_t) * (ino[0] + 3); + OFFSET(ino) = copyto; + +#ifdef DEBUG3 + (void)fprintf(stderr, "split %d/%d\n", + ((__uint16_t *)np)[0] / 2, + ((__uint16_t *)op)[0] / 2); +#endif + /* unpin both pages */ + old_bufp->flags &= ~BUF_PIN; + new_bufp->flags &= ~BUF_PIN; + return (0); +} + +/* + * Called when we encounter an overflow or big key/data page during split + * handling. This is special cased since we have to begin checking whether + * the key/data pairs fit on their respective pages and because we may need + * overflow pages for both the old and new pages. + * + * The first page might be a page with regular key/data pairs in which case + * we have a regular overflow condition and just need to go on to the next + * page or it might be a big key/data pair in which case we need to fix the + * big key/data pair. + * + * Returns: + * 0 ==> success + * -1 ==> failure + */ +static int +ugly_split(hashp, obucket, old_bufp, new_bufp, copyto, moved) + HTAB *hashp; + __uint32_t obucket; /* Same as __split_page. */ + BUFHEAD *old_bufp, *new_bufp; + int copyto; /* First byte on page which contains key/data values. */ + int moved; /* Number of pairs moved to new page. */ +{ + BUFHEAD *bufp; /* Buffer header for ino */ + __uint16_t *ino; /* Page keys come off of */ + __uint16_t *np; /* New page */ + __uint16_t *op; /* Page keys go on to if they aren't moving */ + + BUFHEAD *last_bfp; /* Last buf header OVFL needing to be freed */ + DBT key, val; + SPLIT_RETURN ret; + __uint16_t n, off, ov_addr, scopyto; + char *cino; /* Character value of ino */ + + bufp = old_bufp; + ino = (__uint16_t *)old_bufp->page; + np = (__uint16_t *)new_bufp->page; + op = (__uint16_t *)old_bufp->page; + last_bfp = NULL; + scopyto = (__uint16_t)copyto; /* ANSI */ + + n = ino[0] - 1; + while (n < ino[0]) { + if (ino[2] < REAL_KEY && ino[2] != OVFLPAGE) { + if (__big_split(hashp, old_bufp, + new_bufp, bufp, bufp->addr, obucket, &ret)) + return (-1); + old_bufp = ret.oldp; + if (!old_bufp) + return (-1); + op = (__uint16_t *)old_bufp->page; + new_bufp = ret.newp; + if (!new_bufp) + return (-1); + np = (__uint16_t *)new_bufp->page; + bufp = ret.nextp; + if (!bufp) + return (0); + cino = (char *)bufp->page; + ino = (__uint16_t *)cino; + last_bfp = ret.nextp; + } else if (ino[n + 1] == OVFLPAGE) { + ov_addr = ino[n]; + /* + * Fix up the old page -- the extra 2 are the fields + * which contained the overflow information. + */ + ino[0] -= (moved + 2); + FREESPACE(ino) = + scopyto - sizeof(__uint16_t) * (ino[0] + 3); + OFFSET(ino) = scopyto; + + bufp = __get_buf(hashp, ov_addr, bufp, 0); + if (!bufp) + return (-1); + + ino = (__uint16_t *)bufp->page; + n = 1; + scopyto = hashp->BSIZE; + moved = 0; + + if (last_bfp) + __free_ovflpage(hashp, last_bfp); + last_bfp = bufp; + } + /* Move regular sized pairs of there are any */ + off = hashp->BSIZE; + for (n = 1; (n < ino[0]) && (ino[n + 1] >= REAL_KEY); n += 2) { + cino = (char *)ino; + key.data = (u_char *)cino + ino[n]; + key.size = off - ino[n]; + val.data = (u_char *)cino + ino[n + 1]; + val.size = ino[n] - ino[n + 1]; + off = ino[n + 1]; + + if (__call_hash(hashp, key.data, key.size) == obucket) { + /* Keep on old page */ + if (PAIRFITS(op, (&key), (&val))) + putpair((char *)op, &key, &val); + else { + old_bufp = + __add_ovflpage(hashp, old_bufp); + if (!old_bufp) + return (-1); + op = (__uint16_t *)old_bufp->page; + putpair((char *)op, &key, &val); + } + old_bufp->flags |= BUF_MOD; + } else { + /* Move to new page */ + if (PAIRFITS(np, (&key), (&val))) + putpair((char *)np, &key, &val); + else { + new_bufp = + __add_ovflpage(hashp, new_bufp); + if (!new_bufp) + return (-1); + np = (__uint16_t *)new_bufp->page; + putpair((char *)np, &key, &val); + } + new_bufp->flags |= BUF_MOD; + } + } + } + if (last_bfp) + __free_ovflpage(hashp, last_bfp); + return (0); +} + +/* + * Add the given pair to the page + * + * Returns: + * 0 ==> OK + * 1 ==> failure + */ +extern int +__addel(hashp, bufp, key, val) + HTAB *hashp; + BUFHEAD *bufp; + const DBT *key, *val; +{ + __uint16_t *bp, *sop; + int do_expand; + + bp = (__uint16_t *)bufp->page; + do_expand = 0; + while (bp[0] && (bp[2] < REAL_KEY || bp[bp[0]] < REAL_KEY)) + /* Exception case */ + if (bp[2] == FULL_KEY_DATA && bp[0] == 2) + /* This is the last page of a big key/data pair + and we need to add another page */ + break; + else if (bp[2] < REAL_KEY && bp[bp[0]] != OVFLPAGE) { + bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0); + if (!bufp) + return (-1); + bp = (__uint16_t *)bufp->page; + } else + /* Try to squeeze key on this page */ + if (FREESPACE(bp) > PAIRSIZE(key, val)) { + squeeze_key(bp, key, val); + return (0); + } else { + bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0); + if (!bufp) + return (-1); + bp = (__uint16_t *)bufp->page; + } + + if (PAIRFITS(bp, key, val)) + putpair(bufp->page, key, val); + else { + do_expand = 1; + bufp = __add_ovflpage(hashp, bufp); + if (!bufp) + return (-1); + sop = (__uint16_t *)bufp->page; + + if (PAIRFITS(sop, key, val)) + putpair((char *)sop, key, val); + else + if (__big_insert(hashp, bufp, key, val)) + return (-1); + } + bufp->flags |= BUF_MOD; + /* + * If the average number of keys per bucket exceeds the fill factor, + * expand the table. + */ + hashp->NKEYS++; + if (do_expand || + (hashp->NKEYS / (hashp->MAX_BUCKET + 1) > hashp->FFACTOR)) + return (__expand_table(hashp)); + return (0); +} + +/* + * + * Returns: + * pointer on success + * NULL on error + */ +extern BUFHEAD * +__add_ovflpage(hashp, bufp) + HTAB *hashp; + BUFHEAD *bufp; +{ + __uint16_t *sp; + __uint16_t ndx, ovfl_num; +#ifdef DEBUG1 + int tmp1, tmp2; +#endif + sp = (__uint16_t *)bufp->page; + + /* Check if we are dynamically determining the fill factor */ + if (hashp->FFACTOR == DEF_FFACTOR) { + hashp->FFACTOR = sp[0] >> 1; + if (hashp->FFACTOR < MIN_FFACTOR) + hashp->FFACTOR = MIN_FFACTOR; + } + bufp->flags |= BUF_MOD; + ovfl_num = overflow_page(hashp); +#ifdef DEBUG1 + tmp1 = bufp->addr; + tmp2 = bufp->ovfl ? bufp->ovfl->addr : 0; +#endif + if (!ovfl_num || !(bufp->ovfl = __get_buf(hashp, ovfl_num, bufp, 1))) + return (NULL); + bufp->ovfl->flags |= BUF_MOD; +#ifdef DEBUG1 + (void)fprintf(stderr, "ADDOVFLPAGE: %d->ovfl was %d is now %d\n", + tmp1, tmp2, bufp->ovfl->addr); +#endif + ndx = sp[0]; + /* + * Since a pair is allocated on a page only if there's room to add + * an overflow page, we know that the OVFL information will fit on + * the page. + */ + sp[ndx + 4] = OFFSET(sp); + sp[ndx + 3] = FREESPACE(sp) - OVFLSIZE; + sp[ndx + 1] = ovfl_num; + sp[ndx + 2] = OVFLPAGE; + sp[0] = ndx + 2; +#ifdef HASH_STATISTICS + hash_overflows++; +#endif + return (bufp->ovfl); +} + +/* + * Returns: + * 0 indicates SUCCESS + * -1 indicates FAILURE + */ +extern int +__get_page(hashp, p, bucket, is_bucket, is_disk, is_bitmap) + HTAB *hashp; + char *p; + __uint32_t bucket; + int is_bucket, is_disk, is_bitmap; +{ + int fd, page, size; + int rsize; + __uint16_t *bp; + + fd = hashp->fp; + size = hashp->BSIZE; + + if ((fd == -1) || !is_disk) { + PAGE_INIT(p); + return (0); + } + if (is_bucket) + page = BUCKET_TO_PAGE(bucket); + else + page = OADDR_TO_PAGE(bucket); + if ((lseek(fd, (off_t)page << hashp->BSHIFT, SEEK_SET) == -1) || + ((rsize = read(fd, p, size)) == -1)) + return (-1); + bp = (__uint16_t *)p; + if (!rsize) + bp[0] = 0; /* We hit the EOF, so initialize a new page */ + else + if (rsize != size) { + errno = EFTYPE; + return (-1); + } + if (!is_bitmap && !bp[0]) { + PAGE_INIT(p); + } else + if (hashp->LORDER != BYTE_ORDER) { + int i, max; + + if (is_bitmap) { + max = hashp->BSIZE >> 2; /* divide by 4 */ + for (i = 0; i < max; i++) + M_32_SWAP(((int *)p)[i]); + } else { + M_16_SWAP(bp[0]); + max = bp[0] + 2; + for (i = 1; i <= max; i++) + M_16_SWAP(bp[i]); + } + } + return (0); +} + +/* + * Write page p to disk + * + * Returns: + * 0 ==> OK + * -1 ==>failure + */ +extern int +__put_page(hashp, p, bucket, is_bucket, is_bitmap) + HTAB *hashp; + char *p; + __uint32_t bucket; + int is_bucket, is_bitmap; +{ + int fd, page, size; + int wsize; + + size = hashp->BSIZE; + if ((hashp->fp == -1) && open_temp(hashp)) + return (-1); + fd = hashp->fp; + + if (hashp->LORDER != BYTE_ORDER) { + int i; + int max; + + if (is_bitmap) { + max = hashp->BSIZE >> 2; /* divide by 4 */ + for (i = 0; i < max; i++) + M_32_SWAP(((int *)p)[i]); + } else { + max = ((__uint16_t *)p)[0] + 2; + for (i = 0; i <= max; i++) + M_16_SWAP(((__uint16_t *)p)[i]); + } + } + if (is_bucket) + page = BUCKET_TO_PAGE(bucket); + else + page = OADDR_TO_PAGE(bucket); + if ((lseek(fd, (off_t)page << hashp->BSHIFT, SEEK_SET) == -1) || + ((wsize = write(fd, p, size)) == -1)) + /* Errno is set */ + return (-1); + if (wsize != size) { + errno = EFTYPE; + return (-1); + } + return (0); +} + +#define BYTE_MASK ((1 << INT_BYTE_SHIFT) -1) +/* + * Initialize a new bitmap page. Bitmap pages are left in memory + * once they are read in. + */ +extern int +__ibitmap(hashp, pnum, nbits, ndx) + HTAB *hashp; + int pnum, nbits, ndx; +{ + __uint32_t *ip; + int clearbytes, clearints; + + if ((ip = (__uint32_t *)malloc(hashp->BSIZE)) == NULL) + return (1); + hashp->nmaps++; + clearints = ((nbits - 1) >> INT_BYTE_SHIFT) + 1; + clearbytes = clearints << INT_TO_BYTE; + (void)memset((char *)ip, 0, clearbytes); + (void)memset(((char *)ip) + clearbytes, 0xFF, + hashp->BSIZE - clearbytes); + ip[clearints - 1] = ALL_SET << (nbits & BYTE_MASK); + SETBIT(ip, 0); + hashp->BITMAPS[ndx] = (__uint16_t)pnum; + hashp->mapp[ndx] = ip; + return (0); +} + +static __uint32_t +first_free(map) + __uint32_t map; +{ + __uint32_t i, mask; + + mask = 0x1; + for (i = 0; i < BITS_PER_MAP; i++) { + if (!(mask & map)) + return (i); + mask = mask << 1; + } + return (i); +} + +static __uint16_t +overflow_page(hashp) + HTAB *hashp; +{ + __uint32_t *freep; + int max_free, offset, splitnum; + __uint16_t addr; + int bit, first_page, free_bit, free_page, i, in_use_bits, j; +#ifdef DEBUG2 + int tmp1, tmp2; +#endif + splitnum = hashp->OVFL_POINT; + max_free = hashp->SPARES[splitnum]; + + free_page = (max_free - 1) >> (hashp->BSHIFT + BYTE_SHIFT); + free_bit = (max_free - 1) & ((hashp->BSIZE << BYTE_SHIFT) - 1); + + /* Look through all the free maps to find the first free block */ + first_page = hashp->LAST_FREED >>(hashp->BSHIFT + BYTE_SHIFT); + for ( i = first_page; i <= free_page; i++ ) { + if (!(freep = (__uint32_t *)hashp->mapp[i]) && + !(freep = fetch_bitmap(hashp, i))) + return (0); + if (i == free_page) + in_use_bits = free_bit; + else + in_use_bits = (hashp->BSIZE << BYTE_SHIFT) - 1; + + if (i == first_page) { + bit = hashp->LAST_FREED & + ((hashp->BSIZE << BYTE_SHIFT) - 1); + j = bit / BITS_PER_MAP; + bit = bit & ~(BITS_PER_MAP - 1); + } else { + bit = 0; + j = 0; + } + for (; bit <= in_use_bits; j++, bit += BITS_PER_MAP) + if (freep[j] != ALL_SET) + goto found; + } + + /* No Free Page Found */ + hashp->LAST_FREED = hashp->SPARES[splitnum]; + hashp->SPARES[splitnum]++; + offset = hashp->SPARES[splitnum] - + (splitnum ? hashp->SPARES[splitnum - 1] : 0); + +#define OVMSG "HASH: Out of overflow pages. Increase page size\n" + if (offset > SPLITMASK) { + if (++splitnum >= NCACHED) { + (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1); + return (0); + } + hashp->OVFL_POINT = splitnum; + hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1]; + hashp->SPARES[splitnum-1]--; + offset = 1; + } + + /* Check if we need to allocate a new bitmap page */ + if (free_bit == (hashp->BSIZE << BYTE_SHIFT) - 1) { + free_page++; + if (free_page >= NCACHED) { + (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1); + return (0); + } + /* + * This is tricky. The 1 indicates that you want the new page + * allocated with 1 clear bit. Actually, you are going to + * allocate 2 pages from this map. The first is going to be + * the map page, the second is the overflow page we were + * looking for. The init_bitmap routine automatically, sets + * the first bit of itself to indicate that the bitmap itself + * is in use. We would explicitly set the second bit, but + * don't have to if we tell init_bitmap not to leave it clear + * in the first place. + */ + if (__ibitmap(hashp, + (int)OADDR_OF(splitnum, offset), 1, free_page)) + return (0); + hashp->SPARES[splitnum]++; +#ifdef DEBUG2 + free_bit = 2; +#endif + offset++; + if (offset > SPLITMASK) { + if (++splitnum >= NCACHED) { + (void)write(STDERR_FILENO, OVMSG, + sizeof(OVMSG) - 1); + return (0); + } + hashp->OVFL_POINT = splitnum; + hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1]; + hashp->SPARES[splitnum-1]--; + offset = 0; + } + } else { + /* + * Free_bit addresses the last used bit. Bump it to address + * the first available bit. + */ + free_bit++; + SETBIT(freep, free_bit); + } + + /* Calculate address of the new overflow page */ + addr = OADDR_OF(splitnum, offset); +#ifdef DEBUG2 + (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n", + addr, free_bit, free_page); +#endif + return (addr); + +found: + bit = bit + first_free(freep[j]); + SETBIT(freep, bit); +#ifdef DEBUG2 + tmp1 = bit; + tmp2 = i; +#endif + /* + * Bits are addressed starting with 0, but overflow pages are addressed + * beginning at 1. Bit is a bit addressnumber, so we need to increment + * it to convert it to a page number. + */ + bit = 1 + bit + (i * (hashp->BSIZE << BYTE_SHIFT)); + if (bit >= hashp->LAST_FREED) + hashp->LAST_FREED = bit - 1; + + /* Calculate the split number for this page */ + for (i = 0; (i < splitnum) && (bit > hashp->SPARES[i]); i++); + offset = (i ? bit - hashp->SPARES[i - 1] : bit); + if (offset >= SPLITMASK) + return (0); /* Out of overflow pages */ + addr = OADDR_OF(i, offset); +#ifdef DEBUG2 + (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n", + addr, tmp1, tmp2); +#endif + + /* Allocate and return the overflow page */ + return (addr); +} + +/* + * Mark this overflow page as free. + */ +extern void +__free_ovflpage(hashp, obufp) + HTAB *hashp; + BUFHEAD *obufp; +{ + __uint16_t addr; + __uint32_t *freep; + int bit_address, free_page, free_bit; + __uint16_t ndx; + + addr = obufp->addr; +#ifdef DEBUG1 + (void)fprintf(stderr, "Freeing %d\n", addr); +#endif + ndx = (((__uint16_t)addr) >> SPLITSHIFT); + bit_address = + (ndx ? hashp->SPARES[ndx - 1] : 0) + (addr & SPLITMASK) - 1; + if (bit_address < hashp->LAST_FREED) + hashp->LAST_FREED = bit_address; + free_page = (bit_address >> (hashp->BSHIFT + BYTE_SHIFT)); + free_bit = bit_address & ((hashp->BSIZE << BYTE_SHIFT) - 1); + + if (!(freep = hashp->mapp[free_page])) + freep = fetch_bitmap(hashp, free_page); +#ifdef DEBUG + /* + * This had better never happen. It means we tried to read a bitmap + * that has already had overflow pages allocated off it, and we + * failed to read it from the file. + */ + if (!freep) + assert(0); +#endif + CLRBIT(freep, free_bit); +#ifdef DEBUG2 + (void)fprintf(stderr, "FREE_OVFLPAGE: ADDR: %d BIT: %d PAGE %d\n", + obufp->addr, free_bit, free_page); +#endif + __reclaim_buf(hashp, obufp); +} + +/* + * Returns: + * 0 success + * -1 failure + */ +static int +open_temp(hashp) + HTAB *hashp; +{ + sigset_t set, oset; + static char namestr[] = "_hashXXXXXX"; + + /* Block signals; make sure file goes away at process exit. */ + (void)sigfillset(&set); + (void)sigprocmask(SIG_BLOCK, &set, &oset); + if ((hashp->fp = mkstemp(namestr)) != -1) { + (void)unlink(namestr); + (void)fcntl(hashp->fp, F_SETFD, 1); + } + (void)sigprocmask(SIG_SETMASK, &oset, (sigset_t *)NULL); + return (hashp->fp != -1 ? 0 : -1); +} + +/* + * We have to know that the key will fit, but the last entry on the page is + * an overflow pair, so we need to shift things. + */ +static void +squeeze_key(sp, key, val) + __uint16_t *sp; + const DBT *key, *val; +{ + char *p; + __uint16_t free_space, n, off, pageno; + + p = (char *)sp; + n = sp[0]; + free_space = FREESPACE(sp); + off = OFFSET(sp); + + pageno = sp[n - 1]; + off -= key->size; + sp[n - 1] = off; + memmove(p + off, key->data, key->size); + off -= val->size; + sp[n] = off; + memmove(p + off, val->data, val->size); + sp[0] = n + 2; + sp[n + 1] = pageno; + sp[n + 2] = OVFLPAGE; + FREESPACE(sp) = free_space - PAIRSIZE(key, val); + OFFSET(sp) = off; +} + +static __uint32_t * +fetch_bitmap(hashp, ndx) + HTAB *hashp; + int ndx; +{ + if (ndx >= hashp->nmaps) + return (NULL); + if ((hashp->mapp[ndx] = (__uint32_t *)malloc(hashp->BSIZE)) == NULL) + return (NULL); + if (__get_page(hashp, + (char *)hashp->mapp[ndx], hashp->BITMAPS[ndx], 0, 1, 1)) { + free(hashp->mapp[ndx]); + return (NULL); + } + return (hashp->mapp[ndx]); +} + +#ifdef DEBUG4 +int +print_chain(addr) + int addr; +{ + BUFHEAD *bufp; + short *bp, oaddr; + + (void)fprintf(stderr, "%d ", addr); + bufp = __get_buf(hashp, addr, NULL, 0); + bp = (short *)bufp->page; + while (bp[0] && ((bp[bp[0]] == OVFLPAGE) || + ((bp[0] > 2) && bp[2] < REAL_KEY))) { + oaddr = bp[bp[0] - 1]; + (void)fprintf(stderr, "%d ", (int)oaddr); + bufp = __get_buf(hashp, (int)oaddr, bufp, 0); + bp = (short *)bufp->page; + } + (void)fprintf(stderr, "\n"); +} +#endif diff --git a/newlib/libc/search/hcreate.3 b/newlib/libc/search/hcreate.3 new file mode 100644 index 000000000..1619c9892 --- /dev/null +++ b/newlib/libc/search/hcreate.3 @@ -0,0 +1,206 @@ +.\" $FreeBSD: src/lib/libc/stdlib/hcreate.3,v 1.2 2001/07/09 15:54:36 ru Exp $ +.\" +.Dd May 8, 2001 +.Os +.Dt HCREATE 3 +.Sh NAME +.Nm hcreate , hdestroy , hsearch +.Nd manage hash search table +.Sh LIBRARY +.Lb libc +.Sh SYNOPSIS +.In search.h +.Ft int +.Fn hcreate "size_t nel" +.Ft void +.Fn hdestroy void +.Ft ENTRY * +.Fn hsearch "ENTRY item" "ACTION action" +.Sh DESCRIPTION +The +.Fn hcreate , +.Fn hdestroy , +and +.Fn hsearch +functions manage hash search tables. +.Pp +The +.Fn hcreate +function allocates sufficient space for the table, and the application should +ensure it is called before +.Fn hsearch +is used. +The +.Fa nel +argument is an estimate of the maximum +number of entries that the table should contain. +This number may be adjusted upward by the +algorithm in order to obtain certain mathematically favorable circumstances. +.Pp +The +.Fn hdestroy +function disposes of the search table, and may be followed by another call to +.Fn hcreate . +After the call to +.Fn hdestroy , +the data can no longer be considered accessible. +.Pp +The +.Fn hsearch +function is a hash-table search routine. +It returns a pointer into a hash table +indicating the location at which an entry can be found. +The +.Fa item +argument is a structure of type +.Vt ENTRY +(defined in the +.Aq Pa search.h +header) containing two pointers: +.Fa item.key +points to the comparison key (a +.Vt "char *" ) , +and +.Fa item.data +(a +.Vt "void *" ) +points to any other data to be associated with +that key. +The comparison function used by +.Fn hsearch +is +.Xr strcmp 3 . +The +.Fa action +argument is a +member of an enumeration type +.Vt ACTION +indicating the disposition of the entry if it cannot be +found in the table. +.Dv ENTER +indicates that the +.Fa item +should be inserted in the table at an +appropriate point. +.Dv FIND +indicates that no entry should be made. +Unsuccessful resolution is +indicated by the return of a +.Dv NULL +pointer. +.Sh RETURN VALUES +The +.Fn hcreate +function returns 0 if it cannot allocate sufficient space for the table; +otherwise, it returns non-zero. +.Pp +The +.Fn hdestroy +function does not return a value. +.Pp +The +.Fn hsearch +function returns a +.Dv NULL +pointer if either the +.Fa action +is +.Dv FIND +and the +.Fa item +could not be found or the +.Fa action +is +.Dv ENTER +and the table is full. +.Sh ERRORS +The +.Fn hcreate +and +.Fn hsearch +functions may fail if: +.Bl -tag -width Er +.It Bq Er ENOMEM +Insufficient storage space is available. +.El +.Sh EXAMPLES +The following example reads in strings followed by two numbers +and stores them in a hash table, discarding duplicates. +It then reads in strings and finds the matching entry in the hash +table and prints it out. +.Bd -literal +#include <stdio.h> +#include <search.h> +#include <string.h> + +struct info { /* This is the info stored in the table */ + int age, room; /* other than the key. */ +}; + +#define NUM_EMPL 5000 /* # of elements in search table. */ + +int +main(void) +{ + char string_space[NUM_EMPL*20]; /* Space to store strings. */ + struct info info_space[NUM_EMPL]; /* Space to store employee info. */ + char *str_ptr = string_space; /* Next space in string_space. */ + struct info *info_ptr = info_space; /* Next space in info_space. */ + ENTRY item; + ENTRY *found_item; /* Name to look for in table. */ + char name_to_find[30]; + int i = 0; + + /* Create table; no error checking is performed. */ + (void) hcreate(NUM_EMPL); + + while (scanf("%s%d%d", str_ptr, &info_ptr->age, + &info_ptr->room) != EOF && i++ < NUM_EMPL) { + /* Put information in structure, and structure in item. */ + item.key = str_ptr; + item.data = info_ptr; + str_ptr += strlen(str_ptr) + 1; + info_ptr++; + /* Put item into table. */ + (void) hsearch(item, ENTER); + } + + /* Access table. */ + item.key = name_to_find; + while (scanf("%s", item.key) != EOF) { + if ((found_item = hsearch(item, FIND)) != NULL) { + /* If item is in the table. */ + (void)printf("found %s, age = %d, room = %d\en", + found_item->key, + ((struct info *)found_item->data)->age, + ((struct info *)found_item->data)->room); + } else + (void)printf("no such employee %s\en", name_to_find); + } + return 0; +} +.Ed +.Sh SEE ALSO +.Xr bsearch 3 , +.Xr lsearch 3 , +.Xr malloc 3 , +.Xr strcmp 3 , +.Xr tsearch 3 +.Sh STANDARDS +The +.Fn hcreate , +.Fn hdestroy , +and +.Fn hsearch +functions conform to +.St -xpg4.2 . +.Sh HISTORY +The +.Fn hcreate , +.Fn hdestroy , +and +.Fn hsearch +functions first appeared in +.At V . +.Sh BUGS +The interface permits the use of only one hash table at a time. diff --git a/newlib/libc/search/hcreate.c b/newlib/libc/search/hcreate.c new file mode 100644 index 000000000..84fc92808 --- /dev/null +++ b/newlib/libc/search/hcreate.c @@ -0,0 +1,85 @@ +/* $NetBSD: hcreate.c,v 1.2 2001/02/19 21:26:04 ross Exp $ */ + +/* + * Copyright (c) 2001 Christopher G. Demetriou + * All rights reserved. + * + * 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. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed for the + * NetBSD Project. See http://www.netbsd.org/ for + * information about NetBSD. + * 4. The name of the author may not 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. + * + * <<Id: LICENSE,v 1.2 2000/06/14 15:57:33 cgd Exp>> + */ + +/* + * hcreate() / hsearch() / hdestroy() + * + * SysV/XPG4 hash table functions. + * + * Implementation done based on NetBSD manual page and Solaris manual page, + * plus my own personal experience about how they're supposed to work. + * + * I tried to look at Knuth (as cited by the Solaris manual page), but + * nobody had a copy in the office, so... + */ + +#include <sys/cdefs.h> +#if 0 +#if defined(LIBC_SCCS) && !defined(lint) +__RCSID("$NetBSD: hcreate.c,v 1.2 2001/02/19 21:26:04 ross Exp $"); +#endif /* LIBC_SCCS and not lint */ +#endif + +#include <sys/types.h> +#include <sys/queue.h> +#include <errno.h> +#include <search.h> +#include <stdlib.h> +#include <string.h> + +static struct hsearch_data htab; + +int +hcreate(size_t nel) +{ + return hcreate_r (nel, &htab); +} + +void +hdestroy(void) +{ + hdestroy_r (&htab); +} + +ENTRY * +hsearch(ENTRY item, ACTION action) +{ + ENTRY *retval; + + hsearch_r (item, action, &retval, &htab); + + return retval; +} diff --git a/newlib/libc/search/hcreate_r.c b/newlib/libc/search/hcreate_r.c new file mode 100644 index 000000000..a24f4e74c --- /dev/null +++ b/newlib/libc/search/hcreate_r.c @@ -0,0 +1,193 @@ +/* $NetBSD: hcreate.c,v 1.2 2001/02/19 21:26:04 ross Exp $ */ + +/* + * Copyright (c) 2001 Christopher G. Demetriou + * All rights reserved. + * + * 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. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed for the + * NetBSD Project. See http://www.netbsd.org/ for + * information about NetBSD. + * 4. The name of the author may not 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. + * + * <<Id: LICENSE,v 1.2 2000/06/14 15:57:33 cgd Exp>> + */ + +/* + * hcreate() / hsearch() / hdestroy() + * + * SysV/XPG4 hash table functions. + * + * Implementation done based on NetBSD manual page and Solaris manual page, + * plus my own personal experience about how they're supposed to work. + * + * I tried to look at Knuth (as cited by the Solaris manual page), but + * nobody had a copy in the office, so... + */ + +#include <sys/cdefs.h> +#if 0 +#if defined(LIBC_SCCS) && !defined(lint) +__RCSID("$NetBSD: hcreate.c,v 1.2 2001/02/19 21:26:04 ross Exp $"); +#endif /* LIBC_SCCS and not lint */ +#endif + +#include <sys/types.h> +#include <sys/queue.h> +#include <errno.h> +#include <search.h> +#include <stdlib.h> +#include <string.h> + +/* + * DO NOT MAKE THIS STRUCTURE LARGER THAN 32 BYTES (4 ptrs on 64-bit + * ptr machine) without adjusting MAX_BUCKETS_LG2 below. + */ +struct internal_entry { + SLIST_ENTRY(internal_entry) link; + ENTRY ent; +}; +SLIST_HEAD(internal_head, internal_entry); + +#define MIN_BUCKETS_LG2 4 +#define MIN_BUCKETS (1 << MIN_BUCKETS_LG2) + +/* + * max * sizeof internal_entry must fit into size_t. + * assumes internal_entry is <= 32 (2^5) bytes. + */ +#define MAX_BUCKETS_LG2 (sizeof (size_t) * 8 - 1 - 5) +#define MAX_BUCKETS ((size_t)1 << MAX_BUCKETS_LG2) + +/* Default hash function, from db/hash/hash_func.c */ +extern __uint32_t (*__default_hash)(const void *, size_t); + +int +hcreate_r(size_t nel, struct hsearch_data *htab) +{ + size_t idx; + unsigned int p2; + + /* Make sure this this isn't called when a table already exists. */ + if (htab->htable != NULL) { + errno = EINVAL; + return 0; + } + + /* If nel is too small, make it min sized. */ + if (nel < MIN_BUCKETS) + nel = MIN_BUCKETS; + + /* If it's too large, cap it. */ + if (nel > MAX_BUCKETS) + nel = MAX_BUCKETS; + + /* If it's is not a power of two in size, round up. */ + if ((nel & (nel - 1)) != 0) { + for (p2 = 0; nel != 0; p2++) + nel >>= 1; + nel = 1 << p2; + } + + /* Allocate the table. */ + htab->htablesize = nel; + htab->htable = malloc(htab->htablesize * sizeof htab->htable[0]); + if (htab->htable == NULL) { + errno = ENOMEM; + return 0; + } + + /* Initialize it. */ + for (idx = 0; idx < htab->htablesize; idx++) + SLIST_INIT(&(htab->htable[idx])); + + return 1; +} + +void +hdestroy_r(struct hsearch_data *htab) +{ + struct internal_entry *ie; + size_t idx; + + if (htab->htable == NULL) + return; + +#if 0 + for (idx = 0; idx < htab->htablesize; idx++) { + while (!SLIST_EMPTY(&(htab->htable[idx]))) { + ie = SLIST_FIRST(&(htab->htable[idx])); + SLIST_REMOVE_HEAD(&(htab->htable[idx]), link); + free(ie->ent.key); + free(ie); + } + } +#endif + free(htab->htable); + htab->htable = NULL; +} + +int +hsearch_r(ENTRY item, ACTION action, ENTRY **retval, struct hsearch_data *htab) +{ + struct internal_head *head; + struct internal_entry *ie; + __uint32_t hashval; + size_t len; + + len = strlen(item.key); + hashval = (*__default_hash)(item.key, len); + + head = &(htab->htable[hashval & (htab->htablesize - 1)]); + ie = SLIST_FIRST(head); + while (ie != NULL) { + if (strcmp(ie->ent.key, item.key) == 0) + break; + ie = SLIST_NEXT(ie, link); + } + + if (ie != NULL) + { + *retval = &ie->ent; + return 1; + } + else if (action == FIND) + { + *retval = NULL; + return 0; + } + + ie = malloc(sizeof *ie); + if (ie == NULL) + { + *retval = NULL; + return 0; + } + ie->ent.key = item.key; + ie->ent.data = item.data; + + SLIST_INSERT_HEAD(head, ie, link); + *retval = &ie->ent; + return 1; +} diff --git a/newlib/libc/search/ndbm.c b/newlib/libc/search/ndbm.c new file mode 100644 index 000000000..a29c958f7 --- /dev/null +++ b/newlib/libc/search/ndbm.c @@ -0,0 +1,232 @@ +/*- + * Copyright (c) 1990, 1993 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Margo Seltzer. + * + * 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. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed by the University of + * California, Berkeley and its contributors. + * 4. 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. + */ + +#include <sys/unistd.h> + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)ndbm.c 8.4 (Berkeley) 7/21/94"; +#endif /* LIBC_SCCS and not lint */ +#include <sys/cdefs.h> + +/* + * This package provides a dbm compatible interface to the new hashing + * package described in db(3). + */ + +#include <sys/param.h> + +#include <stdio.h> +#include <string.h> +#include <errno.h> + +#include <ndbm.h> +#include "hash.h" + +/* + * Returns: + * *DBM on success + * NULL on failure + */ +extern DBM * +dbm_open(file, flags, mode) + const char *file; + int flags, mode; +{ + HASHINFO info; + char path[MAXPATHLEN]; + + info.bsize = 4096; + info.ffactor = 40; + info.nelem = 1; + info.cachesize = 0; + info.hash = NULL; + info.lorder = 0; + + if( strlen(file) >= sizeof(path) - strlen(DBM_SUFFIX)) { + errno = ENAMETOOLONG; + return(NULL); + } + (void)strcpy(path, file); + (void)strcat(path, DBM_SUFFIX); + return ((DBM *)__hash_open(path, flags, mode, &info, 0)); +} + +extern void +dbm_close(db) + DBM *db; +{ + (void)(db->close)(db); +} + +/* + * Returns: + * DATUM on success + * NULL on failure + */ +extern datum +dbm_fetch(db, key) + DBM *db; + datum key; +{ + datum retdata; + int status; + DBT dbtkey, dbtretdata; + + dbtkey.data = key.dptr; + dbtkey.size = key.dsize; + status = (db->get)(db, &dbtkey, &dbtretdata, 0); + if (status) { + dbtretdata.data = NULL; + dbtretdata.size = 0; + } + retdata.dptr = dbtretdata.data; + retdata.dsize = dbtretdata.size; + return (retdata); +} + +/* + * Returns: + * DATUM on success + * NULL on failure + */ +extern datum +dbm_firstkey(db) + DBM *db; +{ + int status; + datum retkey; + DBT dbtretkey, dbtretdata; + + status = (db->seq)(db, &dbtretkey, &dbtretdata, R_FIRST); + if (status) + dbtretkey.data = NULL; + retkey.dptr = dbtretkey.data; + retkey.dsize = dbtretkey.size; + return (retkey); +} + +/* + * Returns: + * DATUM on success + * NULL on failure + */ +extern datum +dbm_nextkey(db) + DBM *db; +{ + int status; + datum retkey; + DBT dbtretkey, dbtretdata; + + status = (db->seq)(db, &dbtretkey, &dbtretdata, R_NEXT); + if (status) + dbtretkey.data = NULL; + retkey.dptr = dbtretkey.data; + retkey.dsize = dbtretkey.size; + return (retkey); +} + +/* + * Returns: + * 0 on success + * <0 failure + */ +extern int +dbm_delete(db, key) + DBM *db; + datum key; +{ + int status; + DBT dbtkey; + + dbtkey.data = key.dptr; + dbtkey.size = key.dsize; + status = (db->del)(db, &dbtkey, 0); + if (status) + return (-1); + else + return (0); +} + +/* + * Returns: + * 0 on success + * <0 failure + * 1 if DBM_INSERT and entry exists + */ +extern int +dbm_store(db, key, data, flags) + DBM *db; + datum key, data; + int flags; +{ + DBT dbtkey, dbtdata; + + dbtkey.data = key.dptr; + dbtkey.size = key.dsize; + dbtdata.data = data.dptr; + dbtdata.size = data.dsize; + return ((db->put)(db, &dbtkey, &dbtdata, + (flags == DBM_INSERT) ? R_NOOVERWRITE : 0)); +} + +extern int +dbm_error(db) + DBM *db; +{ + HTAB *hp; + + hp = (HTAB *)db->internal; + return (hp->error); +} + +extern int +dbm_clearerr(db) + DBM *db; +{ + HTAB *hp; + + hp = (HTAB *)db->internal; + hp->error = 0; + return (0); +} + +extern int +dbm_dirfno(db) + DBM *db; +{ + return(((HTAB *)db->internal)->fp); +} diff --git a/newlib/libc/search/page.h b/newlib/libc/search/page.h new file mode 100644 index 000000000..9ecabdacd --- /dev/null +++ b/newlib/libc/search/page.h @@ -0,0 +1,93 @@ +/*- + * Copyright (c) 1990, 1993, 1994 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Margo Seltzer. + * + * 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. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed by the University of + * California, Berkeley and its contributors. + * 4. 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. + * + * @(#)page.h 8.2 (Berkeley) 5/31/94 + * $FreeBSD: src/lib/libc/db/hash/page.h,v 1.2 2002/03/22 23:41:40 obrien Exp $ + */ + +/* + * Definitions for hashing page file format. + */ + +/* + * routines dealing with a data page + * + * page format: + * +------------------------------+ + * p | n | keyoff | datoff | keyoff | + * +------------+--------+--------+ + * | datoff | free | ptr | --> | + * +--------+---------------------+ + * | F R E E A R E A | + * +--------------+---------------+ + * | <---- - - - | data | + * +--------+-----+----+----------+ + * | key | data | key | + * +--------+----------+----------+ + * + * Pointer to the free space is always: p[p[0] + 2] + * Amount of free space on the page is: p[p[0] + 1] + */ + +/* + * How many bytes required for this pair? + * 2 shorts in the table at the top of the page + room for the + * key and room for the data + * + * We prohibit entering a pair on a page unless there is also room to append + * an overflow page. The reason for this it that you can get in a situation + * where a single key/data pair fits on a page, but you can't append an + * overflow page and later you'd have to split the key/data and handle like + * a big pair. + * You might as well do this up front. + */ + +#define PAIRSIZE(K,D) (2*sizeof(__uint16_t) + (K)->size + (D)->size) +#define BIGOVERHEAD (4*sizeof(__uint16_t)) +#define KEYSIZE(K) (4*sizeof(__uint16_t) + (K)->size); +#define OVFLSIZE (2*sizeof(__uint16_t)) +#define FREESPACE(P) ((P)[(P)[0]+1]) +#define OFFSET(P) ((P)[(P)[0]+2]) +#define PAIRFITS(P,K,D) \ + (((P)[2] >= REAL_KEY) && \ + (PAIRSIZE((K),(D)) + OVFLSIZE) <= FREESPACE((P))) +#define PAGE_META(N) (((N)+3) * sizeof(__uint16_t)) + +typedef struct { + BUFHEAD *newp; + BUFHEAD *oldp; + BUFHEAD *nextp; + __uint16_t next_addr; +} SPLIT_RETURN; diff --git a/newlib/libc/search/qsort.c b/newlib/libc/search/qsort.c new file mode 100644 index 000000000..d47f47099 --- /dev/null +++ b/newlib/libc/search/qsort.c @@ -0,0 +1,222 @@ +/* +FUNCTION +<<qsort>>---sort an array + +INDEX + qsort + +ANSI_SYNOPSIS + #include <stdlib.h> + void qsort(void *<[base]>, size_t <[nmemb]>, size_t <[size]>, + int (*<[compar]>)(const void *, const void *) ); + +TRAD_SYNOPSIS + #include <stdlib.h> + qsort(<[base]>, <[nmemb]>, <[size]>, <[compar]> ) + char *<[base]>; + size_t <[nmemb]>; + size_t <[size]>; + int (*<[compar]>)(); + +DESCRIPTION +<<qsort>> sorts an array (beginning at <[base]>) of <[nmemb]> objects. +<[size]> describes the size of each element of the array. + +You must supply a pointer to a comparison function, using the argument +shown as <[compar]>. (This permits sorting objects of unknown +properties.) Define the comparison function to accept two arguments, +each a pointer to an element of the array starting at <[base]>. The +result of <<(*<[compar]>)>> must be negative if the first argument is +less than the second, zero if the two arguments match, and positive if +the first argument is greater than the second (where ``less than'' and +``greater than'' refer to whatever arbitrary ordering is appropriate). + +The array is sorted in place; that is, when <<qsort>> returns, the +array elements beginning at <[base]> have been reordered. + +RETURNS +<<qsort>> does not return a result. + +PORTABILITY +<<qsort>> is required by ANSI (without specifying the sorting algorithm). +*/ + +/*- + * Copyright (c) 1992, 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 + * 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. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed by the University of + * California, Berkeley and its contributors. + * 4. 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. + */ + +#include <_ansi.h> +#include <stdlib.h> + +#ifndef __GNUC__ +#define inline +#endif + +static inline char *med3 _PARAMS((char *, char *, char *, int (*)())); +static inline void swapfunc _PARAMS((char *, char *, int, int)); + +#define min(a, b) (a) < (b) ? a : b + +/* + * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function". + */ +#define swapcode(TYPE, parmi, parmj, n) { \ + long i = (n) / sizeof (TYPE); \ + register TYPE *pi = (TYPE *) (parmi); \ + register TYPE *pj = (TYPE *) (parmj); \ + do { \ + register TYPE t = *pi; \ + *pi++ = *pj; \ + *pj++ = t; \ + } while (--i > 0); \ +} + +#define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \ + es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1; + +static inline void +_DEFUN(swapfunc, (a, b, n, swaptype), + char *a _AND + char *b _AND + int n _AND + int swaptype) +{ + if(swaptype <= 1) + swapcode(long, a, b, n) + else + swapcode(char, a, b, n) +} + +#define swap(a, b) \ + if (swaptype == 0) { \ + long t = *(long *)(a); \ + *(long *)(a) = *(long *)(b); \ + *(long *)(b) = t; \ + } else \ + swapfunc(a, b, es, swaptype) + +#define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype) + +static inline char * +_DEFUN(med3, (a, b, c, cmp), + char *a _AND + char *b _AND + char *c _AND + int (*cmp)()) +{ + return cmp(a, b) < 0 ? + (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a )) + :(cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c )); +} + +void +_DEFUN(qsort, (a, n, es, cmp), + void *a _AND + size_t n _AND + size_t es _AND + int (*cmp)()) +{ + char *pa, *pb, *pc, *pd, *pl, *pm, *pn; + int d, r, swaptype, swap_cnt; + +loop: SWAPINIT(a, es); + swap_cnt = 0; + if (n < 7) { + for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es) + for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0; + pl -= es) + swap(pl, pl - es); + return; + } + pm = (char *) a + (n / 2) * es; + if (n > 7) { + pl = a; + pn = (char *) a + (n - 1) * es; + if (n > 40) { + d = (n / 8) * es; + pl = med3(pl, pl + d, pl + 2 * d, cmp); + pm = med3(pm - d, pm, pm + d, cmp); + pn = med3(pn - 2 * d, pn - d, pn, cmp); + } + pm = med3(pl, pm, pn, cmp); + } + swap(a, pm); + pa = pb = (char *) a + es; + + pc = pd = (char *) a + (n - 1) * es; + for (;;) { + while (pb <= pc && (r = cmp(pb, a)) <= 0) { + if (r == 0) { + swap_cnt = 1; + swap(pa, pb); + pa += es; + } + pb += es; + } + while (pb <= pc && (r = cmp(pc, a)) >= 0) { + if (r == 0) { + swap_cnt = 1; + swap(pc, pd); + pd -= es; + } + pc -= es; + } + if (pb > pc) + break; + swap(pb, pc); + swap_cnt = 1; + pb += es; + pc -= es; + } + if (swap_cnt == 0) { /* Switch to insertion sort */ + for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es) + for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0; + pl -= es) + swap(pl, pl - es); + return; + } + + pn = (char *) a + n * es; + r = min(pa - (char *)a, pb - pa); + vecswap(a, pb - r, r); + r = min(pd - pc, pn - pd - es); + vecswap(pb, pn - r, r); + if ((r = pb - pa) > es) + qsort(a, r / es, es, cmp); + if ((r = pd - pc) > es) { + /* Iterate rather than recurse to save stack space */ + a = pn - r; + n = r / es; + goto loop; + } +/* qsort(pn - r, r / es, es, cmp);*/ +} diff --git a/newlib/libc/search/tdelete.c b/newlib/libc/search/tdelete.c new file mode 100644 index 000000000..e849ada81 --- /dev/null +++ b/newlib/libc/search/tdelete.c @@ -0,0 +1,67 @@ +/* $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 + +#include <assert.h> +#define _SEARCH_PRIVATE +#include <search.h> +#include <stdlib.h> + + +/* delete node with given key */ +void * +tdelete(vkey, vrootp, compar) + const void *vkey; /* key to be deleted */ + void **vrootp; /* address of the root of tree */ + 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/newlib/libc/search/tdestroy.c b/newlib/libc/search/tdestroy.c new file mode 100644 index 000000000..2f8aae695 --- /dev/null +++ b/newlib/libc/search/tdestroy.c @@ -0,0 +1,49 @@ +/* $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 + +#include <assert.h> +#define _SEARCH_PRIVATE +#include <search.h> +#include <stdlib.h> + + +/* Walk the nodes of a tree */ +static void +trecurse(root, free_action) + node_t *root; /* Root of the tree to be walked */ + void (*free_action)(void *); +{ + if (root->llink != NULL) + trecurse(root->llink, free_action); + if (root->rlink != NULL) + trecurse(root->rlink, free_action); + + (*free_action) ((void *) root->key); + free(root); +} + +void +tdestroy (void *vrootp, void (*freefct)(void *)) +{ + node_t *root = (node_t *) vrootp; + + if (root != NULL) + trecurse(root, freefct); +} diff --git a/newlib/libc/search/tfind.c b/newlib/libc/search/tfind.c new file mode 100644 index 000000000..36c90a1cd --- /dev/null +++ b/newlib/libc/search/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 + +#include <assert.h> +#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 **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/newlib/libc/search/tsearch.3 b/newlib/libc/search/tsearch.3 new file mode 100644 index 000000000..a36fe894f --- /dev/null +++ b/newlib/libc/search/tsearch.3 @@ -0,0 +1,118 @@ +.\" $NetBSD$ +.\" Copyright (c) 1997 Todd C. Miller <Todd.Miller@courtesan.com> +.\" All rights reserved. +.\" +.\" 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. The name of the author may not be used to endorse or promote products +.\" derived from this software without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED ``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. +.\" +.\" OpenBSD: tsearch.3,v 1.2 1998/06/21 22:13:49 millert Exp +.\" $FreeBSD: src/lib/libc/stdlib/tsearch.3,v 1.7 2001/09/07 14:46:36 asmodai Exp $ +.\" +.Dd June 15, 1997 +.Dt TSEARCH 3 +.Os +.Sh NAME +.Nm tsearch , tfind , tdelete , twalk +.Nd manipulate binary search trees +.Sh SYNOPSIS +.In search.h +.Ft void * +.Fn tdelete "const void *key" "void **rootp" "int (*compar) (const void *, const void *)" +.Ft void * +.Fn tfind "const void *key" "void **rootp" "int (*compar) (const void *, const void *)" +.Ft void * +.Fn tsearch "const void *key" "void **rootp" "int (*compar) (const void *, const void *)" +.Ft void +.Fn twalk "const void *root" "void (*compar) (const void *, VISIT, int)" +.Sh DESCRIPTION +The +.Fn tdelete , +.Fn tfind , +.Fn tsearch , +and +.Fn twalk +functions manage binary search trees based on algorithms T and D +from Knuth (6.2.2). The comparison function passed in by +the user has the same style of return values as +.Xr strcmp 3 . +.Pp +.Fn Tfind +searches for the datum matched by the argument +.Fa key +in the binary tree rooted at +.Fa rootp , +returning a pointer to the datum if it is found and NULL +if it is not. +.Pp +.Fn Tsearch +is identical to +.Fn tfind +except that if no match is found, +.Fa key +is inserted into the tree and a pointer to it is returned. If +.Fa rootp +points to a NULL value a new binary search tree is created. +.Pp +.Fn Tdelete +deletes a node from the specified binary search tree and returns +a pointer to the parent of the node to be deleted. +It takes the same arguments as +.Fn tfind +and +.Fn tsearch . +If the node to be deleted is the root of the binary search tree, +.Fa rootp +will be adjusted. +.Pp +.Fn Twalk +walks the binary search tree rooted in +.Fa root +and calls the function +.Fa action +on each node. +.Fa Action +is called with three arguments: a pointer to the current node, +a value from the enum +.Sy "typedef enum { preorder, postorder, endorder, leaf } VISIT;" +specifying the traversal type, and a node level (where level +zero is the root of the tree). +.Sh SEE ALSO +.Xr bsearch 3 , +.Xr hsearch 3 , +.Xr lsearch 3 +.Sh RETURN VALUES +The +.Fn tsearch +function returns NULL if allocation of a new node fails (usually +due to a lack of free memory). +.Pp +.Fn Tfind , +.Fn tsearch , +and +.Fn tdelete +return NULL if +.Fa rootp +is NULL or the datum cannot be found. +.Pp +The +.Fn twalk +function returns no value. diff --git a/newlib/libc/search/tsearch.c b/newlib/libc/search/tsearch.c new file mode 100644 index 000000000..cda16992e --- /dev/null +++ b/newlib/libc/search/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 + +#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 *); +{ + 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; +} diff --git a/newlib/libc/search/twalk.c b/newlib/libc/search/twalk.c new file mode 100644 index 000000000..020e5d5ea --- /dev/null +++ b/newlib/libc/search/twalk.c @@ -0,0 +1,58 @@ +/* $NetBSD: twalk.c,v 1.1 1999/02/22 10:33:16 christos 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: twalk.c,v 1.1 1999/02/22 10:33:16 christos Exp $"); +#endif /* LIBC_SCCS and not lint */ +#endif + +#include <assert.h> +#define _SEARCH_PRIVATE +#include <search.h> +#include <stdlib.h> + +static void trecurse(const node_t *, + void (*action)(const void *, VISIT, int), int level); + +/* Walk the nodes of a tree */ +static void +trecurse(root, action, level) + const node_t *root; /* Root of the tree to be walked */ + void (*action)(const void *, VISIT, int); + int level; +{ + + if (root->llink == NULL && root->rlink == NULL) + (*action)(root, leaf, level); + else { + (*action)(root, preorder, level); + if (root->llink != NULL) + trecurse(root->llink, action, level + 1); + (*action)(root, postorder, level); + if (root->rlink != NULL) + trecurse(root->rlink, action, level + 1); + (*action)(root, endorder, level); + } +} + +/* Walk the nodes of a tree */ +void +twalk(vroot, action) + const void *vroot; /* Root of the tree to be walked */ + void (*action)(const void *, VISIT, int); +{ + if (vroot != NULL && action != NULL) + trecurse(vroot, action, 0); +} diff --git a/newlib/libc/stdlib/Makefile.am b/newlib/libc/stdlib/Makefile.am index 2f4166ceb..574ac2ab6 100644 --- a/newlib/libc/stdlib/Makefile.am +++ b/newlib/libc/stdlib/Makefile.am @@ -18,7 +18,6 @@ LIB_SOURCES = \ atoff.c \ atoi.c \ atol.c \ - bsearch.c \ calloc.c \ div.c \ drand48.c \ @@ -59,7 +58,6 @@ LIB_SOURCES = \ on_exit.c \ putenv.c \ putenv_r.c \ - qsort.c \ rand.c \ rand48.c \ rand_r.c \ @@ -154,7 +152,6 @@ CHEWOUT_FILES= \ atof.def \ ecvtbuf.def \ atoi.def \ - bsearch.def \ calloc.def \ div.def \ efgcvt.def \ @@ -171,7 +168,6 @@ CHEWOUT_FILES= \ mlock.def \ mstats.def \ on_exit.def \ - qsort.def \ rand.def \ rand48.def \ strtod.def \ diff --git a/newlib/libc/stdlib/Makefile.in b/newlib/libc/stdlib/Makefile.in index 82e912c2a..bdadd2961 100644 --- a/newlib/libc/stdlib/Makefile.in +++ b/newlib/libc/stdlib/Makefile.in @@ -122,7 +122,6 @@ LIB_SOURCES = \ atoff.c \ atoi.c \ atol.c \ - bsearch.c \ calloc.c \ div.c \ drand48.c \ @@ -163,7 +162,6 @@ LIB_SOURCES = \ on_exit.c \ putenv.c \ putenv_r.c \ - qsort.c \ rand.c \ rand48.c \ rand_r.c \ @@ -219,7 +217,6 @@ CHEWOUT_FILES = \ atof.def \ ecvtbuf.def \ atoi.def \ - bsearch.def \ calloc.def \ div.def \ efgcvt.def \ @@ -236,7 +233,6 @@ CHEWOUT_FILES = \ mlock.def \ mstats.def \ on_exit.def \ - qsort.def \ rand.def \ rand48.def \ strtod.def \ @@ -273,9 +269,9 @@ LIBS = @LIBS@ @USE_LIBTOOL_FALSE@__ten_mu.$(OBJEXT) _Exit.$(OBJEXT) a64l.$(OBJEXT) \ @USE_LIBTOOL_FALSE@abort.$(OBJEXT) abs.$(OBJEXT) assert.$(OBJEXT) \ @USE_LIBTOOL_FALSE@atexit.$(OBJEXT) atof.$(OBJEXT) atoff.$(OBJEXT) \ -@USE_LIBTOOL_FALSE@atoi.$(OBJEXT) atol.$(OBJEXT) bsearch.$(OBJEXT) \ -@USE_LIBTOOL_FALSE@calloc.$(OBJEXT) div.$(OBJEXT) drand48.$(OBJEXT) \ -@USE_LIBTOOL_FALSE@dtoa.$(OBJEXT) dtoastub.$(OBJEXT) ecvtbuf.$(OBJEXT) \ +@USE_LIBTOOL_FALSE@atoi.$(OBJEXT) atol.$(OBJEXT) calloc.$(OBJEXT) \ +@USE_LIBTOOL_FALSE@div.$(OBJEXT) drand48.$(OBJEXT) dtoa.$(OBJEXT) \ +@USE_LIBTOOL_FALSE@dtoastub.$(OBJEXT) ecvtbuf.$(OBJEXT) \ @USE_LIBTOOL_FALSE@efgcvt.$(OBJEXT) environ.$(OBJEXT) envlock.$(OBJEXT) \ @USE_LIBTOOL_FALSE@eprintf.$(OBJEXT) erand48.$(OBJEXT) exit.$(OBJEXT) \ @USE_LIBTOOL_FALSE@getenv.$(OBJEXT) getenv_r.$(OBJEXT) getopt.$(OBJEXT) \ @@ -287,15 +283,15 @@ LIBS = @LIBS@ @USE_LIBTOOL_FALSE@mbtowc_r.$(OBJEXT) mlock.$(OBJEXT) mprec.$(OBJEXT) \ @USE_LIBTOOL_FALSE@mrand48.$(OBJEXT) msize.$(OBJEXT) mstats.$(OBJEXT) \ @USE_LIBTOOL_FALSE@mtrim.$(OBJEXT) nrand48.$(OBJEXT) on_exit.$(OBJEXT) \ -@USE_LIBTOOL_FALSE@putenv.$(OBJEXT) putenv_r.$(OBJEXT) qsort.$(OBJEXT) \ -@USE_LIBTOOL_FALSE@rand.$(OBJEXT) rand48.$(OBJEXT) rand_r.$(OBJEXT) \ -@USE_LIBTOOL_FALSE@realloc.$(OBJEXT) seed48.$(OBJEXT) setenv.$(OBJEXT) \ -@USE_LIBTOOL_FALSE@setenv_r.$(OBJEXT) srand48.$(OBJEXT) \ -@USE_LIBTOOL_FALSE@strdup.$(OBJEXT) strdup_r.$(OBJEXT) strtod.$(OBJEXT) \ -@USE_LIBTOOL_FALSE@strtol.$(OBJEXT) strtoll.$(OBJEXT) \ -@USE_LIBTOOL_FALSE@strtoll_r.$(OBJEXT) strtoul.$(OBJEXT) \ -@USE_LIBTOOL_FALSE@strtoull.$(OBJEXT) strtoull_r.$(OBJEXT) \ -@USE_LIBTOOL_FALSE@system.$(OBJEXT) valloc.$(OBJEXT) wcstombs.$(OBJEXT) \ +@USE_LIBTOOL_FALSE@putenv.$(OBJEXT) putenv_r.$(OBJEXT) rand.$(OBJEXT) \ +@USE_LIBTOOL_FALSE@rand48.$(OBJEXT) rand_r.$(OBJEXT) realloc.$(OBJEXT) \ +@USE_LIBTOOL_FALSE@seed48.$(OBJEXT) setenv.$(OBJEXT) setenv_r.$(OBJEXT) \ +@USE_LIBTOOL_FALSE@srand48.$(OBJEXT) strdup.$(OBJEXT) \ +@USE_LIBTOOL_FALSE@strdup_r.$(OBJEXT) strtod.$(OBJEXT) strtol.$(OBJEXT) \ +@USE_LIBTOOL_FALSE@strtoll.$(OBJEXT) strtoll_r.$(OBJEXT) \ +@USE_LIBTOOL_FALSE@strtoul.$(OBJEXT) strtoull.$(OBJEXT) \ +@USE_LIBTOOL_FALSE@strtoull_r.$(OBJEXT) system.$(OBJEXT) \ +@USE_LIBTOOL_FALSE@valloc.$(OBJEXT) wcstombs.$(OBJEXT) \ @USE_LIBTOOL_FALSE@wcstombs_r.$(OBJEXT) wctomb.$(OBJEXT) \ @USE_LIBTOOL_FALSE@wctomb_r.$(OBJEXT) LTLIBRARIES = $(noinst_LTLIBRARIES) @@ -308,21 +304,20 @@ LTLIBRARIES = $(noinst_LTLIBRARIES) @USE_LIBTOOL_TRUE@libstdlib_la_OBJECTS = __adjust.lo __exp10.lo \ @USE_LIBTOOL_TRUE@__ten_mu.lo _Exit.lo a64l.lo abort.lo abs.lo \ @USE_LIBTOOL_TRUE@assert.lo atexit.lo atof.lo atoff.lo atoi.lo atol.lo \ -@USE_LIBTOOL_TRUE@bsearch.lo calloc.lo div.lo drand48.lo dtoa.lo \ -@USE_LIBTOOL_TRUE@dtoastub.lo ecvtbuf.lo efgcvt.lo environ.lo \ -@USE_LIBTOOL_TRUE@envlock.lo eprintf.lo erand48.lo exit.lo getenv.lo \ -@USE_LIBTOOL_TRUE@getenv_r.lo getopt.lo jrand48.lo l64a.lo labs.lo \ -@USE_LIBTOOL_TRUE@lcong48.lo ldiv.lo ldtoa.lo lrand48.lo malign.lo \ -@USE_LIBTOOL_TRUE@malloc.lo mblen.lo mblen_r.lo mbstowcs.lo \ -@USE_LIBTOOL_TRUE@mbstowcs_r.lo mbtowc.lo mbtowc_r.lo mlock.lo mprec.lo \ -@USE_LIBTOOL_TRUE@mrand48.lo msize.lo mstats.lo mtrim.lo nrand48.lo \ -@USE_LIBTOOL_TRUE@on_exit.lo putenv.lo putenv_r.lo qsort.lo rand.lo \ -@USE_LIBTOOL_TRUE@rand48.lo rand_r.lo realloc.lo seed48.lo setenv.lo \ -@USE_LIBTOOL_TRUE@setenv_r.lo srand48.lo strdup.lo strdup_r.lo \ -@USE_LIBTOOL_TRUE@strtod.lo strtol.lo strtoll.lo strtoll_r.lo \ -@USE_LIBTOOL_TRUE@strtoul.lo strtoull.lo strtoull_r.lo system.lo \ -@USE_LIBTOOL_TRUE@valloc.lo wcstombs.lo wcstombs_r.lo wctomb.lo \ -@USE_LIBTOOL_TRUE@wctomb_r.lo +@USE_LIBTOOL_TRUE@calloc.lo div.lo drand48.lo dtoa.lo dtoastub.lo \ +@USE_LIBTOOL_TRUE@ecvtbuf.lo efgcvt.lo environ.lo envlock.lo eprintf.lo \ +@USE_LIBTOOL_TRUE@erand48.lo exit.lo getenv.lo getenv_r.lo getopt.lo \ +@USE_LIBTOOL_TRUE@jrand48.lo l64a.lo labs.lo lcong48.lo ldiv.lo \ +@USE_LIBTOOL_TRUE@ldtoa.lo lrand48.lo malign.lo malloc.lo mblen.lo \ +@USE_LIBTOOL_TRUE@mblen_r.lo mbstowcs.lo mbstowcs_r.lo mbtowc.lo \ +@USE_LIBTOOL_TRUE@mbtowc_r.lo mlock.lo mprec.lo mrand48.lo msize.lo \ +@USE_LIBTOOL_TRUE@mstats.lo mtrim.lo nrand48.lo on_exit.lo putenv.lo \ +@USE_LIBTOOL_TRUE@putenv_r.lo rand.lo rand48.lo rand_r.lo realloc.lo \ +@USE_LIBTOOL_TRUE@seed48.lo setenv.lo setenv_r.lo srand48.lo strdup.lo \ +@USE_LIBTOOL_TRUE@strdup_r.lo strtod.lo strtol.lo strtoll.lo \ +@USE_LIBTOOL_TRUE@strtoll_r.lo strtoul.lo strtoull.lo strtoull_r.lo \ +@USE_LIBTOOL_TRUE@system.lo valloc.lo wcstombs.lo wcstombs_r.lo \ +@USE_LIBTOOL_TRUE@wctomb.lo wctomb_r.lo CFLAGS = @CFLAGS@ COMPILE = $(CC) $(DEFS) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) LTCOMPILE = $(LIBTOOL) --mode=compile $(CC) $(DEFS) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) diff --git a/newlib/libc/stdlib/stdlib.tex b/newlib/libc/stdlib/stdlib.tex index 7baddc330..5798caa69 100644 --- a/newlib/libc/stdlib/stdlib.tex +++ b/newlib/libc/stdlib/stdlib.tex @@ -11,7 +11,6 @@ The corresponding declarations are in the header file @file{stdlib.h}. * atexit:: Request execution of functions at program exit * atof:: String to double or float * atoi:: String to integer -* bsearch:: Binary search * calloc:: Allocate space for arrays * div:: Divide two integers * ecvtbuf:: Double or float to string of digits @@ -28,7 +27,6 @@ The corresponding declarations are in the header file @file{stdlib.h}. * mbstowcs:: Minimal multibyte string to wide string converter * mblen:: Minimal multibyte length * mbtowc:: Minimal multibyte to wide character converter -* qsort:: Sort an array * rand:: Pseudo-random numbers * rand48:: Uniformly distributed pseudo-random numbers * strtod:: String to double or float @@ -58,9 +56,6 @@ The corresponding declarations are in the header file @file{stdlib.h}. @include stdlib/atoi.def @page -@include stdlib/bsearch.def - -@page @include stdlib/calloc.def @page @@ -106,9 +101,6 @@ The corresponding declarations are in the header file @file{stdlib.h}. @include stdlib/mbtowc.def @page -@include stdlib/qsort.def - -@page @include stdlib/rand.def @page |