Return to hash.h CVS log

Up to [CSRG BSD Unix] / 43BSDReno / usr.bin / make

Annotation of 43BSDReno/usr.bin/make/hash.h, revision 1.1

1.1     ! root        1: /*
        !             2:  * Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
        !             3:  * Copyright (c) 1988, 1989 by Adam de Boor
        !             4:  * Copyright (c) 1989 by Berkeley Softworks
        !             5:  * All rights reserved.
        !             6:  *
        !             7:  * This code is derived from software contributed to Berkeley by
        !             8:  * Adam de Boor.
        !             9:  *
        !            10:  * Redistribution and use in source and binary forms are permitted
        !            11:  * provided that: (1) source distributions retain this entire copyright
        !            12:  * notice and comment, and (2) distributions including binaries display
        !            13:  * the following acknowledgement:  ``This product includes software
        !            14:  * developed by the University of California, Berkeley and its contributors''
        !            15:  * in the documentation or other materials provided with the distribution
        !            16:  * and in all advertising materials mentioning features or use of this
        !            17:  * software. Neither the name of the University nor the names of its
        !            18:  * contributors may be used to endorse or promote products derived
        !            19:  * from this software without specific prior written permission.
        !            20:  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
        !            21:  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
        !            22:  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
        !            23:  *
        !            24:  *     @(#)hash.h      5.3 (Berkeley) 6/1/90
        !            25:  */
        !            26: 
        !            27: /* hash.h --
        !            28:  *
        !            29:  *     This file contains definitions used by the hash module,
        !            30:  *     which maintains hash tables.
        !            31:  */
        !            32: 
        !            33: #ifndef        _HASH
        !            34: #define        _HASH
        !            35: 
        !            36: #include "list.h"
        !            37: /* 
        !            38:  * The following defines one entry in the hash table.
        !            39:  */
        !            40: 
        !            41: typedef struct Hash_Entry {
        !            42:     List_Links       links;            /* Used to link together all the
        !            43:                                         * entries associated with the same
        !            44:                                         * bucket. */
        !            45:     ClientData       clientData;       /* Arbitrary piece of data associated
        !            46:                                         * with key. */
        !            47:     union {
        !            48:        Address  ptr;                   /* One-word key value to identify
        !            49:                                         * entry. */
        !            50:        int words[1];                   /* N-word key value.  Note: the actual
        !            51:                                         * size may be longer if necessary to
        !            52:                                         * hold the entire key. */
        !            53:        char     name[4];               /* Text name of this entry.  Note: the
        !            54:                                         * actual size may be longer if
        !            55:                                         * necessary to hold the whole string.
        !            56:                                         * This MUST be the last entry in the
        !            57:                                         * structure!!! */
        !            58:     } key;
        !            59: } Hash_Entry;
        !            60: 
        !            61: /* 
        !            62:  * A hash table consists of an array of pointers to hash
        !            63:  * lists.  Tables can be organized in either of three ways, depending
        !            64:  * on the type of comparison keys:
        !            65:  *
        !            66:  *     Strings:          these are NULL-terminated; their address
        !            67:  *                       is passed to HashFind as a (char *).
        !            68:  *     Single-word keys: these may be anything, but must be passed
        !            69:  *                       to Hash_Find as an Address.
        !            70:  *     Multi-word keys:  these may also be anything; their address
        !            71:  *                       is passed to HashFind as an Address.
        !            72:  *
        !            73:  *     Single-word keys are fastest, but most restrictive.
        !            74:  */
        !            75:  
        !            76: #define HASH_STRING_KEYS       0
        !            77: #define HASH_ONE_WORD_KEYS     1
        !            78: 
        !            79: typedef struct Hash_Table {
        !            80:     List_Links         *bucketPtr;     /* Pointer to array of List_Links, one
        !            81:                                 * for each bucket in the table. */
        !            82:     int        size;           /* Actual size of array. */
        !            83:     int        numEntries;     /* Number of entries in the table. */
        !            84:     int        downShift;      /* Shift count, used in hashing function. */
        !            85:     int        mask;           /* Used to select bits for hashing. */
        !            86:     int        keyType;        /* Type of keys used in table:
        !            87:                                 * HASH_STRING_KEYS, HASH_ONE-WORD_KEYS,
        !            88:                                 * or >1 menas keyType gives number of words
        !            89:                                 * in keys.
        !            90:                                 */
        !            91: } Hash_Table;
        !            92: 
        !            93: /* 
        !            94:  * The following structure is used by the searching routines
        !            95:  * to record where we are in the search.
        !            96:  */
        !            97: 
        !            98: typedef struct Hash_Search {
        !            99:     Hash_Table  *tablePtr;     /* Table being searched. */
        !           100:     int        nextIndex;      /* Next bucket to check (after current). */
        !           101:     Hash_Entry         *hashEntryPtr;  /* Next entry to check in current bucket. */
        !           102:     List_Links *hashList;      /* Hash chain currently being checked. */
        !           103: } Hash_Search;
        !           104: 
        !           105: /*
        !           106:  * Macros.
        !           107:  */
        !           108: 
        !           109: /*
        !           110:  * ClientData Hash_GetValue(h) 
        !           111:  *     Hash_Entry *h; 
        !           112:  */
        !           113: 
        !           114: #define Hash_GetValue(h) ((h)->clientData)
        !           115: 
        !           116: /* 
        !           117:  * Hash_SetValue(h, val); 
        !           118:  *     HashEntry *h; 
        !           119:  *     char *val; 
        !           120:  */
        !           121: 
        !           122: #define Hash_SetValue(h, val) ((h)->clientData = (ClientData) (val))
        !           123: 
        !           124: /* 
        !           125:  * Hash_Size(n) returns the number of words in an object of n bytes 
        !           126:  */
        !           127: 
        !           128: #define        Hash_Size(n)    (((n) + sizeof (int) - 1) / sizeof (int))
        !           129: 
        !           130: /*
        !           131:  * The following procedure declarations and macros
        !           132:  * are the only things that should be needed outside
        !           133:  * the implementation code.
        !           134:  */
        !           135: 
        !           136: extern Hash_Entry *    Hash_CreateEntry();
        !           137: extern void            Hash_DeleteTable();
        !           138: extern void            Hash_DeleteEntry();
        !           139: extern void            Hash_DeleteTable();
        !           140: extern Hash_Entry *    Hash_EnumFirst();
        !           141: extern Hash_Entry *    Hash_EnumNext();
        !           142: extern Hash_Entry *    Hash_FindEntry();
        !           143: extern void            Hash_InitTable();
        !           144: extern void            Hash_PrintStats();
        !           145: 
        !           146: #endif _HASH

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.