Return to hash.h CVS log

Up to [Research Unix] / researchv10no / cmd / odist / pax / include

Annotation of researchv10no/cmd/odist/pax/include/hash.h, revision 1.1

1.1     ! root        1: /*
        !             2:  * G. S. Fowler
        !             3:  * AT&T Bell Laboratories
        !             4:  *
        !             5:  * hash table library interface definitions
        !             6:  */
        !             7: 
        !             8: #ifndef HASH_ALLOCATE
        !             9: 
        !            10: #define hash_info              _hash_info_
        !            11: #define vhashalloc             hashvalloc
        !            12: 
        !            13: #ifndef VOID
        !            14: #define VOID   char
        !            15: #endif
        !            16: 
        !            17: #define HASH_ALLOCATE  (1<<0)          /* allocate new key names       */
        !            18: #define HASH_FIXED     (1<<1)          /* fixed bucket/table size      */
        !            19: #define HASH_HASHED    (1<<6)          /* key names already hashed     */
        !            20: #define HASH_RESIZE    (1<<2)          /* table has been resized       */
        !            21: #define HASH_SCANNING  (1<<3)          /* currently scanning scope     */
        !            22: #define HASH_SCOPE     (1<<4)          /* push scope / create in bot   */
        !            23: #define HASH_STATIC    (1<<5)          /* static table allocation      */
        !            24: 
        !            25: #define HASH_CREATE    (1<<8)          /* create bucket if not found   */
        !            26: #define HASH_DELETE    (1<<9)          /* delete bucket if found       */
        !            27: #define HASH_LOOKUP    0               /* default op                   */
        !            28: 
        !            29: #define HASH_BUCKET    (1<<11)         /* name is installed bucket     */
        !            30: #define HASH_INSTALL   (1<<12)         /* install allocated bucket     */
        !            31: #define HASH_NOSCOPE   (1<<13)         /* top scope only               */
        !            32: #define HASH_OPAQUE    (1<<14)         /* opaque bucket                */
        !            33: #define HASH_VALUE     (1<<15)         /* value bucket field used      */
        !            34: 
        !            35: #define HASH_GET       (HASH_LOOKUP|HASH_VALUE)
        !            36: #define HASH_NEW       (HASH_CREATE|HASH_FIXED)
        !            37: #define HASH_PUT       (HASH_CREATE|HASH_VALUE)
        !            38: 
        !            39: #define HASH_DELETED   (1<<(8*sizeof(int)-1))  /* deleted placeholder  */
        !            40: #define HASH_KEEP      (1<<(8*sizeof(int)-2))  /* no free on bucket    */
        !            41: #define HASH_HIDDEN    (1<<(8*sizeof(int)-3))  /* hidden by scope      */
        !            42: #define HASH_HIDES     (1<<(8*sizeof(int)-4))  /* hides lower scope    */
        !            43: #define HASH_OPAQUED   (1<<(8*sizeof(int)-5))  /* opaqued placeholder  */
        !            44: 
        !            45: #define HASH_RESET     (HASH_RESIZE|HASH_SCOPE|HASH_STATIC)
        !            46: #define HASH_INTERNAL  (HASH_BUCKET|HASH_RESIZE|HASH_SCANNING|HASH_STATIC)
        !            47: #define HASH_FLAGS     (HASH_DELETED|HASH_HIDDEN|HASH_HIDES|HASH_KEEP|HASH_OPAQUED)
        !            48: 
        !            49: #define HASH_alloc             1
        !            50: #define HASH_clear             2
        !            51: #define HASH_compare           3
        !            52: #define HASH_free              4
        !            53: #define HASH_hash              5
        !            54: #define HASH_meanchain         6
        !            55: #define HASH_name              7
        !            56: #define HASH_namesize          8
        !            57: #define HASH_set               9
        !            58: #define HASH_size              10
        !            59: #define HASH_table             11
        !            60: 
        !            61: #include <hashpart.h>
        !            62: 
        !            63: #define hashclear(t,f)         ((t)->flags &= ~((f) & ~HASH_INTERNAL))
        !            64: #define hashdel(t,n)           hashlook(t, (char*)(n), HASH_DELETE, (char*)0)
        !            65: #define hashget(t,n)           hashlook(t, (char*)(n), HASH_LOOKUP|HASH_VALUE, (char*)0)
        !            66: #define hashlast(t)            (hash_info.last)
        !            67: #define hashname(b)            ((((b)->hash&HASH_HIDES)?((HASHBUCKET*)((b)->name)):(b))->name)
        !            68: #define hashput(t,n,v)         (char*)hashlook(t, (char*)(n), HASH_CREATE|HASH_VALUE, (char*)(v))
        !            69: #define hashscope(t)           ((t)->scope)
        !            70: #define hashset(t,f)           ((t)->flags |= ((f) & ~HASH_INTERNAL))
        !            71: 
        !            72: #define Hashbin_t              HASHBUCKET
        !            73: #define Hashhdr_t              HASHHEADER
        !            74: #define Hashpos_t              HASHPOSITION
        !            75: #define Hashtab_t              HASHTABLE
        !            76: 
        !            77: typedef struct hashbucket      HASHBUCKET;
        !            78: typedef struct hashheader      HASHHEADER;
        !            79: typedef struct hashposition    HASHPOSITION;
        !            80: typedef struct hashroot                HASHROOT;
        !            81: typedef struct hashtable       HASHTABLE;
        !            82: typedef unsigned int           (*HASHFUN)();
        !            83: typedef int                    (*HASHINT)();
        !            84: typedef char*                  (*HASHPTR)();
        !            85: 
        !            86: /*
        !            87:  * the #define's avoid union tags
        !            88:  */
        !            89: 
        !            90: #define HASH_HEADER                    /* common bucket header         */ \
        !            91:        HASHBUCKET*     next;           /* next in collision chain      */ \
        !            92:        unsigned int    hash;           /* hash flags and value         */ \
        !            93:        char*           name            /* key name                     */
        !            94: 
        !            95: #define HASH_DEFAULT                   /* HASH_VALUE bucket elements   */ \
        !            96:        char*           value           /* key value                    */
        !            97: 
        !            98: struct hashheader                      /* bucket header                */
        !            99: {
        !           100:        HASH_HEADER;
        !           101: };
        !           102: 
        !           103: struct hashbucket                      /* prototype bucket             */
        !           104: {
        !           105:        HASH_HEADER;
        !           106:        HASH_DEFAULT;
        !           107: };
        !           108: 
        !           109: struct hashposition                    /* hash scan bucket position    */
        !           110: {
        !           111:        HASHTABLE*      tab;            /* table pointer                */
        !           112:        HASHTABLE*      top;            /* top scope table pointer      */
        !           113:        int             flags;          /* scan flags                   */
        !           114:        HASHBUCKET*     bucket;         /* bucket                       */
        !           115:        HASHBUCKET**    slot;           /* table slot                   */
        !           116:        HASHBUCKET**    limit;          /* slot limit                   */
        !           117: };
        !           118: 
        !           119: struct hashroot                                /* root hash table information  */
        !           120: {
        !           121:        int             flags;          /* flags: see HASH_[A-Z]*       */
        !           122:        int             namesize;       /* fixed name size: 0 => string */
        !           123:        int             meanchain;      /* resize mean chain length     */
        !           124:        HASHFUN         hash;           /* name hash routine            */
        !           125:        HASHINT         compare;        /* name comparision routine     */
        !           126:        HASHPTR         alloc;          /* value allocation routine     */
        !           127:        HASHINT         free;           /* value free routine           */
        !           128:        int             accesses;       /* number of accesses           */
        !           129:        int             collisions;     /* number of collisions         */
        !           130:        HASHROOT*       next;           /* next in list of all roots    */
        !           131:        HASHTABLE*      references;     /* referencing table list       */
        !           132: };
        !           133: 
        !           134: struct hashtable                       /* hash table information       */
        !           135: {
        !           136:        HASHROOT*       root;           /* root hash table information  */
        !           137:        HASHTABLE*      scope;          /* scope covered table          */
        !           138:        short           flags;          /* flags: see HASH_[A-Z]*       */
        !           139:        short           frozen;         /* table freeze nesting         */
        !           140:        HASHBUCKET**    table;          /* hash slot table              */
        !           141:        int             size;           /* table size                   */
        !           142:        int             buckets;        /* active bucket count          */
        !           143:        char*           name;           /* table name                   */
        !           144:        HASHTABLE*      next;           /* root reference list link     */
        !           145: };
        !           146: 
        !           147: struct hashinfo                                /* library hash info            */
        !           148: {
        !           149:        HASHBUCKET*     last;           /* most recent lookup bucket    */
        !           150:        HASHTABLE*      table;          /* most recent lookup table     */
        !           151:        HASHROOT*       list;           /* root table list              */
        !           152: };
        !           153: 
        !           154: #if __cplusplus
        !           155: extern "C" {
        !           156: #endif
        !           157: 
        !           158: extern struct hashinfo hash_info;
        !           159: 
        !           160: #if __cplusplus
        !           161: }
        !           162: #endif
        !           163: 
        !           164: #if __STDC__ || __cplusplus || c_plusplus
        !           165: 
        !           166: #include <stdarg.h>
        !           167: #include <stdio.h>
        !           168: 
        !           169: #if __cplusplus
        !           170: extern "C" {
        !           171: #endif
        !           172: extern HASHTABLE*      hashalloc(HASHTABLE*, ...);
        !           173: extern HASHTABLE*      hashvalloc(HASHTABLE*, va_list);
        !           174: extern void            hashdone(HASHPOSITION*);
        !           175: extern void            hashdump(FILE*, HASHTABLE*, int);
        !           176: extern HASHTABLE*      hashfree(HASHTABLE*);
        !           177: extern char*           hashlook(HASHTABLE*, const char*, int, const char*);
        !           178: extern HASHBUCKET*     hashnext(HASHPOSITION*);
        !           179: extern void            hashscan(HASHTABLE*, int, HASHPOSITION*);
        !           180: extern void            hashsize(HASHTABLE*, int);
        !           181: extern int             hashwalk(HASHTABLE*, int, HASHINT);
        !           182: 
        !           183: extern unsigned int    memhash(const char*, int);
        !           184: extern unsigned long   memsum(const char*, int, unsigned long);
        !           185: extern unsigned int    strhash(const char*);
        !           186: extern unsigned long   strsum(const char*, unsigned long);
        !           187: #if __cplusplus
        !           188: }
        !           189: #endif
        !           190: #else
        !           191: extern HASHTABLE*      hashalloc();
        !           192: extern HASHTABLE*      hashvalloc();
        !           193: extern void                    hashdone();
        !           194: extern void            hashdump();
        !           195: extern HASHTABLE*      hashfree();
        !           196: extern char*           hashlook();
        !           197: extern HASHBUCKET*     hashnext();
        !           198: extern void            hashscan();
        !           199: extern void            hashsize();
        !           200: extern int             hashwalk();
        !           201: 
        !           202: extern unsigned int    memhash();
        !           203: extern unsigned long   memsum();
        !           204: extern unsigned int    strhash();
        !           205: extern unsigned long   strsum();
        !           206: #endif
        !           207: 
        !           208: #endif

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