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