diff options
Diffstat (limited to 'newlib/libc/search')
| -rw-r--r-- | newlib/libc/search/Makefile.am | 67 | ||||
| -rw-r--r-- | newlib/libc/search/Makefile.in | 391 | ||||
| -rw-r--r-- | newlib/libc/search/bsearch.c | 100 | ||||
| -rw-r--r-- | newlib/libc/search/db_local.h | 218 | ||||
| -rw-r--r-- | newlib/libc/search/extern.h | 66 | ||||
| -rw-r--r-- | newlib/libc/search/hash.c | 1027 | ||||
| -rw-r--r-- | newlib/libc/search/hash.h | 310 | ||||
| -rw-r--r-- | newlib/libc/search/hash_bigkey.c | 673 | ||||
| -rw-r--r-- | newlib/libc/search/hash_buf.c | 364 | ||||
| -rw-r--r-- | newlib/libc/search/hash_func.c | 212 | ||||
| -rw-r--r-- | newlib/libc/search/hash_log2.c | 55 | ||||
| -rw-r--r-- | newlib/libc/search/hash_page.c | 948 | ||||
| -rw-r--r-- | newlib/libc/search/hcreate.3 | 206 | ||||
| -rw-r--r-- | newlib/libc/search/hcreate.c | 82 | ||||
| -rw-r--r-- | newlib/libc/search/hcreate_r.c | 188 | ||||
| -rw-r--r-- | newlib/libc/search/page.h | 93 | ||||
| -rw-r--r-- | newlib/libc/search/qsort.c | 222 | ||||
| -rw-r--r-- | newlib/libc/search/tdelete.c | 67 | ||||
| -rw-r--r-- | newlib/libc/search/tdestroy.c | 51 | ||||
| -rw-r--r-- | newlib/libc/search/tfind.c | 48 | ||||
| -rw-r--r-- | newlib/libc/search/tsearch.3 | 118 | ||||
| -rw-r--r-- | newlib/libc/search/tsearch.c | 58 | ||||
| -rw-r--r-- | newlib/libc/search/twalk.c | 58 |
23 files changed, 0 insertions, 5622 deletions
diff --git a/newlib/libc/search/Makefile.am b/newlib/libc/search/Makefile.am deleted file mode 100644 index d170cfa3a..000000000 --- a/newlib/libc/search/Makefile.am +++ /dev/null @@ -1,67 +0,0 @@ -## Process this file with automake to generate Makefile.in - -AUTOMAKE_OPTIONS = cygnus - -INCLUDES = $(NEWLIB_CFLAGS) $(CROSS_CFLAGS) $(TARGET_CFLAGS) - -GENERAL_SOURCES = \ - bsearch.c \ - db_local.h \ - extern.h \ - hash.h \ - page.h \ - qsort.c - -## Following are EL/IX level 2 interfaces -if ELIX_LEVEL_1 -LIB_OBJS = -else -LIB_OBJS = \ - hash.$(oext) \ - hash_bigkey.$(oext) \ - hash_buf.$(oext) \ - hash_func.$(oext) \ - hash_log2.$(oext) \ - hash_page.$(oext) \ - hcreate.$(oext) \ - hcreate_r.$(oext) \ - tdelete.$(oext) \ - tdestroy.$(oext) \ - tfind.$(oext) \ - tsearch.$(oext) \ - twalk.$(oext) -endif - -libsearch_la_LDFLAGS = -Xcompiler -nostdlib - -if USE_LIBTOOL -noinst_LTLIBRARIES = libsearch.la -libsearch_la_SOURCES = $(GENERAL_SOURCES) -libsearch_la_LIBADD = $(LIB_OBJS) -libsearch_la_DEPENDENCIES = $(LIB_OBJS) -noinst_DATA = objectlist.awk.in -else -noinst_LIBRARIES = lib.a -lib_a_SOURCES = $(GENERAL_SOURCES) -lib_a_LIBADD = $(LIB_OBJS) -lib_a_DEPENDENCIES = $(LIB_OBJS) -noinst_DATA = -endif # USE_LIBTOOL - -SUFFIXES = .def - -CHEWOUT_FILES = - -CHEW = ../../doc/makedoc -f $(srcdir)/../../doc/doc.str - -.c.def: - $(CHEW) < $< > $*.def 2> $*.ref - touch stmp-def - -TARGETDOC = ../tmp.texi - -doc: $(CHEWOUT_FILES) - -CLEANFILES = $(CHEWOUT_FILES) *.ref - -include $(srcdir)/../../Makefile.shared diff --git a/newlib/libc/search/Makefile.in b/newlib/libc/search/Makefile.in deleted file mode 100644 index eff92d40b..000000000 --- a/newlib/libc/search/Makefile.in +++ /dev/null @@ -1,391 +0,0 @@ -# Makefile.in generated automatically by automake 1.4-p6 from Makefile.am - -# Copyright (C) 1994, 1995-8, 1999, 2001 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_STDIO64_DEF = @LIBC_STDIO64_DEF@ -LIBC_STDIO64_LIB = @LIBC_STDIO64_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) - -GENERAL_SOURCES = bsearch.c db_local.h extern.h hash.h page.h qsort.c - -@ELIX_LEVEL_1_TRUE@LIB_OBJS = -@ELIX_LEVEL_1_FALSE@LIB_OBJS = hash.$(oext) hash_bigkey.$(oext) hash_buf.$(oext) hash_func.$(oext) hash_log2.$(oext) hash_page.$(oext) hcreate.$(oext) hcreate_r.$(oext) tdelete.$(oext) tdestroy.$(oext) tfind.$(oext) tsearch.$(oext) twalk.$(oext) - -libsearch_la_LDFLAGS = -Xcompiler -nostdlib - -@USE_LIBTOOL_TRUE@noinst_LTLIBRARIES = libsearch.la -@USE_LIBTOOL_TRUE@libsearch_la_SOURCES = $(GENERAL_SOURCES) -@USE_LIBTOOL_TRUE@libsearch_la_LIBADD = $(LIB_OBJS) -@USE_LIBTOOL_TRUE@libsearch_la_DEPENDENCIES = $(LIB_OBJS) -@USE_LIBTOOL_TRUE@noinst_DATA = objectlist.awk.in -@USE_LIBTOOL_FALSE@noinst_DATA = -@USE_LIBTOOL_FALSE@noinst_LIBRARIES = lib.a -@USE_LIBTOOL_FALSE@lib_a_SOURCES = $(GENERAL_SOURCES) -@USE_LIBTOOL_FALSE@lib_a_LIBADD = $(LIB_OBJS) -@USE_LIBTOOL_FALSE@lib_a_DEPENDENCIES = $(LIB_OBJS) - -SUFFIXES = .def - -CHEWOUT_FILES = - -CHEW = ../../doc/makedoc -f $(srcdir)/../../doc/doc.str - -TARGETDOC = ../tmp.texi - -CLEANFILES = $(CHEWOUT_FILES) *.ref -mkinstalldirs = $(SHELL) $(top_srcdir)/../../mkinstalldirs -CONFIG_CLEAN_FILES = -LIBRARIES = $(noinst_LIBRARIES) - - -DEFS = @DEFS@ -I. -I$(srcdir) -CPPFLAGS = @CPPFLAGS@ -LIBS = @LIBS@ -@USE_LIBTOOL_FALSE@lib_a_OBJECTS = bsearch.$(OBJEXT) qsort.$(OBJEXT) -LTLIBRARIES = $(noinst_LTLIBRARIES) - -@USE_LIBTOOL_TRUE@libsearch_la_OBJECTS = bsearch.lo qsort.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 .def .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: - -test -z "$(CLEANFILES)" || rm -f $(CLEANFILES) - -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 - - -.c.def: - $(CHEW) < $< > $*.def 2> $*.ref - touch stmp-def - -doc: $(CHEWOUT_FILES) - -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 deleted file mode 100644 index b9539aa3b..000000000 --- a/newlib/libc/search/bsearch.c +++ /dev/null @@ -1,100 +0,0 @@ -/* - * 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/db_local.h b/newlib/libc/search/db_local.h deleted file mode 100644 index 53f9d17ff..000000000 --- a/newlib/libc/search/db_local.h +++ /dev/null @@ -1,218 +0,0 @@ -/*- - * 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/search/extern.h b/newlib/libc/search/extern.h deleted file mode 100644 index 666a6e5bf..000000000 --- a/newlib/libc/search/extern.h +++ /dev/null @@ -1,66 +0,0 @@ -/*- - * 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 deleted file mode 100644 index 3d919286a..000000000 --- a/newlib/libc/search/hash.c +++ /dev/null @@ -1,1027 +0,0 @@ -/*- - * 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_local.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); -#if (BYTE_ORDER == LITTLE_ENDIAN) -static void swap_header(HTAB *); -static void swap_header_copy(HASHHDR *, HASHHDR *); -#endif - -/* Macros for min/max. */ -#ifndef MIN -#define MIN(a,b) (((a)<(b))?(a):(b)) -#endif -#ifndef MAX -#define MAX(a,b) (((a)>(b))?(a):(b)) -#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) || -#ifdef __USE_INTERNAL_STAT64 - (stat64(file, &statbuf) && (errno == ENOENT))) { -#else - (stat(file, &statbuf) && (errno == ENOENT))) { -#endif - 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) && -#ifdef __USE_INTERNAL_STAT64 - fstat64(hashp->fp, &statbuf) == 0 && statbuf.st_size == 0) -#else - fstat(hashp->fp, &statbuf) == 0 && statbuf.st_size == 0) -#endif - new_table = 1; - -#ifdef HAVE_FCNTL - (void)fcntl(hashp->fp, F_SETFD, 1); -#endif - } - 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)); -#if (BYTE_ORDER == 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 = DB_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) { -#ifdef __USE_INTERNAL_STAT64 - if (stat64(file, &statbuf)) -#else - if (stat(file, &statbuf)) -#endif - 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 != DB_BIG_ENDIAN && - info->lorder != DB_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; -#if (BYTE_ORDER == 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; -#if (BYTE_ORDER == 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); -} - -#if (BYTE_ORDER == 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 deleted file mode 100644 index db9e96dd8..000000000 --- a/newlib/libc/search/hash.h +++ /dev/null @@ -1,310 +0,0 @@ -/*- - * 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 $ - */ - -#include <sys/param.h> - -/* Check that newlib understands the byte order of its target system. */ -#ifndef BYTE_ORDER -#error BYTE_ORDER not defined by sys/param.h -#endif - -/* Define DB endianness constants based on target endianness. */ -#define DB_LITTLE_ENDIAN 1234 -#define DB_BIG_ENDIAN 4321 -#if (BYTE_ORDER == LITTLE_ENDIAN) -#define DB_BYTE_ORDER DB_LITTLE_ENDIAN -#else -#define DB_BYTE_ORDER DB_BIG_ENDIAN -#endif - -/* 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 deleted file mode 100644 index 821acd078..000000000 --- a/newlib/libc/search/hash_bigkey.c +++ /dev/null @@ -1,673 +0,0 @@ -/*- - * 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> - -/* Macros for min/max. */ -#define MIN(a,b) (((a)<(b))?(a):(b)) -#define MAX(a,b) (((a)>(b))?(a):(b)) - -/* - * 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_local.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 deleted file mode 100644 index 3dfc2069f..000000000 --- a/newlib/libc/search/hash_buf.c +++ /dev/null @@ -1,364 +0,0 @@ -/*- - * 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_local.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) - -/* Macros for min/max. */ -#ifndef MIN -#define MIN(a,b) (((a)<(b))?(a):(b)) -#endif -#ifndef MAX -#define MAX(a,b) (((a)>(b))?(a):(b)) -#endif - -/* - * 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 deleted file mode 100644 index 52cb31ccb..000000000 --- a/newlib/libc/search/hash_func.c +++ /dev/null @@ -1,212 +0,0 @@ -/*- - * 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_local.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 deleted file mode 100644 index 9414f26c2..000000000 --- a/newlib/libc/search/hash_log2.c +++ /dev/null @@ -1,55 +0,0 @@ -/*- - * 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_local.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 deleted file mode 100644 index 68ab9db17..000000000 --- a/newlib/libc/search/hash_page.c +++ /dev/null @@ -1,948 +0,0 @@ -/*- - * 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_local.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 != DB_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 != DB_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); -#ifdef HAVE_FCNTL - (void)fcntl(hashp->fp, F_SETFD, 1); -#endif - } - (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 deleted file mode 100644 index 1619c9892..000000000 --- a/newlib/libc/search/hcreate.3 +++ /dev/null @@ -1,206 +0,0 @@ -.\" $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 deleted file mode 100644 index 095e1f208..000000000 --- a/newlib/libc/search/hcreate.c +++ /dev/null @@ -1,82 +0,0 @@ -/* $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. 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_GC,v 1.1 2001/10/01 23:24:05 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 -_DEFUN(hcreate, (nel), size_t nel) -{ - return hcreate_r (nel, &htab); -} - -void -_DEFUN_VOID (hdestroy) -{ - hdestroy_r (&htab); -} - -ENTRY * -_DEFUN(hsearch, (item, action), - ENTRY item _AND - 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 deleted file mode 100644 index 4ff758fdb..000000000 --- a/newlib/libc/search/hcreate_r.c +++ /dev/null @@ -1,188 +0,0 @@ -/* $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. 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_GC,v 1.1 2001/10/01 23:24:05 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/page.h b/newlib/libc/search/page.h deleted file mode 100644 index 9ecabdacd..000000000 --- a/newlib/libc/search/page.h +++ /dev/null @@ -1,93 +0,0 @@ -/*- - * 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 deleted file mode 100644 index d47f47099..000000000 --- a/newlib/libc/search/qsort.c +++ /dev/null @@ -1,222 +0,0 @@ -/* -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 deleted file mode 100644 index e75659913..000000000 --- a/newlib/libc/search/tdelete.c +++ /dev/null @@ -1,67 +0,0 @@ -/* $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 * -_DEFUN(tdelete, (vkey, vrootp, compar), - const void *vkey _AND /* key to be deleted */ - void **vrootp _AND /* 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 deleted file mode 100644 index 3e7327c4d..000000000 --- a/newlib/libc/search/tdestroy.c +++ /dev/null @@ -1,51 +0,0 @@ -/* $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 -_DEFUN(tdestroy, (vrootp, freefct), - void *vrootp _AND - 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 deleted file mode 100644 index 5d7c40c93..000000000 --- a/newlib/libc/search/tfind.c +++ /dev/null @@ -1,48 +0,0 @@ -/* $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 * -_DEFUN(tfind, (vkey, vrootp, compar), - const void *vkey _AND /* key to be found */ - void **vrootp _AND /* 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 deleted file mode 100644 index a36fe894f..000000000 --- a/newlib/libc/search/tsearch.3 +++ /dev/null @@ -1,118 +0,0 @@ -.\" $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 deleted file mode 100644 index 5f41b407d..000000000 --- a/newlib/libc/search/tsearch.c +++ /dev/null @@ -1,58 +0,0 @@ -/* $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 * -_DEFUN(tsearch, (vkey, vrootp, compar), - const void *vkey _AND /* key to be located */ - void **vrootp _AND /* 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 deleted file mode 100644 index 74ad5a615..000000000 --- a/newlib/libc/search/twalk.c +++ /dev/null @@ -1,58 +0,0 @@ -/* $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 -_DEFUN(twalk, (vroot, action), - const void *vroot _AND /* Root of the tree to be walked */ - void (*action)(const void *, VISIT, int)) -{ - if (vroot != NULL && action != NULL) - trecurse(vroot, action, 0); -} |