rom/oop/hash.h

   1 #ifndef HASH_H
   2 #define HASH_H
   3 /*
   4     Copyright © 1995-2001, The AROS Development Team. All rights reserved.
   5     $Id$
   6
   7     Desc: Demo of new OOP system - General hashing definitions.
   8     Lang: english
   9 */
  10
  11 #ifndef EXEC_TYPES_H
  12 #   include <exec/types.h>
  13 #endif
  14 #ifndef INTERN_H
  15 #   include "intern.h"
  16 #endif
  17
  18 /* Macros */
  19 #define HashMask(ht) ( (ht)->HashMask )
  20 #define HashSize(ht)  ( HashMask(ht) + 1 )
  21 #define MAX_HASH_CHARS 50
  22
  23 /* Types of hashtables. Can hash integers or strings */
  24 #define HT_INTEGER      1
  25 #define HT_STRING       2
  26 #define HT_UUID     3
  27
  28 /* structs */
  29
  30 /* Default Bucket struct. The userdefined bucket must
  31 ** have this structure defined at the top
  32 */
  33 struct Bucket
  34 {
  35     /* Each entry in the hashtable is a linked list of buckets */
  36     struct Bucket *Next;
  37     /* The ID used to lookup hashed items */
  38     IPTR ID;
  39 };
  40
  41
  42 struct HashTable
  43 {
  44     /* Pointer hash array itself */
  45     struct Bucket **Table;
  46
  47     /* function for looking up the correct bucket for a supplied ID.
  48     ** Returns NULL if none found.
  49     ** Implementations is dependant on whether it's a HT_STRING
  50     ** or HT_INTEGER hash table. Do not try to look up a string id
  51     ** in an integer hash table or vice versa.
  52     */
  53     struct Bucket * (*Lookup)(struct HashTable *ht, IPTR id, struct IntOOPBase *OOPBase);
  54
  55     /* Calcultes an offset into the hashtable according to the ID.
  56     ** Implementations dependes whether hashtable is of type
  57     ** HT_STRING or HT_INTEGER. Do not try to hash a string id
  58     ** in an integer hash table or vice versa.
  59     */
  60
  61     ULONG (*CalcHash)(struct HashTable *ht, IPTR id);
  62
  63     /* Mask used by CalcHash()  */
  64     ULONG HashMask;
  65
  66     /* Hash table type: HT_STRING or HT_INTEGER */
  67     UBYTE Type; /* String or integer */
  68 };
  69
  70 /* Protos */
  71
  72 /* Create a new empty hashtable. Type can be HT_STRING or HT_INTEGER */
  73 struct HashTable *NewHash(ULONG entries, UBYTE type, struct IntOOPBase *OOPBase);
  74
  75 /* Free a hashtable previously allocated with NewHash().
  76    You must supply a function for freeing evt. buckets in the table.
  77 */
  78 VOID FreeHash(struct HashTable *ht, VOID (*freebucket)(), struct IntOOPBase *OOPBase);
  79
  80 /* The implemntations of hashtable->HashLookup() */
  81 struct Bucket *HashLookupULONG(struct HashTable *ht, IPTR id, struct IntOOPBase *OOPBase);
  82 struct Bucket *HashLookupUUID(struct HashTable *ht, IPTR id, struct IntOOPBase *OOPBase);
  83 struct Bucket *HashLookupStr(struct HashTable *ht, IPTR id, struct IntOOPBase *OOPBase);
  84
  85 /* Copies all the buckets of one hashtable into an other one.
  86    You must supply a function to copy the buckets.
  87    The user-suppplied copybucket() will get a parameter to
  88    the bucket as first parameter, and a pointer to the user
  89    supplied data as second parameter
  90 */
  91
  92 BOOL CopyHash(struct HashTable *dest_ht
  93         ,struct HashTable *src_ht
  94         ,struct Bucket * (*copybucket)()
  95         ,APTR data
  96         ,struct IntOOPBase *OOPBase);
  97
  98 /* Inserts a bucket into the hashtable, according to it's ID */
  99 VOID InsertBucket(struct HashTable *ht, struct Bucket *b, struct IntOOPBase *OOPBase);
 100
 101 /* Removes a bucket from a hashtable */
 102 VOID RemoveBucket(struct  HashTable *ht, struct Bucket *b);
 103
 104 /* The implemntations of hashtable->CalcHash() */
 105 ULONG CalcHashStr(struct HashTable *ht, IPTR id);
 106 ULONG CalcHashULONG(struct HashTable *ht, IPTR id);
 107 ULONG CalcHashUUID(struct HashTable *ht, IPTR id);
 108
 109 VOID print_table(struct HashTable *ht, struct IntOOPBase *OOPBase);
 110 #endif /* HASH_H */