added destructor for List class.
[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.5  1993/12/13 20:11:14  hollings
11  * added destructor for List class.
12  *
13  * Revision 1.4  1993/10/19  15:31:52  hollings
14  * assorted small fixes.
15  *
16  * Revision 1.3  1993/08/02  22:46:37  hollings
17  * added remove which was missing.
18  *
19  * Revision 1.2  1993/07/01  17:02:36  hollings
20  * ansi endif comments
21  *
22  * Revision 1.1  1993/05/07  20:21:15  hollings
23  * Initial revision
24  *
25  * Revision 1.1  1993/03/19  22:51:05  hollings
26  * Initial revision
27  *
28  *
29  */
30 #ifndef LIST_H
31 #define LIST_H
32 #include <stdio.h>
33 #include <stdlib.h>
34
35 typedef char Boolean;
36
37 #define FALSE 0
38 #define TRUE  1
39
40 inline static int ListHash(void *ptr, int size)
41 {
42     return(((int)(ptr) % (int)(size)));
43 }
44
45 template <class Type> class List;
46
47 template <class Type> class ListItem {
48     friend class List<Type>;
49     friend class StringList<Type>;
50     private:
51         Type            data;
52         void            *key;
53         ListItem<Type>  *next;
54 };
55
56 template <class Type> class List {
57     public:
58         ~List();
59         List() { head = NULL; }
60         void add(Type data, void *key);
61         void add(Type data) { add(data, (void *) data); }
62         Boolean addUnique(Type data) { return(addUnique(data, (void *) data)); }
63         Boolean addUnique(Type data, void *key) {
64             Type temp;
65
66             temp = find(key);
67             if (!temp) {
68                 add(data, key);
69                 return(TRUE);
70             } else {
71                 return(FALSE);
72             }
73         }
74         Type find(void *key);
75         Boolean remove(void *key);
76         int count()     {
77             int c;
78             ListItem<Type> *curr;
79
80             for (curr=head,c=0; curr; curr=curr->next) c++;
81             return(c);
82         }
83         Type operator *() { 
84             if (head) 
85                 return(head->data); 
86             else
87                 return((Type) NULL);
88         }
89         void operator +=(List<Type> mergee) {
90             ListItem<Type> *curr;
91
92             for (curr=mergee.head; curr; curr=curr->next) {
93                 add(curr->data, curr->key);
94             }
95         }
96         Type operator ++() { 
97             Type ret = (Type) NULL;
98             if (head) {
99                 ret = head->data;
100                 head = head->next; 
101             }
102             return(ret); 
103         }
104     protected:
105         ListItem<Type>  *head;
106 };
107
108 template <class Type> List<Type>::~List()
109 {
110     ListItem<Type> *temp;
111     ListItem<Type> *curr;
112
113     for (curr=head; curr; curr = temp) {
114         temp = curr->next;
115         delete(curr);
116     }
117 }
118
119 template <class Type> void List<Type>::add(Type data, void *key)
120 {
121     ListItem<Type> *ni;
122
123     ni = new(ListItem<Type>);
124     ni->data = data;
125     ni->key = key;
126
127     ni->next = head;
128     head = ni;
129 }
130
131 template <class Type> Boolean List<Type>::remove(void *key)
132 {
133     ListItem<Type> *lag;
134     ListItem<Type> *curr;
135
136     for (curr=head, lag = NULL; curr; curr=curr->next) {
137         if (curr->key == key) {
138             break;
139         }
140         lag = curr;
141     }
142
143     if (curr) {
144         if (lag) {
145             lag->next = curr->next;
146         } else {
147             head = curr->next;
148         }
149         delete(curr);
150         return(TRUE);
151     } else {
152         return(FALSE);
153     }
154 }
155
156 template <class Type> Type List<Type>::find(void *data)
157 {
158     ListItem<Type> *curr;
159
160     for (curr=head; curr; curr=curr->next) {
161         if (curr->key == data) {
162             return(curr->data);
163         }
164     }
165     return((Type) 0);
166 }
167
168 template <class Type> class HTable {
169
170     public:
171         HTable(Type data) { HTable(); add(data, (void *) data); }
172         HTable(); 
173         void add(Type data, void *key);
174         Boolean addUnique(Type data, void *key) {
175             Type temp;
176
177             temp = find(key);
178             if (temp ) {
179                 return(0);
180             } else {
181                 add(data, key);
182                 return(1);
183             }
184         }
185         Type find(void *key);
186         Boolean remove(void *key);
187         Type operator *() {
188             Type curr;
189
190             curr = *currList;
191             if (curr) return(curr);
192             for (currHid++; currHid < tableSize; currHid++) {
193                 if (table[currHid]) {
194                     currList = *table[currHid];
195                     curr = *currList;
196                     if (curr) return(curr);
197                 }
198             }
199             return(NULL);
200         }
201         Type operator ++() {
202             Type curr;
203
204             curr = *currList;
205             currList++;
206             return(curr);
207         }
208         int count()     {
209             int i, total;
210
211             total = 0;
212             for (i=0; i < tableSize; i++) {
213                 if (table[i]) {
214                     total += table[i]->count();
215                 }
216             }
217             return(total);
218         }
219     private:
220         List<Type> **table;
221         List<Type> currList;
222         int currHid;
223         int tableSize;
224 };
225
226 template <class Type> HTable<Type>::HTable()
227
228     table = NULL;
229     currHid = 0;
230     tableSize = 0;
231 }
232
233 template <class Type> Type HTable<Type>::find(void *key)
234 {
235     int hid;
236
237     if (!tableSize) return(NULL);
238     hid = ListHash(key, tableSize);
239     if (!table[hid]) {
240         return(NULL);
241     } else {
242         return(table[hid]->find(key));
243     }
244 }
245
246 template <class Type> void HTable<Type>::add(Type data, void *key)
247 {
248     int hid;
249
250     if (!tableSize) {
251         tableSize = 97;
252         table = (List<Type>**) calloc(tableSize, sizeof(List<Type>*));
253     }
254     hid = ListHash(key, tableSize);
255     if (!table[hid]) {
256         table[hid] = new(List<Type>);
257     }
258     table[hid]->add(data, key);
259 }
260
261
262 template <class Type> Boolean HTable<Type>::remove(void *key)
263 {
264     int hid;
265
266     hid = ListHash(key, tableSize);
267     if (table[hid]) {
268         return(table[hid]->remove(key));
269     }
270     return(FALSE);
271 }
272
273 template <class Type> class StringList: public List<Type> {
274     public:
275         Type find(void *key);
276 };
277
278 template <class Type> Type StringList<Type>::find(void *data) 
279 {
280     ListItem<Type> *curr;
281
282     for (curr=head; curr; curr=curr->next) {
283         if (!strcmp((char *) curr->key, (char *) data)) {
284             return(curr->data);
285         }
286     }
287     return((Type) 0);
288 }
289
290 #endif /* LIST_H */