1169695Skan/* objalloc.c -- routines to allocate memory for objects 2169695Skan Copyright 1997 Free Software Foundation, Inc. 3169695Skan Written by Ian Lance Taylor, Cygnus Solutions. 4169695Skan 5169695SkanThis program is free software; you can redistribute it and/or modify it 6169695Skanunder the terms of the GNU General Public License as published by the 7169695SkanFree Software Foundation; either version 2, or (at your option) any 8169695Skanlater version. 9169695Skan 10169695SkanThis program is distributed in the hope that it will be useful, 11169695Skanbut WITHOUT ANY WARRANTY; without even the implied warranty of 12169695SkanMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13169695SkanGNU General Public License for more details. 14169695Skan 15169695SkanYou should have received a copy of the GNU General Public License 16169695Skanalong with this program; if not, write to the Free Software 17169695SkanFoundation, 51 Franklin Street - Fifth Floor, 18169695SkanBoston, MA 02110-1301, USA. */ 19169695Skan 20169695Skan#include "config.h" 21169695Skan#include "ansidecl.h" 22169695Skan 23169695Skan#include "objalloc.h" 24169695Skan 25169695Skan/* Get a definition for NULL. */ 26169695Skan#include <stdio.h> 27169695Skan 28169695Skan#if VMS 29169695Skan#include <stdlib.h> 30169695Skan#include <unixlib.h> 31169695Skan#else 32169695Skan 33169695Skan/* Get a definition for size_t. */ 34169695Skan#include <stddef.h> 35169695Skan 36169695Skan#ifdef HAVE_STDLIB_H 37169695Skan#include <stdlib.h> 38169695Skan#else 39169695Skan/* For systems with larger pointers than ints, this must be declared. */ 40169695Skanextern PTR malloc (size_t); 41169695Skanextern void free (PTR); 42169695Skan#endif 43169695Skan 44169695Skan#endif 45169695Skan 46169695Skan/* These routines allocate space for an object. Freeing allocated 47169695Skan space may or may not free all more recently allocated space. 48169695Skan 49169695Skan We handle large and small allocation requests differently. If we 50169695Skan don't have enough space in the current block, and the allocation 51169695Skan request is for more than 512 bytes, we simply pass it through to 52169695Skan malloc. */ 53169695Skan 54169695Skan/* The objalloc structure is defined in objalloc.h. */ 55169695Skan 56169695Skan/* This structure appears at the start of each chunk. */ 57169695Skan 58169695Skanstruct objalloc_chunk 59169695Skan{ 60169695Skan /* Next chunk. */ 61169695Skan struct objalloc_chunk *next; 62169695Skan /* If this chunk contains large objects, this is the value of 63169695Skan current_ptr when this chunk was allocated. If this chunk 64169695Skan contains small objects, this is NULL. */ 65169695Skan char *current_ptr; 66169695Skan}; 67169695Skan 68169695Skan/* The aligned size of objalloc_chunk. */ 69169695Skan 70169695Skan#define CHUNK_HEADER_SIZE \ 71169695Skan ((sizeof (struct objalloc_chunk) + OBJALLOC_ALIGN - 1) \ 72169695Skan &~ (OBJALLOC_ALIGN - 1)) 73169695Skan 74169695Skan/* We ask for this much memory each time we create a chunk which is to 75169695Skan hold small objects. */ 76169695Skan 77169695Skan#define CHUNK_SIZE (4096 - 32) 78169695Skan 79169695Skan/* A request for this amount or more is just passed through to malloc. */ 80169695Skan 81169695Skan#define BIG_REQUEST (512) 82169695Skan 83169695Skan/* Create an objalloc structure. */ 84169695Skan 85169695Skanstruct objalloc * 86169695Skanobjalloc_create (void) 87169695Skan{ 88169695Skan struct objalloc *ret; 89169695Skan struct objalloc_chunk *chunk; 90169695Skan 91169695Skan ret = (struct objalloc *) malloc (sizeof *ret); 92169695Skan if (ret == NULL) 93169695Skan return NULL; 94169695Skan 95169695Skan ret->chunks = (PTR) malloc (CHUNK_SIZE); 96169695Skan if (ret->chunks == NULL) 97169695Skan { 98169695Skan free (ret); 99169695Skan return NULL; 100169695Skan } 101169695Skan 102169695Skan chunk = (struct objalloc_chunk *) ret->chunks; 103169695Skan chunk->next = NULL; 104169695Skan chunk->current_ptr = NULL; 105169695Skan 106169695Skan ret->current_ptr = (char *) chunk + CHUNK_HEADER_SIZE; 107169695Skan ret->current_space = CHUNK_SIZE - CHUNK_HEADER_SIZE; 108169695Skan 109169695Skan return ret; 110169695Skan} 111169695Skan 112169695Skan/* Allocate space from an objalloc structure. */ 113169695Skan 114169695SkanPTR 115169695Skan_objalloc_alloc (struct objalloc *o, unsigned long len) 116169695Skan{ 117169695Skan /* We avoid confusion from zero sized objects by always allocating 118169695Skan at least 1 byte. */ 119169695Skan if (len == 0) 120169695Skan len = 1; 121169695Skan 122169695Skan len = (len + OBJALLOC_ALIGN - 1) &~ (OBJALLOC_ALIGN - 1); 123169695Skan 124169695Skan if (len <= o->current_space) 125169695Skan { 126169695Skan o->current_ptr += len; 127169695Skan o->current_space -= len; 128169695Skan return (PTR) (o->current_ptr - len); 129169695Skan } 130169695Skan 131169695Skan if (len >= BIG_REQUEST) 132169695Skan { 133169695Skan char *ret; 134169695Skan struct objalloc_chunk *chunk; 135169695Skan 136169695Skan ret = (char *) malloc (CHUNK_HEADER_SIZE + len); 137169695Skan if (ret == NULL) 138169695Skan return NULL; 139169695Skan 140169695Skan chunk = (struct objalloc_chunk *) ret; 141169695Skan chunk->next = (struct objalloc_chunk *) o->chunks; 142169695Skan chunk->current_ptr = o->current_ptr; 143169695Skan 144169695Skan o->chunks = (PTR) chunk; 145169695Skan 146169695Skan return (PTR) (ret + CHUNK_HEADER_SIZE); 147169695Skan } 148169695Skan else 149169695Skan { 150169695Skan struct objalloc_chunk *chunk; 151169695Skan 152169695Skan chunk = (struct objalloc_chunk *) malloc (CHUNK_SIZE); 153169695Skan if (chunk == NULL) 154169695Skan return NULL; 155169695Skan chunk->next = (struct objalloc_chunk *) o->chunks; 156169695Skan chunk->current_ptr = NULL; 157169695Skan 158169695Skan o->current_ptr = (char *) chunk + CHUNK_HEADER_SIZE; 159169695Skan o->current_space = CHUNK_SIZE - CHUNK_HEADER_SIZE; 160169695Skan 161169695Skan o->chunks = (PTR) chunk; 162169695Skan 163169695Skan return objalloc_alloc (o, len); 164169695Skan } 165169695Skan} 166169695Skan 167169695Skan/* Free an entire objalloc structure. */ 168169695Skan 169169695Skanvoid 170169695Skanobjalloc_free (struct objalloc *o) 171169695Skan{ 172169695Skan struct objalloc_chunk *l; 173169695Skan 174169695Skan l = (struct objalloc_chunk *) o->chunks; 175169695Skan while (l != NULL) 176169695Skan { 177169695Skan struct objalloc_chunk *next; 178169695Skan 179169695Skan next = l->next; 180169695Skan free (l); 181169695Skan l = next; 182169695Skan } 183169695Skan 184169695Skan free (o); 185169695Skan} 186169695Skan 187169695Skan/* Free a block from an objalloc structure. This also frees all more 188169695Skan recently allocated blocks. */ 189169695Skan 190169695Skanvoid 191169695Skanobjalloc_free_block (struct objalloc *o, PTR block) 192169695Skan{ 193169695Skan struct objalloc_chunk *p, *small; 194169695Skan char *b = (char *) block; 195169695Skan 196169695Skan /* First set P to the chunk which contains the block we are freeing, 197169695Skan and set Q to the last small object chunk we see before P. */ 198169695Skan small = NULL; 199169695Skan for (p = (struct objalloc_chunk *) o->chunks; p != NULL; p = p->next) 200169695Skan { 201169695Skan if (p->current_ptr == NULL) 202169695Skan { 203169695Skan if (b > (char *) p && b < (char *) p + CHUNK_SIZE) 204169695Skan break; 205169695Skan small = p; 206169695Skan } 207169695Skan else 208169695Skan { 209169695Skan if (b == (char *) p + CHUNK_HEADER_SIZE) 210169695Skan break; 211169695Skan } 212169695Skan } 213169695Skan 214169695Skan /* If we can't find the chunk, the caller has made a mistake. */ 215169695Skan if (p == NULL) 216169695Skan abort (); 217169695Skan 218169695Skan if (p->current_ptr == NULL) 219169695Skan { 220169695Skan struct objalloc_chunk *q; 221169695Skan struct objalloc_chunk *first; 222169695Skan 223169695Skan /* The block is in a chunk containing small objects. We can 224169695Skan free every chunk through SMALL, because they have certainly 225169695Skan been allocated more recently. After SMALL, we will not see 226169695Skan any chunks containing small objects; we can free any big 227169695Skan chunk if the current_ptr is greater than or equal to B. We 228169695Skan can then reset the new current_ptr to B. */ 229169695Skan 230169695Skan first = NULL; 231169695Skan q = (struct objalloc_chunk *) o->chunks; 232169695Skan while (q != p) 233169695Skan { 234169695Skan struct objalloc_chunk *next; 235169695Skan 236169695Skan next = q->next; 237169695Skan if (small != NULL) 238169695Skan { 239169695Skan if (small == q) 240169695Skan small = NULL; 241169695Skan free (q); 242169695Skan } 243169695Skan else if (q->current_ptr > b) 244169695Skan free (q); 245169695Skan else if (first == NULL) 246169695Skan first = q; 247169695Skan 248169695Skan q = next; 249169695Skan } 250169695Skan 251169695Skan if (first == NULL) 252169695Skan first = p; 253169695Skan o->chunks = (PTR) first; 254169695Skan 255169695Skan /* Now start allocating from this small block again. */ 256169695Skan o->current_ptr = b; 257169695Skan o->current_space = ((char *) p + CHUNK_SIZE) - b; 258169695Skan } 259169695Skan else 260169695Skan { 261169695Skan struct objalloc_chunk *q; 262169695Skan char *current_ptr; 263169695Skan 264169695Skan /* This block is in a large chunk by itself. We can free 265169695Skan everything on the list up to and including this block. We 266169695Skan then start allocating from the next chunk containing small 267169695Skan objects, setting current_ptr from the value stored with the 268169695Skan large chunk we are freeing. */ 269169695Skan 270169695Skan current_ptr = p->current_ptr; 271169695Skan p = p->next; 272169695Skan 273169695Skan q = (struct objalloc_chunk *) o->chunks; 274169695Skan while (q != p) 275169695Skan { 276169695Skan struct objalloc_chunk *next; 277169695Skan 278169695Skan next = q->next; 279169695Skan free (q); 280169695Skan q = next; 281169695Skan } 282169695Skan 283169695Skan o->chunks = (PTR) p; 284169695Skan 285169695Skan while (p->current_ptr != NULL) 286169695Skan p = p->next; 287169695Skan 288169695Skan o->current_ptr = current_ptr; 289169695Skan o->current_space = ((char *) p + CHUNK_SIZE) - current_ptr; 290169695Skan } 291169695Skan} 292