src/basesuif/snoot/tree.cc

   1 /* file "tree.cc" */
   2
   3 /*  Copyright (c) 1994 Stanford University
   4
   5     All rights reserved.
   6
   7     This software is provided under the terms described in
   8     the "suif_copyright.h" include file. */
   9
  10 #include <suif_copyright.h>
  11
  12 /* snoot tree management */
  13
  14 #include "c.h"
  15
  16 static struct arena first[] =
  17   {
  18     { 0, 0, 0, &first[0], 0 },
  19     { 0, 0, 0, &first[1], 0 },
  20   };
  21
  22 Arena permanent = &first[0]; /* permanent storage */
  23 Arena transient = &first[1]; /* transient storage; released at function end */
  24 static Arena freearenas;     /* list of free arenas */
  25
  26 /* allocate - allocate n bytes in arena **p, adding a new arena if necessary */
  27 char *allocate(int n, Arena *p)
  28   {
  29     Arena ap = *p;
  30
  31     while (ap->avail + n > ap->limit)
  32       {
  33         if (ap->next != NULL)    /* move to next arena */
  34           {
  35             ap = ap->next;
  36             ap->avail = (char *)ap + roundup(sizeof *ap, sizeof (double));
  37           }
  38         else if ((ap->next = freearenas) != NULL)
  39           {
  40             freearenas = freearenas->next;
  41             ap = ap->next;
  42             ap->avail = (char *)ap + roundup(sizeof *ap, sizeof (double));
  43             ap->first = (*p)->first;
  44             ap->next = NULL;
  45           }
  46         else    /* allocate a new arena */
  47           {
  48             int m = n + MEMINCR * 1024 + roundup(sizeof *ap, sizeof (double));
  49             ap->next = (Arena)malloc(m);
  50             assert(ap->next != NULL);
  51             if ((char *)ap->next == ap->limit) /* extend previous arena? */
  52               {
  53                 ap->limit = (char *)ap->next + m;
  54               }
  55             else    /* link to a new arena */
  56               {
  57                 ap = ap->next;
  58                 ap->limit = (char *)ap + m;
  59                 ap->avail = (char *)ap + roundup(sizeof *ap, sizeof (double));
  60               }
  61             ap->first = (*p)->first;
  62             ap->next = NULL;
  63           }
  64       }
  65     *p = ap;
  66     ap->avail += n;
  67     return ap->avail - n;
  68   }
  69
  70 /* deallocate - release all space in arena *p, except the first arena;
  71    reset *p */
  72 void deallocate(Arena *p)
  73   {
  74     Arena first = (*p)->first;
  75
  76     (*p)->next = freearenas;
  77     freearenas = first->next;
  78     first->next = NULL;
  79     *p = first;
  80   }