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