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