home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Professional / OS2PRO194.ISO / os2 / com / bbs / uupc / source / lib / strpool.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-09-20  |  10.0 KB  |  296 lines
  1. /*--------------------------------------------------------------------*/
  2. /*    s t r p o o l . c                                               */
  3. /*                                                                    */
  4. /*    String dynamic literal pool management for UUPC/extended        */
  5. /*                                                                    */
  6. /*    Copyright (c) 1992 by Kendra Electronic Wonderworks; all        */
  7. /*    rights reserved except those explicitly granted by the          */
  8. /*    UUPC/extended license.                                          */
  9. /*--------------------------------------------------------------------*/
  10.  
  11. /*
  12.  *    $Id: strpool.c 1.4 1993/09/20 04:38:11 ahd Exp $
  13.  *
  14.  *    $Log: strpool.c $
  15.  *     Revision 1.4  1993/09/20  04:38:11  ahd
  16.  *     TCP/IP support from Dave Watt
  17.  *     't' protocol support
  18.  *     OS/2 2.x support
  19.  *
  20.  * Revision 1.3  1992/12/04  01:00:27  ahd
  21.  * Delete allocating pool message; now handled by pools allocated summary
  22.  *
  23.  * Revision 1.2  1992/12/01  04:37:03  ahd
  24.  * Add SpeedOverMemory
  25.  *
  26.  * Revision 1.1  1992/11/22  20:58:55  ahd
  27.  * Initial revision
  28.  *
  29.  */
  30.  
  31. /*--------------------------------------------------------------------*/
  32. /*                        System include files                        */
  33. /*--------------------------------------------------------------------*/
  34.  
  35. #include <stdio.h>
  36. #include <stdlib.h>
  37. #include <string.h>
  38. #include <limits.h>
  39.  
  40. /*--------------------------------------------------------------------*/
  41. /*                    UUPC/extended include files                     */
  42. /*--------------------------------------------------------------------*/
  43.  
  44. #include "lib.h"
  45.  
  46. /*--------------------------------------------------------------------*/
  47. /*                          Local structures                          */
  48. /*--------------------------------------------------------------------*/
  49.  
  50. typedef struct str_queue {
  51.    struct str_queue *next_link;
  52.    size_t used;
  53.    char pool[BUFSIZ];
  54. }  STR_QUEUE;
  55.  
  56. /*--------------------------------------------------------------------*/
  57. /*                          Local variables                           */
  58. /*--------------------------------------------------------------------*/
  59.  
  60. static STR_QUEUE *anchor = NULL;
  61. static const size_t pool_size = BUFSIZ;
  62. static int pools      = 0;
  63.  
  64. #ifdef _UDEBUG
  65.  
  66. static int strings    = 0;
  67. static int used       = 0;
  68. static int duplicates = 0;
  69. static int saved      = 0;
  70.  
  71. /*--------------------------------------------------------------------*/
  72. /*                          Local prototypes                          */
  73. /*--------------------------------------------------------------------*/
  74.  
  75. void dump_pool( void );
  76.  
  77. #endif
  78.  
  79. /*--------------------------------------------------------------------*/
  80. /*    The problem:  UUPC/extended allocates large number of small     */
  81. /*    (<< 50 characters) string variables off the heap which are      */
  82. /*    never modified and never deallocated.  This means that the      */
  83. /*    possibly duplicate and relatively large overhead required by    */
  84. /*    malloc and causes these variables to waste space.               */
  85. /*                                                                    */
  86. /*    The solution:  We use this routine to maintain our own local    */
  87. /*    pool of storage for allocating NULL terminated strings out      */
  88. /*    of a chain of large buffers.  This allows us to both reduce     */
  89. /*    storage overhead by placing the strings end to end, and to      */
  90. /*    optionally scan the list for duplicates entries.                */
  91. /*                                                                    */
  92. /*    The duplicate string search can be questionable on a small      */
  93. /*    system, because we have to walk the entire list to locate       */
  94. /*    the duplicate.  However, a smaller system is less likely to     */
  95. /*    have a large dynamic string pool, so we take the hit anyway.    */
  96. /*--------------------------------------------------------------------*/
  97.  
  98. /*--------------------------------------------------------------------*/
  99. /*    s t r p o o l                                                   */
  100. /*                                                                    */
  101. /*    Allocate a string from the string poll                          */
  102. /*--------------------------------------------------------------------*/
  103.  
  104. char *strpool( const char *input , const char *file, size_t line)
  105. {
  106.    int len  = strlen( input );
  107.    int best_fit = SHRT_MAX;
  108.    char *result;
  109.  
  110.    STR_QUEUE *current = anchor;
  111.    STR_QUEUE *last    = anchor;
  112.    STR_QUEUE *save    = NULL;
  113.  
  114. /*--------------------------------------------------------------------*/
  115. /*                      Perform best fit search                       */
  116. /*--------------------------------------------------------------------*/
  117.  
  118.    while(current != NULL )
  119.    {
  120.       int available;
  121.  
  122. /*--------------------------------------------------------------------*/
  123. /*                 Scan current buffer for the string                 */
  124. /*--------------------------------------------------------------------*/
  125.  
  126.       if ( ! bflag[ F_SPEEDOVERMEMORY ] )
  127.       {
  128.          char *target = current->pool;
  129.          char *bufend = target + current->used;
  130.  
  131.          while( target < bufend )
  132.          {
  133.             int target_len = strlen( target );
  134.             int diff =  target_len - len;
  135.  
  136.             if ((diff >= 0 ) && equal( target + diff, input))
  137.             {
  138.  
  139. #ifdef _UDEBUG
  140.                duplicates ++;
  141.                saved += len + 1;
  142. #endif
  143.                return target+diff;
  144.             }
  145.  
  146.             target += target_len + 1;  /* Step to start of next string  */
  147.  
  148.          } /* while( offset < current->used ) */
  149.       }  /* if */
  150.  
  151. /*--------------------------------------------------------------------*/
  152. /*    No string in this buffer, look for best fit in case we need     */
  153. /*    to allocate the string from scratch                             */
  154. /*--------------------------------------------------------------------*/
  155.  
  156.       available = pool_size - current->used;
  157.  
  158.       if (( available < best_fit) && (available > len ))
  159.       {
  160.          best_fit = available;
  161.          save     = current;
  162.       }
  163.       else
  164.          last =  current;        /* Save last buffer in case we
  165.                                     have to chain new buffer in      */
  166.       current = current->next_link;
  167.    }  /* while */
  168.  
  169. /*--------------------------------------------------------------------*/
  170. /*    We have no matching string, we have to insert the new string    */
  171. /*    into our pool                                                   */
  172. /*--------------------------------------------------------------------*/
  173.  
  174.    if ( save == NULL )           /* We find a buffer?                */
  175.    {                             /* No --> Allocate a new one        */
  176.       pools ++;
  177.  
  178.       save = malloc( sizeof *save );
  179.       checkptr(save, file, line);
  180.  
  181.       if ( anchor == NULL )
  182.       {
  183.  
  184. #ifdef _UDEBUG
  185.          atexit( dump_pool );
  186. #endif
  187.  
  188.          anchor = save;
  189.       }
  190.       else
  191.          last->next_link = save;
  192.  
  193.       save->used = 0;
  194.       save->next_link = NULL;
  195.    }
  196.  
  197. /*--------------------------------------------------------------------*/
  198. /*    Save the string, update memory available in current pool,       */
  199. /*    and return to the caller with the new string                    */
  200. /*--------------------------------------------------------------------*/
  201.  
  202.    result = strcpy( save->pool + save->used, input );
  203.    save->used += len + 1;
  204.  
  205. #ifdef _UDEBUG
  206.    strings ++;
  207.    used    += len + 1;
  208. #endif
  209.  
  210.    return result;
  211.  
  212.  } /* strpool */
  213.  
  214. /*--------------------------------------------------------------------*/
  215. /*    s a f e f r e e                                                 */
  216. /*                                                                    */
  217. /*    Insure we are not freeing memory saved for a pool               */
  218. /*--------------------------------------------------------------------*/
  219.  
  220. void safefree( void *input , const char *file, size_t line)
  221. {
  222.    STR_QUEUE *current = anchor;
  223.    int buffers = 0;
  224.    while( current != NULL )
  225.    {
  226.       buffers ++;
  227.       if (( input > (void *) current ) &&
  228.           (input < (void *) (current->pool + pool_size ) ))
  229.       {
  230.          printmsg(0,"Attempt to free string \"%s\" allocated via newstr() in pool %d",
  231.                   input , buffers );
  232.  
  233.          bugout( line, file);
  234.       }
  235.  
  236.       current = current->next_link;
  237.    }
  238.  
  239. #undef free
  240.  
  241.    free(input);
  242.  
  243. } /* safefree */
  244.  
  245. #ifdef _UDEBUG
  246.  
  247. /*--------------------------------------------------------------------*/
  248. /*    d u m  p _ p o o l                                              */
  249. /*                                                                    */
  250. /*    Print the free storage pool                                     */
  251. /*--------------------------------------------------------------------*/
  252.  
  253. void dump_pool( void )
  254. {
  255.  
  256.    STR_QUEUE *current = anchor;
  257.    int buffers = 0;
  258.  
  259.    printmsg(3,"Allocated %d bytes in %d strings "
  260.               "requiring %d pools of %d bytes each",
  261.               used, strings, pools, pool_size );
  262.  
  263.    if ( duplicates )
  264.       printmsg(3,"Saved %d bytes in %d redundant strings",
  265.                saved, duplicates);
  266.  
  267.    if ( debuglevel > 5 )
  268.    while(current != NULL )
  269.    {
  270.       size_t offset = 0;
  271.       size_t strings = 0;
  272.       buffers ++;
  273.  
  274.       printmsg(5,"Buffer %d length is %d bytes",buffers, current->used);
  275.  
  276.       while( offset < current->used )
  277.       {
  278.          size_t target_len = strlen( current->pool + offset );
  279.          strings ++;
  280.          printmsg(5,"[%d,%02d,%02d]=\"%s\"",
  281.                      buffers,
  282.                      strings,
  283.                      target_len,
  284.                      current->pool + offset);
  285.          offset += target_len +1;  /* Go to end of string            */
  286.  
  287.       } /* while( offset < current->used ) */
  288.  
  289.       current = current->next_link;
  290.  
  291.    }  /* while */
  292.  
  293. } /* dump_pool */
  294.  
  295. #endif
  296.