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