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