/[ascend]/branches/relerrorlist/ascend/compiler/freestore.c
ViewVC logotype

Contents of /branches/relerrorlist/ascend/compiler/freestore.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 3234 - (show annotations) (download) (as text)
Thu Nov 2 11:26:15 2017 UTC (4 years, 8 months ago) by jpye
File MIME type: text/x-csrc
File size: 8664 byte(s)
added very simple test for the module 'freestore'.

1 /*
2 * Implementation of Free Store Module
3 * Kirk A. Abbott
4 * Created Dec 18, 1994
5 * Version: $Revision: 1.8 $
6 * Version control file: $RCSfile: freestore.c,v $
7 * Date last modified: $Date: 1997/07/18 12:29:49 $
8 * Last modified by: $Author: mthomas $
9 *
10 * This file is part of the Ascend Language Interpreter.
11 *
12 * Copyright (C) 1994, 1995 Kirk Andre Abbott.
13 *
14 * The Ascend Language Interpreter is free software; you can redistribute
15 * it and/or modify it under the terms of the GNU General Public License
16 * as published by the Free Software Foundation; either version 2 of the
17 * License, or (at your option) any later version.
18 *
19 * The Ascend Language Interpreter is distributed in hope that it will be
20 * useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
21 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
22 * General Public License for more details.
23 *
24 * You should have received a copy of the GNU General Public License
25 * along with this program. If not, see <http://www.gnu.org/licenses/>.
26 */
27
28 #include <limits.h> /* for INT_MAX */
29 #include <ascend/utilities/config.h>
30 #include <ascend/general/platform.h>
31
32 #include "freestore.h"
33
34 #include <stdarg.h>
35 #include <ascend/general/platform.h>
36
37 #include <ascend/general/panic.h>
38 #include <ascend/general/ascMalloc.h>
39 #include <ascend/general/stack.h>
40
41
42 #include "functype.h"
43 #include "expr_types.h"
44 #include "relation_type.h"
45 #include "freestore.h"
46 #include <ascend/general/mathmacros.h>
47
48 /*
49 * This is an implementation of a *freestore* which is hoped to
50 * reduce the memory management difficulties associated with
51 * symbolic processing. This is algorithm 1
52 * which does no *freeing* until a computation is done.
53 * In this way it acts as a *buffer*. The difficulty is that
54 * instantaneous size of the buffer may be large, depending upon
55 * the number of terms generated, as we dont *free* or mark nodes
56 * as unused until we are done.
57 *
58 * A second variation of this algorithm would be to call Copy
59 * and Destroy, which would play a reference count game. We would
60 * also maintain a stack of pointers to nodes, as they were requested
61 * to be destroyed. This stack would allow us to find free terms quickly
62 * as within the distribution of terms.
63 *
64 *
65 * --------------------------------------------------------
66 * | | | | | | | |
67 * ------> | O | X | X | X | O | O | O |
68 * | | | | | | | |
69 * --------------------------------------------------------
70 * ^ ^
71 * | |
72 * | |--------------->-------
73 * --------------------------------------------------------
74 * ------> | | | | | | | |
75 * --------------------------------------------------------
76 */
77
78 static struct FreeStore *g_free_store = NULL;
79 static long g_units_alloc = 0L;
80
81 struct FreeStore *FreeStore_Create(int n_buffers,int buffer_length){
82 struct FreeStore *result;
83 union RelationTermUnion **root;
84 int i;
85
86 result = ASC_NEW(struct FreeStore);
87 /*
88 * Make and initialize the array of pointers to the buffers.
89 */
90 root = ASC_NEW_ARRAY_CLEAR(union RelationTermUnion *,n_buffers);
91
92 /*
93 * Allocate all n_buffers of size buffer_length.
94 * Allocate the return stack at 30% of the buffer_length;
95 * The return stack is expanded by the stack module at a rate
96 * orig_capacity *(1.5)^n-1, where n is the number of times that the
97 * stack has to be reallocated.
98 */
99 for (i=0;i<n_buffers;i++) {
100 root[i] = ASC_NEW_ARRAY(union RelationTermUnion,buffer_length);
101 }
102 result->returned = gs_stack_create(MAX(8,(long)0.3*buffer_length));
103
104 /*
105 * Set the structures created to the result; Add the other
106 * information about the freestore.
107 */
108 result->root = root;
109 result->next_free = root[0]; /* start of first buffer */
110 result->n_buffers = n_buffers;
111 result->buffer_length = buffer_length;
112 result->row = 0;
113 result->col = 0;
114 return result;
115 }
116
117 void FreeStore_ReInit(struct FreeStore *store){
118 if (store && store->root) {
119 gs_stack_destroy(store->returned,0); /* faster to destroy and rebuild */
120 store->returned = gs_stack_create(MAX(8,(long)0.3*store->buffer_length));
121 store->row = 0;
122 store->col = 0;
123 store->next_free = store->root[0];
124 g_units_alloc = 0;
125 }
126 }
127
128 static union RelationTermUnion *FreeStore__GetMem(struct FreeStore *store){
129 union RelationTermUnion *result;
130 union RelationTermUnion *ptr;
131 union RelationTermUnion **root;
132 int i;
133
134 root = store->root;
135 if (!root) {
136 FPRINTF(stderr,"FreeStore not initialized\n");
137 return NULL;
138 }
139
140 /*
141 * Try the returned list first.
142 */
143 ptr = (union RelationTermUnion *)gs_stack_pop(store->returned);
144 if (ptr!=NULL) {
145 return ptr;
146 }
147 else if (store->col == store->buffer_length) {
148 /*
149 * Nothing on the returned stack, and we are out of blocks
150 * on the current buffer, i.e, need to make a buffer.
151 */
152 i = store->n_buffers++; /* update buffer count */
153 root = (union RelationTermUnion **)
154 realloc(root,store->n_buffers * sizeof(union RelationTermUnion*));
155 root[i] = (union RelationTermUnion *)
156 malloc(store->buffer_length * sizeof(union RelationTermUnion));
157 store->root = root; /* critical !! -- realloc could moved root */
158 result = &root[i][0]; /* memory to be returned */
159 store->col = 1; /* point to next free block */
160 store->row = i; /* update the row counter */
161 store->next_free = &root[i][1];
162 return result;
163 }
164 else{
165 ptr = store->next_free;
166 store->next_free++;
167 store->col++;
168 return ptr;
169 }
170 }
171
172
173 static union RelationTermUnion *FreeStore__FindMem(
174 struct FreeStore *store
175 ,union RelationTermUnion *term
176 ){
177 union RelationTermUnion **root, *start, *end;
178 int i;
179
180 if (store==NULL || term==NULL)
181 return NULL;
182 root = store->root;
183 for (i=0;i<store->n_buffers;i++) {
184 start = root[i] - 1; /* just before the start */
185 end = root[i] + store->buffer_length; /* just beyond the end */
186 if ((term > start ) && (term < end)) {
187 return term;
188 }
189 }
190 return NULL; /* term not found within range */
191 }
192
193 static int FreeStore__FreeMem(struct FreeStore *store
194 ,union RelationTermUnion *term
195 ){
196 union RelationTermUnion *ptr;
197
198 ptr = FreeStore__FindMem(store,term); /* check if we own the memory */
199 if(ptr==NULL){
200 FPRINTF(stderr,"This is not one of our pointers;");
201 FPRINTF(stderr,"free it yourself.\n");
202 return 1;
203 }
204 gs_stack_push(store->returned,ptr);
205 return 0;
206 }
207
208 union RelationTermUnion *FreeStoreCheckMem(union RelationTermUnion *term){
209 return FreeStore__FindMem(FreeStore_GetFreeStore(),term);
210 }
211
212 void FreeStore__Statistics(FILE *fp, struct FreeStore *store){
213 union RelationTermUnion *bufptr;
214 int n_allocated=0;
215 int n_maxused=0;
216 int n_destroyed=0;
217 int n_buffers, buffer_length;
218 int i,j;
219
220 if (store==NULL) {
221 FPRINTF(stderr,"FreeStore is nonexistent\n");
222 return;
223 }
224 n_buffers = store->n_buffers;
225 buffer_length = store->buffer_length;
226 n_allocated = n_buffers * buffer_length;
227 n_maxused = (store->row)*buffer_length + store->col;
228 for (i=0;i<n_buffers;i++) {
229 bufptr = store->root[i];
230 for (j=0;j<buffer_length;j++) {
231 if (bufptr == store->next_free)
232 break;
233 bufptr++;
234 }
235 }
236 n_destroyed = (int)gs_stack_size(store->returned);
237 FPRINTF(fp,"Memory Allocated = %d or %ld bytes\n",
238 n_allocated,(long)n_allocated*sizeof(union RelationTermUnion));
239 FPRINTF(fp,"Maximum Memory Used = %d or %ld bytes\n",
240 n_maxused,(long)n_maxused*sizeof(union RelationTermUnion));
241 FPRINTF(fp,"Memory Destroyed = %d or %ld bytes\n",
242 n_destroyed,(long)n_destroyed*sizeof(union RelationTermUnion));
243 }
244
245 /*
246 * This is to be used as a high water counter
247 * over many invocations of the free strore.
248 */
249 long FreeStore_UnitsAllocated(){
250 return g_units_alloc;
251 }
252
253 void FreeStore__BlastMem(struct FreeStore *store){
254 int i,n_buffers;
255 if (!store)
256 return;
257 n_buffers = store->n_buffers;
258 for (i=0;i<n_buffers;i++) {
259 ascfree((char *)store->root[i]); /* freeup each buffer */
260 store->root[i] = NULL; /* unnecessary ... oh well*/
261 }
262 ascfree((char *)store->root);
263 gs_stack_destroy(store->returned,0);
264 store->row = store->col = 0;
265 store->next_free = NULL;
266 ascfree((char *)store);
267 store = NULL;
268 g_units_alloc = 0;
269 }
270
271 void FreeStore_SetFreeStore(struct FreeStore *store){
272 g_free_store = store;
273 }
274
275 struct FreeStore *FreeStore_GetFreeStore(void){
276 return g_free_store;
277 }
278
279 union RelationTermUnion *FreeStore_GetMem(){
280 g_units_alloc++;
281 return FreeStore__GetMem(g_free_store);
282 }
283
284 int FreeStore_FreeMem(union RelationTermUnion *term){
285 return FreeStore__FreeMem(g_free_store,term);
286 }
287

john.pye@anu.edu.au
ViewVC Help
Powered by ViewVC 1.1.22