1/*
2 * "$Id: print-list.c,v 1.25 2010/08/04 00:33:57 rlk Exp $"
3 *
4 *   Gutenprint list functions.  A doubly-linked list implementation,
5 *   with callbacks for freeing, sorting, and retrieving nodes by name
6 *   or long name.
7 *
8 *   Copyright 2002 Roger Leigh (rleigh@debian.org)
9 *
10 *   This program is free software; you can redistribute it and/or modify it
11 *   under the terms of the GNU General Public License as published by the Free
12 *   Software Foundation; either version 2 of the License, or (at your option)
13 *   any later version.
14 *
15 *   This program is distributed in the hope that it will be useful, but
16 *   WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
17 *   or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
18 *   for more details.
19 *
20 *   You should have received a copy of the GNU General Public License
21 *   along with this program; if not, write to the Free Software
22 *   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
23 */
24
25/*
26 * This file must include only standard C header files.  The core code must
27 * compile on generic platforms that don't support glib, gimp, etc.
28 */
29
30
31#ifdef HAVE_CONFIG_H
32#include <config.h>
33#endif
34#include <gutenprint/gutenprint.h>
35#include "gutenprint-internal.h"
36#include <gutenprint/gutenprint-intl-internal.h>
37#include <stdlib.h>
38#include <stdio.h>
39#include <string.h>
40
41/** The internal representation of an stp_list_item_t list node. */
42struct stp_list_item
43{
44  void *data;			/*!< Data		*/
45  struct stp_list_item *prev;	/*!< Previous node	*/
46  struct stp_list_item *next;	/*!< Next node		*/
47};
48
49/** The internal representation of an stp_list_t list. */
50struct stp_list
51{
52  int index_cache;				/*!< Cached node index			*/
53  struct stp_list_item *start;			/*!< Start node				*/
54  struct stp_list_item *end;			/*!< End node				*/
55  struct stp_list_item *index_cache_node;	/*!< Cached node (for index)		*/
56  int length;					/*!< Number of nodes			*/
57  stp_node_freefunc freefunc;			/*!< Callback to free node data		*/
58  stp_node_copyfunc copyfunc;			/*!< Callback to copy node		*/
59  stp_node_namefunc namefunc;			/*!< Callback to get node name		*/
60  stp_node_namefunc long_namefunc;		/*!< Callback to get node long name	*/
61  stp_node_sortfunc sortfunc;			/*!< Callback to compare (sort) nodes	*/
62  char *name_cache;				/*!< Cached name			*/
63  struct stp_list_item *name_cache_node;	/*!< Cached node (for name)		*/
64  char *long_name_cache;			/*!< Cached long name			*/
65  struct stp_list_item *long_name_cache_node;	/*!< Cached node (for long name)	*/
66};
67
68/**
69 * Cache a list node by its short name.
70 * @param list the list to use.
71 * @param name the short name.
72 * @param cache the node to cache.
73 */
74static void
75set_name_cache(stp_list_t *list,
76	       const char *name,
77	       stp_list_item_t *cache)
78{
79  if (list->name_cache)
80    stp_free(list->name_cache);
81  list->name_cache = NULL;
82  if (name)
83    list->name_cache = stp_strdup(name);
84  list->name_cache_node = cache;
85}
86
87/**
88 * Cache a list node by its long name.
89 * @param list the list to use.
90 * @param long_name the long name.
91 * @param cache the node to cache.
92 */
93static void
94set_long_name_cache(stp_list_t *list,
95		    const char *long_name,
96		    stp_list_item_t *cache)
97{
98  if (list->long_name_cache)
99    stp_free(list->long_name_cache);
100  list->long_name_cache = NULL;
101  if (long_name)
102    list->long_name_cache = stp_strdup(long_name);
103  list->long_name_cache_node = cache;
104}
105
106/**
107 * Clear cached nodes.
108 * @param list the list to use.
109 */
110static inline void
111clear_cache(stp_list_t *list)
112{
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);
117}
118
119void
120stp_list_node_free_data (void *item)
121{
122  stp_free(item);
123  stp_deprintf(STP_DBG_LIST, "stp_list_node_free_data destructor\n");
124}
125
126/** Check the validity of a list. */
127#define check_list(List) STPI_ASSERT(List != NULL, NULL)
128
129/* List head functions.
130 * These functions operate on the list as a whole, and not the
131 * individual nodes in a list. */
132
133/* create a new list */
134stp_list_t *
135stp_list_create(void)
136{
137  stp_list_t *list =
138    stp_malloc(sizeof(stp_list_t));
139
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;
155
156  stp_deprintf(STP_DBG_LIST, "stp_list_head constructor\n");
157  return list;
158}
159
160stp_list_t *
161stp_list_copy(const stp_list_t *list)
162{
163  stp_list_t *ret;
164  stp_node_copyfunc copyfunc = stp_list_get_copyfunc(list);
165  stp_list_item_t *item = list->start;
166
167  check_list(list);
168
169  ret = stp_list_create();
170  stp_list_set_copyfunc(ret, stp_list_get_copyfunc(list));
171  /* If we use default (shallow) copy, we can't free the elements of it */
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));
177  while (item)
178    {
179      void *data = item->data;
180      if (copyfunc)
181	stp_list_item_create (ret, NULL, (*copyfunc)(data));
182      else
183	stp_list_item_create(ret, NULL, data);
184      item = stp_list_item_next(item);
185    }
186  return ret;
187}
188
189/* free a list, freeing all child nodes first */
190int
191stp_list_destroy(stp_list_t *list)
192{
193  stp_list_item_t *cur;
194  stp_list_item_t *next;
195
196  check_list(list);
197  clear_cache(list);
198  cur = list->start;
199  while(cur)
200    {
201      next = cur->next;
202      stp_list_item_destroy(list, cur);
203      cur = next;
204    }
205  stp_deprintf(STP_DBG_LIST, "stp_list_head destructor\n");
206  stp_free(list);
207
208  return 0;
209}
210
211int
212stp_list_get_length(const stp_list_t *list)
213{
214  check_list(list);
215  return list->length;
216}
217
218/* find a node */
219
220/* get the first node in the list */
221
222stp_list_item_t *
223stp_list_get_start(const stp_list_t *list)
224{
225  return list->start;
226}
227
228/* get the last node in the list */
229
230stp_list_item_t *
231stp_list_get_end(const stp_list_t *list)
232{
233  return list->end;
234}
235
236static inline stp_list_t *
237deconst_list(const stp_list_t *list)
238{
239  return (stp_list_t *) list;
240}
241
242/* get the node by its place in the list */
243stp_list_item_t *
244stp_list_get_item_by_index(const stp_list_t *list, int idx)
245{
246  stp_list_item_t *node = NULL;
247  stp_list_t *ulist = deconst_list(list);
248  int i; /* current index */
249  int d = 0; /* direction of list traversal, 0=forward */
250  int c = 0; /* use cache? */
251  check_list(list);
252
253  if (idx >= list->length)
254    return NULL;
255
256  /* see if using the cache is worthwhile */
257  if (list->index_cache)
258    {
259      if (idx < (list->length/2))
260	{
261	  if (idx > abs(idx - list->index_cache))
262	    c = 1;
263	  else
264	    d = 0;
265	}
266      else
267	{
268	  if (list->length - 1 - idx >
269	      abs (list->length - 1 - idx - list->index_cache))
270	    c = 1;
271	  else
272	    d = 1;
273	}
274    }
275
276
277  if (c) /* use the cached index and node */
278    {
279      if (idx > list->index_cache) /* forward */
280	d = 0;
281      else /* backward */
282	d = 1;
283      i = list->index_cache;
284      node = list->index_cache_node;
285    }
286  else /* start from one end of the list */
287    {
288      if (d)
289	{
290	  i = list->length - 1;
291	  node = list->end;
292	}
293      else
294	{
295	  i = 0;
296	  node = list->start;
297	}
298    }
299
300  while (node && i != idx)
301    {
302      if (d)
303	{
304	  i--;
305	  node = node->prev;
306	}
307      else
308	{
309	  i++;
310	  node = node->next;
311	}
312    }
313
314  /* update cache */
315  ulist->index_cache = i;
316  ulist->index_cache_node = node;
317
318  return node;
319}
320
321/**
322 * Find an item in a list by its name.
323 * This internal helper is not optimised to use any caching.
324 * @param list the list to use.
325 * @param name the name to find.
326 * @returns a pointer to the list item, or NULL if the name is
327 * invalid or the list is empty.
328 */
329static stp_list_item_t *
330stp_list_get_item_by_name_internal(const stp_list_t *list, const char *name)
331{
332  stp_list_item_t *node = list->start;
333  while (node && strcmp(name, list->namefunc(node->data)))
334    {
335      node = node->next;
336    }
337  return node;
338}
339
340/* get the first node with name; requires a callback function to
341   read data */
342stp_list_item_t *
343stp_list_get_item_by_name(const stp_list_t *list, const char *name)
344{
345  stp_list_item_t *node = NULL;
346  stp_list_t *ulist = deconst_list(list);
347  check_list(list);
348
349  if (!list->namefunc)
350    return NULL;
351
352  if (list->name_cache && name && list->name_cache_node)
353    {
354      const char *new_name;
355      node = list->name_cache_node;
356      /* Is this the item we've cached? */
357      if (strcmp(name, list->name_cache) == 0 &&
358	  strcmp(name, list->namefunc(node->data)) == 0)
359	return node;
360
361      /* If not, check the next item in case we're searching the list */
362      node = node->next;
363      if (node)
364	{
365	  new_name = list->namefunc(node->data);
366	  if (strcmp(name, new_name) == 0)
367	    {
368	      set_name_cache(ulist, new_name, node);
369	      return node;
370	    }
371	}
372      /* If not, check the index cache */
373      node = list->index_cache_node;
374      if (node)
375	{
376	  new_name = list->namefunc(node->data);
377	  if (strcmp(name, new_name) == 0)
378	    {
379	      set_name_cache(ulist, new_name, node);
380	      return node;
381	    }
382	}
383    }
384
385  node = stp_list_get_item_by_name_internal(list, name);
386
387  if (node)
388    set_name_cache(ulist, name, node);
389
390  return node;
391}
392
393
394/**
395 * Find an item in a list by its long name.
396 * This internal helper is not optimised to use any caching.
397 * @param list the list to use.
398 * @param long_name the long name to find.
399 * @returns a pointer to the list item, or NULL if the long name is
400 * invalid or the list is empty.
401 */
402static stp_list_item_t *
403stp_list_get_item_by_long_name_internal(const stp_list_t *list,
404					 const char *long_name)
405{
406  stp_list_item_t *node = list->start;
407  while (node && strcmp(long_name, list->long_namefunc(node->data)))
408    {
409      node = node->next;
410    }
411  return node;
412}
413
414/* get the first node with long_name; requires a callack function to
415   read data */
416stp_list_item_t *
417stp_list_get_item_by_long_name(const stp_list_t *list, const char *long_name)
418{
419  stp_list_item_t *node = NULL;
420  stp_list_t *ulist = deconst_list(list);
421  check_list(list);
422
423  if (!list->long_namefunc)
424    return NULL;
425
426  if (list->long_name_cache && long_name && list->long_name_cache_node)
427    {
428      const char *new_long_name;
429      node = list->long_name_cache_node;
430      /* Is this the item we've cached? */
431      if (strcmp(long_name, list->long_name_cache) == 0 &&
432	  strcmp(long_name, list->long_namefunc(node->data)) == 0)
433	return node;
434
435      /* If not, check the next item in case we're searching the list */
436      node = node->next;
437      if (node)
438	{
439	  new_long_name = list->long_namefunc(node->data);
440	  if (strcmp(long_name, new_long_name) == 0)
441	    {
442	      set_long_name_cache(ulist, new_long_name, node);
443	      return node;
444	    }
445	}
446      /* If not, check the index cache */
447      node = list->index_cache_node;
448      if (node)
449	{
450	  new_long_name = list->long_namefunc(node->data);
451	  if (strcmp(long_name, new_long_name) == 0)
452	    {
453	      set_long_name_cache(ulist, new_long_name, node);
454	      return node;
455	    }
456	}
457    }
458
459  node = stp_list_get_item_by_long_name_internal(list, long_name);
460
461  if (node)
462    set_long_name_cache(ulist, long_name, node);
463
464  return node;
465}
466
467
468/* callback for freeing data */
469void
470stp_list_set_freefunc(stp_list_t *list, stp_node_freefunc freefunc)
471{
472  check_list(list);
473  list->freefunc = freefunc;
474}
475
476stp_node_freefunc
477stp_list_get_freefunc(const stp_list_t *list)
478{
479  check_list(list);
480  return list->freefunc;
481}
482
483/* callback for copying data */
484void
485stp_list_set_copyfunc(stp_list_t *list, stp_node_copyfunc copyfunc)
486{
487  check_list(list);
488  list->copyfunc = copyfunc;
489}
490
491stp_node_copyfunc
492stp_list_get_copyfunc(const stp_list_t *list)
493{
494  check_list(list);
495  return list->copyfunc;
496}
497
498/* callback for getting data name */
499void
500stp_list_set_namefunc(stp_list_t *list, stp_node_namefunc namefunc)
501{
502  check_list(list);
503  list->namefunc = namefunc;
504}
505
506stp_node_namefunc
507stp_list_get_namefunc(const stp_list_t *list)
508{
509  check_list(list);
510  return list->namefunc;
511}
512
513/* callback for getting data long_name */
514void
515stp_list_set_long_namefunc(stp_list_t *list, stp_node_namefunc long_namefunc)
516{
517  check_list(list);
518  list->long_namefunc = long_namefunc;
519}
520
521stp_node_namefunc
522stp_list_get_long_namefunc(const stp_list_t *list)
523{
524  check_list(list);
525  return list->long_namefunc;
526}
527
528/* callback for sorting nodes */
529void
530stp_list_set_sortfunc(stp_list_t *list, stp_node_sortfunc sortfunc)
531{
532  check_list(list);
533  list->sortfunc = sortfunc;
534}
535
536stp_node_sortfunc
537stp_list_get_sortfunc(const stp_list_t *list)
538{
539  check_list(list);
540  return list->sortfunc;
541}
542
543
544/* list item functions */
545
546/* these functions operate on individual nodes in a list */
547
548/*
549 * create a new node in list, before next (may be null e.g. if sorting
550 * next is calculated automatically, else defaults to end).  Must be
551 * initialised with data (null nodes are disallowed).  The
552 * stp_list_item_t type can not exist unless it is associated with an
553 * stp_list_t list head.
554 */
555int
556stp_list_item_create(stp_list_t *list,
557		     stp_list_item_t *next,
558		     const void *data)
559{
560  stp_list_item_t *ln; /* list node to add */
561  stp_list_item_t *lnn; /* list node next */
562
563  check_list(list);
564
565  clear_cache(list);
566
567  ln = stp_malloc(sizeof(stp_list_item_t));
568  ln->prev = ln->next = NULL;
569
570  if (data)
571    ln->data = (void *) data;
572  else
573    {
574      stp_free(ln);
575      return 1;
576    }
577
578  if (list->sortfunc)
579    {
580      /* set np to the previous node (before the insertion */
581      lnn = list->end;
582      while (lnn)
583	{
584	  if (list->sortfunc(lnn->data, ln->data) <= 0)
585	    break;
586	  lnn = lnn->prev;
587	}
588    }
589#if 0
590  /*
591   * This code #ifdef'ed out by Robert Krawitz on April 3, 2004.
592   * Setting a debug variable should not result in taking a materially
593   * different code path.
594   */
595  else if (stpi_get_debug_level() & STPI_DBG_LIST)
596    {
597      if (next)
598	{
599	  lnn = list->start;
600	  while (lnn)
601	    {
602	      if (lnn == next)
603		break;
604	      lnn = lnn->prev;
605	    }
606	}
607      else
608	lnn = NULL;
609    }
610#endif
611  else
612    lnn = next;
613
614  /* got lnp; now insert the new ln */
615
616  /* set next */
617  ln->next = lnn;
618
619  if (!ln->prev) /* insert at start of list */
620    {
621      if (list->start) /* list not empty */
622	ln->prev = list->end;
623      else
624	list->start = ln;
625      list->end = ln;
626    }
627
628  /* set prev (already set if at start of list) */
629
630  if (!ln->prev && ln->next) /* insert at end of list */
631    ln->prev = ln->next->prev;
632
633  if (list->start == ln->next) /* prev was old end */
634    {
635      list->start = ln;
636    }
637
638  /* set next->prev */
639  if (ln->next)
640    ln->next->prev = ln;
641
642  /* set prev->next */
643  if (ln->prev)
644    ln->prev->next = ln;
645
646  /* increment reference count */
647  list->length++;
648
649  stp_deprintf(STP_DBG_LIST, "stp_list_node constructor\n");
650  return 0;
651}
652
653/* remove a node from list */
654int
655stp_list_item_destroy(stp_list_t *list, stp_list_item_t *item)
656{
657  check_list(list);
658
659  clear_cache(list);
660  /* decrement reference count */
661  list->length--;
662
663  if (list->freefunc)
664    list->freefunc((void *) item->data);
665  if (item->prev)
666    item->prev->next = item->next;
667  else
668    list->start = item->next;
669  if (item->next)
670    item->next->prev = item->prev;
671  else
672    list->end = item->prev;
673  stp_free(item);
674
675  stp_deprintf(STP_DBG_LIST, "stp_list_node destructor\n");
676  return 0;
677}
678
679/* get previous node */
680stp_list_item_t *
681stp_list_item_prev(const stp_list_item_t *item)
682{
683  return item->prev;
684}
685
686/* get next node */
687stp_list_item_t *
688stp_list_item_next(const stp_list_item_t *item)
689{
690  return item->next;
691}
692
693/* get data for node */
694void *
695stp_list_item_get_data(const stp_list_item_t *item)
696{
697  return item->data;
698}
699
700/* set data for node */
701int
702stp_list_item_set_data(stp_list_item_t *item, void *data)
703{
704  if (data)
705    {
706      item->data = data;
707      return 0;
708    }
709  return 1; /* return error if data was NULL */
710}
711