This is the open source Pawn interpreter ported to mbed. See here: http://www.compuphase.com/pawn/pawn.htm and here: http://code.google.com/p/pawnscript/
amxpool.c
00001 /* Simple allocation from a memory pool, with automatic release of 00002 * least-recently used blocks (LRU blocks). 00003 * 00004 * These routines are as simple as possible, and they are neither re-entrant 00005 * nor thread-safe. Their purpose is to have a standard implementation for 00006 * systems where overlays are used and malloc() is not available. 00007 * 00008 * The algorithm uses a first-fit strategy. It keeps all blocks in a single 00009 * list (both used blocks and free blocks are in the same list). Every memory 00010 * block must have a unique number that identifies the block. This unique 00011 * number allows to search for the presence of the block in the pool and for 00012 * "conditional allocation". 00013 * 00014 * 00015 * Copyright (c) ITB CompuPhase, 2007-2012 00016 * 00017 * Licensed under the Apache License, Version 2.0 (the "License"); you may not 00018 * use this file except in compliance with the License. You may obtain a copy 00019 * of the License at 00020 * 00021 * http://www.apache.org/licenses/LICENSE-2.0 00022 * 00023 * Unless required by applicable law or agreed to in writing, software 00024 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT 00025 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the 00026 * License for the specific language governing permissions and limitations 00027 * under the License. 00028 * 00029 * Version: $Id: amxpool.c 4731 2012-06-21 11:11:18Z thiadmer $ 00030 */ 00031 #include <assert.h> 00032 #include "amx.h" 00033 #include "amxpool.h" 00034 00035 #if !defined NULL 00036 #define NULL ((void*)0) 00037 #endif 00038 00039 #define MIN_BLOCKSIZE 32 00040 #define PROTECT_LRU 0xffff 00041 00042 typedef struct tagARENA { 00043 unsigned blocksize; 00044 short index; /* overlay index, -1 if free */ 00045 unsigned short lru; 00046 } ARENA; 00047 00048 static void *pool_base; 00049 static unsigned pool_size; 00050 static unsigned short pool_lru; 00051 00052 static void touchblock(ARENA *hdr); 00053 static ARENA *findblock(int index); 00054 00055 /* amx_poolinit() initializes the memory pool for the allocated blocks. 00056 * If parameter pool is NULL, the existing pool is cleared (without changing 00057 * its position or size). 00058 */ 00059 void amx_poolinit(void *pool, unsigned size) 00060 { 00061 assert(pool!=NULL || pool_base!=NULL); 00062 if (pool!=NULL) { 00063 assert(size>sizeof(ARENA)); 00064 /* save parameters in global variables, then "free" the entire pool */ 00065 pool_base=pool; 00066 pool_size=size; 00067 } /* if */ 00068 pool_lru=0; 00069 amx_poolfree(NULL); 00070 } 00071 00072 /* amx_poolfree() releases a block allocated earlier. The parameter must have 00073 * the same value as that returned by an earlier call to amx_poolalloc(). That 00074 * is, the "block" parameter must point directly behind the arena header of the 00075 * block. 00076 * When parameter "block" is NULL, the pool is re-initialized (meaning that 00077 * all blocks are freed). 00078 */ 00079 void amx_poolfree(void *block) 00080 { 00081 ARENA *hdr,*hdr2; 00082 unsigned sz; 00083 00084 assert(pool_base!=NULL); 00085 assert(pool_size>sizeof(ARENA)); 00086 00087 /* special case: if "block" is NULL, create a single free space */ 00088 if (block==NULL) { 00089 /* store an arena header at the start of the pool */ 00090 hdr=(ARENA*)pool_base; 00091 hdr->blocksize=pool_size-sizeof(ARENA); 00092 hdr->index=-1; 00093 hdr->lru=0; 00094 } else { 00095 hdr=(ARENA*)((char*)block-sizeof(ARENA)); 00096 assert((char*)hdr>=(char*)pool_base && (char*)hdr<(char*)pool_base+pool_size); 00097 assert(hdr->blocksize<pool_size); 00098 00099 /* free this block */ 00100 hdr->index=-1; 00101 00102 /* try to coalesce with the next block */ 00103 hdr2=(ARENA*)((char*)hdr+hdr->blocksize+sizeof(ARENA)); 00104 if (hdr2->index==-1) 00105 hdr->blocksize+=hdr2->blocksize+sizeof(ARENA); 00106 00107 /* try to coalesce with the previous block */ 00108 if ((void*)hdr!=pool_base) { 00109 sz=pool_size; 00110 hdr2=(ARENA*)pool_base; 00111 while (sz>0 && (char*)hdr2+hdr2->blocksize+sizeof(ARENA)!=(char*)hdr) { 00112 assert(sz<=pool_size); 00113 sz-=hdr2->blocksize+sizeof(ARENA); 00114 hdr2=(ARENA*)((char*)hdr2+hdr2->blocksize+sizeof(ARENA)); 00115 } /* while */ 00116 assert((char*)hdr2+hdr2->blocksize+sizeof(ARENA)==(char*)hdr); 00117 if (hdr2->index==-1) 00118 hdr2->blocksize+=hdr->blocksize+sizeof(ARENA); 00119 } /* if */ 00120 } /* if */ 00121 } 00122 00123 /* amx_poolalloc() allocates the requested number of bytes from the pool and 00124 * returns a header to the start of it. Every block in the pool is prefixed 00125 * with an "arena header"; the return value of this function points just 00126 * behind this arena header. 00127 * 00128 * The block with the specified "index" should not already exist in the pool. 00129 * In other words, parameter "index" should be unique for every of memory block, 00130 * and the block should not change in size. Use amx_poolfind() to verify whether 00131 * a block is already in the pool (and optionally amx_poolfree() to remove it). 00132 * 00133 * If no block of sufficient size is available, the routine frees blocks until 00134 * the requested amount of memory can be allocated. There is no intelligent 00135 * algorithm involved: the routine just frees the least-recently used block at 00136 * every iteration (without considering the size of the block or whether that 00137 * block is adjacent to a free block). 00138 */ 00139 void *amx_poolalloc(unsigned size,int index) 00140 { 00141 ARENA *hdr,*hdrlru; 00142 unsigned sz; 00143 unsigned short minlru; 00144 00145 assert(size>0); 00146 assert(index>=0 && index<=SHRT_MAX); 00147 assert(findblock(index)==NULL); 00148 00149 /* align the size to a cell boundary */ 00150 if ((size % sizeof(cell))!=0) 00151 size+=sizeof(cell)-(size % sizeof(cell)); 00152 if (size+sizeof(ARENA)>pool_size) 00153 return NULL; /* requested block does not fit in the pool */ 00154 00155 /* find a block large enough to get the size plus an arena header; at 00156 * the same time, detect the block with the lowest LRU 00157 * if no block of sufficient size can be found, the routine then frees 00158 * the block with the lowest LRU count and tries again 00159 */ 00160 do { 00161 sz=pool_size; 00162 hdr=(ARENA*)pool_base; 00163 hdrlru=hdr; 00164 minlru=USHRT_MAX; 00165 while (sz>0) { 00166 assert(sz<=pool_size); 00167 assert((char*)hdr>=(char*)pool_base && (char*)hdr<(char*)pool_base+pool_size); 00168 if (hdr->index==-1 && hdr->blocksize>=size) 00169 break; 00170 if (hdr->index!=-1 && hdr->lru<minlru) { 00171 minlru=hdr->lru; 00172 hdrlru=hdr; 00173 } /* if */ 00174 sz-=hdr->blocksize+sizeof(ARENA); 00175 hdr=(ARENA*)((char*)hdr+hdr->blocksize+sizeof(ARENA)); 00176 } /* while */ 00177 assert(sz<=pool_size); 00178 if (sz==0) { 00179 /* free up memory and try again */ 00180 assert(hdrlru->index!=-1); 00181 amx_poolfree((char*)hdrlru+sizeof(ARENA)); 00182 } /* if */ 00183 } while (sz==0); 00184 00185 /* see whether to allocate the entire free block, or to cut it in two blocks */ 00186 if (hdr->blocksize>size+MIN_BLOCKSIZE+sizeof(ARENA)) { 00187 /* cut the block in two */ 00188 ARENA *next=(ARENA*)((char*)hdr+size+sizeof(ARENA)); 00189 next->blocksize=hdr->blocksize-size-sizeof(ARENA); 00190 next->index=-1; 00191 next->lru=0; 00192 } else { 00193 size=hdr->blocksize; 00194 } /* if */ 00195 hdr->blocksize=size; 00196 hdr->index=(short)index; 00197 touchblock(hdr); /* set LRU field */ 00198 00199 return (void*)((char*)hdr+sizeof(ARENA)); 00200 } 00201 00202 /* amx_poolfind() returns the address of the memory block with the given index, 00203 * or NULL if no such block exists. Parameter "index" should not be -1, because 00204 * -1 represents a free block (actually, only positive values are valid). 00205 * When amx_poolfind() finds the block, it increments its LRU count. 00206 */ 00207 void *amx_poolfind(int index) 00208 { 00209 ARENA *hdr=findblock(index); 00210 if (hdr==NULL) 00211 return NULL; 00212 touchblock(hdr); 00213 return (void*)((char*)hdr+sizeof(ARENA)); 00214 } 00215 00216 int amx_poolprotect(int index) 00217 { 00218 ARENA *hdr=findblock(index); 00219 if (hdr==NULL) 00220 return AMX_ERR_GENERAL; 00221 hdr->lru=PROTECT_LRU; 00222 return AMX_ERR_NONE; 00223 } 00224 00225 static ARENA *findblock(int index) 00226 { 00227 ARENA *hdr; 00228 unsigned sz; 00229 00230 assert(index>=0); 00231 sz=pool_size; 00232 hdr=(ARENA*)pool_base; 00233 while (sz>0 && hdr->index!=index) { 00234 assert(sz<=pool_size); 00235 assert((char*)hdr>=(char*)pool_base && (char*)hdr<(char*)pool_base+pool_size); 00236 sz-=hdr->blocksize+sizeof(ARENA); 00237 hdr=(ARENA*)((char*)hdr+hdr->blocksize+sizeof(ARENA)); 00238 } /* while */ 00239 assert(sz<=pool_size); 00240 return (sz>0 && hdr->index==index) ? hdr : NULL; 00241 } 00242 00243 static void touchblock(ARENA *hdr) 00244 { 00245 assert(hdr!=NULL); 00246 if (++pool_lru >= PROTECT_LRU) 00247 pool_lru=0; 00248 hdr->lru=pool_lru; 00249 00250 /* special case: if the overlay LRU count wrapped back to zero, set the 00251 * LRU count of all blocks to zero, but set the count of the block just 00252 * touched to 1 (skip blocks marked as protected, too) 00253 */ 00254 if (pool_lru==0) { 00255 ARENA *hdr2; 00256 unsigned sz=pool_size; 00257 hdr2=(ARENA*)pool_base; 00258 while (sz>0) { 00259 assert(sz<=pool_size); 00260 if (hdr2->lru!=PROTECT_LRU) 00261 hdr2->lru=0; 00262 sz-=hdr2->blocksize+sizeof(ARENA); 00263 hdr2=(ARENA*)((char*)hdr2+hdr2->blocksize+sizeof(ARENA)); 00264 } /* while */ 00265 assert(sz==0); 00266 hdr->lru=++pool_lru; 00267 } /* if */ 00268 }
Generated on Sat Jul 16 2022 16:09:35 by 1.7.2