pdutil/h/list.h

   1 /*
   2  *  Copyright 1993 Jeff Hollingsworth.  All rights reserved.
   3  *
   4  */
   5
   6 /*
   7  * list.h - list ADT
   8  *
   9  * $Log: list.h,v $
  10  * Revision 1.1  1993/05/07 20:21:15  hollings
  11  * Initial revision
  12  *
  13  * Revision 1.1  1993/03/19  22:51:05  hollings
  14  * Initial revision
  15  *
  16  *
  17  */
  18 #ifndef LIST_H
  19 #define LIST_H
  20 #include <stdio.h>
  21
  22 #define FALSE 0
  23 #define TRUE  1
  24
  25 inline static int ListHash(void *ptr, int size)
  26 {
  27     return(((int)(ptr) % (int)(size)));
  28 }
  29
  30 class List;
  31
  32 template <class Type> class ListItem {
  33     friend class List<Type>;
  34     private:
  35         Type            data;
  36         void            *key;
  37         ListItem<Type>  *next;
  38 };
  39
  40 template <class Type> class List {
  41     public:
  42         List() { head = NULL; }
  43         void add(Type data, void *key);
  44         void add(Type data) { add(data, (void *) data); }
  45         Boolean addUnique(Type data) { return(addUnique(data, (void *) data)); }
  46         Boolean addUnique(Type data, void *key) {
  47             Type temp;
  48
  49             temp = find(key);
  50             if (!temp) {
  51                 add(data, key);
  52                 return(TRUE);
  53             } else {
  54                 return(FALSE);
  55             }
  56         }
  57         Type find(void *key);
  58         void remove(Type data);
  59         int count()     {
  60             int c;
  61             ListItem<Type> *curr;
  62
  63             for (curr=head,c=0; curr; curr=curr->next) c++;
  64             return(c);
  65         }
  66         Type operator *() {
  67             if (head)
  68                 return(head->data);
  69             else
  70                 return((Type) NULL);
  71         }
  72         void operator +=(List<Type> mergee) {
  73             ListItem<Type> *curr;
  74
  75             for (curr=mergee.head; curr; curr=curr->next) {
  76                 add(curr->data, curr->key);
  77             }
  78         }
  79         Type operator ++() {
  80             Type ret = (Type) NULL;
  81             if (head) {
  82                 ret = head->data;
  83                 head = head->next;
  84             }
  85             return(ret);
  86         }
  87     private:
  88         ListItem<Type>  *head;
  89 };
  90
  91
  92 template <class Type> void List<Type>::add(Type data, void *key)
  93 {
  94     ListItem<Type> *ni;
  95
  96     ni = new(ListItem<Type>);
  97     ni->data = data;
  98     ni->key = key;
  99
 100     ni->next = head;
 101     head = ni;
 102 }
 103
 104 template <class Type> void List<Type>::remove(Type data)
 105 {
 106     ListItem<Type> *lag;
 107     ListItem<Type> *curr;
 108
 109     for (curr=head, lag = NULL; curr; curr=curr->next) {
 110         if (curr->data == data) {
 111             break;
 112         }
 113         lag = curr;
 114     }
 115
 116     if (curr) {
 117         if (lag) {
 118             lag->next = curr->next;
 119         } else {
 120             head = curr->next;
 121         }
 122         delete(curr);
 123     } else {
 124         abort();
 125     }
 126 }
 127
 128 template <class Type> Type List<Type>::find(void *data)
 129 {
 130     ListItem<Type> *curr;
 131
 132     for (curr=head; curr; curr=curr->next) {
 133         if (curr->key == data) {
 134             return(curr->data);
 135         }
 136     }
 137     return((Type) 0);
 138 }
 139
 140 template <class Type> class HTable {
 141
 142     public:
 143         HTable(Type data) { HTable(); add(data, (void *) data); }
 144         HTable();
 145         void add(Type data, void *key);
 146         Boolean addUnique(Type data, void *key) {
 147             Type temp;
 148
 149             temp = find(key);
 150             if (temp ) {
 151                 return(0);
 152             } else {
 153                 add(data, key);
 154                 return(1);
 155             }
 156         }
 157         Type find(void *key);
 158         // void remove(Type data);
 159         Type operator *() {
 160             Type curr;
 161
 162             curr = *currList;
 163             if (curr) return(curr);
 164             for (currHid++; currHid < tableSize; currHid++) {
 165                 if (table[currHid]) {
 166                     currList = *table[currHid];
 167                     curr = *currList;
 168                     if (curr) return(curr);
 169                 }
 170             }
 171             return(NULL);
 172         }
 173         Type operator ++() {
 174             Type curr;
 175
 176             curr = *currList;
 177             currList++;
 178             return(curr);
 179         }
 180         int count()     {
 181             int i, total;
 182
 183             total = 0;
 184             for (i=0; i < tableSize; i++) {
 185                 if (table[i]) {
 186                     total += table[i]->count();
 187                 }
 188             }
 189             return(total);
 190         }
 191     private:
 192         List<Type> **table;
 193         List<Type> currList;
 194         int currHid;
 195         int tableSize;
 196 };
 197
 198 template <class Type> HTable<Type>::HTable()
 199 {
 200     table = NULL;
 201     currHid = 0;
 202     tableSize = 0;
 203 }
 204
 205 template <class Type> Type HTable<Type>::find(void *key)
 206 {
 207     int hid;
 208
 209     if (!tableSize) return(NULL);
 210     hid = ListHash(key, tableSize);
 211     if (!table[hid]) {
 212         return(NULL);
 213     } else {
 214         return(table[hid]->find(key));
 215     }
 216 }
 217
 218 template <class Type> void HTable<Type>::add(Type data, void *key)
 219 {
 220     int hid;
 221
 222     if (!tableSize) {
 223         tableSize = 97;
 224         table = (List<Type>**) calloc(tableSize, sizeof(List<Type>*));
 225     }
 226     hid = ListHash(key, tableSize);
 227     if (!table[hid]) {
 228         table[hid] = new(List<Type>);
 229     }
 230     table[hid]->add(data, key);
 231 }
 232 #endif LIST_H