lib.c

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