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
  27 /* structs */
  28
  29 /* Default Bucket struct. The userdefined bucket must
  30 ** have this structure defined at the top
  31 */
  32 struct Bucket
  33 {
  34     /* Each entry in the hashtable is a linked list of buckets */
  35     struct Bucket *Next;
  36     /* The ID used to lookup hashed items */
  37     IPTR ID;
  38 };
  39
  40
  41 struct HashTable
  42 {
  43     /* Pointer hash array itself */
  44     struct Bucket **Table;
  45
  46     /* function for looking up the correct bucket for a supplied ID.
  47     ** Returns NULL if none found.
  48     ** Implementations is dependant on whether it's a HT_STRING
  49     ** or HT_INTEGER hash table. Do not try to look up a string id
  50     ** in an integer hash table or vice versa.
  51     */
  52     struct Bucket * (*Lookup)(struct HashTable *ht, IPTR id, struct IntOOPBase *OOPBase);
  53
  54     /* Calcultes an offset into the hashtable according to the ID.
  55     ** Implementations dependes whether hashtable is of type
  56     ** HT_STRING or HT_INTEGER. Do not try to hash a string id
  57     ** in an integer hash table or vice versa.
  58     */
  59
  60     ULONG (*CalcHash)(struct HashTable *ht, IPTR id);
  61
  62     /* Mask used by CalcHash()  */
  63     ULONG HashMask;
  64
  65     /* Hash table type: HT_STRING or HT_INTEGER */
  66     UBYTE Type; /* String or integer */
  67 };
  68
  69 /* Protos */
  70
  71 /* Create a new empty hashtable. Type can be HT_STRING or HT_INTEGER */
  72 struct HashTable *NewHash(ULONG entries, UBYTE type, struct IntOOPBase *OOPBase);
  73
  74 /* Free a hashtable previously allocated with NewHash().
  75    You must supply a function for freeing evt. buckets in the table.
  76 */
  77 VOID FreeHash(struct HashTable *ht, VOID (*freebucket)(), struct IntOOPBase *OOPBase);
  78
  79 /* The implemntations of hashtable->HashLookup() */
  80 struct Bucket *HashLookupULONG(struct HashTable *ht, IPTR id, struct IntOOPBase *OOPBase);
  81 struct Bucket *HashLookupStr(struct HashTable *ht, IPTR id, struct IntOOPBase *OOPBase);
  82
  83 /* Copies all the buckets of one hashtable into an other one.
  84    You must supply a function to copy the buckets.
  85    The user-suppplied copybucket() will get a parameter to
  86    the bucket as first parameter, and a pointer to the user
  87    supplied data as second parameter
  88 */
  89
  90 BOOL CopyHash(struct HashTable *dest_ht
  91         ,struct HashTable *src_ht
  92         ,struct Bucket * (*copybucket)()
  93         ,APTR data
  94         ,struct IntOOPBase *OOPBase);
  95
  96 /* Inserts a bucket into the hashtable, according to it's ID */
  97 VOID InsertBucket(struct HashTable *ht, struct Bucket *b, struct IntOOPBase *OOPBase);
  98
  99 /* Removes a bucket from a hashtable */
 100 VOID RemoveBucket(struct  HashTable *ht, struct Bucket *b);
 101
 102 /* The implemntations of hashtable->CalcHash() */
 103 ULONG CalcHashStr(struct HashTable *ht, IPTR id);
 104 ULONG CalcHashULONG(struct HashTable *ht, IPTR id);
 105
 106 VOID print_table(struct HashTable *ht, struct IntOOPBase *OOPBase);
 107 #endif /* HASH_H */