1/* -----------------------------------------------------------------------------
2 * list.c
3 *
4 *     Implements a simple list object.
5 *
6 * Author(s) : David Beazley (beazley@cs.uchicago.edu)
7 *
8 * Copyright (C) 1999-2000.  The University of Chicago
9 * See the file LICENSE for information on usage and redistribution.
10 * ----------------------------------------------------------------------------- */
11
12char cvsroot_list_c[] = "$Id: list.c 10926 2008-11-11 22:17:40Z wsfulton $";
13
14#include "dohint.h"
15
16typedef struct List {
17  int maxitems;			/* Max size  */
18  int nitems;			/* Num items */
19  DOH *file;
20  int line;
21  DOH **items;
22} List;
23
24extern DohObjInfo DohListType;
25
26/* Doubles amount of memory in a list */
27static
28void more(List *l) {
29  l->items = (void **) DohRealloc(l->items, l->maxitems * 2 * sizeof(void *));
30  assert(l->items);
31  l->maxitems *= 2;
32}
33
34/* -----------------------------------------------------------------------------
35 * CopyList()
36 *
37 * Make a shallow copy of a list.
38 * ----------------------------------------------------------------------------- */
39static DOH *CopyList(DOH *lo) {
40  List *l, *nl;
41  int i;
42  l = (List *) ObjData(lo);
43  nl = (List *) DohMalloc(sizeof(List));
44  nl->nitems = l->nitems;
45  nl->maxitems = l->maxitems;
46  nl->items = (void **) DohMalloc(l->maxitems * sizeof(void *));
47  for (i = 0; i < l->nitems; i++) {
48    nl->items[i] = l->items[i];
49    Incref(nl->items[i]);
50  }
51  nl->file = l->file;
52  if (nl->file)
53    Incref(nl->file);
54  nl->line = l->line;
55  return DohObjMalloc(&DohListType, nl);
56}
57
58/* -----------------------------------------------------------------------------
59 * DelList()
60 *
61 * Delete a list.
62 * ----------------------------------------------------------------------------- */
63
64static void DelList(DOH *lo) {
65  List *l = (List *) ObjData(lo);
66  int i;
67  for (i = 0; i < l->nitems; i++)
68    Delete(l->items[i]);
69  DohFree(l->items);
70  DohFree(l);
71}
72
73/* -----------------------------------------------------------------------------
74 * List_clear()
75 *
76 * Remove all of the list entries, but keep the list object intact.
77 * ----------------------------------------------------------------------------- */
78
79static void List_clear(DOH *lo) {
80  List *l = (List *) ObjData(lo);
81  int i;
82  for (i = 0; i < l->nitems; i++) {
83    Delete(l->items[i]);
84  }
85  l->nitems = 0;
86}
87
88/* -----------------------------------------------------------------------------
89 * List_insert()
90 *
91 * Insert an item into the list. If the item is not a DOH object, it is assumed
92 * to be a 'char *' and is used to construct an equivalent string object.
93 * ----------------------------------------------------------------------------- */
94
95static int List_insert(DOH *lo, int pos, DOH *item) {
96  List *l = (List *) ObjData(lo);
97  int i;
98
99  if (!item)
100    return -1;
101  if (!DohCheck(item)) {
102    item = NewString(item);
103    Decref(item);
104  }
105  if (pos == DOH_END)
106    pos = l->nitems;
107  if (pos < 0)
108    pos = 0;
109  if (pos > l->nitems)
110    pos = l->nitems;
111  if (l->nitems == l->maxitems)
112    more(l);
113  for (i = l->nitems; i > pos; i--) {
114    l->items[i] = l->items[i - 1];
115  }
116  l->items[pos] = item;
117  Incref(item);
118  l->nitems++;
119  return 0;
120}
121
122/* -----------------------------------------------------------------------------
123 * List_remove()
124 *
125 * Remove an item from a list.
126 * ----------------------------------------------------------------------------- */
127
128static int List_remove(DOH *lo, int pos) {
129  List *l = (List *) ObjData(lo);
130  int i;
131  if (pos == DOH_END)
132    pos = l->nitems - 1;
133  if (pos == DOH_BEGIN)
134    pos = 0;
135  assert(!((pos < 0) || (pos >= l->nitems)));
136  Delete(l->items[pos]);
137  for (i = pos; i < l->nitems - 1; i++) {
138    l->items[i] = l->items[i + 1];
139  }
140  l->nitems--;
141  return 0;
142}
143
144/* -----------------------------------------------------------------------------
145 * List_len()
146 *
147 * Return the number of elements in the list
148 * ----------------------------------------------------------------------------- */
149
150static int List_len(DOH *lo) {
151  List *l = (List *) ObjData(lo);
152  return l->nitems;
153}
154
155/* -----------------------------------------------------------------------------
156 * List_get()
157 *
158 * Get the nth item from the list.
159 * ----------------------------------------------------------------------------- */
160
161static DOH *List_get(DOH *lo, int n) {
162  List *l = (List *) ObjData(lo);
163  if (n == DOH_END)
164    n = l->nitems - 1;
165  if (n == DOH_BEGIN)
166    n = 0;
167  assert(!((n < 0) || (n >= l->nitems)));
168  return l->items[n];
169}
170
171/* -----------------------------------------------------------------------------
172 * List_set()
173 *
174 * Set the nth item in the list replacing any previous item.
175 * ----------------------------------------------------------------------------- */
176
177static int List_set(DOH *lo, int n, DOH *val) {
178  List *l = (List *) ObjData(lo);
179  if (!val)
180    return -1;
181  assert(!((n < 0) || (n >= l->nitems)));
182  if (!DohCheck(val)) {
183    val = NewString(val);
184    Decref(val);
185  }
186  Delete(l->items[n]);
187  l->items[n] = val;
188  Incref(val);
189  Delete(val);
190  return 0;
191}
192
193/* -----------------------------------------------------------------------------
194 * List_first()
195 *
196 * Return the first item in the list.
197 * ----------------------------------------------------------------------------- */
198
199static DohIterator List_first(DOH *lo) {
200  DohIterator iter;
201  List *l = (List *) ObjData(lo);
202  iter.object = lo;
203  iter._index = 0;
204  iter._current = 0;
205  iter.key = 0;
206  if (l->nitems > 0) {
207    iter.item = l->items[0];
208  } else {
209    iter.item = 0;
210  }
211  return iter;
212}
213
214/* -----------------------------------------------------------------------------
215 * List_next()
216 *
217 * Return the next item in the list.
218 * ----------------------------------------------------------------------------- */
219
220static DohIterator List_next(DohIterator iter) {
221  List *l = (List *) ObjData(iter.object);
222  iter._index = iter._index + 1;
223  if (iter._index >= l->nitems) {
224    iter.item = 0;
225    iter.key = 0;
226  } else {
227    iter.item = l->items[iter._index];
228  }
229  return iter;
230}
231
232/* -----------------------------------------------------------------------------
233 * List_str()
234 *
235 * Create a string representation of the list.
236 * ----------------------------------------------------------------------------- */
237static DOH *List_str(DOH *lo) {
238  DOH *s;
239  int i;
240  List *l = (List *) ObjData(lo);
241  s = NewStringEmpty();
242  if (ObjGetMark(lo)) {
243    Printf(s, "List(%x)", lo);
244    return s;
245  }
246  ObjSetMark(lo, 1);
247  Printf(s, "List[ ");
248  for (i = 0; i < l->nitems; i++) {
249    Printf(s, "%s", l->items[i]);
250    if ((i + 1) < l->nitems)
251      Printf(s, ", ");
252  }
253  Printf(s, " ]\n");
254  ObjSetMark(lo, 0);
255  return s;
256}
257
258/* -----------------------------------------------------------------------------
259 * List_dump()
260 *
261 * Dump the items to an output stream.
262 * ----------------------------------------------------------------------------- */
263
264static int List_dump(DOH *lo, DOH *out) {
265  int nsent = 0;
266  int i, ret;
267  List *l = (List *) ObjData(lo);
268  for (i = 0; i < l->nitems; i++) {
269    ret = Dump(l->items[i], out);
270    if (ret < 0)
271      return -1;
272    nsent += ret;
273  }
274  return nsent;
275}
276
277static void List_setfile(DOH *lo, DOH *file) {
278  DOH *fo;
279  List *l = (List *) ObjData(lo);
280
281  if (!DohCheck(file)) {
282    fo = NewString(file);
283    Decref(fo);
284  } else
285    fo = file;
286  Incref(fo);
287  Delete(l->file);
288  l->file = fo;
289}
290
291static DOH *List_getfile(DOH *lo) {
292  List *l = (List *) ObjData(lo);
293  return l->file;
294}
295
296static void List_setline(DOH *lo, int line) {
297  List *l = (List *) ObjData(lo);
298  l->line = line;
299}
300
301static int List_getline(DOH *lo) {
302  List *l = (List *) ObjData(lo);
303  return l->line;
304}
305
306static DohListMethods ListListMethods = {
307  List_get,
308  List_set,
309  List_remove,
310  List_insert,
311  0,				/* delslice */
312};
313
314DohObjInfo DohListType = {
315  "List",			/* objname */
316  DelList,			/* doh_del */
317  CopyList,			/* doh_copy */
318  List_clear,			/* doh_clear */
319  List_str,			/* doh_str */
320  0,				/* doh_data */
321  List_dump,			/* doh_dump */
322  List_len,			/* doh_len */
323  0,				/* doh_hash    */
324  0,				/* doh_cmp */
325  0,				/* doh_equal    */
326  List_first,			/* doh_first    */
327  List_next,			/* doh_next     */
328  List_setfile,			/* doh_setfile */
329  List_getfile,			/* doh_getfile */
330  List_setline,			/* doh_setline */
331  List_getline,			/* doh_getline */
332  0,				/* doh_mapping */
333  &ListListMethods,		/* doh_sequence */
334  0,				/* doh_file */
335  0,				/* doh_string */
336  0,				/* doh_callable */
337  0,				/* doh_position */
338};
339
340/* -----------------------------------------------------------------------------
341 * NewList()
342 *
343 * Create a new list.
344 * ----------------------------------------------------------------------------- */
345
346#define MAXLISTITEMS 8
347
348DOH *DohNewList(void) {
349  List *l;
350  int i;
351  l = (List *) DohMalloc(sizeof(List));
352  l->nitems = 0;
353  l->maxitems = MAXLISTITEMS;
354  l->items = (void **) DohMalloc(l->maxitems * sizeof(void *));
355  for (i = 0; i < MAXLISTITEMS; i++) {
356    l->items[i] = 0;
357  }
358  l->file = 0;
359  l->line = 0;
360  return DohObjMalloc(&DohListType, l);
361}
362
363static int (*List_sort_compare_func) (const DOH *, const DOH *);
364static int List_qsort_compare(const void *a, const void *b) {
365  return List_sort_compare_func(*((DOH **) a), *((DOH **) b));
366}
367
368/* Sort a list */
369void DohSortList(DOH *lo, int (*cmp) (const DOH *, const DOH *)) {
370  List *l = (List *) ObjData(lo);
371  if (cmp) {
372    List_sort_compare_func = cmp;
373  } else {
374    List_sort_compare_func = DohCmp;
375  }
376  qsort(l->items, l->nitems, sizeof(DOH *), List_qsort_compare);
377}
378