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