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