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.13  1994/02/24 07:05:28  markc
  11  * Man page for librpcUtil.a
  12  * Extended list class to provide map function.  rpcUtil supports internet domain
  13  * sockets.
  14  *
  15  * Revision 1.12  1994/02/10  23:08:21  hollings
  16  * Fixed list.h ++ function to work when a hash table has an element at
  17  * slot zero in the table.
  18  *
  19  * Removed unused fields in hist class.
  20  *
  21  * Revision 1.11  1994/02/09  22:37:09  hollings
  22  * Added print routines to list and hash table.
  23  *
  24  * Revision 1.10  1994/02/08  00:30:32  hollings
  25  * Make libutil more compatable with ATT CC.
  26  *
  27  * Revision 1.9  1994/02/03  23:30:43  hollings
  28  * changed listHash to a macro to work with g++ 2.5.2.
  29  *
  30  * Revision 1.8  1994/01/25  20:49:40  hollings
  31  * First real version of utility library.
  32  *
  33  * Revision 1.7  1994/01/19  20:46:17  hollings
  34  * guardef defn of true/false.
  35  *
  36  * Revision 1.6  1993/12/15  21:06:54  hollings
  37  * removed destructors.  Our current list semantics don't support auto
  38  * destruction of list comonents since list elements can be shared between
  39  * lists.
  40  *
  41  * Revision 1.5  1993/12/13  20:11:14  hollings
  42  * added destructor for List class.
  43  *
  44  * Revision 1.4  1993/10/19  15:31:52  hollings
  45  * assorted small fixes.
  46  *
  47  * Revision 1.3  1993/08/02  22:46:37  hollings
  48  * added remove which was missing.
  49  *
  50  * Revision 1.2  1993/07/01  17:02:36  hollings
  51  * ansi endif comments
  52  *
  53  * Revision 1.1  1993/05/07  20:21:15  hollings
  54  * Initial revision
  55  *
  56  * Revision 1.1  1993/03/19  22:51:05  hollings
  57  * Initial revision
  58  *
  59  *
  60  */
  61 #ifndef LIST_H
  62 #define LIST_H
  63 #include <stdio.h>
  64 #include <iostream.h>
  65 #include <stdlib.h>
  66
  67 typedef int Boolean;
  68
  69 #ifndef FALSE
  70 #define FALSE 0
  71 #define TRUE  1
  72 #endif
  73
  74 #define ListHash(ptr, size) (((int)(ptr) % (int)(size)))
  75
  76 template <class Type> class List;
  77 template <class Type> class StringList;
  78
  79 template <class Type> class ListItem {
  80     friend class List<Type>;
  81     friend class StringList<Type>;
  82     private:
  83         Type            data;
  84         void            *key;
  85         ListItem<Type>  *next;
  86 };
  87
  88 template <class Type> class List {
  89     public:
  90         List() { head = NULL; current = NULL; }
  91         int  empty() { return (head == NULL);}
  92         friend ostream &operator<<(ostream&, List<Type>&);
  93         void print();
  94         void add(Type data, void *key);
  95         void add(Type data);
  96         Boolean addUnique(Type data);
  97         Boolean addUnique(Type data, void *key) {
  98             Type temp;
  99
 100             temp = find(key);
 101             if (!temp) {
 102                 add(data, key);
 103                 return(TRUE);
 104             } else {
 105                 return(FALSE);
 106             }
 107         }
 108         Type find(void *key);
 109         Boolean remove(void *key);
 110         int count()     {
 111             int c;
 112             ListItem<Type> *curr;
 113
 114             for (curr=head,c=0; curr; curr=curr->next) c++;
 115             return(c);
 116         }
 117         Type operator *() {
 118             if (head)
 119                 return(head->data);
 120             else
 121                 return((Type) NULL);
 122         }
 123         void operator +=(List<Type> mergee) {
 124             ListItem<Type> *curr;
 125
 126             for (curr=mergee.head; curr; curr=curr->next) {
 127                 add(curr->data, curr->key);
 128             }
 129         }
 130         Type operator ++() {
 131             Type ret = (Type) NULL;
 132             if (head) {
 133                 ret = head->data;
 134                 head = head->next;
 135             }
 136             return(ret);
 137         }
 138         void map (void (*map_function)(const Type item)) {
 139           const ListItem<Type> *temp_ptr = 0;
 140
 141           if (!map_function) return;
 142           for (temp_ptr = head; temp_ptr && temp_ptr->data; temp_ptr = temp_ptr->next)
 143             map_function (temp_ptr->data);
 144         }
 145         void setCurrent() { current = head;}
 146         const Type getCurrent() {
 147           if (current) return ( (const Type) current->data);
 148           else return 0;
 149         }
 150         const Type next() {
 151           advanceCurrent();
 152           return getCurrent();
 153         }
 154         void advanceCurrent() { if (current) current = current->next;}
 155     protected:
 156         ListItem<Type>  *head;
 157         ListItem<Type>  *current;
 158 };
 159
 160 template <class Type> ostream &operator<<(ostream &os, List<Type> &data)
 161 {
 162     List<Type> curr;
 163
 164     for (curr= data; *curr; curr++) {
 165         os << *curr << endl;
 166     }
 167     return os;
 168 }
 169
 170 //
 171 // Warning this function should be replaced by the stream operator above, but
 172 //   g++ is broken and won't create it.
 173 //
 174 template <class Type> void List<Type>::print()
 175 {
 176     ListItem<Type> *curr;
 177
 178     for (curr=head; curr; curr=curr->next) {
 179         cout << (curr->data) << endl;
 180     }
 181 }
 182
 183 template <class Type> void List<Type>::add(Type data, void *key)
 184 {
 185     ListItem<Type> *ni;
 186
 187     ni = new(ListItem<Type>);
 188     ni->data = data;
 189     ni->key = key;
 190
 191     ni->next = head;
 192     head = ni;
 193 }
 194
 195 template <class Type> void List<Type>::add(Type data)
 196 {
 197     add(data, (void *) data);
 198 }
 199
 200 template <class Type> Boolean List<Type>::addUnique(Type data)
 201 {
 202     return(addUnique(data, (void *) data));
 203 }
 204
 205 template <class Type> Boolean List<Type>::remove(void *key)
 206 {
 207     ListItem<Type> *lag;
 208     ListItem<Type> *curr;
 209
 210     for (curr=head, lag = NULL; curr; curr=curr->next) {
 211         if (curr->key == key) {
 212             break;
 213         }
 214         lag = curr;
 215     }
 216
 217     if (curr) {
 218         if (lag) {
 219             lag->next = curr->next;
 220         } else {
 221             head = curr->next;
 222         }
 223         // if the 'current' pointer is this element, advance it
 224         if (current == curr)
 225           advanceCurrent();
 226         delete(curr);
 227         return(TRUE);
 228     } else {
 229         return(FALSE);
 230     }
 231 }
 232
 233 template <class Type> Type List<Type>::find(void *data)
 234 {
 235     ListItem<Type> *curr;
 236
 237     for (curr=head; curr; curr=curr->next) {
 238         if (curr->key == data) {
 239             return(curr->data);
 240         }
 241     }
 242     return((Type) 0);
 243 }
 244
 245 template <class Type> class HTable {
 246
 247     public:
 248         friend ostream &operator<<(ostream&, HTable<Type>&);
 249         void print();
 250         HTable(Type data) { (void) HTable(); add(data, (void *) data); }
 251         void add(Type data, void *key);
 252         HTable();
 253         Boolean addUnique(Type data, void *key) {
 254             Type temp;
 255
 256             temp = find(key);
 257             if (temp ) {
 258                 return(0);
 259             } else {
 260                 add(data, key);
 261                 return(1);
 262             }
 263         }
 264         Type find(void *key);
 265         Boolean remove(void *key);
 266         Type operator =(HTable<Type> arg) {
 267             table = arg.table;
 268             tableSize = arg.tableSize;
 269
 270             // find the first item.
 271             currHid = -1;
 272             (*this)++;
 273         }
 274         Type operator *() {
 275             return(*currList);
 276         }
 277         Type operator ++() {
 278             Type curr;
 279
 280             currList++;
 281             curr = *currList;
 282             if (curr) return(curr);
 283             for (currHid++; currHid < tableSize; currHid++) {
 284                 if (table[currHid]) {
 285                     currList = *table[currHid];
 286                     curr = *currList;
 287                     if (curr) return(curr);
 288                 }
 289             }
 290             return(NULL);
 291         }
 292         int count()     {
 293             int i, total;
 294
 295             total = 0;
 296             for (i=0; i < tableSize; i++) {
 297                 if (table[i]) {
 298                     total += table[i]->count();
 299                 }
 300             }
 301             return(total);
 302         }
 303     private:
 304         List<Type> **table;
 305         List<Type> currList;
 306         int currHid;
 307         int tableSize;
 308 };
 309
 310 template <class Type> ostream &operator<<(ostream &os, HTable<Type> &data)
 311 {
 312     int i, total;
 313
 314     total = 0;
 315     for (i=0; i < data.tableSize; i++) {
 316         if (data.table[i]) {
 317             os << *data.table[i];
 318         }
 319     }
 320     return os;
 321 }
 322
 323
 324 //
 325 // Warning this function should be replaced by the stream operator above, but
 326 //   g++ is broken and won't create it.
 327 //
 328 template <class Type> void HTable<Type>::print()
 329 {
 330     int i, total;
 331
 332     total = 0;
 333     for (i=0; i < tableSize; i++) {
 334         if (table[i]) {
 335             table[i]->print();
 336         }
 337     }
 338 }
 339
 340 template <class Type> HTable<Type>::HTable()
 341 {
 342     table = NULL;
 343     currHid = 0;
 344     tableSize = 0;
 345 }
 346
 347 template <class Type> Type HTable<Type>::find(void *key)
 348 {
 349     int hid;
 350
 351     if (!tableSize) return(NULL);
 352     hid = ListHash(key, tableSize);
 353     if (!table[hid]) {
 354         return(NULL);
 355     } else {
 356         return(table[hid]->find(key));
 357     }
 358 }
 359
 360 template <class Type> void HTable<Type>::add(Type data, void *key)
 361 {
 362     int hid;
 363
 364     if (!tableSize) {
 365         tableSize = 97;
 366         table = (List<Type>**) calloc(tableSize, sizeof(List<Type>*));
 367     }
 368     hid = ListHash(key, tableSize);
 369     if (!table[hid]) {
 370         table[hid] = new(List<Type>);
 371     }
 372     table[hid]->add(data, key);
 373 }
 374
 375
 376 template <class Type> Boolean HTable<Type>::remove(void *key)
 377 {
 378     int hid;
 379
 380     hid = ListHash(key, tableSize);
 381     if (table[hid]) {
 382         return(table[hid]->remove(key));
 383     }
 384     return(FALSE);
 385 }
 386
 387 template <class Type> class StringList: public List<Type> {
 388     public:
 389         Type find(void *key);
 390 };
 391
 392 template <class Type> Type StringList<Type>::find(void *data)
 393 {
 394     ListItem<Type> *curr;
 395
 396     for (curr=head; curr; curr=curr->next) {
 397         if (!strcmp((char *) curr->key, (char *) data)) {
 398             return(curr->data);
 399         }
 400     }
 401     return((Type) 0);
 402 }
 403
 404 #endif /* LIST_H */