home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume12 / cake / part03 / list.c next >
Encoding:
C/C++ Source or Header  |  1987-10-14  |  2.6 KB  |  172 lines
  1. /*
  2. **    Linked list module.
  3. */
  4.  
  5. static    char
  6. rcs_id[] = "$Header: /mip/zs/src/sys/cake/RCS/list.c,v 1.14 86/07/19 12:23:15 zs Exp $";
  7.  
  8. #include    "cake.h"
  9.  
  10. /*
  11. **    Make an empty list.
  12. */
  13.  
  14. List *
  15. makelist0()
  16. {
  17.     reg    List    *list;
  18.  
  19.     list = make(List);
  20.     ldata(list) = (Cast) 0;
  21.     next(list)  = list;
  22.     prev(list)  = list;
  23.     
  24.     return list;
  25. }
  26.  
  27. /*
  28. **    Make a list with the argument is its only element.
  29. */
  30.  
  31. List *
  32. _makelist(data)
  33. reg    Cast    data;
  34. {
  35.     return addhead(makelist0(), data);
  36. }
  37.  
  38. /*
  39. **    Add some data to the head of a list.
  40. */
  41.  
  42. List *
  43. _addhead(list, data)
  44. reg    List    *list;
  45. reg    Cast    data;
  46. {
  47.     reg    List    *item;
  48.  
  49.     if (list == NULL)
  50.         list = makelist0();
  51.  
  52.     item = make(List);
  53.     ldata(item) = data;
  54.     ldata(list) = (Cast) ((int) ldata(list) + 1);
  55.  
  56.     /* item's pointers    */
  57.     next(item) = next(list);
  58.     prev(item) = list;
  59.     /* neighbours' pointers    */
  60.     next(prev(item)) = item;
  61.     prev(next(item)) = item;
  62.  
  63.     return list;
  64. }
  65.  
  66. /*
  67. **    Add some data to the tail of a list.
  68. */
  69.  
  70. List *
  71. _addtail(list, data)
  72. reg    List    *list;
  73. reg    Cast    data;
  74. {
  75.     reg    List    *item;
  76.  
  77.     if (list == NULL)
  78.         list = makelist0();
  79.  
  80.     item = make(List);
  81.     ldata(item) = data;
  82.     ldata(list) = (Cast) ((int) ldata(list) + 1);
  83.  
  84.     /* item's pointers    */
  85.     next(item) = list;
  86.     prev(item) = prev(list);
  87.     /* neighbours' pointers    */
  88.     next(prev(item)) = item;
  89.     prev(next(item)) = item;
  90.  
  91.     return list;
  92. }
  93.  
  94. /*
  95. **    Destructively append list2 to list1. Since the header of
  96. **    list2 is not meaningful after the operation, it is freed.
  97. */
  98.  
  99. List *
  100. addlist(list1, list2)
  101. reg    List    *list1;
  102. reg    List    *list2;
  103. {
  104.     if (list1 == NULL)
  105.         list1 = makelist0();
  106.  
  107.     if (list2 == NULL)
  108.         list2 = makelist0();
  109.  
  110.     if (length(list2) > 0)
  111.     {
  112.         if (length(list1) == 0)
  113.         {
  114.             ldata(list1) = ldata(list2);
  115.             /* pointers from header    */
  116.             next(list1)  = next(list2);
  117.             prev(list1)  = prev(list2);
  118.             /* pointers to header    */
  119.             prev(next(list1)) = list1;
  120.             next(prev(list1)) = list1;
  121.         }
  122.         else
  123.         {
  124.             ldata(list1) = (Cast) ((int) ldata(list1) + (int) ldata(list2));
  125.             /* end of list 1 to start of list 2    */
  126.             next(prev(list1)) = next(list2);
  127.             prev(next(list2)) = prev(list1);
  128.             /* end of list 2 to start of list 1    */
  129.             next(prev(list2)) = list1;
  130.             prev(list1) = prev(list2);
  131.         }
  132.     }
  133.  
  134.     oldmem((Cast) list2);
  135.     return list1;
  136. }
  137.  
  138. /*
  139. **    Return the length of a given list.
  140. */
  141.  
  142. int
  143. length(list)
  144. reg    List    *list;
  145. {
  146.     if (list == NULL)
  147.         return 0;
  148.  
  149.     return (int) ldata(list);
  150. }
  151.  
  152. /*
  153. **    Delete an item from its linked list, and free the node.
  154. */
  155.  
  156. delete(list, item)
  157. reg    List    *list;
  158. reg    List    *item;
  159. {
  160.     if (list == NULL)
  161.         return;
  162.  
  163.     if (item == NULL)
  164.         return;
  165.  
  166.     ldata(list) = (Cast) ((int) ldata(list) - 1);
  167.     next(prev(item)) = next(item);
  168.     prev(next(item)) = prev(item);
  169.  
  170.     oldmem((Cast) item);
  171. }
  172.