sys/src/ape/lib/ap/plan9/malloc.c

   1 #include <stdlib.h>
   2 #include <string.h>
   3
   4 typedef unsigned int    uint;
   5
   6 enum
   7 {
   8         MAGIC           = 0xbada110c,
   9         MAX2SIZE        = 32,
  10         CUTOFF          = 12,
  11 };
  12
  13 typedef struct Bucket Bucket;
  14 struct Bucket
  15 {
  16         int     size;
  17         int     magic;
  18         Bucket  *next;
  19         int     pad;
  20         char    data[1];
  21 };
  22
  23 typedef struct Arena Arena;
  24 struct Arena
  25 {
  26         Bucket  *btab[MAX2SIZE];
  27 };
  28 static Arena arena;
  29
  30 #define datoff          ((int)((Bucket*)0)->data)
  31 #define nil             ((void*)0)
  32
  33 extern  void    *sbrk(unsigned long);
  34
  35 void*
  36 malloc(size_t size)
  37 {
  38         uint next;
  39         int pow, n;
  40         Bucket *bp, *nbp;
  41
  42         for(pow = 1; pow < MAX2SIZE; pow++) {
  43                 if(size <= (1<<pow))
  44                         goto good;
  45         }
  46
  47         return nil;
  48 good:
  49         /* Allocate off this list */
  50         bp = arena.btab[pow];
  51         if(bp) {
  52                 arena.btab[pow] = bp->next;
  53
  54                 if(bp->magic != 0)
  55                         abort();
  56
  57                 bp->magic = MAGIC;
  58                 return  bp->data;
  59         }
  60         size = sizeof(Bucket)+(1<<pow);
  61         size += 7;
  62         size &= ~7;
  63
  64         if(pow < CUTOFF) {
  65                 n = (CUTOFF-pow)+2;
  66                 bp = sbrk(size*n);
  67                 if((int)bp < 0)
  68                         return nil;
  69
  70                 next = (uint)bp+size;
  71                 nbp = (Bucket*)next;
  72                 arena.btab[pow] = nbp;
  73                 for(n -= 2; n; n--) {
  74                         next = (uint)nbp+size;
  75                         nbp->next = (Bucket*)next;
  76                         nbp->size = pow;
  77                         nbp = nbp->next;
  78                 }
  79                 nbp->size = pow;
  80         }
  81         else {
  82                 bp = sbrk(size);
  83                 if((int)bp < 0)
  84                         return nil;
  85         }
  86
  87         bp->size = pow;
  88         bp->magic = MAGIC;
  89
  90         return bp->data;
  91 }
  92
  93 void
  94 free(void *ptr)
  95 {
  96         Bucket *bp, **l;
  97
  98         if(ptr == nil)
  99                 return;
 100
 101         /* Find the start of the structure */
 102         bp = (Bucket*)((uint)ptr - datoff);
 103
 104         if(bp->magic != MAGIC)
 105                 abort();
 106
 107         bp->magic = 0;
 108         l = &arena.btab[bp->size];
 109         bp->next = *l;
 110         *l = bp;
 111 }
 112
 113 void*
 114 realloc(void *ptr, size_t n)
 115 {
 116         void *new;
 117         uint osize;
 118         Bucket *bp;
 119
 120         if(ptr == nil)
 121                 return malloc(n);
 122
 123         /* Find the start of the structure */
 124         bp = (Bucket*)((uint)ptr - datoff);
 125
 126         if(bp->magic != MAGIC)
 127                 abort();
 128
 129         /* enough space in this bucket */
 130         osize = 1<<bp->size;
 131         if(osize >= n)
 132                 return ptr;
 133
 134         new = malloc(n);
 135         if(new == nil)
 136                 return nil;
 137
 138         memmove(new, ptr, osize);
 139         free(ptr);
 140
 141         return new;
 142 }