git.sur5r.net Git - cc65/blob - src/cc65/exprheap.c

   1 /*****************************************************************************/
   2 /*                                                                           */
   3 /*                                exprheap.c                                 */
   4 /*                                                                           */
   5 /*                       Expression node heap manager                        */
   6 /*                                                                           */
   7 /*                                                                           */
   8 /*                                                                           */
   9 /* (C) 2000      Ullrich von Bassewitz                                       */
  10 /*               Wacholderweg 14                                             */
  11 /*               D-70597 Stuttgart                                           */
  12 /* EMail:        uz@musoftware.de                                            */
  13 /*                                                                           */
  14 /*                                                                           */
  15 /* This software is provided 'as-is', without any expressed or implied       */
  16 /* warranty.  In no event will the authors be held liable for any damages    */
  17 /* arising from the use of this software.                                    */
  18 /*                                                                           */
  19 /* Permission is granted to anyone to use this software for any purpose,     */
  20 /* including commercial applications, and to alter it and redistribute it    */
  21 /* freely, subject to the following restrictions:                            */
  22 /*                                                                           */
  23 /* 1. The origin of this software must not be misrepresented; you must not   */
  24 /*    claim that you wrote the original software. If you use this software   */
  25 /*    in a product, an acknowledgment in the product documentation would be  */
  26 /*    appreciated but is not required.                                       */
  27 /* 2. Altered source versions must be plainly marked as such, and must not   */
  28 /*    be misrepresented as being the original software.                      */
  29 /* 3. This notice may not be removed or altered from any source              */
  30 /*    distribution.                                                          */
  31 /*                                                                           */
  32 /*****************************************************************************/
  33
  34
  35
  36 /* common */
  37 #include "check.h"
  38 #include "xmalloc.h"
  39
  40 /* cc65 */
  41 #include "exprheap.h"
  42
  43
  44
  45 /*****************************************************************************/
  46 /*                                   Data                                    */
  47 /*****************************************************************************/
  48
  49
  50
  51 /* A block of expression nodes */
  52 typedef struct ExprNodeBlock ExprNodeBlock;
  53 struct ExprNodeBlock {
  54     ExprNodeBlock*      Next;           /* Pointer to next block */
  55     unsigned            Count;          /* Number of nodes in the block */
  56     unsigned            Used;           /* Number of nodes used */
  57     ExprNode            Nodes[1];       /* Nodes, dynamically allocated */
  58 };
  59
  60 /* An expression heap */
  61 struct ExprHeap {
  62     ExprHeap*           Last;           /* Upper level expression tree */
  63     ExprNodeBlock*      BlockRoot;      /* Root of node blocks */
  64     ExprNodeBlock*      BlockLast;      /* Last node block */
  65     ExprNode*           FreeList;       /* List of free nodes */
  66 };
  67
  68 /* The current expression heap */
  69 static ExprHeap*        CurHeap = 0;
  70
  71
  72
  73 /*****************************************************************************/
  74 /*                           struct ExprHeapBlock                            */
  75 /*****************************************************************************/
  76
  77
  78
  79 static ExprNodeBlock* NewExprNodeBlock (unsigned Count)
  80 /* Create a new ExprNodeBlock, initialize and return it */
  81 {
  82     /* Calculate the size of the memory block requested */
  83     unsigned Size = sizeof (ExprNodeBlock) + (Count-1) * sizeof (ExprNode);
  84
  85     /* Allocate memory */
  86     ExprNodeBlock* B = xmalloc (Size);
  87
  88     /* Initialize the fields */
  89     B->Next  = 0;
  90     B->Count = Count;
  91     B->Used  = 0;
  92
  93     /* Return the new block */
  94     return B;
  95 }
  96
  97
  98
  99 /*****************************************************************************/
 100 /*                              struct ExprHeap                              */
 101 /*****************************************************************************/
 102
 103
 104
 105 static ExprHeap* NewExprHeap (void)
 106 /* Create and return a new expression tree */
 107 {
 108     /* Allocate memory */
 109     ExprHeap* H = xmalloc (sizeof (ExprHeap));
 110
 111     /* Allocate the first node block */
 112     H->BlockRoot = NewExprNodeBlock (64);
 113
 114     /* Initialize the remaining fields */
 115     H->Last      = 0;
 116     H->BlockLast = H->BlockRoot;
 117     H->FreeList  = 0;
 118
 119     /* Return the new heap */
 120     return H;
 121 }
 122
 123
 124
 125 /*****************************************************************************/
 126 /*                                   Code                                    */
 127 /*****************************************************************************/
 128
 129
 130
 131 void PushExprHeap (void)
 132 /* Create a new expression heap and push it onto the expression heap stack, so
 133  * it is the current expression heap.
 134  */
 135 {
 136     /* Create a new heap */
 137     ExprHeap* H = NewExprHeap ();
 138
 139     /* Push it onto the stack */
 140     H->Last = CurHeap;
 141     CurHeap = H;
 142 }
 143
 144
 145
 146 ExprHeap* PopExprHeap (void)
 147 /* Pop the current expression heap from the heap stack and return it */
 148 {
 149     ExprHeap* H;
 150
 151     /* Cannot pop a non existant heap */
 152     PRECONDITION (CurHeap != 0);
 153
 154     /* Pop the heap */
 155     H = CurHeap;
 156     CurHeap = H->Last;
 157
 158     /* Return the old heap */
 159     return H;
 160 }
 161
 162
 163
 164 ExprNode* AllocExprNode (nodetype_t NT, type* Type, int LValue)
 165 /* Get a new node from the current expression heap */
 166 {
 167     ExprNode* N;
 168
 169     /* Must have a heap */
 170     PRECONDITION (CurHeap != 0);
 171
 172     /* Get a node from the freelist if possible */
 173     if (CurHeap->FreeList) {
 174         /* There are nodes in the free list */
 175         N = CurHeap->FreeList;
 176         CurHeap->FreeList = N->MData.Next;
 177     } else {
 178         /* Free list is empty, allocate a new node */
 179         ExprNodeBlock* B = CurHeap->BlockLast;
 180         if (B->Used >= B->Count) {
 181             /* No nodes left, allocate a new node block */
 182             B = NewExprNodeBlock (64);
 183             CurHeap->BlockLast->Next = B;
 184             CurHeap->BlockLast = B;
 185         }
 186         N = B->Nodes + B->Count++;
 187     }
 188
 189     /* Initialize and return the allocated node */
 190     return InitExprNode (N, NT, Type, LValue, CurHeap);
 191 }
 192
 193
 194
 195 void FreeExprNode (ExprNode* N)
 196 /* Free an expression node from the current expression heap */
 197 {
 198     /* There must be a heap, and the node must be from this heap */
 199     PRECONDITION (CurHeap != 0 && N->MData.Owner == CurHeap);
 200
 201     /* Insert the node in the freelist invalidating the owner pointer */
 202     N->MData.Next = CurHeap->FreeList;
 203     CurHeap->FreeList = N;
 204 }
 205
 206
 207
 208 void FreeExprTree (ExprNode* N)
 209 /* Free a complete expression tree starting with the current node */
 210 {
 211     if (IsBranchNode (N)) {
 212         /* Free the leaf nodes if necessary */
 213         if ((N->NT & NT_MASK_LIST) == NT_LIST_EXPR) {
 214             unsigned I;
 215             unsigned Count = CollCount (&N->List);
 216             for (I = 0; I < Count; ++I) {
 217                 FreeExprNode (CollAt (&N->List, I));
 218             }
 219         }
 220     }
 221
 222     /* Free the node itself */
 223     FreeExprNode (N);
 224 }
 225
 226
 227