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