home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 5 Edit / 05-Edit.zip / me34src.zip / me3 / util / dtable.c < prev    next >
C/C++ Source or Header  |  1995-01-14  |  7KB  |  246 lines
  1. /* dtable.c : dynamic tables
  2.  * xpand_dTable:  Make sure a dTable can hold n more items.
  3.  *   Input:
  4.  *     dtable:         A pointer to a dTable.
  5.  *     n:         Number of items that will be added to the table after
  6.  *               this call.
  7.  *     initial_size: Number of cells to initialize table to.
  8.  *     step:         Grow table by multiples of step cells.
  9.  *   Returns:
  10.  *     TRUE:  Table has room for n items.
  11.  *     FALSE: Not enough memory for n new items.  The table may have been
  12.  *       cleared, check the size.
  13.  *   How to use:
  14.  *     #include "dtable.h"
  15.  *     typedef struct { ... } Blob;
  16.  *     * IF dTable is global (or static):
  17.  *       declare_and_init_dTable(foobar,Blob);
  18.  *     * IF dTable is a typdef'ed global:
  19.  *       typedef declare_dTable_of(Blob) FooBar;
  20.  *       FooBar foobar = initial_dTable_data(foobar);
  21.  *     * IF dTable is automatic (local):
  22.  *       declare_dTable_of(Blob) foobar;
  23.  *         INIT_dTable(&foobar); or initialize_dTable(&foobar,sizeof(Blob));
  24.  *     xpand_dTable(&foobar, n, initial_size, step);
  25.  *     foobar.table[j] = a_Blob;    -- do this n times 
  26.  *   Notes:
  27.  *     Make sure the dTable is initialized!  See "How to use" above.
  28.  *     If you want to reuse the table: reset_dTable(dtable);
  29.  *     sizeof_dTable(dtable) is the number of items in the table (not the
  30.  *       max).
  31.  *     To release the dtable: free_dTable(dtable).  If you are going to
  32.  *       reuse the table header, do an INIT_dTable(dtable) after the
  33.  *       free.
  34.  *     extern declare_dTable_of(Blob) foobar; is legal.
  35.  *     typedef declare_dTable_of(Blob) foobar; is legal.
  36.  *     If initial_size is not big enough to hold the first n items, the
  37.  *       table is created n+step big.
  38.  *   WARNINGS:
  39.  *     Table may be moved during xpand_dTable().  So don't expect
  40.  *       ptr = foo->table; xpand_dTable(foo,...) to work.  Always set ptr
  41.  *       after the xpand.
  42.  *     For 2 byte int machines (eg MS-DOS), there are some overflow checks.
  43.  *       The following MUST be true for them to work:
  44.  *         - sizeof(int) < sizeof(long int)
  45.  *         - In xpand_dtable(dtable, n, initial_size, step), the args n,
  46.  *         initial_size and step are int and therefore must be <= INT_MAX
  47.  *         (32k - 1).  DON'T change them to unsigned int or pass in
  48.  *         anything bigger - it can break the checking.
  49.  *         - malloc and realloc must take size_t (unsigned int) ie be able
  50.  *           to allocate up to 64k bytes.
  51.  *
  52.  * Craig Durland 6/89, 1/93
  53.  */
  54.  
  55. /* Copyright 1989, 1990 Craig Durland
  56.  *   Distributed under the terms of the GNU General Public License.
  57.  *   Distributed "as is", without warranties of any kind, but comments,
  58.  *     suggestions and bug reports are welcome.
  59.  */
  60.  
  61. #include <limits.h>        /* for INT_MAX */
  62. #include "const.h"
  63. #include "dtable.h"
  64.  
  65. extern char *malloc(), *realloc();
  66.  
  67.  
  68. void initialize_dTable(dtable,blob_size) dTable *dtable;
  69. {
  70.   dtable->max_items = dtable->num_items = 0;
  71.   dtable->blob_size = blob_size;
  72.   dtable->table = NULL;        /* for debugging purposes */
  73. }
  74.  
  75.  
  76. void free_dTable(dtable) dTable *dtable;
  77.     { if (dtable->max_items) free((char *)dtable->table); }
  78.  
  79.  
  80.     /* Pad dtable so there is enough room for n more items without having to
  81.      *   malloc().  This is useful when you know you are going to add a
  82.      *   bunchg of stuff but not all at once.
  83.      */
  84. pad_dTable(dtable, n) dTable *dtable;
  85. {
  86.   unsigned int z;
  87.  
  88.   z = dtable->num_items;
  89.   if (!xpand_dTable(dtable, n, 0, 1)) return FALSE;
  90.   dtable->num_items = z;
  91.  
  92.   return TRUE;
  93. }
  94.  
  95.  
  96. #define SMALL_INT    (INT_MAX == 0x7FFF)    /* (sizeof(int) == 2) */
  97.  
  98. #if SMALL_INT    /* Check to see if trying to overflow a size_t */
  99.  
  100. static int overflowed(), too_big();
  101.  
  102. #define CHECK_REQUEST_SIZE if (too_big(dtable, n)) return FALSE;
  103. #define CHECK_FOR_OVERFLOW if (overflowed(dtable, &blobs, n)) return FALSE;
  104.  
  105. #else    /* Don't need no steenking overflow checking */
  106.  
  107. #define CHECK_FOR_OVERFLOW
  108. #define CHECK_REQUEST_SIZE
  109.  
  110. #endif    /* SMALL_INT */
  111.  
  112. xpand_dTable(dtable, n, initial_size, step) dTable *dtable;
  113. {
  114.   char *ptr;
  115.   int blob_size;
  116.   unsigned int max_items, num_items;
  117.   long int blobs;
  118.  
  119.   CHECK_REQUEST_SIZE
  120.  
  121.   max_items = dtable->max_items;
  122.   num_items = (dtable->num_items += n);
  123.  
  124.     /* check to see if already have enough room for n more items */
  125.   if (num_items <= max_items) return TRUE;
  126.  
  127.   blob_size = dtable->blob_size;
  128.   if (max_items == 0)                /* table not allocated yet */
  129.   {
  130.     if ((blobs = initial_size) < num_items) /* initial size ain't big enough */
  131.      blobs = num_items + step;
  132.     CHECK_FOR_OVERFLOW
  133.     ptr = malloc((unsigned int)blobs * blob_size);
  134.   }
  135.   else                        /* table full, make bigger */
  136.   {
  137.     blobs = (num_items - max_items + step - 1)/step;
  138.     blobs = blobs*step + max_items;
  139.     CHECK_FOR_OVERFLOW
  140.     ptr = realloc(dtable->table, (unsigned int)blobs * blob_size);
  141. #ifdef __STDC__
  142.     if (!ptr)    /* in ANSI C, realloc may fail but table is still OK */
  143.     {
  144.       dtable->num_items -= n;
  145.       return FALSE;
  146.     }
  147. #endif    /* __STDC__ */
  148.   }
  149.  
  150.   dtable->max_items = blobs;
  151.   if ((dtable->table = ptr) == NULL)    /* out of memory => table is mush */
  152.     { initialize_dTable(dtable,blob_size); return FALSE; }
  153.  
  154.   return TRUE;
  155. }
  156.  
  157.  
  158. #if SMALL_INT    /* Check to see if trying to overflow a size_t */
  159.  
  160. static int too_big(dtable, n) dTable *dtable; int n;
  161. {
  162.   unsigned int num_items = dtable->num_items;
  163.  
  164.   return (n < 0 || num_items + n < num_items);
  165.  
  166. /* 
  167.   if ((long int)UINT_MAX <= ((long int)n + num_items))
  168.     return TRUE;
  169. */
  170. }
  171.  
  172. static int overflowed(dtable, blobs, n)
  173.   dTable *dtable; long int *blobs; int n;
  174. {
  175.   long int z = *blobs;
  176.   int blob_size = dtable->blob_size;
  177.  
  178.   if ((long int)UINT_MAX <= (z * blob_size))    /* Can't have what they want */
  179.   {                /* but maybe they can have what they need */
  180.     z = (long int)UINT_MAX / blob_size;
  181.     if (z < dtable->num_items)            /* Won't fit no way, no how */
  182.     {
  183.       dtable->num_items -= n;
  184.       return TRUE;
  185.     }
  186.     *blobs = z;
  187.   }
  188.   return FALSE;
  189. }
  190. #endif    /* SMALL_INT */
  191.  
  192. #ifdef TEST
  193. /* ******************************************************************** */
  194. /* ******************************* TEST ******************************* */
  195. /* ******************************************************************** */
  196.  
  197. typedef struct { char *name; int token; } Blob;
  198.  
  199. declare_and_init_dTable(foo,Blob);
  200. declare_and_init_dTable(bar,char);
  201.  
  202. main(argc, argv) char **argv;
  203. {
  204.   char zik[100], *name, *savestr();
  205.   int n, s, j, step;
  206.   
  207.   if (argc != 1)
  208.   {
  209.     if (argc == 2)
  210.     {
  211.       printf("dtable <step> n [n ...]\n");
  212.       exit(1);
  213.     }
  214.  
  215.     step = atoi(argv[1]);
  216.  
  217.     for (j = 2; j < argc; j++)
  218.     {
  219.       s = xpand_dTable(&bar, atoi(argv[j]), 0, step);
  220.       printf("%d | num_items = %u, max_items = %u\n",
  221.     s, sizeof_dTable(&bar), bar.max_items);
  222.     }
  223.  
  224.     exit(0);
  225.   }
  226.  
  227.   for (j = 0; 1; j++)
  228.   {
  229.     printf("name: ");  gets(zik);
  230. if (*zik=='q') break;
  231.     name = savestr(zik);
  232.     printf("token: "); gets(zik); n = atoi(zik);
  233.     s = xpand_dTable(&foo, 1, 3, 2);
  234.     foo.table[j].name = name;
  235.     foo.table[j].token = n;
  236.     printf("%d | num_items = %d, max_items = %d: %d %s\n",
  237.     s, 
  238.     sizeof_dTable(&foo),
  239.     foo.max_items,
  240.     foo.table[j].token,foo.table[j].name);
  241.   }
  242.   for (n=0; n<sizeof_dTable(&foo); n++) 
  243.     printf("%d: %d %s\n",n, foo.table[n].token,foo.table[n].name);
  244. }
  245. #endif
  246.