lbutingtaon.h

   1
   2 /**
   3    @section <a href="https://github.com/tsoding/arena">Arena
   4    Allocator</a> library from Mr. Zozin.
   5
   6    I split up the code to have the header declarations come first and
   7    the implementation after that of this library's.
   8  */
   9
  10 #ifndef ARENA_H_
  11 #define ARENA_H_
  12
  13 #include <stddef.h>
  14 #include <stdint.h>
  15 #include <bits/stdint-intn.h>
  16 #include <string.h>
  17
  18 #ifndef ARENA_NOSTDIO
  19 #include <stdarg.h>
  20 #include <stdio.h>
  21 #endif // ARENA_NOSTDIO
  22
  23 #ifndef ARENA_ASSERT
  24 #include <assert.h>
  25 #define ARENA_ASSERT assert
  26 #endif
  27
  28 #define ARENA_BACKEND_LIBC_MALLOC 0
  29 #define ARENA_BACKEND_LINUX_MMAP 1
  30 #define ARENA_BACKEND_WIN32_VIRTUALALLOC 2
  31 #define ARENA_BACKEND_WASM_HEAPBASE 3
  32
  33 #ifndef ARENA_BACKEND
  34 #define ARENA_BACKEND ARENA_BACKEND_LIBC_MALLOC
  35 #endif // ARENA_BACKEND
  36
  37 typedef struct Region Region;
  38
  39 struct Region {
  40     Region *next;
  41     size_t count;
  42     size_t capacity;
  43     uintptr_t data[];
  44 };
  45
  46 typedef struct {
  47     Region *begin, *end;
  48 } Arena;
  49
  50 typedef struct  {
  51     Region *region;
  52     size_t count;
  53 } Arena_Mark;
  54
  55 #define REGION_DEFAULT_CAPACITY (8*1024)
  56
  57 Region *new_region(size_t capacity);
  58 void free_region(Region *r);
  59
  60 void *arena_alloc(Arena *a, size_t size_bytes);
  61 void *arena_realloc(Arena *a, void *oldptr, size_t oldsz, size_t newsz);
  62 char *arena_strdup(Arena *a, const char *cstr);
  63 void *arena_memdup(Arena *a, void *data, size_t size);
  64 #ifndef ARENA_NOSTDIO
  65 char *arena_sprintf(Arena *a, const char *format, ...);
  66 #endif // ARENA_NOSTDIO
  67
  68 Arena_Mark arena_snapshot(Arena *a);
  69 void arena_reset(Arena *a);
  70 void arena_rewind(Arena *a, Arena_Mark m);
  71 void arena_free(Arena *a);
  72 void arena_trim(Arena *a);
  73
  74 #define ARENA_DA_INIT_CAP 256
  75
  76 #ifdef __cplusplus
  77     #define cast_ptr(ptr) (decltype(ptr))
  78 #else
  79     #define cast_ptr(...)
  80 #endif
  81
  82 #define arena_da_append(a, da, item)                                                          \
  83     do {                                                                                      \
  84         if ((da)->count >= (da)->capacity) {                                                  \
  85             size_t new_capacity = (da)->capacity == 0 ? ARENA_DA_INIT_CAP : (da)->capacity*2; \
  86             (da)->items = cast_ptr((da)->items)arena_realloc(                                 \
  87                 (a), (da)->items,                                                             \
  88                 (da)->capacity*sizeof(*(da)->items),                                          \
  89                 new_capacity*sizeof(*(da)->items));                                           \
  90             (da)->capacity = new_capacity;                                                    \
  91         }                                                                                     \
  92                                                                                               \
  93         (da)->items[(da)->count++] = (item);                                                  \
  94     } while (0)
  95
  96 #endif // ARENA_H_
  97
  98
  99 #ifndef LIBBUTINGTAON_H
 100 #define LIBBUTINGTAON_H 1
 101
 102 #include <stddef.h>
 103 #include <assert.h>
 104 #include <stdint.h>
 105
 106 extern int LBTTN_ERRNO;
 107
 108 char* lbttn_decode_errno(int errno);
 109
 110 typedef struct lbttn_cell lbttn_cell;
 111
 112 typedef lbttn_cell *(*transform_fn)(Arena *context, lbttn_cell *cell, void *param);
 113 typedef void (*callback_fn)(lbttn_cell *cell, void *param);
 114 typedef int (*compare_fn)(lbttn_cell*, lbttn_cell*);
 115 typedef int (*pred_fn)(lbttn_cell*);
 116 typedef lbttn_cell *(*reducer_fn)(Arena *context, lbttn_cell *prev, lbttn_cell *next);
 117
 118 typedef lbttn_cell *(*from_int_fn)(Arena *context, int64_t integer);
 119 typedef lbttn_cell *(*from_uint_fn)(Arena *context, uint64_t uint);
 120 typedef lbttn_cell *(*from_dec_fn)(Arena *context, double dec);
 121 typedef lbttn_cell *(*from_byte_fn)(Arena *context, char byte);
 122 typedef lbttn_cell *(*from_cstring_fn)(Arena *context, char *cstring);
 123 typedef int64_t (*cell_get_int_fn)(lbttn_cell *cell);
 124 typedef uint64_t (*cell_get_uint_fn)(lbttn_cell *cell);
 125 typedef double (*cell_get_decimal_fn)(lbttn_cell *cell);
 126 typedef char (*cell_get_byte_fn)(lbttn_cell *cell);
 127 typedef char *(*cell_get_cstr_fn)(lbttn_cell *cell);
 128 typedef int64_t (*cell_get_cstrlen_fn)(lbttn_cell *cell);
 129 typedef int (*cell_set_int_fn)(lbttn_cell *cell, int64_t integer);
 130 typedef int (*cell_set_uint_fn)(lbttn_cell *cell, uint64_t uint);
 131 typedef int (*cell_set_decimal_fn)(lbttn_cell *cell, double decimal);
 132 typedef int (*cell_set_byte_fn)(lbttn_cell *cell, char byte);
 133 typedef int (*cell_set_cstr_fn)(lbttn_cell *cell, char* cstr);
 134
 135
 136 typedef struct lbttn_cell_vt lbttn_cell_vt;
 137
 138 struct lbttn_cell_vt
 139 {
 140     from_int_fn from_int;
 141     from_uint_fn from_uint;
 142     from_dec_fn from_decimal;
 143     from_byte_fn from_byte;
 144     from_cstring_fn from_cstr;
 145     cell_get_int_fn get_int;
 146     cell_get_uint_fn get_uint;
 147     cell_get_decimal_fn get_decimal;
 148     cell_get_byte_fn get_byte;
 149     cell_get_cstr_fn get_cstr;
 150     cell_get_cstrlen_fn get_cstrlen;
 151     cell_set_int_fn set_int;
 152     cell_set_uint_fn set_uint;
 153     cell_set_decimal_fn set_decimal;
 154     cell_set_byte_fn set_byte;
 155     cell_set_cstr_fn set_cstr;
 156 };
 157
 158 extern lbttn_cell_vt Cell_Vt;
 159
 160 typedef lbttn_cell *(*pair_head_fn)(lbttn_cell *pair);
 161 typedef lbttn_cell *(*pair_rest_fn)(lbttn_cell *pair);
 162 typedef lbttn_cell *(*pair_cons_fn)(Arena *context, lbttn_cell *value, lbttn_cell *pair);
 163 typedef unsigned int *(*pair_count_fn)(lbttn_cell *pair);
 164 typedef lbttn_cell *(*pair_by_index_fn)(lbttn_cell *pair, unsigned int skip);
 165 typedef lbttn_cell *(*pair_reverse_fn)(Arena *context, lbttn_cell *pair);
 166 typedef lbttn_cell *(*pair_append_fn)(Arena *context, lbttn_cell *pair1, lbttn_cell *pair2);
 167 typedef lbttn_cell *(*pair_min_fn)(lbttn_cell *pair, compare_fn compare);
 168 typedef lbttn_cell *(*pair_sort_fn)(Arena *context, lbttn_cell *pair, compare_fn compare);
 169 typedef lbttn_cell *(*pair_filter_fn)(Arena *context, lbttn_cell *pair, pred_fn predicate);
 170 typedef lbttn_cell *(*pair_nil_fn)();
 171 typedef lbttn_cell *(*pair_map_fn)(Arena *context, lbttn_cell *pair, transform_fn transform, void *param);
 172 typedef void (*pair_foreach_fn)(lbttn_cell *pair, callback_fn callback, void *param);
 173 typedef lbttn_cell *(*pair_reduce_fn)(Arena *context, lbttn_cell *pair, reducer_fn reducer);
 174
 175 typedef struct lbttn_list_vt lbttn_list_vt;
 176
 177 struct lbttn_list_vt
 178 {
 179     pair_head_fn head;
 180     pair_rest_fn rest;
 181     pair_cons_fn cons;
 182     pair_count_fn count;
 183     pair_by_index_fn by_index;
 184     pair_reverse_fn reverse;
 185     pair_append_fn append;
 186     pair_min_fn min;
 187     pair_sort_fn sort;
 188     pair_filter_fn filter;
 189     pair_nil_fn nil;
 190     pair_map_fn map;
 191     pair_foreach_fn foreach;
 192     pair_reduce_fn reduce;
 193 };
 194
 195 extern lbttn_list_vt List_Vt;
 196
 197 #endif
 198
 199 #define LIBBUTINGTAON_IMPL 1
 200 #ifdef LIBBUTINGTAON_IMPL
 201 #define ARENA_IMPLEMENTATION
 202
 203 enum lbttn_type
 204 {
 205     LBTTN_BYTE,
 206     LBTTN_INT,
 207     LBTTN_UINT,
 208     LBTTN_DECIMAL,
 209     LBTTN_STRING,
 210     LBTTN_ARRAY,
 211     LBTTN_PAIR,
 212     LBTTN_HASHMAP,
 213     LBTTN_CUSTOM
 214 };
 215
 216 /**
 217    @brief The "header" type.
 218
 219    This is the entrypoint for the data structures in this library. It
 220    uses the header+data approach to type generics in C.
 221  */
 222 struct lbttn_cell
 223 {
 224     enum lbttn_type type;
 225     size_t size;
 226     void *data;
 227 };
 228
 229 lbttn_cell *cell_from_int(Arena *context, int64_t integer);
 230 lbttn_cell *cell_from_uint(Arena *context, uint64_t uint);
 231 lbttn_cell *cell_from_decimal(Arena *context, double decimal);
 232 lbttn_cell *cell_from_byte(Arena *context, char byte);
 233 lbttn_cell *cell_from_cstring(Arena *context, char *cstring);
 234 int64_t cell_get_int(lbttn_cell *cell);
 235 uint64_t cell_get_uint(lbttn_cell *cell);
 236 double cell_get_decimal(lbttn_cell *cell);
 237 char cell_get_byte(lbttn_cell *cell);
 238 char *cell_get_cstr(lbttn_cell *cell);
 239 int64_t cell_get_cstrlen(lbttn_cell *cell);
 240 int cell_set_int(lbttn_cell *cell, int64_t integer);
 241 int cell_set_uint(lbttn_cell *cell, uint64_t uint);
 242 int cell_set_decimal(lbttn_cell *cell, double decimal);
 243 int cell_set_byte(lbttn_cell *cell, char byte);
 244 int cell_set_cstr(lbttn_cell *cell, char* cstr);
 245
 246 lbttn_cell_vt Cell_Vt = (lbttn_cell_vt)
 247 {
 248     .from_int = cell_from_int,
 249     .from_uint = cell_from_uint,
 250     .from_decimal = cell_from_decimal,
 251     .from_byte = cell_from_byte,
 252     .from_cstr = cell_from_cstring,
 253     .get_int = cell_get_int,
 254     .get_uint = cell_get_uint,
 255     .get_decimal = cell_get_decimal,
 256     .get_byte = cell_get_byte,
 257     .get_cstr = cell_get_cstr,
 258     .get_cstrlen = cell_get_cstrlen,
 259     .set_int = cell_set_int,
 260     .set_uint = cell_set_uint,
 261     .set_decimal = cell_set_decimal,
 262     .set_byte = cell_set_byte,
 263     .set_cstr = cell_set_cstr,
 264 };
 265
 266 lbttn_cell *cell_from_int(Arena *context, int64_t integer)
 267 {
 268     lbttn_cell *result = (lbttn_cell *) arena_alloc(context, sizeof(lbttn_cell));
 269     result->type = LBTTN_INT;
 270     result->size = sizeof(int64_t);
 271     result->data = arena_alloc(context, result->size);
 272     *((int64_t *) result->data) = integer;
 273
 274     return result;
 275 }
 276
 277 lbttn_cell *cell_from_uint(Arena *context, uint64_t uint)
 278 {
 279     lbttn_cell *result = (lbttn_cell *) arena_alloc(context, sizeof(lbttn_cell));
 280     result->type = LBTTN_UINT;
 281     result->size = sizeof(uint64_t);
 282     result->data = arena_alloc(context, result->size);
 283     *((uint64_t *) result->data) = uint;
 284
 285     return result;
 286 }
 287
 288 lbttn_cell *cell_from_decimal(Arena *context, double decimal)
 289 {
 290     lbttn_cell *result = (lbttn_cell *) arena_alloc(context, sizeof(lbttn_cell));
 291     result->type = LBTTN_DECIMAL;
 292     result->size = sizeof(double);
 293     result->data = arena_alloc(context, result->size);
 294     *((double *) result->data) = decimal;
 295
 296     return result;
 297 }
 298
 299 lbttn_cell *cell_from_byte(Arena *context, char byte)
 300 {
 301     lbttn_cell *result = (lbttn_cell *) arena_alloc(context, sizeof(lbttn_cell));
 302     result->type = LBTTN_BYTE;
 303     result->size = sizeof(char);
 304     result->data = arena_alloc(context, result->size);
 305     *((char *) result->data) = byte;
 306
 307     return result;
 308 }
 309
 310 lbttn_cell *cell_from_cstring(Arena *context, char *cstring)
 311 {
 312     lbttn_cell *result = (lbttn_cell *) arena_alloc(context, sizeof(lbttn_cell));
 313     int64_t length = 0;
 314     char *buffer;
 315
 316     result->type = LBTTN_STRING;
 317
 318     {
 319         for ( int64_t index = 0; cstring[index]; index++ ) length++;
 320     }
 321
 322     buffer = (char *) arena_alloc(context, length + 1);
 323     result->size = (size_t) length;
 324
 325     {
 326         for ( int64_t index = 0; index < length + 1; index++ ) buffer[index] = 0;
 327     }
 328
 329     {
 330         for ( int64_t index = 0; index < length; index++ )
 331             buffer[index] = cstring[index];
 332     }
 333
 334     result->data = buffer;
 335
 336     return result;
 337 }
 338
 339 int64_t cell_get_int(lbttn_cell *cell) { return *((int64_t *) cell->data); }
 340 uint64_t cell_get_uint(lbttn_cell *cell) { return *((uint64_t *) cell->data); }
 341 double cell_get_decimal(lbttn_cell *cell) { return *((double *) cell->data); }
 342 char cell_get_byte(lbttn_cell *cell) { return *((char *) cell->data); }
 343 char *cell_get_cstr(lbttn_cell *cell) { return (char *) cell->data; }
 344 int64_t cell_get_cstrlen(lbttn_cell *cell) { return (int64_t) cell->size; }
 345
 346 int cell_set_int(lbttn_cell *cell, int64_t integer)
 347 {
 348     if ( cell->type != LBTTN_INT )
 349     {
 350         LBTTN_ERRNO = 1;
 351         return 1;
 352     }
 353
 354     *((int64_t *) cell->data) = integer;
 355     return 0;
 356 }
 357
 358
 359 int cell_set_uint(lbttn_cell *cell, uint64_t uint)
 360 {
 361     if ( cell->type != LBTTN_UINT )
 362     {
 363         LBTTN_ERRNO = 1;
 364         return 1;
 365     }
 366
 367     *((uint64_t *) cell->data) = uint;
 368     return 0;
 369 }
 370
 371 int cell_set_decimal(lbttn_cell *cell, double decimal)
 372 {
 373     if ( cell->type != LBTTN_DECIMAL )
 374     {
 375         LBTTN_ERRNO = 1;
 376         return 1;
 377     }
 378
 379     *((double *) cell->data) = decimal;
 380     return 0;
 381 }
 382
 383 int cell_set_byte(lbttn_cell *cell, char byte)
 384 {
 385     if ( cell->type != LBTTN_BYTE )
 386     {
 387         LBTTN_ERRNO = 1;
 388         return 1;
 389     }
 390
 391     *((char *) cell->data) = byte;
 392     return 0;
 393 }
 394
 395 int cell_set_cstr(lbttn_cell *cell, char* cstr)
 396 {
 397     if ( cell->type != LBTTN_STRING )
 398     {
 399         LBTTN_ERRNO = 1;
 400         return 1;
 401     }
 402
 403     cell->data = cstr;
 404     return 0;
 405 }
 406
 407 lbttn_cell *pair_head(lbttn_cell *pair);
 408 lbttn_cell *pair_rest(lbttn_cell *pair);
 409 lbttn_cell *pair_cons(Arena *context, lbttn_cell *value, lbttn_cell *pair);
 410 unsigned int *pair_count(lbttn_cell *pair);
 411 lbttn_cell *pair_by_index(lbttn_cell *pair, unsigned int skip);
 412 lbttn_cell *pair_reverse(Arena *context, lbttn_cell *pair);
 413 lbttn_cell *pair_append(Arena *context, lbttn_cell *pair1, lbttn_cell *pair2);
 414 lbttn_cell *pair_nil();
 415
 416 lbttn_list_vt List_Vt = (lbttn_list_vt)
 417 {
 418     .head = pair_head,
 419     .rest = pair_rest,
 420     .cons = pair_cons,
 421     .by_index = pair_by_index,
 422     .reverse = pair_reverse,
 423     .nil  = pair_nil,
 424 };
 425
 426 struct lbttn_pair
 427 {
 428     lbttn_cell *head;
 429     lbttn_cell *rest;
 430 };
 431
 432 static lbttn_cell PAIR_NIL = (lbttn_cell)
 433 {
 434     .type = LBTTN_PAIR,
 435     .size = 0,
 436     .data = 0
 437 };
 438
 439 lbttn_cell *pair_head(lbttn_cell *pair)
 440 {
 441     if ( pair && pair->data )
 442     {
 443         struct lbttn_pair *as_pair = (struct lbttn_pair *) pair->data;
 444         return as_pair->head;
 445     }
 446
 447     else return 0;
 448 }
 449
 450 lbttn_cell *pair_rest(lbttn_cell *pair)
 451 {
 452     struct lbttn_pair *as_pair = (struct lbttn_pair *) pair->data;
 453     return as_pair->rest;
 454 }
 455
 456 lbttn_cell *pair_cons(Arena *context, lbttn_cell *value, lbttn_cell *pair)
 457 {
 458     lbttn_cell *result = (lbttn_cell *) arena_alloc(context, sizeof(lbttn_cell));
 459     struct lbttn_pair *new_pair = (struct lbttn_pair *) arena_alloc(context, sizeof(struct lbttn_pair));
 460
 461     result->type = LBTTN_PAIR;
 462     new_pair->head = value;
 463     new_pair->rest = pair;
 464     result->data = new_pair;
 465     result->size = sizeof(struct lbttn_cell);
 466
 467     return result;
 468 }
 469
 470 lbttn_cell *pair_reverse(Arena *context, lbttn_cell *pair)
 471 {
 472     lbttn_cell *result = pair_nil();
 473
 474     for ( lbttn_cell *tracker = pair;
 475           pair_head(tracker);
 476           tracker = pair_rest(tracker) )
 477     {
 478         result = pair_cons(context, pair_head(tracker), result);
 479     }
 480
 481     return result;
 482 }
 483
 484 lbttn_cell *pair_nil() { return &PAIR_NIL; }
 485
 486 lbttn_cell *pair_by_index(lbttn_cell *pair, unsigned int skip)
 487 {
 488     lbttn_cell *result = pair;
 489
 490     for ( unsigned int index = skip; index > 0; index-- )
 491     {
 492         result = pair_rest(result);
 493     }
 494
 495     return result;
 496 }
 497
 498 char* lbttn_decode_errno(int errno) { return ""; };
 499
 500 #endif // LIBBUTINGTAON_IMPL
 501
 502 #ifdef ARENA_IMPLEMENTATION
 503
 504 #if ARENA_BACKEND == ARENA_BACKEND_LIBC_MALLOC
 505 #include <stdlib.h>
 506
 507 // TODO: instead of accepting specific capacity new_region() should accept the size of the object we want to fit into the region
 508 // It should be up to new_region() to decide the actual capacity to allocate
 509 Region *new_region(size_t capacity)
 510 {
 511     size_t size_bytes = sizeof(Region) + sizeof(uintptr_t)*capacity;
 512     // TODO: it would be nice if we could guarantee that the regions are allocated by ARENA_BACKEND_LIBC_MALLOC are page aligned
 513     Region *r = (Region*)malloc(size_bytes);
 514     ARENA_ASSERT(r);
 515     r->next = NULL;
 516     r->count = 0;
 517     r->capacity = capacity;
 518     return r;
 519 }
 520
 521 void free_region(Region *r)
 522 {
 523     free(r);
 524 }
 525 #elif ARENA_BACKEND == ARENA_BACKEND_LINUX_MMAP
 526 #include <unistd.h>
 527 #include <sys/mman.h>
 528
 529 Region *new_region(size_t capacity)
 530 {
 531     size_t size_bytes = sizeof(Region) + sizeof(uintptr_t) * capacity;
 532     Region *r = mmap(NULL, size_bytes, PROT_READ | PROT_WRITE, MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);
 533     ARENA_ASSERT(r != MAP_FAILED);
 534     r->next = NULL;
 535     r->count = 0;
 536     r->capacity = capacity;
 537     return r;
 538 }
 539
 540 void free_region(Region *r)
 541 {
 542     size_t size_bytes = sizeof(Region) + sizeof(uintptr_t) * r->capacity;
 543     int ret = munmap(r, size_bytes);
 544     ARENA_ASSERT(ret == 0);
 545 }
 546
 547 #elif ARENA_BACKEND == ARENA_BACKEND_WIN32_VIRTUALALLOC
 548
 549 #if !defined(_WIN32)
 550 #  error "Current platform is not Windows"
 551 #endif
 552
 553 #define WIN32_LEAN_AND_MEAN
 554 #include <windows.h>
 555
 556 #define INV_HANDLE(x)       (((x) == NULL) || ((x) == INVALID_HANDLE_VALUE))
 557
 558 Region *new_region(size_t capacity)
 559 {
 560     SIZE_T size_bytes = sizeof(Region) + sizeof(uintptr_t) * capacity;
 561     Region *r = VirtualAllocEx(
 562         GetCurrentProcess(),      /* Allocate in current process address space */
 563         NULL,                     /* Unknown position */
 564         size_bytes,               /* Bytes to allocate */
 565         MEM_COMMIT | MEM_RESERVE, /* Reserve and commit allocated page */
 566         PAGE_READWRITE            /* Permissions ( Read/Write )*/
 567     );
 568     if (INV_HANDLE(r))
 569         ARENA_ASSERT(0 && "VirtualAllocEx() failed.");
 570
 571     r->next = NULL;
 572     r->count = 0;
 573     r->capacity = capacity;
 574     return r;
 575 }
 576
 577 void free_region(Region *r)
 578 {
 579     if (INV_HANDLE(r))
 580         return;
 581
 582     BOOL free_result = VirtualFreeEx(
 583         GetCurrentProcess(),        /* Deallocate from current process address space */
 584         (LPVOID)r,                  /* Address to deallocate */
 585         0,                          /* Bytes to deallocate ( Unknown, deallocate entire page ) */
 586         MEM_RELEASE                 /* Release the page ( And implicitly decommit it ) */
 587     );
 588
 589     if (FALSE == free_result)
 590         ARENA_ASSERT(0 && "VirtualFreeEx() failed.");
 591 }
 592
 593 #elif ARENA_BACKEND == ARENA_BACKEND_WASM_HEAPBASE
 594 #  error "TODO: WASM __heap_base backend is not implemented yet"
 595 #else
 596 #  error "Unknown Arena backend"
 597 #endif
 598
 599 // TODO: add debug statistic collection mode for arena
 600 // Should collect things like:
 601 // - How many times new_region was called
 602 // - How many times existing region was skipped
 603 // - How many times allocation exceeded REGION_DEFAULT_CAPACITY
 604
 605 void *arena_alloc(Arena *a, size_t size_bytes)
 606 {
 607     size_t size = (size_bytes + sizeof(uintptr_t) - 1)/sizeof(uintptr_t);
 608
 609     if (a->end == NULL) {
 610         ARENA_ASSERT(a->begin == NULL);
 611         size_t capacity = REGION_DEFAULT_CAPACITY;
 612         if (capacity < size) capacity = size;
 613         a->end = new_region(capacity);
 614         a->begin = a->end;
 615     }
 616
 617     while (a->end->count + size > a->end->capacity && a->end->next != NULL) {
 618         a->end = a->end->next;
 619     }
 620
 621     if (a->end->count + size > a->end->capacity) {
 622         ARENA_ASSERT(a->end->next == NULL);
 623         size_t capacity = REGION_DEFAULT_CAPACITY;
 624         if (capacity < size) capacity = size;
 625         a->end->next = new_region(capacity);
 626         a->end = a->end->next;
 627     }
 628
 629     void *result = &a->end->data[a->end->count];
 630     a->end->count += size;
 631     return result;
 632 }
 633
 634 void *arena_realloc(Arena *a, void *oldptr, size_t oldsz, size_t newsz)
 635 {
 636     if (newsz <= oldsz) return oldptr;
 637     void *newptr = arena_alloc(a, newsz);
 638     char *newptr_char = (char*)newptr;
 639     char *oldptr_char = (char*)oldptr;
 640     for (size_t i = 0; i < oldsz; ++i) {
 641         newptr_char[i] = oldptr_char[i];
 642     }
 643     return newptr;
 644 }
 645
 646 char *arena_strdup(Arena *a, const char *cstr)
 647 {
 648     size_t n = strlen(cstr);
 649     char *dup = (char*)arena_alloc(a, n + 1);
 650     memcpy(dup, cstr, n);
 651     dup[n] = '\0';
 652     return dup;
 653 }
 654
 655 void *arena_memdup(Arena *a, void *data, size_t size)
 656 {
 657     return memcpy(arena_alloc(a, size), data, size);
 658 }
 659
 660 #ifndef ARENA_NOSTDIO
 661 char *arena_sprintf(Arena *a, const char *format, ...)
 662 {
 663     va_list args;
 664     va_start(args, format);
 665     int n = vsnprintf(NULL, 0, format, args);
 666     va_end(args);
 667
 668     ARENA_ASSERT(n >= 0);
 669     char *result = (char*)arena_alloc(a, n + 1);
 670     va_start(args, format);
 671     vsnprintf(result, n + 1, format, args);
 672     va_end(args);
 673
 674     return result;
 675 }
 676 #endif // ARENA_NOSTDIO
 677
 678 Arena_Mark arena_snapshot(Arena *a)
 679 {
 680     Arena_Mark m;
 681     if(a->end == NULL){ //snapshot of uninitialized arena
 682         ARENA_ASSERT(a->begin == NULL);
 683         m.region = a->end;
 684         m.count  = 0;
 685     }else{
 686         m.region = a->end;
 687         m.count  = a->end->count;
 688     }
 689
 690     return m;
 691 }
 692
 693 void arena_reset(Arena *a)
 694 {
 695     for (Region *r = a->begin; r != NULL; r = r->next) {
 696         r->count = 0;
 697     }
 698
 699     a->end = a->begin;
 700 }
 701
 702 void arena_rewind(Arena *a, Arena_Mark m)
 703 {
 704     if(m.region == NULL){ //snapshot of uninitialized arena
 705         arena_reset(a);   //leave allocation
 706         return;
 707     }
 708
 709     m.region->count = m.count;
 710     for (Region *r = m.region->next; r != NULL; r = r->next) {
 711         r->count = 0;
 712     }
 713
 714     a->end = m.region;
 715 }
 716
 717 void arena_free(Arena *a)
 718 {
 719     Region *r = a->begin;
 720     while (r) {
 721         Region *r0 = r;
 722         r = r->next;
 723         free_region(r0);
 724     }
 725     a->begin = NULL;
 726     a->end = NULL;
 727 }
 728
 729 void arena_trim(Arena *a){
 730     Region *r = a->end->next;
 731     while (r) {
 732         Region *r0 = r;
 733         r = r->next;
 734         free_region(r0);
 735     }
 736     a->end->next = NULL;
 737 }
 738
 739 #endif // ARENA_IMPLEMENTATION