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