home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / lifeos2.zip / LIFE-1.02 / SOURCE / LIST.C < prev    next >
C/C++ Source or Header  |  1996-06-04  |  11KB  |  454 lines
  1. /* 
  2.  * Copyright 1991 Digital Equipment Corporation.
  3.  * All Rights Reserved.
  4.  */
  5. /*     $Id: list.c,v 1.2 1994/12/08 23:28:16 duchier Exp $     */
  6.  
  7. #ifndef lint
  8. static char vcid[] = "$Id: list.c,v 1.2 1994/12/08 23:28:16 duchier Exp $";
  9. #endif /* lint */
  10.  
  11. /*
  12. ** list.c contains the functions to manage double link list
  13. ** with 2 entries (first and last element)
  14. ** Links belongs to each atom
  15. */
  16.  
  17. #include "list.h"
  18.  
  19.  
  20.  
  21. /*=============================================================================*/
  22. /*            Set functions                           */
  23. /*=============================================================================*/
  24.  
  25. void List_SetLinkProc (header, getLinks)
  26. RefListHeader header;
  27. RefListGetLinksProc getLinks;
  28. {
  29.     header->First = NULL;
  30.     header->Last = NULL;
  31.  
  32. #ifdef prlDEBUG
  33.     header->Lock = 0;
  34. #endif
  35.  
  36.     header->GetLinks = getLinks;
  37. }
  38.  
  39. /*=============================================================================*/
  40. /*            List functions                           */
  41. /*=============================================================================*/
  42.  
  43. void List_InsertAhead (header, atom) 
  44. RefListHeader header;
  45. Ref atom;
  46. {
  47.     RefListGetLinksProc  getLinks = header->GetLinks;
  48.  
  49.         /* Update links of atom to insert */
  50.  
  51.     (*getLinks)(atom)->Next = header->First;
  52.     (*getLinks)(atom)->Prev = NULL;
  53.  
  54.         /* Link to the head of list */
  55.  
  56.     if (header->First != NULL)
  57.       (*getLinks)(header->First)->Prev = atom;
  58.  
  59.     else    /* The list is empty */
  60.       header->Last  = atom;
  61.  
  62.     header->First = atom;
  63. }
  64.  
  65. /*==============================================================================*/
  66.  
  67. void List_Append (header, atom) 
  68. RefListHeader header;
  69. Ref atom;
  70. {
  71.     RefListGetLinksProc  getLinks = header->GetLinks;
  72.  
  73.             /* Link to the end of list */
  74.  
  75.     if (header->Last != NULL)
  76.       (*getLinks)(header->Last)->Next = atom;
  77.  
  78.     else    /* The list is empty */
  79.       header->First = atom;
  80.  
  81.             /* Update links of atom to insert */
  82.  
  83.     (*getLinks)(atom)->Prev = header->Last;
  84.     (*getLinks)(atom)->Next = NULL;
  85.  
  86.         /* Update last element of header */
  87.  
  88.     header->Last  = atom;
  89. }
  90.  
  91. /*==============================================================================*/
  92.  
  93. void List_InsertBefore (header, atom, mark)
  94. RefListHeader header;
  95. Ref atom;
  96. Ref mark;
  97. {
  98.     RefListGetLinksProc  getLinks = header->GetLinks;
  99.  
  100.     if (mark != NULL)
  101.     {
  102.         (*getLinks)(atom)->Next = mark;
  103.  
  104.         if (mark != header->First)
  105.         {
  106.             (*getLinks)(atom)->Prev = (*getLinks)(mark)->Prev;
  107.             (*getLinks)((*getLinks)(mark)->Prev)->Next = atom;
  108.         }
  109.         else    /* Insert ahead the list */
  110.         {
  111.             (*getLinks)(atom)->Prev = NULL;
  112.             header->First = atom;
  113.         }
  114.  
  115.         (*getLinks)(mark)->Prev = atom;
  116.     }
  117.     else        /* Append to the list */
  118.       List_Append (header, atom);
  119. } 
  120.  
  121. /*==============================================================================*/
  122.  
  123. void List_InsertAfter (header, atom, mark)
  124. RefListHeader header;
  125. Ref atom;
  126. Ref mark;
  127. {
  128.     RefListGetLinksProc  getLinks = header->GetLinks;
  129.  
  130. #ifdef prlDEBUG
  131.     if (header->Lock > 1)
  132.       OS_PrintMessage ("List_InsertAfter: Warning insert after on recursive List_Enum call !!\n");
  133. #endif
  134.  
  135.     if (mark != NULL)
  136.     {
  137.         (*getLinks)(atom)->Prev = mark;
  138.  
  139.         if (mark != header->Last)
  140.         {
  141.             (*getLinks)(atom)->Next = (*getLinks)(mark)->Next;
  142.             (*getLinks)((*getLinks)(mark)->Next)->Prev = atom;
  143.         }
  144.         else    /* Insert at the end of the list */
  145.         {
  146.             (*getLinks)(atom)->Next = NULL;
  147.             header->Last = atom;
  148.         }
  149.  
  150.         (*getLinks)(mark)->Next = atom;
  151.     }
  152.     else        /* Insert ahead the list */
  153.       List_InsertAhead (header, atom);
  154. } 
  155.  
  156. /*==============================================================================*/
  157.  
  158. void List_Swap (header, first, second)
  159. RefListHeader header;
  160. Ref first;
  161. Ref second;
  162. {
  163.     RefListGetLinksProc    getLinks = header->GetLinks;
  164.  
  165.     /* Don't swap if the input is wrong */
  166.  
  167.     if ((*getLinks)(first)->Next != second)
  168.     {
  169. #ifdef prlDEBUG
  170.     OS_PrintMessage ("List_Swap: WARNING wrong input data, swap not done..\n");
  171. #endif
  172.     return;
  173.     }
  174.  
  175.         /* Special Cases */
  176.  
  177.     if (header->First == first)
  178.       header->First = second;
  179.     else
  180.       (*getLinks)((*getLinks)(first)->Prev)->Next = second;
  181.     
  182.     if (header->Last == second)
  183.       header->Last = first;
  184.     else
  185.       (*getLinks)((*getLinks)(second)->Next)->Prev = first;
  186.  
  187.         /* Swap the atoms */
  188.  
  189.     (*getLinks)(second)->Prev = (*getLinks)(first)->Prev;
  190.     (*getLinks)(first)->Next  = (*getLinks)(second)->Next;
  191.     (*getLinks)(first)->Prev  = second;
  192.     (*getLinks)(second)->Next = first;
  193. }
  194.  
  195. /*==============================================================================*/
  196.  
  197. static long List_SwapLinks (header, atom)
  198. RefListHeader header;
  199. Ref atom;
  200. {
  201.     Ref    save;
  202.  
  203.     save = (*header->GetLinks)(atom)->Next;
  204.     (*header->GetLinks)(atom)->Next = (*header->GetLinks)(atom)->Prev;
  205.     (*header->GetLinks)(atom)->Prev = save;
  206.  
  207.     return TRUE;
  208. }
  209.  
  210. void List_Reverse (header)
  211. RefListHeader header;
  212. {
  213.     Ref            cur, next;
  214.     RefListGetLinksProc    getLinks = header->GetLinks;
  215.  
  216.     /* This traverse cannot be done with function List_Enum() */
  217.  
  218.     cur = header->First;
  219.  
  220.     /* Swap the headers */
  221.     header->First = header->Last;
  222.     header->Last  = cur;
  223.  
  224.     while (cur != NULL)
  225.     {
  226.     next = (*getLinks)(cur)->Next;
  227.     List_SwapLinks (header, cur);
  228.     cur = next;
  229.     }
  230. }
  231.  
  232. /*==============================================================================*/
  233.  
  234. void List_Remove (header, atom)
  235. RefListHeader header;
  236. Ref atom;
  237. {
  238. /*-----------------------------------------------------------------------------
  239.  
  240. WARNING
  241.     - The container is 'updated' two times if the first and last atom
  242.       of list is the only one to remove.
  243.  
  244. -----------------------------------------------------------------------------*/
  245.  
  246.     RefListGetLinksProc  getLinks = header->GetLinks;
  247.  
  248. #ifdef prlDEBUG
  249.     if (header->Lock > 1)
  250.       OS_PrintMessage ("List_Remove: Warning remove on recursive List_Enum call !!\n");
  251. #endif
  252.  
  253.         /* Update the DownStream links */
  254.  
  255.     if ((*getLinks)(atom)->Prev != NULL)
  256.     {
  257.         (*getLinks)((*getLinks)(atom)->Prev)->Next = 
  258.             (*getLinks)(atom)->Next;
  259.     }
  260.     else            /* Atom is the first of list */
  261.       header->First = (*getLinks)(atom)->Next;
  262.  
  263.         /* Update the UpStream links */
  264.  
  265.     if ((*getLinks)(atom)->Next != NULL)
  266.     {
  267.         (*getLinks)((*getLinks)(atom)->Next)->Prev = 
  268.             (*getLinks)(atom)->Prev;
  269.     }
  270.     else            /* Atom is the last of list */
  271.       header->Last = (*getLinks)(atom)->Prev;
  272.  
  273.         /* Reset the atom links */
  274.  
  275.     (*getLinks)(atom)->Prev = NULL;
  276.     (*getLinks)(atom)->Next = NULL;
  277. } 
  278.  
  279. /*==============================================================================*/
  280.  
  281. void List_Concat (header1, header2)
  282. RefListHeader header1;
  283. RefListHeader header2;
  284. {
  285.     RefListGetLinksProc  getLinks = header1->GetLinks;
  286.  
  287.     if (header1->GetLinks == header2->GetLinks)
  288.     {
  289. #ifdef prlDEBUG
  290.     OS_PrintMessage ("List_Concat: ERROR concat different lists\n");
  291. #endif
  292.     return;
  293.     }
  294.  
  295.     /* Concatenate only if the second list is not empty */
  296.  
  297.     if (header2->First != NULL)
  298.     {
  299.     /* Obvious concatenate when the first list is empty */
  300.  
  301.         if (header1->First == NULL)
  302.             header1->First = header2->First;
  303.  
  304.         else    /* Concatenate the two non empty lists */
  305.         {
  306.             (*getLinks)(header1->Last)->Next  = header2->First;
  307.             (*getLinks)(header2->First)->Prev = header1->Last;
  308.         }
  309.         header1->Last = header2->Last;
  310.     }
  311. } 
  312.  
  313. /*==============================================================================*/
  314.  
  315. long List_EnumFrom (header, atom, proc, closure)
  316. RefListHeader    header;
  317. Ref atom;
  318. RefListEnumProc    proc;
  319. Ref closure;
  320. {
  321.     Ref    cur, next;
  322.     int    notInterrupted = TRUE;
  323.  
  324. #ifdef prlDEBUG
  325.     header->Lock += 1;
  326. #endif
  327.  
  328.     cur = atom;
  329.     while (cur != NULL && notInterrupted)
  330.     {
  331.     next = List_Next (header, cur);
  332.     notInterrupted = (*proc)(cur, closure);
  333.     cur = next;
  334.     }
  335.  
  336. #ifdef prlDEBUG
  337.     header->Lock -=1;
  338. #endif
  339.     
  340.     return (notInterrupted);
  341. }
  342.  
  343. /*==============================================================================*/
  344.  
  345. long List_Enum (header, proc, closure)
  346. RefListHeader    header;
  347. RefListEnumProc    proc;
  348. Ref closure;
  349. /*-----------------------------------------------------------------------------
  350.  
  351. (NO) SIDE EFFECTS
  352.     The current atom can be modified by the function RemoveAtom () during
  353.     the traversing of the list. This is the reason why the current pointer
  354.     is managed on the header.
  355.  
  356. -----------------------------------------------------------------------------*/
  357. {
  358.     return (List_EnumFrom (header, header->First, proc, closure));
  359. }
  360.  
  361. /*==============================================================================*/
  362.  
  363. long List_EnumBackFrom (header, atom, proc, closure)
  364. RefListHeader    header;
  365. Ref        atom;
  366. RefListEnumProc    proc;
  367. Ref        closure;
  368. {
  369.     Ref    cur, prev;
  370.     int    notInterrupted = TRUE;
  371.  
  372. #ifdef prlDEBUG
  373.     header->Lock += 1;
  374. #endif
  375.  
  376.     cur = atom;
  377.     while (cur != NULL && notInterrupted)
  378.     {
  379.     prev = List_Prev (header, cur);
  380.     notInterrupted = (*proc)(cur, closure);
  381.     cur = prev;
  382.     }
  383.  
  384. #ifdef prlDEBUG
  385.     header->Lock -=1;
  386. #endif
  387.     
  388.     return (notInterrupted);
  389. }
  390.  
  391. /*==============================================================================*/
  392.  
  393. long List_EnumBack (header, proc, closure)
  394. RefListHeader    header;
  395. RefListEnumProc    proc;
  396. Ref            closure;
  397. {
  398.     return (List_EnumBackFrom (header, header->Last, proc, closure));
  399. }
  400.  
  401. /*==============================================================================*/
  402.  
  403. /*ARGSUSED*/
  404. static long List_CountAtom (p, nbR)
  405. Ref p; 
  406. Ref nbR;
  407. {
  408.     long *nb = (long *)nbR;
  409.     
  410.     ++*nb;
  411.     return TRUE;
  412. }
  413.  
  414. long List_Card (header)
  415. RefListHeader header;
  416. {
  417.     long n = 0;
  418.     
  419.     List_Enum (header, List_CountAtom, &n);
  420.     return n;
  421. }
  422.  
  423. /*==============================================================================*/
  424.  
  425. long List_IsUnlink (links)
  426. RefListLinks links;
  427. {
  428.     return (links->Next == NULL && links->Prev == NULL);
  429. }
  430.  
  431. /*==============================================================================*/
  432.  
  433. void List_Cut (header, atom, newHeader)
  434. RefListHeader    header;
  435. Ref            atom;
  436. RefListHeader    newHeader;
  437. {
  438.     RefListGetLinksProc  getLinks = header->GetLinks;
  439.  
  440.     if (atom != List_Last (header))
  441.     {
  442.     newHeader->First = List_Next (header, atom);
  443.     newHeader->Last  = header->Last;
  444.  
  445.     header->Last = atom;
  446.  
  447.     /* Update the links */
  448.     (*getLinks)(atom)->Next = NULL;
  449.     (*getLinks)(newHeader->First)->Prev = NULL;
  450.     }
  451. }
  452.  
  453. /*==============================================================================*/
  454.