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