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