added pragma for external g++ functions.
[dyninst.git] / 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 */