lib.c

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