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