1 /*****************************************************************************/
5 /* Expression node heap manager */
9 /* (C) 2000 Ullrich von Bassewitz */
11 /* D-70597 Stuttgart */
12 /* EMail: uz@musoftware.de */
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. */
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: */
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 */
32 /*****************************************************************************/
45 /*****************************************************************************/
47 /*****************************************************************************/
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 */
60 /* An expression heap */
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 */
68 /* The current expression heap */
69 static ExprHeap* CurHeap = 0;
73 /*****************************************************************************/
74 /* struct ExprHeapBlock */
75 /*****************************************************************************/
79 static ExprNodeBlock* NewExprNodeBlock (unsigned Count)
80 /* Create a new ExprNodeBlock, initialize and return it */
82 /* Calculate the size of the memory block requested */
83 unsigned Size = sizeof (ExprNodeBlock) + (Count-1) * sizeof (ExprNode);
86 ExprNodeBlock* B = xmalloc (Size);
88 /* Initialize the fields */
93 /* Return the new block */
99 /*****************************************************************************/
100 /* struct ExprHeap */
101 /*****************************************************************************/
105 static ExprHeap* NewExprHeap (void)
106 /* Create and return a new expression tree */
108 /* Allocate memory */
109 ExprHeap* H = xmalloc (sizeof (ExprHeap));
111 /* Allocate the first node block */
112 H->BlockRoot = NewExprNodeBlock (64);
114 /* Initialize the remaining fields */
116 H->BlockLast = H->BlockRoot;
119 /* Return the new heap */
125 /*****************************************************************************/
127 /*****************************************************************************/
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.
136 /* Create a new heap */
137 ExprHeap* H = NewExprHeap ();
139 /* Push it onto the stack */
146 ExprHeap* PopExprHeap (void)
147 /* Pop the current expression heap from the heap stack and return it */
151 /* Cannot pop a non existant heap */
152 PRECONDITION (CurHeap != 0);
158 /* Return the old heap */
164 ExprNode* AllocExprNode (nodetype_t NT, type* Type, int LValue)
165 /* Get a new node from the current expression heap */
169 /* Must have a heap */
170 PRECONDITION (CurHeap != 0);
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;
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;
186 N = B->Nodes + B->Count++;
189 /* Initialize and return the allocated node */
190 return InitExprNode (N, NT, Type, LValue, CurHeap);
195 void FreeExprNode (ExprNode* N)
196 /* Free an expression node from the current expression heap */
198 /* There must be a heap, and the node must be from this heap */
199 PRECONDITION (CurHeap != 0 && N->MData.Owner == CurHeap);
201 /* Insert the node in the freelist invalidating the owner pointer */
202 N->MData.Next = CurHeap->FreeList;
203 CurHeap->FreeList = N;