home *** CD-ROM | disk | FTP | other *** search
/ APDL Public Domain 1 / APDL_PD1A.iso / program / language / icon / Source / Iconx / C / Rmemexp < prev    next >
Encoding:
Text File  |  1990-07-19  |  12.9 KB  |  445 lines
  1. /*
  2.  * File: rmemexp.c - memory management functions for expandable regions
  3.  *  Contents: initalloc, reclaim, malloc, calloc, free
  4.  */
  5.  
  6. /*
  7.  * Prototypes.
  8.  */
  9.  
  10. hidden    novalue moremem    Params((uword units));
  11. hidden    novalue    reclaim    Params((int region));
  12.  
  13. word xcodesize;
  14.  
  15. /*
  16.  * initalloc - initialization routine to allocate memory regions
  17.  */
  18.  
  19. novalue initalloc(codesize)
  20. word codesize;
  21.    {
  22.  
  23.    xcodesize = codesize;
  24.  
  25.    /*
  26.     * Establish icode region
  27.     */
  28.    code = (char *)sbrk((word)0);
  29.  
  30.    /*
  31.     * Set up allocated memory.    The regions are:
  32.     *
  33.     *    Static memory region
  34.     *    Allocated string region
  35.     *    Allocate block region
  36.     *    Qualifier list
  37.     */
  38.  
  39.    statfree = statbase = (char *)((uword)(code + codesize + 3)  & ~03);
  40.  
  41. /*
  42.  * The following code is operating-system dependent [@rmemexp.01].  Set end of
  43.  *  static region, rounding up if necessary.
  44.  */
  45.  
  46. #if PORT
  47.    statend = (char *)(((uword)statbase) + mstksize + statsize);
  48. Deliberate Syntax Error
  49. #endif                    /* PORT */
  50.  
  51. #if AMIGA || ARM || HIGHC_386 || OS2 || ((MVS || VM) && !SASC)
  52.    /* use fixed regions */
  53. #endif                    /* AMIGA || ARM || HIGHC_386 || ... */
  54.  
  55. #if MSDOS
  56.    statend =
  57.       (char *)(((uword)statbase) + (((mstksize + statsize + 511)/512) * 512));
  58. #endif                    /* MSDOS */
  59.  
  60. #if MACINTOSH
  61. #if MPW
  62.    statend = (char *)(((uword)statbase) + mstksize + statsize);
  63. #endif                    /* MPW */
  64. #endif                    /* MACINTOSH */
  65.  
  66. #if ATARI_ST || SASC || UNIX || VMS
  67.    statend = (char *)(((uword)statbase) + mstksize + statsize);
  68. #endif                    /* ATARI_ST || SASC || UNIX || VMS */
  69.  
  70. /*
  71.  * End of operating-system specific code.
  72.  */
  73.  
  74.    strfree = strbase = (char *)((uword)(statend + 63) & ~077);
  75.    blkfree = blkbase = strend = (char *)((((uword)strbase) + ssize +
  76.       63) & ~077);
  77.    equallist = (dptr *)(blkend =
  78.       (char *)((((uword)(blkbase) + abrsize + 63)) & ~077));
  79.  
  80.    /*
  81.     * Try to move the break back to the end of memory to allocate (the
  82.     *  end of the string qualifier list) and die if the space isn't
  83.     *  available.
  84.     */
  85.    if ((int)brk((char *)equallist) == -1)
  86.       error("insufficient memory");
  87.    currend = (char *)sbrk((word)0);    /* keep track of end of memory */
  88.    }
  89.  
  90. /*
  91.  * reclaim - reclaim space in the allocated memory regions. The marking
  92.  *  phase has already been completed.
  93.  */
  94.  
  95. static novalue reclaim(region)
  96. int region;
  97. {
  98.    register word stat_extra, str_extra, blk_extra;
  99.    register char *newend;
  100.  
  101.    stat_extra = 0;
  102.    str_extra = 0;
  103.    blk_extra = 0;
  104.  
  105.    /*
  106.     * Collect available co-expression blocks.
  107.     */
  108.    cofree();
  109.  
  110.    /*
  111.     * If there was no room to construct the qualifier list, the string
  112.     *  region cannot be collected and the static region cannot be expanded.
  113.     */
  114.    if (!qualfail) {
  115.       /*
  116.        * Check whether the static region needs to be expanded. Regions cannot
  117.        *  be expanded if someone else has moved the end of allocated storage.
  118.        */
  119.       if (statneed && currend == sbrk((word)0)) {
  120.          /*
  121.           * Make sure there is space for the requested static region expansion.
  122.           *  The check involving equallist and newend appears to only be
  123.           *  required on machines where the above addition of statneed might
  124.           *  overflow.
  125.           */
  126.          newend = (char *)equallist + statneed;
  127.          if ((uword)newend >= (uword)(char *)equallist &&
  128.              (int)brk((char *)newend) != -1) {
  129.                stat_extra = statneed;
  130.                statneed = 0;
  131.                statend += stat_extra;
  132.                equallist = (dptr *)newend;
  133.                currend = sbrk((word)0);
  134.                }
  135.          }
  136.    
  137.       /*
  138.        * Collect the string space, indicating that it must be moved back
  139.        *  extra bytes.
  140.        */
  141.       scollect(stat_extra);
  142.    
  143.       if (region == Strings && currend == sbrk((word)0)) {
  144.          /*
  145.           * Calculate a value for extra space.  The value is (the larger of
  146.           *  (twice the string space needed) or (a quarter of the string space))
  147.           *  minus the unallocated string space.
  148.           */
  149.          str_extra = (Max(2*strneed, ((uword)strend - (uword)strbase)/4) -
  150.                ((uword)strend - (uword)strfree) + (GranSize-1)) & ~(GranSize-1);
  151.          while (str_extra > 0) {
  152.             /*
  153.              * Try to get str_extra more bytes of storage.  If it can't be
  154.              *  gotten, decrease the value by GranSize and try again.  If
  155.              *  it's gotten, move back equallist.
  156.              */
  157.             newend = (char *)equallist + str_extra;
  158.             if ((uword)newend >= (uword)(char *)equallist &&
  159.                 (int)brk((char *)newend) != -1) {
  160.                    equallist = (dptr *) newend;
  161.                    currend = sbrk((word)0);
  162.                    break;
  163.                    }
  164.             str_extra -= GranSize;
  165.             }
  166.          if (str_extra < 0)
  167.             str_extra = 0;
  168.          }
  169.       }
  170.  
  171.    /*
  172.     * Adjust the pointers in the block region.
  173.     */
  174.    adjust(blkbase, blkbase + stat_extra + str_extra);
  175.  
  176.    /*
  177.     * Compact the block region.
  178.     */
  179.    compact(blkbase);
  180.  
  181.    if (region == Blocks && currend == sbrk((word)0)) {
  182.       /*
  183.        * Calculate a value for extra space.  The value is (the larger of
  184.        *  (twice the block region space needed) or (one quarter of the
  185.        *  block region)) plus the unallocated block space.
  186.        */
  187.       blk_extra = (Max(2*blkneed, ((uword)blkend - (uword)blkbase)/4) -
  188.                ((uword)blkend - (uword)blkfree) + (GranSize-1)) & ~(GranSize-1);
  189.       while (blk_extra > 0) {
  190.          /*
  191.           * Try to get blk_extra more bytes of storage.  If it can't be gotten,
  192.           *  decrease the value by GranSize and try again.  If it's gotten,
  193.           *  move back equallist.
  194.           */
  195.          newend = (char *)equallist + blk_extra;
  196.          if ((uword)newend >= (uword)(char *)equallist &&
  197.              (int)brk((char *)newend) != -1) {
  198.                 equallist = (dptr *) newend;
  199.                 currend = sbrk((word)0);
  200.                 break;
  201.                 }
  202.          blk_extra -= GranSize;
  203.          }
  204.       if (blk_extra < 0)
  205.          blk_extra = 0;
  206.    }
  207.                 
  208.    if (stat_extra + str_extra > 0) {
  209.       /*
  210.        * The block region must be moved.  There is an assumption here that the
  211.        *  block region always moves up in memory, i.e., the static and
  212.        *  string regions never shrink.    With this assumption in hand,
  213.        *  the block region must be moved before the string space lest the
  214.        *  string space overwrite block data.  The assumption is valid,
  215.        *  but beware if shrinking regions are ever implemented.
  216.        */
  217.       mvc((uword)blkfree - (uword)blkbase, blkbase, blkbase + stat_extra +
  218.          str_extra);
  219.       blkbase += stat_extra + str_extra;
  220.       blkfree += stat_extra + str_extra;
  221.       }
  222.    blkend += stat_extra + str_extra + blk_extra;
  223.  
  224.    if (stat_extra > 0) {
  225.       /*
  226.        * The string space must be moved up in memory.
  227.        */
  228.       mvc((uword)strfree - (uword)strbase, strbase, strbase + stat_extra);
  229.       strbase += stat_extra;
  230.       strfree += stat_extra;
  231.       }
  232.    strend += stat_extra + str_extra;
  233.    }
  234.  
  235. /*
  236.  * These are Icon's own versions of the allocation routines.  They are
  237.  *  not used for the fixed-regions versions of memory management.  They
  238.  *  normally overload the corresponding library routines. If this is not
  239.  *  possible, they are re-named and calls to them are renamed.
  240.  */
  241.  
  242. static HEADER base;        /* start with empty list */
  243. static HEADER *allocp = NULL;    /* last allocated block */
  244.  
  245. #if LATTICE || LSC
  246. #define nothing 0
  247. int free(ap)
  248. #else                    /* LATTICE || LSC */
  249. #define nothing
  250. novalue free(ap)        /* return block pointed to by ap to free list */
  251. #endif                    /* LATTICE || LSC */
  252. pointer ap;
  253.    {
  254.    register HEADER *p, *q;
  255.  
  256. /* free may be called to free a block before the static region is
  257.  *  initialized.
  258.  */
  259.    if (statbase == (char *)NULL || (char *)ap < statbase)
  260.       return nothing;
  261.  
  262.    p = (HEADER *)ap - 1;    /* point to header */
  263.  
  264. #ifdef MemMon
  265.    if (p->s.bsize > 1)    {
  266.       if (*(int *)(p + 1) != T_Coexpr)
  267.          MMStat((char *)ap, (word)((p->s.bsize - 1) * sizeof(HEADER)), 'F');
  268.       *(int *)(p + 1) = FREEMAGIC;
  269.       }
  270. #endif                    /* MemMon */
  271.  
  272.    if (p->s.bsize * sizeof(HEADER) >= statneed)
  273.      statneed = 0;
  274.    for (q = allocp; !((uword)p > (uword)q && (uword)p < (uword)q->s.ptr);
  275.       q = q->s.ptr)
  276.          if ((uword)q >= (uword)q->s.ptr && ((uword)p > (uword)q ||
  277.             (uword)p < (uword)q->s.ptr))
  278.                break;         /* at one end or the other */
  279.    if ((uword)p + sizeof(HEADER) * p->s.bsize
  280.       == (uword)q->s.ptr) {    /* join to upper */
  281.       p->s.bsize += q->s.ptr->s.bsize;
  282.       if (p->s.bsize * sizeof(HEADER) >= statneed)
  283.          statneed = 0;
  284.       p->s.ptr = q->s.ptr->s.ptr;
  285.       }
  286.    else
  287.       p->s.ptr = q->s.ptr;
  288.    if ((uword)q + sizeof(HEADER) * q->s.bsize ==
  289.       (uword)p) {        /* join to lower */
  290.          q->s.bsize += p->s.bsize;
  291.          if (q->s.bsize * sizeof(HEADER) >= statneed)
  292.             statneed = 0;
  293.          q->s.ptr = p->s.ptr;
  294.          }
  295.    else
  296.       q->s.ptr = p;
  297.    allocp = q;
  298.    }
  299.  
  300. pointer malloc(nbytes)
  301. msize nbytes;
  302.    {
  303.    register HEADER *p, *q;
  304.    register uword nunits;
  305.    register pointer xbase;
  306.    int attempts;
  307.  
  308.    if (statbase == NULL) {
  309.      if ((xbase = sbrk(nbytes)) == (pointer)-1)
  310.         syserr("malloc: failed during startup");
  311.      return xbase;
  312.      }
  313.  
  314.    nunits = 1 + (nbytes + sizeof(HEADER) - 1) / sizeof(HEADER);
  315.  
  316.    if ((q = allocp) == NULL) {    /* no free list yet */
  317.       base.s.ptr = allocp = q = &base;
  318.       base.s.bsize = 0;
  319.       }
  320.  
  321.    for (attempts = 2; attempts--; q = allocp) {
  322.       for (p = q->s.ptr;; q = p, p = p->s.ptr) {
  323.          if (p->s.bsize >= nunits) {    /* block is big enough */
  324.             if (p->s.bsize == nunits)    /* exactly right */
  325.                q->s.ptr = p->s.ptr;
  326.             else {            /* allocate tail end */
  327.                p->s.bsize -= nunits;
  328.                p += p->s.bsize;
  329.                p->s.bsize = nunits;
  330.                }
  331.             allocp = q;
  332.  
  333. #ifdef MemMon
  334.             if (nunits > 1)   {
  335.                MMStat((char *)(p + 1), (word) nbytes, 'A');
  336.                *(int *)(p + 1) = 0;    /* clear FREEMAGIC flag */
  337.                }
  338. #endif                    /* MemMon */
  339.  
  340.             return (char *)(p + 1);
  341.             }
  342.          if (p == allocp) {    /* wrap around */
  343.             moremem(nunits);    /* garbage collect and expand if needed */
  344.             break;
  345.             }
  346.          }
  347.       }
  348.  
  349.       return NULL;
  350.    }
  351.  
  352. #define FREESIZE 2    /* units sizeof(HEADER) that justify free() */
  353.  
  354. /*
  355.  *  realloc() allocates a block of memory of a requested size (amount) to
  356.  *  contain the contents of the current block (curmem) or as much as will
  357.  *  fit.  Blocks are allocated in units of sizeof(HEADER)
  358.  */
  359.  
  360. pointer realloc(curmem,newsiz)
  361. register pointer curmem;        /* the current memory pointer */
  362. msize newsiz;                /* bytes needed for new allocation */
  363.    {
  364.    register int cunits;        /* currently allocated units */
  365.    register int nunits;        /* new units required */
  366.    char *newmem;        /* the new memory pointer */
  367.    register HEADER *head;    /* all blocks used or free have a header */
  368.  
  369.    /*
  370.     * First establish the unit sizes involved.
  371.     */
  372.  
  373.    nunits = 1 + (newsiz + sizeof(HEADER) - 1) / sizeof(HEADER);
  374.    head = ((HEADER *)curmem) - 1;    /* move back a block header */
  375.    cunits = (int)head->s.bsize;
  376.  
  377.    /*
  378.     * Now allocate or free space as required.
  379.     */
  380.  
  381.    if (nunits <= cunits) {    /* we already have the space */
  382.       if (cunits - nunits < FREESIZE)
  383.          return curmem;
  384.       else {            /* free space at end of current block */
  385.          head->s.bsize = nunits;    /* reduce space used */
  386.          head += nunits;        /* move to free space */
  387.          head->s.bsize = cunits - nunits;
  388.          free((pointer)(++head));    /* free this new block */
  389.          return curmem;
  390.          }
  391.       }
  392.    else {                /* more space needed */
  393.       if ((newmem = malloc((msize)newsiz)) != NULL) {
  394.          memcopy(newmem,curmem,(word)((cunits - 1) * sizeof(HEADER)));
  395.          free(curmem);
  396.          return newmem;
  397.          }
  398.       }
  399.    return NULL;
  400.    }
  401.  
  402. /*
  403.  * calloc() allocates ecnt number of esiz-sized chunks of zero-initialized
  404.  * memory for an array of ecnt elements.
  405.  */
  406.  
  407. pointer calloc(ecnt,esiz)
  408.    register msize ecnt, esiz;
  409.    {
  410.    register char *mem;            /* the memory pointer */
  411.    register msize amount;        /* the amount of memory needed */
  412.  
  413.    amount = ecnt * esiz;
  414.    if ((mem = malloc(amount)) != NULL) {
  415.       memfill(mem,0,(word)amount);        /* initialize it to zero */
  416.       return mem;
  417.       }
  418.    return NULL;
  419.    }
  420.  
  421. static novalue moremem(nunits)
  422. uword nunits;
  423.    {
  424.    register HEADER *up;
  425.    register word rnu;
  426.    word n;
  427.  
  428.    rnu = NALLOC * ((nunits + NALLOC - 1) / NALLOC);
  429.    n = rnu * sizeof(HEADER);
  430.    if (((uword)statfree) + n > (uword)statend) {
  431.       statneed = ((n / statincr) + 1) * statincr;
  432.       coll_stat++;
  433.       collect(Static);
  434.       }
  435.    /*
  436.     * See if there is any room left.
  437.     */
  438.    if ((uword)statend - (uword)statfree > sizeof(HEADER)) {
  439.       up = (HEADER *) statfree;
  440.       up->s.bsize = ((uword)statend - (uword)statfree) / sizeof(HEADER);
  441.       statfree = (char *) (up + up->s.bsize);
  442.       free((pointer)(up + 1));    /* add block to free memory */
  443.       }
  444.    }
  445.