1/*
2	Copyright 1999, Be Incorporated.   All Rights Reserved.
3	This file may be used under the terms of the Be Sample Code License.
4*/
5
6#ifndef UTIL_H
7#define UTIL_H
8
9#include <memory.h>
10#include <stdlib.h>
11#include "error.h"
12
13template <class contents>
14struct LispNode {
15	contents* car;
16	LispNode* cdr;
17
18	/* Create a node with no next */
19	inline LispNode(contents* value)
20		: car(value), cdr(0) { }
21
22	/* Create a node with specified next */
23	inline LispNode(contents* value, LispNode* next)
24 		: car (value), cdr(next) { }
25
26	/* Create a node and insert it in a list right after `prev' */
27	inline LispNode(LispNode* prev, contents* value)
28		: car(value), cdr(prev->cdr) { prev->cdr = this; }
29};
30
31
32template <class contents>
33struct LispList {
34	LispNode<contents> *first;
35
36	/* -------- List creation --------------- */
37	/* Create an empty list */
38	inline LispList()
39	{
40		first = 0;
41	}
42
43
44	/* Create a list pointing to the specified node */
45	inline LispList(LispNode<contents>* _first)
46	{
47		first = _first;
48	}
49
50
51	/* ?? */
52	inline LispList(LispList &init)
53	{
54		first = init.first;
55	}
56
57
58	/* ---------- List queries ------------- */
59	inline int is_empty()
60	{
61		return first == 0;
62	}
63
64
65	/* Determines if a thing is on the list */
66	inline int is_present(contents* element)
67	{
68		for (LispNode<contents>* node = first; node; node = node->cdr)
69			if (node->car == element)
70				return 1;
71		return 0;
72	}
73
74
75	/* Returns the length of the list */
76	inline int count()
77	{
78		int n = 0;
79		for (LispNode<contents>* node = first; node; node = node->cdr)
80			n++;
81	    return n;
82	}
83
84
85	/* ----------- Adding "nodes" to the list ------------ */
86	/* Add a specified node to the head of the list.  */
87	inline void add_head(LispNode<contents>* new_element)
88	{
89		new_element->cdr = first;
90		first = new_element;
91	}
92
93
94	/* Add a specified node anywhere on the list */
95	inline void add(LispNode<contents>* new_element)
96	{
97		add_head (new_element);
98	}
99
100
101	inline void add_tail(LispNode<contents>* new_element)
102	{
103		LispNode<contents>** pred = &first;
104		while(*pred)
105			pred = &(*pred)->cdr;
106		*pred = new_element;
107		new_element->cdr = 0;
108	}
109
110
111	/* ----------- Adding "contents" to the list ------------ */
112	/* -----  (Which in my opinion is far more useful) ------ */
113
114	/* Create new node pointing to thing, & add to head of list. */
115	inline void add_head_new(contents* new_element)
116	{
117		first = new LispNode<contents>(new_element, first);
118	}
119
120
121	inline void add_head(contents* new_element)
122	{
123		add_head_new(new_element);
124	}
125
126
127	/* Create new node pointing to thing, & add to end of list. */
128	inline void add_tail_new(contents* new_element)
129	{
130		LispNode< contents >** pred = &first;
131		while (*pred)
132			pred = &(*pred)->cdr;
133
134		*pred = new LispNode< contents >(new_element);
135	}
136
137
138	inline void add_tail(contents* new_element)
139	{
140		add_tail_new(new_element);
141	}
142
143
144	/* Create new node pointing to thing, & add anywhere on list */
145	inline void add_new(contents* new_element)
146	{
147		add_head_new(new_element);
148	}
149
150
151	inline void add(contents* new_element)
152	{
153		add_new(new_element);
154	}
155
156
157	/* Create and add a new node for a specified element,
158		but only if it's not already on the list.  */
159	inline void add_new_once(contents* new_element)
160	{
161		if (!is_present(new_element))
162			add_head_new(new_element);
163	}
164
165
166	inline void add_tail_once(contents *new_element)
167	{
168		if (!is_present(new_element))
169			add_tail_new(new_element);
170	}
171
172
173	/* ------- Removing things from the list ------------ */
174
175	/* Remove and return the first node on the list j.h. */
176	inline LispNode<contents>* rem_head ()
177	{
178		LispNode<contents>* n = first;
179
180		if (n) {
181			first = first->cdr;
182		}
183
184		return n;
185	}
186
187
188	/* Remove and return any node on the list.  */
189	inline LispNode<contents>* remove ()
190	{
191		return( rem_head() );
192	}
193
194
195	/* Remove a specified node from the list.  */
196	inline void remove (LispNode<contents>* node)
197	{
198		for (LispNode<contents> **pp = &first; *pp; pp = &(*pp)->cdr)
199			if (*pp == node) {
200				*pp = (*pp)->cdr;
201		  		return;
202			}
203	}
204
205
206	/* Remove & delete all nodes pointing to a particular element. */
207	inline void rem_del (contents* element)
208	{
209		LispNode<contents>** pp = &first;
210		while (*pp) {
211			if ((*pp)->car == element) {
212				LispNode<contents> *o = *pp;
213				*pp = o->cdr;
214				delete o;
215			} else
216				pp = &(*pp)->cdr;
217		}
218	}
219
220
221	/* Remove and delete all nodes on the list.  */
222	inline void rem_del_all()
223	{
224		while (first) {
225			LispNode<contents>* old = first;
226			first = first->cdr;
227			delete old;
228		}
229	}
230
231
232	/* -------- Simple list storage (by j.h.) ------------ */
233
234	/* When you just want to hold a bunch of stuff on a list and then pull them
235		off later.  Note that these calls do NOT check for to see if a thing is
236		already on the list.  Use is_present() before adding.
237	*/
238	/* Put something anywhere on the list */
239	inline void put( contents* c )
240	{
241		add_tail( c );
242	}
243
244
245	/* Put something at beginning of list */
246	inline void put_head( contents* c )
247	{
248		add_head( c );
249	}
250
251
252	/* Put something at end of the list */
253	inline void put_tail( contents* c )
254	{
255		add_tail( c );
256	}
257
258#if 0 /* leaks memory */
259	  /* Take a specific thing off the list */
260	  inline contents *get(contents *element)
261	    {
262	      contents *c = 0;
263	      for (LispNode<contents> *node = first; node; node = node->cdr)
264	      {
265		if (node->car == element)
266		{
267		  c = node->car;
268		  remove(node);
269		  break;
270		}
271	      }
272	      return c;
273	    }
274#endif
275
276	/* Take the first thing off the list */
277	inline contents* get_head()
278	{
279		contents *c = 0;
280		if(first) {
281			c = first->car;
282			delete rem_head();
283		}
284		return c;
285	}
286
287
288	/* Take something off the list */
289	inline contents* get()
290	{
291		return(get_head());
292	}
293
294
295	/* XXX inline contents *get_tail() { } */
296
297/* -------- Stack simulation (by j.h.) ------------ */
298	/* Put a thing onto the head of the list */
299	inline void push(contents* c)
300	{
301		put_head(c);
302	}
303
304
305	/* Remove a thing from the head of the list */
306	inline contents* pop()
307	{
308		return(get_head());
309	}
310
311	/* Pop everything off the stack.  Empty the stack/list. */
312	inline void pop_all()
313	{
314		rem_del_all();
315	}
316
317
318	/* ----------- list/list manipulations ------------ */
319
320	/* Add all elements present on another list to this list also. */
321	inline void add_new(LispList other)
322	{
323		for (LispNode<contents>* n = other.first; n; n = n->cdr)
324			add_new(n->car);
325	}
326
327
328	inline void add_new_once(LispList other)
329	{
330		for (LispNode<contents>* n = other.first; n; n = n->cdr)
331			add_new_once(n->car);
332	}
333
334
335	/* Remove and delete all nodes whose contents are also present
336	   in a different list (set disjunction). */
337	inline void rem_del(LispList other)
338	{
339		for (LispNode<contents>* n = other.first; n; n = n->cdr)
340			rem_del(n->car);
341	}
342};
343
344template <class thetype>
345struct DoubleLinkedNode
346{
347	thetype* next;
348	thetype* prev;
349
350	DoubleLinkedNode()
351	{
352		next = prev = NULL;
353	}
354
355
356	void insert_after(thetype* n)
357	{
358		if (next != NULL)
359			next->prev = n;
360
361		n->next = next;
362		n->prev = (thetype*)this;
363		next = n;
364	}
365
366
367	void insert_before(thetype* n)
368	{
369		prev->next = n;
370		n->next = (thetype*)this;
371		n->prev = prev;
372		prev = n;
373	}
374
375
376	void remove()
377	{
378		assert(prev != NULL);
379		prev->next = next;
380
381		if (next != NULL)
382			next->prev = prev;
383	}
384};
385
386
387template <class thetype>
388struct DoubleLinkedList : public DoubleLinkedNode<thetype>
389{
390	DoubleLinkedList() : DoubleLinkedNode<thetype>() {};
391
392	void insert(thetype* n)
393	{
394		insert_after(n);
395	}
396
397
398	void add(thetype* n)
399	{
400		insert_after(n);
401	}
402};
403
404
405template <class T>
406struct BufferArray {
407	T * items;
408	int num_items;
409	int num_slots;
410	int slot_inc;
411
412	void resize(int i)
413	{
414		items = (T*)realloc(items,sizeof(T)*i);
415		num_slots = i;
416	}
417
418
419	T & operator [](int index)
420	{
421		assert(index < num_items);
422		return items[index];
423	}
424
425
426	T & get(int index)
427	{
428		assert(index < num_items);
429		return items[index];
430	}
431
432
433	void add(T &item)
434	{
435		if (num_items == num_slots)
436			resize(num_slots+slot_inc);
437
438		memcpy(items+num_items,&item,sizeof(item));
439		num_items++;
440	}
441
442
443	BufferArray(int start_slots, int _slot_inc)
444	{
445		num_slots = start_slots;
446		slot_inc = _slot_inc;
447		assert(slot_inc > 0);
448		num_items = 0;
449		items = (T*)malloc(sizeof(T)*num_slots);
450	}
451
452
453	~BufferArray()
454	{
455		free(items);
456	}
457};
458
459#endif // UTIL_H
460