home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / snip9707.zip / LLD.C < prev    next >
C/C++ Source or Header  |  1997-07-05  |  20KB  |  663 lines
  1. /* +++Date last modified: 05-Jul-1997 */
  2.  
  3. /* =======================================================================
  4.     LLD.c           Generic Doubly Linked Lists for fixed size data.
  5.                     Each List has its own specific data size.
  6.                     This version uses dummy head and dummy tail nodes.
  7.                     Which prevents special handling for the first and last
  8.                     nodes.
  9.  
  10.                     v1.00  94-08-21
  11.                     v1.01  95-10-21  Changed ListCountInit to unsigned.
  12.  
  13.                     Compile with NDEBUG not defined for debugging version.
  14.                     Compile with NDEBUG defined for production version.
  15.  
  16.                     The node pointers are restricted to valid values.
  17.                     They point only in empty lists to invalid data.
  18.  
  19.                     Possible future enhancements:
  20.                     - List(s) of free nodes for fast node memory alloc.
  21.                     - FindFirst() & FindNext().
  22.                     - Data access via first and/or last node pointers.
  23.                       (duplicate the functions and change .current to
  24.                       .first or .last)
  25.                     - Node deletion via first and/or last node pointers.
  26.                       (as for access functions, then simplify ...)
  27.  
  28.  _____              This version is Public Domain.
  29.  /_|__|             A.Reitsma, Delft, The Netherlands.
  30. /  | \  --------------------------------------------------------------- */
  31.  
  32. #include <stdarg.h>         /* variable arg handling */
  33. #include <assert.h>         /* debugging */
  34.  
  35. #if defined( __TURBOC__ ) && !defined( __BORLANDC__ )
  36.  #include <stdio.h> /* required for early Turbo compilers with assert() */
  37. #endif
  38.  
  39. #include "ll_defs.h"        /* debugging incl MALLOC (re-) definition   */
  40. #include "LLD.h"            /* also includes extkword.h if necessary    */
  41.  
  42. #define NO_PROBLEMS LIST_NO_PROBLEMS /* local redefinition */
  43.  
  44. struct Node
  45. {
  46.     struct Node * next;
  47.     struct Node * prev;
  48.     int data;               /* also place-holder for larger items.      */
  49. };                          /* actual nodes have various sizes,         */
  50.                             /* but a fixed size within a list.          */
  51. struct ListHead
  52. {
  53.     struct Node * current;  /* points to the actual current node        */
  54.     struct Node * first;    /* always points to dummy head node         */
  55.     struct Node * last;     /* always points to dummy tail node         */
  56.     int itemsize ;          /* zero value: used as 'list not used' flag */
  57. };
  58.  
  59. #define ERR_MEMORY          -1
  60.  
  61. #define NODE_MALLOC(list)   (struct Node *) \
  62.                             MALLOC( ListControl[ list ].itemsize \
  63.                                     + 2 * sizeof( struct Node * ), char )
  64.  
  65. #define NODE_FREE(node)     FREE(node)
  66.  
  67. /* ---- Local data ---------------------------------------------------- */
  68.  
  69. static struct ListHead * ListControl = NULL;
  70. static unsigned int ListCount ;
  71.  
  72. /* ---- LL system management ------------------------------------------ */
  73.  
  74. static int ListInit( int List, int ItemSize )
  75. {
  76.     struct Node * Tmp ;
  77.  
  78.     if( 0 != ItemSize )
  79.     {
  80.         /* create dummy head node
  81.         */
  82.         Tmp = NODE_MALLOC( List );
  83.         if( NULL == Tmp )
  84.         {
  85.             return ERR_MEMORY ;
  86.         }
  87.         Tmp->prev = NULL ;     /* NULL identifies it as dummy head node */
  88.         Tmp->data = (int)0xA709;       /* dummy value                   */
  89.         ListControl[ List ].first = Tmp ;
  90.  
  91.         /* create dummy tail node
  92.         */
  93.         Tmp = NODE_MALLOC( List );
  94.         if( NULL == Tmp )
  95.         {
  96.             NODE_FREE( Tmp );          /* no need to cause memory leaks */
  97.             ListControl[ List ].first = NULL ; /* or other errors       */
  98.             return ERR_MEMORY ;        /* even if we're in trouble ...  */
  99.         }
  100.         Tmp->next = NULL ;     /* NULL identifies it as dummy tail node */
  101.         Tmp->data = (int)0xA725;       /* dummy value                   */
  102.         Tmp->prev = ListControl[ List ].first ;
  103.  
  104.         ListControl[ List ].current     =
  105.         ListControl[ List ].last        =
  106.         ListControl[ List ].first->next = Tmp ;
  107.     }
  108.     else
  109.     {
  110.         ListControl[ List ].current =
  111.         ListControl[ List ].first   =
  112.         ListControl[ List ].last    = NULL ;
  113.     }
  114.  
  115.     ListControl[ List ].itemsize = ItemSize ; /* zero: list not used    */
  116.     return NO_PROBLEMS ;
  117. }
  118.  
  119. int LLDsystemInit( unsigned ListCountInit )
  120. {
  121.     assert( (unsigned) ( ListCountInit -1 ) <= 20 -1 );
  122.                  /* higher than 20 is ridiculous for an initial setup   */
  123.                  /* zero is useless                                     */
  124.  
  125.     if( NULL != ListControl )
  126.     {
  127.         return NO_PROBLEMS ; /* LL system already initialized */
  128.     }
  129.  
  130.     ListControl = MALLOC( ListCountInit, struct ListHead );
  131.     if( NULL == ListControl )
  132.     {
  133.         return ERR_MEMORY ;
  134.     }
  135.  
  136.     for( ListCount = 0 ; ListCount < ListCountInit ; ListCount++ )
  137.         ListInit( ListCount, 0 ); /* just mark it as usable ... */
  138.  
  139.     /* ListCount is now ListCountInit */
  140.     assert( ListCount == ListCountInit );
  141.  
  142.     return NO_PROBLEMS;
  143. }
  144.  
  145. int LLDcreate( int ItemSize )
  146. {
  147.     unsigned List ;
  148.  
  149.     assert( (unsigned) ( ItemSize -1 ) < 1024 -1 ) ;
  150.                              /* limit to 1kB. A size of 0 is ridiculous */
  151.  
  152.     /* trigger automatic system initialisation if necessary
  153.     */
  154.     if( NULL == ListControl  &&  0 != LLDsystemInit( 1 ))
  155.     {
  156.         return ERR_MEMORY ;
  157.     }
  158.  
  159.     /* Look for empty slot
  160.     */
  161.     for( List = 0; List < ListCount; List++ )
  162.     {
  163.         if( 0 == ListControl[ List ].itemsize )
  164.             break;
  165.     }
  166.  
  167.     /*  What if NO EMPTY slot ???
  168.     */
  169.     if( List == ListCount )
  170.     {
  171.         struct ListHead * tmp ;         /* ListControl expansion needed */
  172.  
  173.         tmp = MALLOC( ListCount + 1, struct ListHead );
  174.         if( NULL == tmp )
  175.         {
  176.             return ERR_MEMORY ;
  177.         }
  178.  
  179.         memcpy( tmp, ListControl, ListCount * sizeof( struct ListHead ));
  180.         ListControl = tmp ;
  181.         ListCount++ ;
  182.     }
  183.  
  184.     /* create dummy head node and set up ListControl for the list.
  185.     */
  186.     if( ERR_MEMORY == ListInit( List, ItemSize ))
  187.     {
  188.         return ERR_MEMORY ;
  189.     }
  190.  
  191.     return (int) List ;
  192. }
  193.  
  194. void LLDdelete( int List )
  195. {
  196.     struct Node * Tmp ;
  197.     struct Node * Old ;
  198.  
  199.     assert( (unsigned) List < ListCount );
  200.  
  201.     Tmp = ListControl[ List ].first ; /* dummies are also deleted !!!   */
  202.     while( NULL != Tmp )              /* still assuming last node has   */
  203.     {                                 /* a NULL next pointer ...        */
  204.         Old = Tmp ;
  205.         Tmp = Old->next;
  206.         NODE_FREE( Old ); /* data already presumed to be deleted */
  207.     }
  208.  
  209.     ListInit( List, 0 ); /* 0: mark list as not used. */
  210.  
  211.     return ;
  212. }
  213.  
  214. /* ---- LL system maintenance ----------------------------------------- */
  215.  
  216. int LLDcheck( int List )
  217. {
  218.     if( NULL == ListControl )
  219.     {
  220.         return LIST_SYSTEM_NULL ;
  221.     }
  222.  
  223.     if( (unsigned) List >= ListCount )
  224.     {
  225.         return LIST_INV_NUMBER ;
  226.     }
  227.  
  228.     if( 0 == ListControl[ List ].itemsize )
  229.     {
  230.         return LIST_NOT_CREATED ;
  231.     }
  232.  
  233.     if( NULL == ListControl[ List ].first
  234.         || NULL == ListControl[ List ].first->next    /* missing tail ? */
  235.         || NULL != ListControl[ List ].first->prev )
  236.     {
  237.         return LIST_ERR_HEAD ;
  238.     }
  239.  
  240.     /* Validate current pointer
  241.     */
  242.     if( NULL == ListControl[ List ].current )
  243.     {
  244.         return LIST_CORRUPT7 ;    /* shouldn't be NULL with a good head */
  245.     }
  246.  
  247.     if( NULL != ListControl[ List ].first->next->next ) /* empty list ? */
  248.     {                                                   /* not empty.   */
  249.         struct Node * tmp = ListControl[ List ].first ;
  250.  
  251.         if( NULL == ListControl[ List ].current->next )
  252.         {
  253.             return LIST_CORRUPT6 ; /* a NULL next pointer is only valid */
  254.         }                          /* for an empty list.                */
  255.  
  256.         /* look for .current in list,
  257.            checking the .prev links along the way
  258.         */
  259.         do
  260.         {
  261.             tmp = tmp->next ;
  262.  
  263.             if( NULL == tmp || NULL == tmp->prev
  264.                 || tmp != tmp->prev->next )
  265.             {
  266.                 return LIST_CORRUPT5 ;  /* current not found in list */
  267.             }                           /* or link to/from next node */
  268.                                         /* invalid                   */
  269.         }while( tmp != ListControl[ List ].current );
  270.  
  271.         /* Found .current in list. Also without link errors.
  272.            Now look for valid last node pointer in the list,
  273.            checking the .prev links along the way
  274.            Note that .current itself is never supposed to be equal
  275.            to .last (which points to the dummy tail) !
  276.         */
  277.         if( NULL == ListControl[ List ].last )
  278.         {
  279.             return LIST_ERR_LAST ;
  280.         }
  281.  
  282.         do
  283.         {
  284.             tmp = tmp->next ;
  285.             if( NULL == tmp || NULL == tmp->prev
  286.                 || tmp != tmp->prev->next )
  287.             {
  288.                 return LIST_CORRUPT4 ;  /* last not found in list    */
  289.             }                           /* or link to/from prev node */
  290.                                         /* invalid                   */
  291.         }while( tmp != ListControl[ List ].last );
  292.  
  293.         /* Found .last in list but is it really a valid last pointer?
  294.            Note: tmp == .last
  295.         */
  296.         if( NULL != tmp->next )
  297.         {
  298.             return LIST_CORRUPT3 ;
  299.         }
  300.  
  301.         return NO_PROBLEMS ;
  302.     }
  303.  
  304.     /* .first->next->next == NULL  =>  list is empty
  305.     */
  306.     if( ListControl[ List ].current != ListControl[ List ].first->next )
  307.     {
  308.         return LIST_CORRUPT2 ;
  309.     }
  310.  
  311.     if( ListControl[ List ].last != ListControl[ List ].first->next
  312.         || ListControl[ List ].last
  313.                              != ListControl[ List ].current->prev->next )
  314.     {
  315.         return LIST_CORRUPT1 ;
  316.     }
  317.  
  318.     return LIST_EMPTY ;
  319. }
  320.  
  321. /* ---- node management ----------------------------------------------- */
  322.  
  323. int LLDnodeInsert( int List, ... )      /* insert _BEFORE_ current node */
  324. {
  325.     va_list DataPtr ;
  326.     int Retval ;
  327.  
  328.     /* set DataPtr to the address of "..."
  329.        then action, cleanup and return.
  330.     */
  331.     va_start( DataPtr, List );
  332.  
  333.     Retval = LLDnodeInsertFrom( List, DataPtr );
  334.  
  335.     va_end( DataPtr );
  336.     return Retval ;
  337. }
  338.  
  339. int LLDnodeAdd( int List, ... )          /* insert _AFTER_ current node */
  340. {
  341.     va_list DataPtr ;
  342.     int Retval ;
  343.  
  344.     /* set DataPtr to the address of "..."
  345.        then action, cleanup and return.
  346.     */
  347.     va_start( DataPtr, List );
  348.  
  349.     Retval = LLDnodeAddFrom( List, DataPtr );
  350.  
  351.     va_end( DataPtr );
  352.     return Retval ;
  353. }
  354.  
  355. int LLDnodePrepend( int List, ... )             /* insert as first node */
  356. {
  357.     va_list DataPtr ;
  358.     int Retval ;
  359.  
  360.     /* set DataPtr to the address of "..."
  361.        then action, cleanup and return.
  362.     */
  363.     va_start( DataPtr, List );
  364.  
  365.     Retval = LLDnodePrependFrom( List, DataPtr );
  366.  
  367.     va_end( DataPtr );
  368.     return Retval ;
  369. }
  370.  
  371. int LLDnodeAppend( int List, ... )               /* insert as last node */
  372. {
  373.     va_list DataPtr ;
  374.     int Retval ;
  375.  
  376.     /* set DataPtr to the address of "..."
  377.        then action, cleanup and return.
  378.     */
  379.     va_start( DataPtr, List );
  380.  
  381.     Retval = LLDnodeAppendFrom( List, DataPtr );
  382.  
  383.     va_end( DataPtr );
  384.     return Retval ;
  385. }
  386.  
  387. int LLDnodeInsertFrom( int List, void * Source )
  388. {                                       /* insert _BEFORE_ current node */
  389.     struct Node * New ;
  390.  
  391.     assert( (unsigned) List < ListCount );
  392.  
  393.     /* create new node if possible
  394.     */
  395.     New = NODE_MALLOC( List );
  396.     if( NULL == New )
  397.     {
  398.         return ERR_MEMORY ;
  399.     }
  400.  
  401.     /* fill node with data, link to next and previous nodes
  402.        and adjust current node pointer
  403.     */
  404.     memcpy( & New->data, Source, ListControl[ List ].itemsize );
  405.     New->next = ListControl[ List ].current;
  406.     New->prev = ListControl[ List ].current->prev;
  407.  
  408.     ListControl[ List ].current->prev = New ;
  409.     New->prev->next = New ;
  410.  
  411.     ListControl[ List ].current = New ;
  412.  
  413.     return NO_PROBLEMS;
  414. }
  415.  
  416. int LLDnodeAddFrom( int List, void * Source )
  417. {                                        /* insert _AFTER_ current node */
  418.     struct Node * New ;
  419.  
  420.     assert( (unsigned) List < ListCount );
  421.  
  422.     /* create new node if possible
  423.     */
  424.     New = NODE_MALLOC( List );
  425.     if( NULL == New )
  426.     {
  427.         return ERR_MEMORY ;
  428.     }
  429.  
  430.     /* fill node with data and link to next and previous nodes
  431.        with special handling when the current node pointer points
  432.        to the dummy tail node: i.e it is an empty list.
  433.        (the same case in a non-empty list is made not to occur.)
  434.     */
  435.     memcpy( & New->data, Source, ListControl[ List ].itemsize );
  436.  
  437.     if( NULL != ListControl[ List ].current->next )
  438.         ListControl[ List ].current = ListControl[ List ].current->next ;
  439.  
  440.     New->next = ListControl[ List ].current;
  441.     New->prev = ListControl[ List ].current->prev;
  442.  
  443.     ListControl[ List ].current->prev = New ;
  444.     New->prev->next = New ;
  445.  
  446.     ListControl[ List ].current = New ;
  447.  
  448.     return NO_PROBLEMS;
  449. }
  450.  
  451. int LLDnodePrependFrom( int List, void * Source )
  452. {                                               /* insert as first node */
  453.     struct Node * New ;
  454.  
  455.     assert( (unsigned) List < ListCount );
  456.  
  457.     /* create new node if possible
  458.     */
  459.     New = NODE_MALLOC( List );
  460.     if( NULL == New )
  461.     {
  462.         return ERR_MEMORY ;
  463.     }
  464.  
  465.     /* fill node with data and link to dummy head and actual first nodes
  466.     */
  467.     memcpy( & New->data, Source, ListControl[ List ].itemsize );
  468.     New->prev = ListControl[ List ].first;     /* == .first->next->prev */
  469.     New->next = ListControl[ List ].first->next;
  470.  
  471.     ListControl[ List ].first->next = New;
  472.     New->next->prev = New ;
  473.  
  474.     /* Prevent .current from pointing at the dummy tail
  475.        (New is the only normal node...)
  476.     */
  477.     if( NULL == ListControl[ List ].current->next )
  478.         ListControl[ List ].current = New;
  479.  
  480.     return NO_PROBLEMS;
  481. }
  482.  
  483. int LLDnodeAppendFrom( int List, void * Source )
  484. {                                                /* insert as last node */
  485.     struct Node * New ;
  486.  
  487.     assert( (unsigned) List < ListCount );
  488.  
  489.     /* create new node if possible
  490.     */
  491.     New = NODE_MALLOC( List );
  492.     if( NULL == New )
  493.     {
  494.         return ERR_MEMORY ;
  495.     }
  496.  
  497.     /* fill node with data and link to dummy tail and actual last nodes
  498.     */
  499.     memcpy( & New->data, Source, ListControl[ List ].itemsize );
  500.     New->next = ListControl[ List ].last ;      /* == .last->prev->next */
  501.     New->prev = ListControl[ List ].last->prev;
  502.  
  503.     ListControl[ List ].last->prev = New ;
  504.     New->prev->next = New ;
  505.  
  506.     /* Prevent .current from pointing at the dummy tail
  507.        (New is the only normal node...)
  508.     */
  509.     if( NULL == ListControl[ List ].current->next )
  510.         ListControl[ List ].current = New;
  511.  
  512.     return NO_PROBLEMS;
  513. }
  514.  
  515. void LLDnodeDelete( int List )
  516. {
  517.     struct Node * Old = ListControl[ List ].current ;
  518.  
  519.     assert( (unsigned) List < ListCount );
  520.  
  521.     if( NULL == ListControl[ List ].current->next )
  522.     {
  523.         return ;  /* don't delete dummy tail node (list is empty) */
  524.     }
  525.  
  526.     /* adjust links
  527.     */
  528.     Old->prev->next = Old->next ;
  529.     Old->next->prev = Old->prev ;
  530.  
  531.     /* adjust current node pointer
  532.        prevent it from pointing to the dummy tail node
  533.     */
  534.     if( NULL != Old->next->next )
  535.         ListControl[ List ].current = Old->next ;
  536.     else
  537.         ListControl[ List ].current = Old->prev ;
  538.  
  539.     NODE_FREE( Old );
  540.  
  541.     return ;
  542. }
  543.  
  544. int LLDnodeFind( int List, CompFunPtr Compare, void * DataPtr )
  545. {                        /* FindFirst/FindNext format may be needed ... */
  546.     int RetVal ;
  547.  
  548.     assert( (unsigned) List < ListCount );
  549.  
  550.     if( NULL == ListControl[ List ].first->next->next ) /* empty list ? */
  551.     {
  552.         return 2; /* a compare usually returns just -1, 0 or 1 !!! */
  553.     }
  554.  
  555.     /* note: current->next will never be NULL in a non-empty list */
  556.  
  557.     if( NULL == Compare ) /* default to memcmp with .itemsize */
  558.     {
  559.         while( 0 != (RetVal = memcmp( DataPtr,
  560.                                       & ListControl[ List ].current->data,
  561.                                       ListControl[ List ].itemsize ))
  562.                && NULL != ListControl[ List ].current->next->next )
  563.         {
  564.             ListControl[ List ].current=ListControl[ List ].current->next;
  565.         }
  566.         return RetVal ;
  567.     }
  568.     else
  569.     {
  570.         while( 0 != (RetVal = (*Compare)( DataPtr,
  571.                                    & ListControl[ List ].current->data ))
  572.                && NULL != ListControl[ List ].current->next->next )
  573.         {
  574.             ListControl[ List ].current=ListControl[ List ].current->next;
  575.         }
  576.         return RetVal ;
  577.     }
  578. }
  579.  
  580. /* ---- current node pointer management ------------------------------- */
  581.  
  582. int  LLDnodePtr2First( int List )
  583. {
  584.     assert( (unsigned) List < ListCount );
  585.  
  586.     ListControl[ List ].current = ListControl[ List ].first->next ;
  587.  
  588.     return NULL != ListControl[ List ].first->next->next ;
  589. }
  590.  
  591. int  LLDnodePtr2Last( int List )
  592. {
  593.     assert( (unsigned) List < ListCount );
  594.  
  595.     ListControl[ List ].current = ListControl[ List ].last->prev ;
  596.  
  597.     return NULL != ListControl[ List ].last->prev->prev ;
  598. }
  599.  
  600. int  LLDnodePtr2Next( int List )
  601. {
  602.     assert( (unsigned) List < ListCount );
  603.  
  604.     if( NULL == ListControl[ List ].current->next       /* empty list ? */
  605.         || NULL == ListControl[ List ].current->next->next ) /* at end ?*/
  606.     {
  607.         return 0 ;             /* do not allow the current node pointer */
  608.     }                          /* to point at the dummy tail node ...   */
  609.  
  610.     ListControl[ List ].current = ListControl[ List ].current->next ;
  611.     return 1 ;
  612. }
  613.  
  614. int  LLDnodePtr2Prev( int List )
  615. {
  616.     assert( (unsigned) List < ListCount );
  617.  
  618.     if( NULL == ListControl[ List ].current->prev       /* empty list ? */
  619.         || NULL == ListControl[ List ].current->prev->prev ) /* begin ? */
  620.     {
  621.         return 0 ;             /* do not allow the current node pointer */
  622.     }                          /* to point at the dummy head node ...   */
  623.  
  624.     ListControl[ List ].current = ListControl[ List ].current->prev ;
  625.     return 1 ;
  626. }
  627.  
  628. /* ---- stored data management ---------------------------------------- */
  629.  
  630. int LLDnodeInt( int List )
  631. {
  632.     return ListControl[ List ].current->data;
  633. }
  634.  
  635. long LLDnodeLong( int List )
  636. {
  637.     return *((long *) &ListControl[ List ].current->data );
  638. }
  639.  
  640. void * LLDnodePtr( int List )
  641. {
  642.     return *((void **) &ListControl[ List ].current->data );
  643. }
  644.  
  645. void FAR * LLDnodeFptr( int List )
  646. {
  647.     return *((void FAR **) &ListControl[ List ].current->data );
  648. }
  649.  
  650. int LLDnodeDataTo( int List, void * Destination )
  651. {
  652.     if( NULL != Destination )
  653.     {
  654.         memcpy( Destination,
  655.                 & ListControl[ List ].current->data,
  656.                 ListControl[ List ].itemsize );
  657.     }
  658.  
  659.     return ListControl[ List ].itemsize ;       /* size needed for blob */
  660. }
  661.  
  662. /* ==== LLD.c  end ==================================================== */
  663.