lib.c

   1 /*
   2  * 'sparse' library helper routines.
   3  *
   4  * Copyright (C) 2003 Transmeta Corp.
   5  *
   6  *  Licensed under the Open Software License version 1.1
   7  */
   8 #include <stddef.h>
   9 #include <stdarg.h>
  10 #include <stdio.h>
  11 #include <stdlib.h>
  12 #include <string.h>
  13 #include <sys/mman.h>
  14
  15 #include "lib.h"
  16 #include "token.h"
  17 #include "parse.h"
  18 #include "symbol.h"
  19 #include "expression.h"
  20 #include "scope.h"
  21
  22 struct token *skip_to(struct token *token, int op)
  23 {
  24         while (!match_op(token, op) && !eof_token(token))
  25                 token = token->next;
  26         return token;
  27 }
  28
  29 struct token *expect(struct token *token, int op, const char *where)
  30 {
  31         if (!match_op(token, op)) {
  32                 static struct token bad_token;
  33                 if (token != &bad_token) {
  34                         bad_token.next = token;
  35                         warn(token->pos, "Expected %s %s", show_special(op), where);
  36                         warn(token->pos, "got %s", show_token(token));
  37                 }
  38                 if (op == ';')
  39                         return skip_to(token, op);
  40                 return &bad_token;
  41         }
  42         return token->next;
  43 }
  44
  45 unsigned int hexval(unsigned int c)
  46 {
  47         int retval = 256;
  48         switch (c) {
  49         case '0'...'9':
  50                 retval = c - '0';
  51                 break;
  52         case 'a'...'f':
  53                 retval = c - 'a' + 10;
  54                 break;
  55         case 'A'...'F':
  56                 retval = c - 'A' + 10;
  57                 break;
  58         }
  59         return retval;
  60 }
  61
  62 /*
  63  * Simple allocator for data that doesn't get partially free'd.
  64  * The tokenizer and parser allocate a _lot_ of small data structures
  65  * (often just two-three bytes for things like small integers),
  66  * and since they all depend on each other you can't free them
  67  * individually _anyway_. So do something that is very space-
  68  * efficient: allocate larger "blobs", and give out individual
  69  * small bits and pieces of it with no maintenance overhead.
  70  */
  71 struct allocation_blob {
  72         struct allocation_blob *next;
  73         unsigned int left, offset;
  74         unsigned char data[];
  75 };
  76
  77 #define CHUNK 32768
  78 #define blob_alloc(size) mmap(NULL, ((size)+4095) & ~4095, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0)
  79 #define blob_free(addr,size) munmap((addr), ((size)+4095) & ~4095)
  80
  81 struct allocator_struct {
  82         const char *name;
  83         struct allocation_blob *blobs;
  84         unsigned int alignment;
  85         unsigned int chunking;
  86         /* statistics */
  87         unsigned int allocations, total_bytes, useful_bytes;
  88 };
  89
  90 void drop_all_allocations(struct allocator_struct *desc)
  91 {
  92         struct allocation_blob *blob = desc->blobs;
  93
  94         desc->blobs = NULL;
  95         desc->allocations = 0;
  96         desc->total_bytes = 0;
  97         desc->useful_bytes = 0;
  98         while (blob) {
  99                 struct allocation_blob *next = blob->next;
 100                 blob_free(blob, desc->chunking);
 101                 blob = next;
 102         }
 103 }
 104
 105 void *allocate(struct allocator_struct *desc, unsigned int size)
 106 {
 107         unsigned long alignment = desc->alignment;
 108         struct allocation_blob *blob = desc->blobs;
 109         void *retval;
 110
 111         desc->allocations++;
 112         desc->useful_bytes += size;
 113         size = (size + alignment - 1) & ~(alignment-1);
 114         if (!blob || blob->left < size) {
 115                 unsigned int offset, chunking = desc->chunking;
 116                 struct allocation_blob *newblob = blob_alloc(chunking);
 117                 if (!newblob)
 118                         die("out of memory");
 119                 desc->total_bytes += chunking;
 120                 newblob->next = blob;
 121                 blob = newblob;
 122                 desc->blobs = newblob;
 123                 offset = offsetof(struct allocation_blob, data);
 124                 if (alignment > offset)
 125                         offset = alignment;
 126                 blob->left = chunking - offset;
 127                 blob->offset = offset - offsetof(struct allocation_blob, data);
 128         }
 129         retval = blob->data + blob->offset;
 130         blob->offset += size;
 131         blob->left -= size;
 132         return retval;
 133 }
 134
 135 static void show_allocations(struct allocator_struct *x)
 136 {
 137         fprintf(stderr, "%s: %d allocations, %d bytes (%d total bytes, "
 138                         "%6.2f%% usage, %6.2f average size)\n",
 139                 x->name, x->allocations, x->useful_bytes, x->total_bytes,
 140                 100 * (double) x->useful_bytes / x->total_bytes,
 141                 (double) x->useful_bytes / x->allocations);
 142 }
 143
 144 struct allocator_struct ident_allocator = { "identifiers", NULL, __alignof__(struct ident), CHUNK };
 145 struct allocator_struct token_allocator = { "tokens", NULL, __alignof__(struct token), CHUNK };
 146 struct allocator_struct symbol_allocator = { "symbols", NULL, __alignof__(struct symbol), CHUNK };
 147 struct allocator_struct expression_allocator = { "expressions", NULL, __alignof__(struct expression), CHUNK };
 148 struct allocator_struct statement_allocator = { "statements", NULL, __alignof__(struct statement), CHUNK };
 149 struct allocator_struct string_allocator = { "strings", NULL, __alignof__(struct statement), CHUNK };
 150 struct allocator_struct scope_allocator = { "scopes", NULL, __alignof__(struct scope), CHUNK };
 151 struct allocator_struct bytes_allocator = { "bytes", NULL, 1, CHUNK };
 152
 153 #define __ALLOCATOR(type, size, x)                              \
 154         type *__alloc_##x(int extra)                            \
 155         {                                                       \
 156                 return allocate(&x##_allocator, size+extra);    \
 157         }                                                       \
 158         void show_##x##_alloc(void)                             \
 159         {                                                       \
 160                 show_allocations(&x##_allocator);               \
 161         }                                                       \
 162         void clear_##x##_alloc(void)                            \
 163         {                                                       \
 164                 drop_all_allocations(&x##_allocator);           \
 165         }
 166 #define ALLOCATOR(x) __ALLOCATOR(struct x, sizeof(struct x), x)
 167
 168 ALLOCATOR(ident); ALLOCATOR(token); ALLOCATOR(symbol);
 169 ALLOCATOR(expression); ALLOCATOR(statement); ALLOCATOR(string);
 170 ALLOCATOR(scope); __ALLOCATOR(void, 0, bytes);
 171
 172 int ptr_list_size(struct ptr_list *head)
 173 {
 174         int nr = 0;
 175
 176         if (head) {
 177                 struct ptr_list *list = head;
 178                 do {
 179                         nr += list->nr;
 180                 } while ((list = list->next) != head);
 181         }
 182         return nr;
 183 }
 184
 185 void iterate(struct ptr_list *head, void (*callback)(void *, void *, int), void *data)
 186 {
 187         struct ptr_list *list = head;
 188         int flag = ITERATE_FIRST;
 189
 190         if (!head)
 191                 return;
 192         do {
 193                 int i;
 194                 for (i = 0; i < list->nr; i++) {
 195                         if (i == list->nr-1 && list->next == head)
 196                                 flag |= ITERATE_LAST;
 197                         callback(list->list[i], data, flag);
 198                         flag = 0;
 199                 }
 200                 list = list->next;
 201         } while (list != head);
 202 }
 203
 204 void add_ptr_list(struct ptr_list **listp, void *ptr)
 205 {
 206         struct ptr_list *list = *listp;
 207         int nr;
 208
 209         if (!list || (nr = list->nr) >= LIST_NODE_NR) {
 210                 struct ptr_list *newlist = malloc(sizeof(*newlist));
 211                 if (!newlist)
 212                         die("out of memory for symbol/statement lists");
 213                 memset(newlist, 0, sizeof(*newlist));
 214                 if (!list) {
 215                         newlist->next = newlist;
 216                         newlist->prev = newlist;
 217                         *listp = newlist;
 218                 } else {
 219                         newlist->next = list;
 220                         newlist->prev = list->prev;
 221                         list->prev->next = newlist;
 222                         list->prev = newlist;
 223                 }
 224                 list = newlist;
 225                 nr = 0;
 226         }
 227         list->list[nr] = ptr;
 228         nr++;
 229         list->nr = nr;
 230 }
 231
 232 static void do_warn(const char *type, struct position pos, const char * fmt, va_list args)
 233 {
 234         static char buffer[512];
 235         const char *name;
 236
 237         vsprintf(buffer, fmt, args);
 238         name = input_streams[pos.stream].name;
 239
 240         fprintf(stderr, "%s: %s:%d:%d: %s\n",
 241                 type, name, pos.line, pos.pos, buffer);
 242 }
 243
 244 void warn(struct position pos, const char * fmt, ...)
 245 {
 246         static int warnings = 0;
 247         va_list args;
 248
 249         if (warnings > 100) {
 250                 static int once = 0;
 251                 if (once)
 252                         return;
 253                 fmt = "too many warnings";
 254                 once = 1;
 255         }
 256
 257         va_start(args, fmt);
 258         do_warn("warning", pos, fmt, args);
 259         va_end(args);
 260         warnings++;
 261 }
 262
 263 void error(struct position pos, const char * fmt, ...)
 264 {
 265         va_list args;
 266         va_start(args, fmt);
 267         do_warn("error", pos, fmt, args);
 268         va_end(args);
 269         exit(1);
 270 }
 271
 272 void die(const char *fmt, ...)
 273 {
 274         va_list args;
 275         static char buffer[512];
 276
 277         va_start(args, fmt);
 278         vsnprintf(buffer, sizeof(buffer), fmt, args);
 279         va_end(args);
 280
 281         fprintf(stderr, "%s\n", buffer);
 282         exit(1);
 283 }
 284
 285