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