src/main/print-list.c

2  * "$Id: print-list.c,v 1.25 2010/08/04 00:33:57 rlk Exp $"
4  *   Gutenprint list functions.  A doubly-linked list implementation,
41 /** The internal representation of an stp_list_item_t list node. */
49 /** The internal representation of an stp_list_t list. */
69  * Cache a list node by its short name.
70  * @param list the list to use.
75 set_name_cache(stp_list_t *list,
79   if (list->name_cache)
80     stp_free(list->name_cache);
81   list->name_cache = NULL;
83     list->name_cache = stp_strdup(name);
84   list->name_cache_node = cache;
88  * Cache a list node by its long name.
89  * @param list the list to use.
94 set_long_name_cache(stp_list_t *list,
98   if (list->long_name_cache)
99     stp_free(list->long_name_cache);
100   list->long_name_cache = NULL;
102     list->long_name_cache = stp_strdup(long_name);
103   list->long_name_cache_node = cache;
108  * @param list the list to use.
111 clear_cache(stp_list_t *list)
113   list->index_cache = 0;
114   list->index_cache_node = NULL;
115   set_name_cache(list, NULL, NULL);
116   set_long_name_cache(list, NULL, NULL);
126 /** Check the validity of a list. */
130  * These functions operate on the list as a whole, and not the
131  * individual nodes in a list. */
133 /* create a new list */
137   stp_list_t *list =
140   /* initialise an empty list */
141   list->index_cache = 0;
142   list->length = 0;
143   list->start = NULL;
144   list->end = NULL;
145   list->index_cache_node = NULL;
146   list->freefunc = NULL;
147   list->namefunc = NULL;
148   list->long_namefunc = NULL;
149   list->sortfunc = NULL;
150   list->copyfunc = NULL;
151   list->name_cache = NULL;
152   list->name_cache_node = NULL;
153   list->long_name_cache = NULL;
154   list->long_name_cache_node = NULL;
157   return list;
161 stp_list_copy(const stp_list_t *list)
164   stp_node_copyfunc copyfunc = stp_list_get_copyfunc(list);
165   stp_list_item_t *item = list->start;
167   check_list(list);
170   stp_list_set_copyfunc(ret, stp_list_get_copyfunc(list));
172   if (stp_list_get_copyfunc(list))
173     stp_list_set_freefunc(ret, stp_list_get_freefunc(list));
174   stp_list_set_namefunc(ret, stp_list_get_namefunc(list));
175   stp_list_set_long_namefunc(ret, stp_list_get_long_namefunc(list));
176   stp_list_set_sortfunc(ret, stp_list_get_sortfunc(list));
189 /* free a list, freeing all child nodes first */
191 stp_list_destroy(stp_list_t *list)
196   check_list(list);
197   clear_cache(list);
198   cur = list->start;
202       stp_list_item_destroy(list, cur);
206   stp_free(list);
212 stp_list_get_length(const stp_list_t *list)
214   check_list(list);
215   return list->length;
220 /* get the first node in the list */
223 stp_list_get_start(const stp_list_t *list)
225   return list->start;
228 /* get the last node in the list */
231 stp_list_get_end(const stp_list_t *list)
233   return list->end;
237 deconst_list(const stp_list_t *list)
239   return (stp_list_t *) list;
242 /* get the node by its place in the list */
244 stp_list_get_item_by_index(const stp_list_t *list, int idx)
247   stp_list_t *ulist = deconst_list(list);
249   int d = 0; /* direction of list traversal, 0=forward */
251   check_list(list);
253   if (idx >= list->length)
257   if (list->index_cache)
259       if (idx < (list->length/2))
261 	  if (idx > abs(idx - list->index_cache))
268 	  if (list->length - 1 - idx >
269 	      abs (list->length - 1 - idx - list->index_cache))
279       if (idx > list->index_cache) /* forward */
283       i = list->index_cache;
284       node = list->index_cache_node;
286   else /* start from one end of the list */
290 	  i = list->length - 1;
291 	  node = list->end;
296 	  node = list->start;
322  * Find an item in a list by its name.
324  * @param list the list to use.
326  * @returns a pointer to the list item, or NULL if the name is
327  * invalid or the list is empty.
330 stp_list_get_item_by_name_internal(const stp_list_t *list, const char *name)
332   stp_list_item_t *node = list->start;
333   while (node && strcmp(name, list->namefunc(node->data)))
343 stp_list_get_item_by_name(const stp_list_t *list, const char *name)
346   stp_list_t *ulist = deconst_list(list);
347   check_list(list);
349   if (!list->namefunc)
352   if (list->name_cache && name && list->name_cache_node)
355       node = list->name_cache_node;
357       if (strcmp(name, list->name_cache) == 0 &&
358 	  strcmp(name, list->namefunc(node->data)) == 0)
361       /* If not, check the next item in case we're searching the list */
365 	  new_name = list->namefunc(node->data);
373       node = list->index_cache_node;
376 	  new_name = list->namefunc(node->data);
385   node = stp_list_get_item_by_name_internal(list, name);
395  * Find an item in a list by its long name.
397  * @param list the list to use.
399  * @returns a pointer to the list item, or NULL if the long name is
400  * invalid or the list is empty.
403 stp_list_get_item_by_long_name_internal(const stp_list_t *list,
406   stp_list_item_t *node = list->start;
407   while (node && strcmp(long_name, list->long_namefunc(node->data)))
417 stp_list_get_item_by_long_name(const stp_list_t *list, const char *long_name)
420   stp_list_t *ulist = deconst_list(list);
421   check_list(list);
423   if (!list->long_namefunc)
426   if (list->long_name_cache && long_name && list->long_name_cache_node)
429       node = list->long_name_cache_node;
431       if (strcmp(long_name, list->long_name_cache) == 0 &&
432 	  strcmp(long_name, list->long_namefunc(node->data)) == 0)
435       /* If not, check the next item in case we're searching the list */
439 	  new_long_name = list->long_namefunc(node->data);
447       node = list->index_cache_node;
450 	  new_long_name = list->long_namefunc(node->data);
459   node = stp_list_get_item_by_long_name_internal(list, long_name);
470 stp_list_set_freefunc(stp_list_t *list, stp_node_freefunc freefunc)
472   check_list(list);
473   list->freefunc = freefunc;
477 stp_list_get_freefunc(const stp_list_t *list)
479   check_list(list);
480   return list->freefunc;
485 stp_list_set_copyfunc(stp_list_t *list, stp_node_copyfunc copyfunc)
487   check_list(list);
488   list->copyfunc = copyfunc;
492 stp_list_get_copyfunc(const stp_list_t *list)
494   check_list(list);
495   return list->copyfunc;
500 stp_list_set_namefunc(stp_list_t *list, stp_node_namefunc namefunc)
502   check_list(list);
503   list->namefunc = namefunc;
507 stp_list_get_namefunc(const stp_list_t *list)
509   check_list(list);
510   return list->namefunc;
515 stp_list_set_long_namefunc(stp_list_t *list, stp_node_namefunc long_namefunc)
517   check_list(list);
518   list->long_namefunc = long_namefunc;
522 stp_list_get_long_namefunc(const stp_list_t *list)
524   check_list(list);
525   return list->long_namefunc;
530 stp_list_set_sortfunc(stp_list_t *list, stp_node_sortfunc sortfunc)
532   check_list(list);
533   list->sortfunc = sortfunc;
537 stp_list_get_sortfunc(const stp_list_t *list)
539   check_list(list);
540   return list->sortfunc;
544 /* list item functions */
546 /* these functions operate on individual nodes in a list */
549  * create a new node in list, before next (may be null e.g. if sorting
553  * stp_list_t list head.
556 stp_list_item_create(stp_list_t *list,
560   stp_list_item_t *ln; /* list node to add */
561   stp_list_item_t *lnn; /* list node next */
563   check_list(list);
565   clear_cache(list);
578   if (list->sortfunc)
581       lnn = list->end;
584 	  if (list->sortfunc(lnn->data, ln->data) <= 0)
599 	  lnn = list->start;
619   if (!ln->prev) /* insert at start of list */
621       if (list->start) /* list not empty */
622 	ln->prev = list->end;
624 	list->start = ln;
625       list->end = ln;
628   /* set prev (already set if at start of list) */
630   if (!ln->prev && ln->next) /* insert at end of list */
633   if (list->start == ln->next) /* prev was old end */
635       list->start = ln;
647   list->length++;
653 /* remove a node from list */
655 stp_list_item_destroy(stp_list_t *list, stp_list_item_t *item)
657   check_list(list);
659   clear_cache(list);
661   list->length--;
663   if (list->freefunc)
664     list->freefunc((void *) item->data);
668     list->start = item->next;
672     list->end = item->prev;