home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume27 / bootp-2.2.B / part01 / hash.h < prev    next >
Encoding:
C/C++ Source or Header  |  1993-10-11  |  4.3 KB  |  138 lines
  1. #ifndef _BLURB_
  2. #define _BLURB_
  3. /************************************************************************
  4.           Copyright 1988, 1991 by Carnegie Mellon University
  5.  
  6.                           All Rights Reserved
  7.  
  8. Permission to use, copy, modify, and distribute this software and its
  9. documentation for any purpose and without fee is hereby granted, provided
  10. that the above copyright notice appear in all copies and that both that
  11. copyright notice and this permission notice appear in supporting
  12. documentation, and that the name of Carnegie Mellon University not be used
  13. in advertising or publicity pertaining to distribution of the software
  14. without specific, written prior permission.
  15.  
  16. CARNEGIE MELLON UNIVERSITY DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS
  17. SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS.
  18. IN NO EVENT SHALL CMU BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
  19. DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
  20. PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
  21. ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
  22. SOFTWARE.
  23. ************************************************************************/
  24. #endif /* _BLURB_ */
  25.  
  26.  
  27. /*
  28.  * Generalized hash table ADT
  29.  *
  30.  * Provides multiple, dynamically-allocated, variable-sized hash tables on
  31.  * various data and keys.
  32.  *
  33.  * This package attempts to follow some of the coding conventions suggested
  34.  * by Bob Sidebotham and the AFS Clean Code Committee.
  35.  */
  36.  
  37.  
  38. /*
  39.  * The user must supply the following:
  40.  *
  41.  *    1.  A comparison function which is declared as:
  42.  *
  43.  *        int compare(data1, data2)
  44.  *        hash_datum *data1, *data2;
  45.  *
  46.  *        This function must compare the desired fields of data1 and
  47.  *        data2 and return TRUE (1) if the data should be considered
  48.  *        equivalent (i.e. have the same key value) or FALSE (0)
  49.  *        otherwise.  This function is called through a pointer passed to
  50.  *        the various hashtable functions (thus pointers to different
  51.  *        functions may be passed to effect different tests on different
  52.  *        hash tables).
  53.  *
  54.  *        Internally, all the functions of this package always call the
  55.  *        compare function with the "key" parameter as the first parameter,
  56.  *        and a full data element as the second parameter.  Thus, the key
  57.  *        and element arguments to functions such as hash_Lookup() may
  58.  *        actually be of different types and the programmer may provide a
  59.  *        compare function which compares the two different object types
  60.  *        as desired.
  61.  *
  62.  *        Example:
  63.  *
  64.  *        int compare(key, element)
  65.  *        char *key;
  66.  *        struct some_complex_structure *element;
  67.  *        {
  68.  *            return !strcmp(key, element->name);
  69.  *        }
  70.  *
  71.  *        key = "John C. Doe"
  72.  *        element = &some_complex_structure
  73.  *        hash_Lookup(table, hashcode, compare, key);
  74.  *
  75.  *    2.  A hash function yielding an unsigned integer value to be used
  76.  *        as the hashcode (index into the hashtable).  Thus, the user
  77.  *        may hash on whatever data is desired and may use several
  78.  *        different hash functions for various different hash tables.
  79.  *        The actual hash table index will be the passed hashcode modulo
  80.  *        the hash table size.
  81.  *
  82.  *        A generalized hash function, hash_HashFunction(), is included
  83.  *        with this package to make things a little easier.  It is not
  84.  *        guarenteed to use the best hash algorithm in existence. . . .
  85.  */
  86.  
  87.  
  88.  
  89. /*
  90.  * Various hash table definitions
  91.  */
  92.  
  93.  
  94. #ifndef __HASHXYZ973__
  95.  
  96. #define __HASHXYZ973__
  97.  
  98. /*
  99.  * Define "hash_datum" as a universal data type
  100.  */
  101. #ifdef __STDC__
  102. typedef void hash_datum;
  103. #else
  104. typedef char hash_datum;
  105. #endif
  106.  
  107. typedef struct hash_memberstruct  hash_member;
  108. typedef struct hash_tblstruct     hash_tbl;
  109. typedef struct hash_tblstruct_hdr hash_tblhdr;
  110.  
  111. struct hash_memberstruct {
  112.     hash_member *next;
  113.     hash_datum  *data;
  114. };
  115.  
  116. struct hash_tblstruct_hdr {
  117.     unsigned    size, bucketnum;
  118.     hash_member *member;
  119. };
  120.  
  121. struct hash_tblstruct {
  122.     unsigned    size, bucketnum;
  123.     hash_member *member;        /* Used for linear dump */
  124.     hash_member    *table[1];        /* Dynamically extended */
  125. };
  126.  
  127. extern hash_tbl      *hash_Init();
  128. extern void       hash_Reset();
  129. extern unsigned       hash_HashFunction();
  130. extern int       hash_Exists();
  131. extern int       hash_Insert();
  132. extern int       hash_Delete();
  133. extern hash_datum *hash_Lookup();
  134. extern hash_datum *hash_FirstEntry();
  135. extern hash_datum *hash_NextEntry();
  136.  
  137. #endif
  138.