diff options
| -rw-r--r-- | usr.bin/make/Makefile | 4 | ||||
| -rw-r--r-- | usr.bin/make/arch.c | 220 | ||||
| -rw-r--r-- | usr.bin/make/hash.c | 426 | ||||
| -rw-r--r-- | usr.bin/make/hash.h | 119 |
4 files changed, 127 insertions, 642 deletions
diff --git a/usr.bin/make/Makefile b/usr.bin/make/Makefile index 4fc77dcace0..47c2912f9b9 100644 --- a/usr.bin/make/Makefile +++ b/usr.bin/make/Makefile @@ -1,4 +1,4 @@ -# $OpenBSD: Makefile,v 1.22 2000/09/14 13:32:05 espie Exp $ +# $OpenBSD: Makefile,v 1.23 2000/09/14 13:56:14 espie Exp $ PROG= make CFLAGS+= -I${.OBJDIR} -I${.CURDIR} -Wall -Wno-char-subscripts -Wstrict-prototypes @@ -7,7 +7,7 @@ CFLAGS+= -I${.OBJDIR} -I${.CURDIR} -Wall -Wno-char-subscripts -Wstrict-prototype CFLAGS+=-O0 .endif -SRCS= arch.c buf.c compat.c cond.c dir.c error.c for.c hash.c job.c lowparse.c \ +SRCS= arch.c buf.c compat.c cond.c dir.c error.c for.c job.c lowparse.c \ main.c make.c parse.c str.c suff.c targ.c var.c varmodifiers.c #util.c SRCS+= lstAppend.c lstAtEnd.c lstAtFront.c lstClose.c lstConcat.c \ lstConcatDestroy.c lstDeQueue.c lstDestroy.c lstDupl.c lstEnQueue.c \ diff --git a/usr.bin/make/arch.c b/usr.bin/make/arch.c index 30df6314ee0..7f1a2aefdcc 100644 --- a/usr.bin/make/arch.c +++ b/usr.bin/make/arch.c @@ -1,4 +1,4 @@ -/* $OpenBSD: arch.c,v 1.34 2000/09/14 13:52:41 espie Exp $ */ +/* $OpenBSD: arch.c,v 1.35 2000/09/14 13:56:14 espie Exp $ */ /* $NetBSD: arch.c,v 1.17 1996/11/06 17:58:59 christos Exp $ */ /* @@ -100,7 +100,6 @@ #include <fcntl.h> #include "make.h" #include "ohash.h" -#include "hash.h" #include "dir.h" #include "config.h" @@ -109,7 +108,7 @@ static char sccsid[] = "@(#)arch.c 8.2 (Berkeley) 1/2/94"; #else UNUSED -static char rcsid[] = "$OpenBSD: arch.c,v 1.34 2000/09/14 13:52:41 espie Exp $"; +static char rcsid[] = "$OpenBSD: arch.c,v 1.35 2000/09/14 13:56:14 espie Exp $"; #endif #endif /* not lint */ @@ -124,19 +123,41 @@ static char rcsid[] = "$OpenBSD: arch.c,v 1.34 2000/09/14 13:52:41 espie Exp $"; static LIST archives; /* Lst of archives we've already examined */ -typedef struct Arch { +typedef struct Arch_ { char *name; /* Name of archive */ - Hash_Table members; /* All the members of the archive described - * by <name, struct ar_hdr *> key/value pairs */ + struct hash members; /* All the members of this archive, as + * struct arch_member entries. */ char *fnametab; /* Extended name table strings */ size_t fnamesize; /* Size of the string table */ } Arch; +/* Used to get to ar's field sizes. */ +static struct ar_hdr *dummy; +#define AR_NAME_SIZE (sizeof(dummy->ar_name)) +#define AR_DATE_SIZE (sizeof(dummy->ar_date)) + +/* Each archive member is tied to an arch_member structure, + * suitable for hashing. */ +struct arch_member { + TIMESTAMP mtime; /* Member modification date. */ + char date[AR_DATE_SIZE+1]; + /* Same, before conversion to numeric value. */ + char name[1]; /* Member name. */ +}; + +static struct hash_info members_info = { + offsetof(struct arch_member, name), NULL, + hash_alloc, hash_free, element_alloc +}; + +static struct arch_member *new_arch_member __P((struct ar_hdr *, const char *)); +static TIMESTAMP mtime_of_member __P((struct arch_member *)); + static int ArchFindArchive __P((void *, void *)); #ifdef CLEANUP static void ArchFree __P((void *)); #endif -static struct ar_hdr *ArchStatMember __P((char *, char *, Boolean)); +static TIMESTAMP ArchMTimeMember __P((char *, char *, Boolean)); static FILE *ArchFindMember __P((char *, char *, struct ar_hdr *, char *)); #if defined(__svr4__) || defined(__SVR4) || \ (defined(__OpenBSD__) && defined(__mips__)) || \ @@ -145,6 +166,32 @@ static FILE *ArchFindMember __P((char *, char *, struct ar_hdr *, char *)); static int ArchSVR4Entry __P((Arch *, char *, size_t, FILE *)); #endif +static struct arch_member * +new_arch_member(hdr, name) + struct ar_hdr *hdr; + const char *name; +{ + const char *end = NULL; + struct arch_member *n; + + n = hash_create_entry(&members_info, name, &end); + /* XXX ar entries are NOT null terminated. */ + memcpy(n->date, &(hdr->ar_date), AR_DATE_SIZE); + n->date[AR_DATE_SIZE] = '\0'; + /* Don't compute mtime before it is needed. */ + set_out_of_date(n->mtime); + return n; +} + +static TIMESTAMP +mtime_of_member(m) + struct arch_member *m; +{ + if (is_out_of_date(m->mtime)) + grab_date((time_t) strtol(m->date, NULL, 10), m->mtime); + return m->mtime; +} + #ifdef CLEANUP /*- *----------------------------------------------------------------------- @@ -164,18 +211,17 @@ ArchFree(ap) void *ap; { Arch *a = (Arch *) ap; - Hash_Search search; - Hash_Entry *entry; + struct arch_member *mem; + unsigned i; /* Free memory from hash entries */ - for (entry = Hash_EnumFirst(&a->members, &search); - entry != NULL; - entry = Hash_EnumNext(&search)) - free(Hash_GetValue(entry)); + for (mem = hash_first(&a->members, &i); mem != NULL; + mem = hash_next(&a->members, &i)) + free(mem); free(a->name); efree(a->fnametab); - Hash_DeleteTable(&a->members); + hash_delete(&a->members); free(a); } #endif @@ -435,18 +481,14 @@ Arch_ParseArchive(linePtr, nodeLst, ctxt) *----------------------------------------------------------------------- * ArchFindArchive -- * See if the given archive is the one we are looking for. Called - * From ArchStatMember and ArchFindMember via Lst_Find. + * From ArchMTimeMember and ArchFindMember via Lst_Find. * * Results: * 0 if it is, non-zero if it isn't. - * - * Side Effects: - * None. - * *----------------------------------------------------------------------- */ static int -ArchFindArchive (ar, archName) +ArchFindArchive(ar, archName) void *ar; /* Current list element */ void *archName; /* Name we want */ { @@ -455,7 +497,7 @@ ArchFindArchive (ar, archName) /*- *----------------------------------------------------------------------- - * ArchStatMember -- + * ArchMTimeMember -- * Locate a member of an archive, given the path of the archive and * the path of the desired member. * @@ -470,8 +512,8 @@ ArchFindArchive (ar, archName) * *----------------------------------------------------------------------- */ -static struct ar_hdr * -ArchStatMember (archive, member, hash) +static TIMESTAMP +ArchMTimeMember(archive, member, hash) char *archive; /* Path to the archive */ char *member; /* Name of member. If it is a path, only the * last component is used. */ @@ -485,10 +527,14 @@ ArchStatMember (archive, member, hash) char magic[SARMAG]; LstNode ln; /* Lst member containing archive descriptor */ Arch *ar; /* Archive descriptor */ - Hash_Entry *he; /* Entry containing member's description */ + struct arch_member *he; /* Entry containing member's description */ struct ar_hdr arh; /* archive-member header for reading archive */ char memName[MAXPATHLEN+1]; /* Current member name while hashing. */ + const char *end = NULL; + TIMESTAMP result; + + set_out_of_date(result); /* * Because of space constraints and similar things, files are archived @@ -496,31 +542,28 @@ ArchStatMember (archive, member, hash) * to point 'member' to the final component, if there is one, to make * the comparisons easier... */ - cp = strrchr (member, '/'); + cp = strrchr(member, '/'); if (cp != NULL) member = cp + 1; ln = Lst_Find(&archives, ArchFindArchive, archive); if (ln != NULL) { ar = (Arch *)Lst_Datum(ln); - - he = Hash_FindEntry (&ar->members, member); - - if (he != NULL) { - return ((struct ar_hdr *) Hash_GetValue (he)); - } else { - /* Try truncated name */ - char copy[AR_MAX_NAME_LEN+1]; - int len = strlen (member); - - if (len > AR_MAX_NAME_LEN) { - len = AR_MAX_NAME_LEN; - strncpy(copy, member, AR_MAX_NAME_LEN); - copy[AR_MAX_NAME_LEN] = '\0'; + end = NULL; + he = hash_find(&ar->members, hash_qlookupi(&ar->members, member, &end)); + if (he != NULL) + return mtime_of_member(he); + else { + if (end - member > AR_NAME_SIZE) { + /* Try truncated name */ + end = member + AR_NAME_SIZE; + + he = hash_find(&ar->members, + hash_qlookupi(&ar->members, member, &end)); + if (he != NULL) + return mtime_of_member(he); } - if ((he = Hash_FindEntry (&ar->members, copy)) != NULL) - return ((struct ar_hdr *) Hash_GetValue (he)); - return (NULL); + return result; } } @@ -536,11 +579,12 @@ ArchStatMember (archive, member, hash) arch = ArchFindMember(archive, member, &sarh, "r"); - if (arch == NULL) { - return (NULL); - } else { + if (arch == NULL) + return NULL; + else { fclose(arch); - return (&sarh); + grab_date( (time_t)strtol(sarh.ar_date, NULL, 10), result); + return result; } } @@ -548,30 +592,29 @@ ArchStatMember (archive, member, hash) * We don't have this archive on the list yet, so we want to find out * everything that's in it and cache it so we can get at it quickly. */ - arch = fopen (archive, "r"); - if (arch == NULL) { + arch = fopen(archive, "r"); + if (arch == NULL) return (NULL); - } /* * We use the ARMAG string to make sure this is an archive we * can handle... */ - if ((fread (magic, SARMAG, 1, arch) != 1) || - (strncmp (magic, ARMAG, SARMAG) != 0)) { - fclose (arch); - return (NULL); + if ((fread(magic, SARMAG, 1, arch) != 1) || + (strncmp(magic, ARMAG, SARMAG) != 0)) { + fclose(arch); + return NULL; } - ar = (Arch *)emalloc (sizeof (Arch)); - ar->name = estrdup (archive); + ar = (Arch *)emalloc(sizeof (Arch)); + ar->name = estrdup(archive); ar->fnametab = NULL; ar->fnamesize = 0; - Hash_InitTable (&ar->members, -1); + hash_init(&ar->members, 8, &members_info); memName[AR_MAX_NAME_LEN] = '\0'; - while (fread ((char *)&arh, sizeof (struct ar_hdr), 1, arch) == 1) { - if (strncmp ( arh.ar_fmag, ARFMAG, sizeof (arh.ar_fmag)) != 0) { + while (fread((char *)&arh, sizeof (struct ar_hdr), 1, arch) == 1) { + if (strncmp( arh.ar_fmag, ARFMAG, sizeof (arh.ar_fmag)) != 0) { /* * The header is bogus, so the archive is bad * and there's no way we can recover... @@ -587,7 +630,7 @@ ArchStatMember (archive, member, hash) arh.ar_size[sizeof(arh.ar_size)-1] = '\0'; size = (int) strtol(arh.ar_size, NULL, 10); - (void) strncpy (memName, arh.ar_name, sizeof(arh.ar_name)); + (void) strncpy(memName, arh.ar_name, sizeof(arh.ar_name)); for (cp = &memName[AR_MAX_NAME_LEN]; *cp == ' '; cp--) { continue; } @@ -631,21 +674,21 @@ ArchStatMember (archive, member, hash) if (fread (memName, elen, 1, arch) != 1) goto badarch; memName[elen] = '\0'; - fseek (arch, -elen, SEEK_CUR); + fseek(arch, -elen, SEEK_CUR); if (DEBUG(ARCH) || DEBUG(MAKE)) { printf("ArchStat: Extended format entry for %s\n", memName); } } #endif - he = Hash_CreateEntry(&ar->members, memName, NULL); - Hash_SetValue(he, emalloc(sizeof(struct ar_hdr))); - memcpy(Hash_GetValue(he), &arh, sizeof(struct ar_hdr)); + hash_insert(&ar->members, + hash_qlookup(&ar->members, memName), + new_arch_member(&arh, memName)); } - fseek (arch, (size + 1) & ~1, SEEK_CUR); + fseek(arch, (size + 1) & ~1, SEEK_CUR); } - fclose (arch); + fclose(arch); Lst_AtEnd(&archives, ar); @@ -653,20 +696,20 @@ ArchStatMember (archive, member, hash) * Now that the archive has been read and cached, we can look into * the hash table to find the desired member's header. */ - he = Hash_FindEntry (&ar->members, member); + he = hash_find(&ar->members, + hash_qlookupi(&ar->members, member, &end)); - if (he != NULL) { - return ((struct ar_hdr *) Hash_GetValue (he)); - } else { - return (NULL); - } + if (he != NULL) + return mtime_of_member(he); + else + return result; badarch: fclose(arch); - Hash_DeleteTable(&ar->members); + hash_delete(&ar->members); efree(ar->fnametab); free(ar); - return NULL; + return result; } #ifdef SVR4ARCHIVES @@ -1006,18 +1049,13 @@ Arch_TouchLib (gn) *----------------------------------------------------------------------- */ TIMESTAMP -Arch_MTime (gn) +Arch_MTime(gn) GNode *gn; /* Node describing archive member */ { - struct ar_hdr *arhPtr; /* Header of desired member */ + gn->mtime = ArchMTimeMember(Varq_Value(ARCHIVE_INDEX, gn), + Varq_Value(MEMBER_INDEX, gn), + TRUE); - arhPtr = ArchStatMember(Varq_Value(ARCHIVE_INDEX, gn), - Varq_Value(MEMBER_INDEX, gn), - TRUE); - if (arhPtr != NULL) - gn->mtime = (time_t) strtol(arhPtr->ar_date, NULL, 10); - else - gn->mtime = OUT_OF_DATE; return gn->mtime; } @@ -1175,25 +1213,20 @@ Arch_LibOODate (gn) oodate = TRUE; } else { #ifdef RANLIBMAG - struct ar_hdr *arhPtr; /* Header for __.SYMDEF */ time_t modTimeTOC; /* The table-of-contents's mod time */ - arhPtr = ArchStatMember (gn->path, RANLIBMAG, FALSE); - - if (arhPtr != NULL) { - modTimeTOC = (time_t) strtol(arhPtr->ar_date, NULL, 10); + modTimeTOC = ArchMTimeMember(gn->path, RANLIBMAG, FALSE); - if (DEBUG(ARCH) || DEBUG(MAKE)) { + if (!is_out_of_date(modTimeTOC)) { + if (DEBUG(ARCH) || DEBUG(MAKE)) printf("%s modified %s...", RANLIBMAG, Targ_FmtTime(modTimeTOC)); - } - oodate = (gn->cmtime > modTimeTOC); + oodate = is_before(modTimeTOC, gn->cmtime); } else { /* * A library w/o a table of contents is out-of-date */ - if (DEBUG(ARCH) || DEBUG(MAKE)) { + if (DEBUG(ARCH) || DEBUG(MAKE)) printf("No t.o.c...."); - } oodate = TRUE; } #else @@ -1208,9 +1241,6 @@ Arch_LibOODate (gn) * Arch_Init -- * Initialize things for this module. * - * Results: - * None. - * * Side Effects: * The 'archives' list is initialized. * diff --git a/usr.bin/make/hash.c b/usr.bin/make/hash.c deleted file mode 100644 index 9a135f37744..00000000000 --- a/usr.bin/make/hash.c +++ /dev/null @@ -1,426 +0,0 @@ -/* $OpenBSD: hash.c,v 1.6 2000/09/14 13:32:06 espie Exp $ */ -/* $NetBSD: hash.c,v 1.6 1996/11/06 17:59:06 christos Exp $ */ - -/* - * Copyright (c) 1988, 1989, 1990 The Regents of the University of California. - * Copyright (c) 1988, 1989 by Adam de Boor - * Copyright (c) 1989 by Berkeley Softworks - * All rights reserved. - * - * This code is derived from software contributed to Berkeley by - * Adam de Boor. - * - * 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.c -- - * - * This module contains routines to manipulate a hash table. - * See hash.h for a definition of the structure of the hash - * table. Hash tables grow automatically as the amount of - * information increases. - */ -#include "sprite.h" -#include "make.h" -#include "hash.h" - -#ifndef lint -#if 0 -static char sccsid[] = "@(#)hash.c 8.1 (Berkeley) 6/6/93"; -#else -UNUSED -static char rcsid[] = "$OpenBSD: hash.c,v 1.6 2000/09/14 13:32:06 espie Exp $"; -#endif -#endif /* not lint */ - -/* - * Forward references to local procedures that are used before they're - * defined: - */ - -static void RebuildTable __P((Hash_Table *)); - -/* - * The following defines the ratio of # entries to # buckets - * at which we rebuild the table to make it larger. - */ - -#define rebuildLimit 8 - -/* - *--------------------------------------------------------- - * - * Hash_InitTable -- - * - * This routine just sets up the hash table. - * - * Results: - * None. - * - * Side Effects: - * Memory is allocated for the initial bucket area. - * - *--------------------------------------------------------- - */ - -void -Hash_InitTable(t, numBuckets) - register Hash_Table *t; /* Structure to use to hold table. */ - int numBuckets; /* How many buckets to create for starters. - * This number is rounded up to a power of - * two. If <= 0, a reasonable default is - * chosen. The table will grow in size later - * as needed. */ -{ - register int i; - register struct Hash_Entry **hp; - - /* - * Round up the size to a power of two. - */ - if (numBuckets <= 0) - i = 16; - else { - for (i = 2; i < numBuckets; i <<= 1) - continue; - } - t->numEntries = 0; - t->size = i; - t->mask = i - 1; - t->bucketPtr = hp = (struct Hash_Entry **)emalloc(sizeof(*hp) * i); - while (--i >= 0) - *hp++ = NULL; -} - -/* - *--------------------------------------------------------- - * - * Hash_DeleteTable -- - * - * This routine removes everything from a hash table - * and frees up the memory space it occupied (except for - * the space in the Hash_Table structure). - * - * Results: - * None. - * - * Side Effects: - * Lots of memory is freed up. - * - *--------------------------------------------------------- - */ - -void -Hash_DeleteTable(t) - Hash_Table *t; -{ - register struct Hash_Entry **hp, *h, *nexth = NULL; - register int i; - - for (hp = t->bucketPtr, i = t->size; --i >= 0;) { - for (h = *hp++; h != NULL; h = nexth) { - nexth = h->next; - free((char *)h); - } - } - free((char *)t->bucketPtr); - - /* - * Set up the hash table to cause memory faults on any future access - * attempts until re-initialization. - */ - t->bucketPtr = NULL; -} - -/* - *--------------------------------------------------------- - * - * Hash_FindEntry -- - * - * Searches a hash table for an entry corresponding to key. - * - * Results: - * The return value is a pointer to the entry for key, - * if key was present in the table. If key was not - * present, NULL is returned. - * - * Side Effects: - * None. - * - *--------------------------------------------------------- - */ - -Hash_Entry * -Hash_FindEntry(t, key) - Hash_Table *t; /* Hash table to search. */ - char *key; /* A hash key. */ -{ - register Hash_Entry *e; - register unsigned h; - register char *p; - - for (h = 0, p = key; *p;) - h = (h << 5) - h + *p++; - p = key; - for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next) - if (e->namehash == h && strcmp(e->name, p) == 0) - return (e); - return (NULL); -} - -/* - *--------------------------------------------------------- - * - * Hash_CreateEntry -- - * - * Searches a hash table for an entry corresponding to - * key. If no entry is found, then one is created. - * - * Results: - * The return value is a pointer to the entry. If *newPtr - * isn't NULL, then *newPtr is filled in with TRUE if a - * new entry was created, and FALSE if an entry already existed - * with the given key. - * - * Side Effects: - * Memory may be allocated, and the hash buckets may be modified. - *--------------------------------------------------------- - */ - -Hash_Entry * -Hash_CreateEntry(t, key, newPtr) - register Hash_Table *t; /* Hash table to search. */ - char *key; /* A hash key. */ - Boolean *newPtr; /* Filled in with TRUE if new entry created, - * FALSE otherwise. */ -{ - register Hash_Entry *e; - register unsigned h; - register char *p; - int keylen; - struct Hash_Entry **hp; - - /* - * Hash the key. As a side effect, save the length (strlen) of the - * key in case we need to create the entry. - */ - for (h = 0, p = key; *p;) - h = (h << 5) - h + *p++; - keylen = p - key; - p = key; - for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next) { - if (e->namehash == h && strcmp(e->name, p) == 0) { - if (newPtr != NULL) - *newPtr = FALSE; - return (e); - } - } - - /* - * The desired entry isn't there. Before allocating a new entry, - * expand the table if necessary (and this changes the resulting - * bucket chain). - */ - if (t->numEntries >= rebuildLimit * t->size) - RebuildTable(t); - e = (Hash_Entry *) emalloc(sizeof(*e) + keylen); - hp = &t->bucketPtr[h & t->mask]; - e->next = *hp; - *hp = e; - e->clientData = NULL; - e->namehash = h; - (void) strcpy(e->name, p); - t->numEntries++; - - if (newPtr != NULL) - *newPtr = TRUE; - return (e); -} - -/* - *--------------------------------------------------------- - * - * Hash_DeleteEntry -- - * - * Delete the given hash table entry and free memory associated with - * it. - * - * Results: - * None. - * - * Side Effects: - * Hash chain that entry lives in is modified and memory is freed. - * - *--------------------------------------------------------- - */ - -void -Hash_DeleteEntry(t, e) - Hash_Table *t; - Hash_Entry *e; -{ - register Hash_Entry **hp, *p; - - if (e == NULL) - return; - for (hp = &t->bucketPtr[e->namehash & t->mask]; - (p = *hp) != NULL; hp = &p->next) { - if (p == e) { - *hp = p->next; - free((char *)p); - t->numEntries--; - return; - } - } - (void) write(2, "bad call to Hash_DeleteEntry\n", 29); - abort(); -} - -/* - *--------------------------------------------------------- - * - * Hash_EnumFirst -- - * This procedure sets things up for a complete search - * of all entries recorded in the hash table. - * - * Results: - * The return value is the address of the first entry in - * the hash table, or NULL if the table is empty. - * - * Side Effects: - * The information in searchPtr is initialized so that successive - * calls to Hash_Next will return successive HashEntry's - * from the table. - * - *--------------------------------------------------------- - */ - -Hash_Entry * -Hash_EnumFirst(t, searchPtr) - Hash_Table *t; /* Table to be searched. */ - register Hash_Search *searchPtr;/* Area in which to keep state - * about search.*/ -{ - searchPtr->tablePtr = t; - searchPtr->nextIndex = 0; - searchPtr->hashEntryPtr = NULL; - return Hash_EnumNext(searchPtr); -} - -/* - *--------------------------------------------------------- - * - * Hash_EnumNext -- - * This procedure returns successive entries in the hash table. - * - * Results: - * The return value is a pointer to the next HashEntry - * in the table, or NULL when the end of the table is - * reached. - * - * Side Effects: - * The information in searchPtr is modified to advance to the - * next entry. - * - *--------------------------------------------------------- - */ - -Hash_Entry * -Hash_EnumNext(searchPtr) - register Hash_Search *searchPtr; /* Area used to keep state about - search. */ -{ - register Hash_Entry *e; - Hash_Table *t = searchPtr->tablePtr; - - /* - * The hashEntryPtr field points to the most recently returned - * entry, or is null if we are starting up. If not null, we have - * to start at the next one in the chain. - */ - e = searchPtr->hashEntryPtr; - if (e != NULL) - e = e->next; - /* - * If the chain ran out, or if we are starting up, we need to - * find the next nonempty chain. - */ - while (e == NULL) { - if (searchPtr->nextIndex >= t->size) - return (NULL); - e = t->bucketPtr[searchPtr->nextIndex++]; - } - searchPtr->hashEntryPtr = e; - return (e); -} - -/* - *--------------------------------------------------------- - * - * RebuildTable -- - * This local routine makes a new hash table that - * is larger than the old one. - * - * Results: - * None. - * - * Side Effects: - * The entire hash table is moved, so any bucket numbers - * from the old table are invalid. - * - *--------------------------------------------------------- - */ - -static void -RebuildTable(t) - register Hash_Table *t; -{ - register Hash_Entry *e, *next = NULL, **hp, **xp; - register int i, mask; - register Hash_Entry **oldhp; - int oldsize; - - oldhp = t->bucketPtr; - oldsize = i = t->size; - i <<= 1; - t->size = i; - t->mask = mask = i - 1; - t->bucketPtr = hp = (struct Hash_Entry **) emalloc(sizeof(*hp) * i); - while (--i >= 0) - *hp++ = NULL; - for (hp = oldhp, i = oldsize; --i >= 0;) { - for (e = *hp++; e != NULL; e = next) { - next = e->next; - xp = &t->bucketPtr[e->namehash & mask]; - e->next = *xp; - *xp = e; - } - } - free((char *)oldhp); -} diff --git a/usr.bin/make/hash.h b/usr.bin/make/hash.h deleted file mode 100644 index d43f8678b66..00000000000 --- a/usr.bin/make/hash.h +++ /dev/null @@ -1,119 +0,0 @@ -/* $OpenBSD: hash.h,v 1.6 2000/06/10 01:41:05 espie Exp $ */ -/* $NetBSD: hash.h,v 1.5 1996/11/06 17:59:07 christos Exp $ */ - -/* - * Copyright (c) 1988, 1989, 1990 The Regents of the University of California. - * Copyright (c) 1988, 1989 by Adam de Boor - * Copyright (c) 1989 by Berkeley Softworks - * All rights reserved. - * - * This code is derived from software contributed to Berkeley by - * Adam de Boor. - * - * 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. - * - * from: @(#)hash.h 8.1 (Berkeley) 6/6/93 - */ - -/* hash.h -- - * - * This file contains definitions used by the hash module, - * which maintains hash tables. - */ - -#ifndef _HASH -#define _HASH - -/* - * The following defines one entry in the hash table. - */ - -typedef struct Hash_Entry { - struct Hash_Entry *next; /* Used to link together all the - * entries associated with the same - * bucket. */ - void *clientData; /* Arbitrary piece of data associated - * with key. */ - unsigned namehash; /* hash value of key */ - char name[1]; /* key string */ -} Hash_Entry; - -typedef struct Hash_Table { - struct Hash_Entry **bucketPtr;/* Pointers to Hash_Entry, one - * for each bucket in the table. */ - int size; /* Actual size of array. */ - int numEntries; /* Number of entries in the table. */ - int mask; /* Used to select bits for hashing. */ -} Hash_Table; - -/* - * The following structure is used by the searching routines - * to record where we are in the search. - */ - -typedef struct Hash_Search { - Hash_Table *tablePtr; /* Table being searched. */ - int nextIndex; /* Next bucket to check (after current). */ - Hash_Entry *hashEntryPtr; /* Next entry to check in current bucket. */ -} Hash_Search; - -/* - * Macros. - */ - -/* - * void *Hash_GetValue(h) - * Hash_Entry *h; - */ - -#define Hash_GetValue(h) ((h)->clientData) - -/* - * Hash_SetValue(h, val); - * Hash_Entry *h; - * char *val; - */ - -#define Hash_SetValue(h, val) ((h)->clientData = (val)) - -/* - * Hash_Size(n) returns the number of words in an object of n bytes - */ - -#define Hash_Size(n) (((n) + sizeof (int) - 1) / sizeof (int)) - -void Hash_InitTable __P((Hash_Table *, int)); -void Hash_DeleteTable __P((Hash_Table *)); -Hash_Entry *Hash_FindEntry __P((Hash_Table *, char *)); -Hash_Entry *Hash_CreateEntry __P((Hash_Table *, char *, Boolean *)); -void Hash_DeleteEntry __P((Hash_Table *, Hash_Entry *)); -Hash_Entry *Hash_EnumFirst __P((Hash_Table *, Hash_Search *)); -Hash_Entry *Hash_EnumNext __P((Hash_Search *)); - -#endif /* _HASH */ |