core: make fake cur_slists stackable
[smatch.git] / allocate.c
blob5cc52a98cce90742d8d7b2257d58a901354d5a6c
1 /*
2 * allocate.c - simple space-efficient blob allocator.
4 * Copyright (C) 2003 Transmeta Corp.
5 * 2003-2004 Linus Torvalds
7 * Licensed under the Open Software License version 1.1
9 * Simple allocator for data that doesn't get partially free'd.
10 * The tokenizer and parser allocate a _lot_ of small data structures
11 * (often just two-three bytes for things like small integers),
12 * and since they all depend on each other you can't free them
13 * individually _anyway_. So do something that is very space-
14 * efficient: allocate larger "blobs", and give out individual
15 * small bits and pieces of it with no maintenance overhead.
17 #include <stdlib.h>
18 #include <stddef.h>
19 #include <stdio.h>
21 #include "lib.h"
22 #include "allocate.h"
23 #include "compat.h"
24 #include "token.h"
25 #include "symbol.h"
26 #include "scope.h"
27 #include "expression.h"
28 #include "linearize.h"
30 void protect_allocations(struct allocator_struct *desc)
32 desc->blobs = NULL;
35 void drop_all_allocations(struct allocator_struct *desc)
37 struct allocation_blob *blob = desc->blobs;
39 desc->blobs = NULL;
40 desc->allocations = 0;
41 desc->total_bytes = 0;
42 desc->useful_bytes = 0;
43 desc->freelist = NULL;
44 while (blob) {
45 struct allocation_blob *next = blob->next;
46 blob_free(blob, desc->chunking);
47 blob = next;
51 void free_one_entry(struct allocator_struct *desc, void *entry)
53 void **p = entry;
54 *p = desc->freelist;
55 desc->freelist = p;
58 void *allocate(struct allocator_struct *desc, unsigned int size)
60 unsigned long alignment = desc->alignment;
61 struct allocation_blob *blob = desc->blobs;
62 void *retval;
65 * NOTE! The freelist only works with things that are
66 * (a) sufficiently aligned
67 * (b) use a constant size
68 * Don't try to free allocators that don't follow
69 * these rules.
71 if (desc->freelist) {
72 void **p = desc->freelist;
73 retval = p;
74 desc->freelist = *p;
75 do {
76 *p = NULL;
77 p++;
78 } while ((size -= sizeof(void *)) > 0);
79 return retval;
82 desc->allocations++;
83 desc->useful_bytes += size;
84 size = (size + alignment - 1) & ~(alignment-1);
85 if (!blob || blob->left < size) {
86 unsigned int offset, chunking = desc->chunking;
87 struct allocation_blob *newblob = blob_alloc(chunking);
88 if (!newblob)
89 die("out of memory");
90 desc->total_bytes += chunking;
91 newblob->next = blob;
92 blob = newblob;
93 desc->blobs = newblob;
94 offset = offsetof(struct allocation_blob, data);
95 offset = (offset + alignment - 1) & ~(alignment-1);
96 blob->left = chunking - offset;
97 blob->offset = offset - offsetof(struct allocation_blob, data);
99 retval = blob->data + blob->offset;
100 blob->offset += size;
101 blob->left -= size;
102 return retval;
105 void show_allocations(struct allocator_struct *x)
107 fprintf(stderr, "%s: %d allocations, %d bytes (%d total bytes, "
108 "%6.2f%% usage, %6.2f average size)\n",
109 x->name, x->allocations, x->useful_bytes, x->total_bytes,
110 100 * (double) x->useful_bytes / x->total_bytes,
111 (double) x->useful_bytes / x->allocations);
114 ALLOCATOR(ident, "identifiers");
115 ALLOCATOR(token, "tokens");
116 ALLOCATOR(context, "contexts");
117 ALLOCATOR(symbol, "symbols");
118 ALLOCATOR(expression, "expressions");
119 ALLOCATOR(statement, "statements");
120 ALLOCATOR(string, "strings");
121 ALLOCATOR(scope, "scopes");
122 __DO_ALLOCATOR(void, 0, 1, "bytes", bytes);
123 ALLOCATOR(basic_block, "basic_block");
124 ALLOCATOR(entrypoint, "entrypoint");
125 ALLOCATOR(instruction, "instruction");
126 ALLOCATOR(multijmp, "multijmp");
127 ALLOCATOR(pseudo, "pseudo");