home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / gnu / fax-3.2.1 / lib / libutil / list.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-07-31  |  10.3 KB  |  638 lines
  1. /*
  2.   This file is part of the NetFax system.
  3.  
  4.   (c) Copyright 1989 by David M. Siegel and Sundar Narasimhan.
  5.       All rights reserved.
  6.  
  7.     This program is free software; you can redistribute it and/or modify
  8.     it under the terms of the GNU General Public License as published by
  9.     the Free Software Foundation.
  10.  
  11.     This program is distributed in the hope that it will be useful, 
  12.     but WITHOUT ANY WARRANTY; without even the implied warranty of 
  13.     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14.     GNU General Public License for more details.
  15.  
  16.     You should have received a copy of the GNU General Public License
  17.     along with this program; if not, write to the Free Software
  18.     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  19. */
  20.  
  21. #include <stdio.h>
  22. #include <rpc/rpc.h>
  23.  
  24. #include "alloc.h"
  25. #include "bool.h"
  26. #include "list.h"
  27.  
  28. static int
  29. default_cmp(v1, v2)
  30. int v1, v2;
  31. {
  32.     return (v1 - v2);
  33. }
  34.  
  35. int
  36. list_init(list, cmp_func, free_func)
  37. LIST *list;
  38. int (*cmp_func)();
  39. int (*free_func)();
  40. {
  41.     list->count = 0;
  42.     list->cmp_func = (cmp_func == NULL) ? default_cmp : cmp_func;
  43.     list->free_func = free_func;
  44.  
  45.     return (0);
  46. }
  47.  
  48. LIST *
  49. list_make(cmp_func, free_func)
  50. int (*cmp_func)();
  51. int (*free_func)();
  52. {
  53.     LIST *list;
  54.  
  55.     if ((list = salloc(1, LIST)) == NULL)
  56.       return (NULL);
  57.  
  58.     if (list_init(list, cmp_func, free_func) < 0) {
  59.     free(list);
  60.     return (NULL);
  61.     }
  62.  
  63.     return (list);
  64. }
  65.  
  66. static NODE *
  67. node_make(value)
  68. char *value;
  69. {
  70.     NODE *node;
  71.  
  72.     if ((node = salloc(1, NODE)) == NULL)
  73.       return (NULL);
  74.  
  75.     node->value = value;
  76.  
  77.     return (node);
  78. }
  79.  
  80. int
  81. list_free(list)
  82. LIST *list;
  83. {
  84.     NODE *n = list->head;
  85.     NODE *hold;
  86.  
  87.     while (n) {
  88.     if (list->free_func != NULL) 
  89.       (*list->free_func)(n->value);
  90.     hold = n->next;
  91.     cfree(n);
  92.     n = hold;
  93.     }
  94.  
  95.     list->head = NULL;
  96.     list->tail = NULL;
  97.     list->count = 0;
  98. }
  99.  
  100. int
  101. list_length(list)
  102. LIST *list;
  103. {
  104.     return (list->count);
  105. }
  106.  
  107. NODE *
  108. list_nth_node(list, n)
  109. LIST *list;
  110. int n;
  111. {
  112.     NODE *node;
  113.     int i;
  114.  
  115.     if (n >= list->count)
  116.       return (NULL);
  117.  
  118.     for (i = 0, node = list->head; i < n; i++)
  119.       node = node->next;
  120.  
  121.     return (node);
  122. }
  123.  
  124. char *
  125. list_nth(list, n)
  126. LIST *list;
  127. int n;
  128. {
  129.     NODE *node;
  130.     int i;
  131.  
  132.     if (n >= list->count)
  133.       return (NULL);
  134.  
  135.     for (i = 0, node = list->head; i < n; i++)
  136.       node = node->next;
  137.  
  138.     return (node->value);
  139. }
  140.  
  141. NODE *
  142. list_last_node(list)
  143. LIST *list;
  144. {
  145.     if (list->count == 0)
  146.       return (NULL);
  147.  
  148.     return (list->tail);
  149. }
  150.  
  151. char *
  152. list_last(list)
  153. LIST *list;
  154. {
  155.     if (list->count == 0)
  156.       return (NULL);
  157.  
  158.     return (list->tail->value);
  159. }
  160.  
  161. NODE *
  162. list_first_node(list)
  163. LIST *list;
  164. {
  165.     if (list->count == 0)
  166.       return (NULL);
  167.  
  168.     return (list->head);
  169. }
  170.  
  171. char *
  172. list_first(list)
  173. LIST *list;
  174. {
  175.     if (list->count == 0)
  176.       return (NULL);
  177.  
  178.     return (list->head->value);
  179. }
  180.  
  181. static LIST *
  182. add_node(list, prev, new)
  183. LIST *list;
  184. NODE *prev;
  185. NODE *new;
  186. {
  187.     if (prev == NULL) {
  188.     new->next = list->head;
  189.     new->previous = NULL;
  190.     if (list->head) {
  191.         list->head->previous = new;
  192.         list->head = new;
  193.     } else {
  194.         list->tail = new;
  195.         list->head = new;
  196.     }
  197.     } else {
  198.     new->previous = prev;
  199.     new->next = prev->next;
  200.     if (prev->next)
  201.       prev->next->previous = new;
  202.     else
  203.       list->tail = new;
  204.     prev->next = new;
  205.     }
  206.  
  207.     list->count++;
  208.  
  209.     return (list);
  210. }
  211.  
  212. LIST *
  213. list_add_node(list, node)
  214. LIST *list;
  215. NODE *node;
  216. {
  217.     return (add_node(list, list->tail, node));
  218. }
  219.  
  220. LIST *
  221. list_add(list, value)
  222. LIST *list;
  223. char *value;
  224. {
  225.     return (add_node(list, list->tail, node_make(value)));
  226. }
  227.  
  228. LIST *
  229. list_add_first_node(list, node)
  230. LIST *list;
  231. NODE *node;
  232. {
  233.     return (add_node(list, NULL, node));
  234. }
  235.  
  236. LIST *
  237. list_add_first(list, value)
  238. LIST *list;
  239. char *value;
  240. {
  241.     return (add_node(list, NULL, node_make(value)));
  242. }
  243.  
  244. LIST *
  245. list_append(list1, list2)
  246. LIST *list1;
  247. LIST *list2;
  248. {
  249.     NODE *n;
  250.  
  251.     for (n = list2->head; n != NULL; n = n->next)
  252.       list_add(list1, n->value);
  253.  
  254.     return (list1);
  255. }
  256.  
  257. static NODE *
  258. delete_node(list, n, do_free)
  259. LIST *list;
  260. NODE *n;
  261. int do_free;
  262. {
  263.     NODE *next = n->next;
  264.     
  265.     if (n->previous)
  266.       n->previous->next = n->next;
  267.     if (n->next)
  268.       n->next->previous = n->previous;
  269.  
  270.     if (n == list->head)
  271.       list->head = n->next;
  272.     if (n == list->tail)
  273.       list->tail = n->previous;
  274.     
  275.     list->count--;
  276.     
  277.     if (do_free && (list->free_func != NULL))
  278.       (*list->free_func)(n->value);
  279.  
  280.     if (do_free)
  281.       cfree(n);
  282.     
  283.     return (next);
  284. }
  285.  
  286. static LIST *
  287. delete_list_internal(list, value, func, filter_mode, do_free)
  288. LIST *list;
  289. char *value;
  290. int (*func)();
  291. int filter_mode;
  292. int do_free;
  293. {
  294.     NODE *n = list->head;
  295.     int do_delete = FALSE;
  296.  
  297.     while(n) {
  298.     if (func != NULL)
  299.       do_delete = ((*func)(n->value, value) == 0);
  300.     else
  301.       do_delete = ((*list->cmp_func)(n->value, value) == 0);
  302.      
  303.     if (do_delete) {
  304.         n = delete_node(list, n, do_free);
  305.         if (!filter_mode)
  306.           return (list);
  307.     } else
  308.       n = n->next;
  309.     }
  310.  
  311.     return (list);
  312. }
  313.  
  314. LIST *
  315. list_delete_node(list, node)
  316. LIST *list;
  317. NODE *node;
  318. {
  319.     delete_node(list, node, FALSE);
  320.     
  321.     return (list);
  322. }
  323.  
  324. LIST *
  325. list_delete(list, value)
  326. LIST *list;
  327. char *value;
  328. {
  329.     return (delete_list_internal(list, value, NULL, FALSE, TRUE));
  330. }
  331.  
  332. LIST *
  333. list_delete_with_function(list, value, function)
  334. LIST *list;
  335. char *value;
  336. int (*function)();
  337. {
  338.     return (delete_list_internal(list, value, function, FALSE, TRUE));
  339. }
  340.  
  341. LIST *
  342. list_filter(list, value)
  343. LIST *list;
  344. char *value;
  345. {
  346.     return (delete_list_internal(list, value, NULL, TRUE, TRUE));
  347. }
  348.  
  349. LIST *
  350. list_filter_with_function(list, value, function)
  351. LIST *list;
  352. char *value;
  353. int (*function)();
  354. {
  355.     return (delete_list_internal(list, value, function, TRUE, TRUE));
  356. }
  357.  
  358. LIST *
  359. list_delete_first(list)
  360. LIST *list;
  361. {
  362.     NODE *first = list->head;
  363.  
  364.     if (first)
  365.       delete_node(list, first, TRUE);
  366.     
  367.     return (list);
  368. }
  369.  
  370. LIST *
  371. list_delete_last(list)
  372. LIST *list;
  373. {
  374.     NODE *last = list->tail;
  375.  
  376.     if (last)
  377.       delete_node(list, last, TRUE);
  378.     
  379.     return (list);
  380. }
  381.  
  382. char *
  383. list_car(list)
  384. LIST *list;
  385. {
  386.     return (list_first(list));
  387. }
  388.  
  389. LIST *
  390. list_cdr(list)
  391. LIST *list;
  392. {
  393.     return (list_delete_first(list));
  394. }
  395.  
  396. LIST *
  397. list_push(list, value)
  398. LIST *list;
  399. char *value;
  400. {
  401.     return (list_add_first(list, value));
  402. }
  403.  
  404. LIST *
  405. list_push_new(list, value)
  406. LIST *list;
  407. char *value;
  408. {
  409.     NODE *n;
  410.  
  411.     for (n = list->head; n != NULL; n = n->next)
  412.       if ((*list->cmp_func)(n->value, value) == 0)
  413.     return (list);
  414.     
  415.     return (list_add_first(list, value));
  416. }
  417.  
  418. char *
  419. list_pop(list)
  420. LIST *list;
  421. {
  422.     char *value = list_first(list);
  423.     
  424.     list_delete_first(list);
  425.     return (value);
  426. }
  427.  
  428. char *
  429. list_find(list, value)
  430. LIST *list;
  431. char *value;
  432. {
  433.     NODE *n;
  434.  
  435.     for (n = list->head; n != NULL; n = n->next)
  436.       if ((*list->cmp_func)(n->value, value) == 0)
  437.     return (n->value);
  438.  
  439.     return (NULL);
  440. }
  441.  
  442. LIST *
  443. list_insert(list, value, order)
  444. LIST *list;
  445. char *value;
  446. int order;
  447. {
  448.     NODE *n, *prev_n;
  449.     int new_order;
  450.  
  451.     for (n = list->head, prev_n = NULL; n != NULL; prev_n = n, n = n->next) {
  452.     new_order = (*list->cmp_func)(value, n->value);
  453.     if (new_order < 0)
  454.       new_order = -1;
  455.     else if (new_order > 0)
  456.       new_order = 1;
  457.     else
  458.       new_order = 0;
  459.     
  460.     if (order != new_order)
  461.       return (add_node(list, prev_n, node_make(value)));
  462.     }
  463.  
  464.     return (add_node(list, prev_n, node_make(value)));
  465. }
  466.  
  467. NODE *
  468. list_next_node(list, node)
  469. LIST *list;
  470. NODE **node;
  471. {
  472.     if (*node == NULL)
  473.       *node = list->head;
  474.     else
  475.       *node = (*node)->next;
  476.     
  477.     return (*node);
  478. }
  479.  
  480. char *
  481. list_next(list, node)
  482. LIST *list;
  483. NODE **node;
  484. {
  485.     if (*node == NULL)
  486.       *node = list->head;
  487.     else
  488.       *node = (*node)->next;
  489.     
  490.     if (*node == NULL)
  491.       return (NULL);
  492.     else
  493.       return ((*node)->value);
  494. }
  495.  
  496. char *
  497. list_delete_next(list, node)
  498. LIST *list;
  499. NODE **node;
  500. {
  501.     if (*node == NULL) {
  502.     *node = list->head;
  503.     return ((*node)->value);
  504.     } else
  505.       *node = delete_node(list, *node, TRUE);
  506.  
  507.     if (*node != NULL)
  508.       return ((*node)->value);
  509.     else
  510.       return (NULL);
  511. }
  512.  
  513. /*VARARGS*/
  514. int
  515. list_map(list, function, arg1, arg2, arg3, arg4, arg5, arg6, arg7)
  516. LIST *list;
  517. int (*function)();
  518. char *arg1, *arg2, *arg3, *arg4, *arg5, *arg6, *arg7;
  519. {
  520.     NODE *n;
  521.     int rc;
  522.  
  523.     for (n = list->head; n != NULL; n = n->next)
  524.       /*SUPPRESS 62*/
  525.       if ((rc = (*function)(n->value,arg1,arg2,arg3,arg4,arg5,arg6,arg7)) != 0)
  526.     return (rc);
  527.  
  528.     return(0);
  529. }
  530.  
  531. /*VARARGS*/
  532. int
  533. list_map_node(list, function, arg1, arg2, arg3, arg4, arg5, arg6, arg7)
  534. LIST *list;
  535. int (*function)();
  536. char *arg1, *arg2, *arg3, *arg4, *arg5, *arg6, *arg7;
  537. {
  538.     NODE *n;
  539.     int rc;
  540.  
  541.     for (n = list->head; n != NULL; n = n->next)
  542.       /*SUPPRESS 62*/
  543.       if ((rc = (*function)(n,arg1,arg2,arg3,arg4,arg5,arg6,arg7)) != 0)
  544.     return (rc);
  545.  
  546.     return(0);
  547. }
  548.  
  549. static int 
  550. node_describe(node, fp, i) 
  551. NODE *node;
  552. FILE *fp; 
  553. int *i; 
  554. {
  555.     fprintf(fp, "Node %d: value=%d, node=0x%x, previous=0x%x, next=0x%x\n",
  556.         *i, node->value, node, node->previous, node->next); 
  557.     (*i)++;
  558.  
  559.     return (0);
  560. }
  561.  
  562. int
  563. list_describe(list, fp)
  564. LIST *list;
  565. FILE *fp;
  566. {
  567.     int i = 0;
  568.  
  569.     if (fp == NULL)
  570.       fp = stdout;
  571.  
  572.     fprintf(fp, "length=%d, head=0x%x, tail=0x%x\n",
  573.         list->count, list->head, list->tail);
  574.     list_map_node(list, node_describe, fp, &i);
  575.  
  576.     return (0);
  577. }
  578.  
  579. bool_t
  580. xdr_list(xdrs, listpp, size, xdrel)
  581. XDR *xdrs;
  582. LIST **listpp;
  583. int size;
  584. xdrproc_t xdrel;
  585. {
  586.     bool_t more_data = TRUE;
  587.     NODE *node = NULL;
  588.  
  589.     switch (xdrs->x_op) {
  590.       case XDR_ENCODE:
  591.     if (*listpp != NULL) {
  592.         while (list_next(*listpp, &node) != NULL) {
  593.         if (!xdr_bool(xdrs, &more_data))
  594.           return (FALSE);
  595.         if (!xdr_reference(xdrs, &node->value, size, xdrel))
  596.           return (FALSE);
  597.         }
  598.     }
  599.     more_data = FALSE;
  600.     if (!xdr_bool(xdrs, &more_data))
  601.       return (FALSE);
  602.     return (TRUE);
  603.     
  604.       case XDR_DECODE:
  605.     if (!xdr_bool(xdrs, &more_data))
  606.       return (FALSE);
  607.     while (more_data) {
  608.         char *value;
  609.  
  610.         if (*listpp == NULL) {
  611.         if ((*listpp = list_make(NULL, NULL)) == NULL)
  612.           return (FALSE);
  613.         }
  614.         value = NULL;
  615.         if (!xdr_reference(xdrs, &value, size, xdrel))
  616.           return (FALSE);
  617.         list_add(*listpp, value);
  618.         if (!xdr_bool(xdrs, &more_data))
  619.           return (FALSE);
  620.     }
  621.     return (TRUE);
  622.  
  623.       case XDR_FREE:
  624.     if (*listpp != NULL) {
  625.         char *value;
  626.         
  627.         while ((value = (char *)list_next(*listpp, &node)) != NULL) {
  628.         if (!xdr_reference(xdrs, &value, size, xdrel))
  629.           return (FALSE);
  630.         }
  631.     }
  632.     if (*listpp)
  633.       list_free(*listpp);
  634.     return (TRUE);
  635.     }
  636.     return (FALSE);
  637. }
  638.