scenefile
annotate src/dynarr.c @ 2:c15992cedec9
scene
| author | John Tsiombikas <nuclear@mutantstargoat.com> |
|---|---|
| date | Sun, 15 Jan 2012 08:32:19 +0200 |
| parents | |
| children |
| rev | line source |
|---|---|
| nuclear@1 | 1 #include <stdio.h> |
| nuclear@1 | 2 #include <stdlib.h> |
| nuclear@1 | 3 #include <string.h> |
| nuclear@1 | 4 #include "dynarr.h" |
| nuclear@1 | 5 |
| nuclear@1 | 6 /* The array descriptor keeps auxilliary information needed to manipulate |
| nuclear@1 | 7 * the dynamic array. It's allocated adjacent to the array buffer. |
| nuclear@1 | 8 */ |
| nuclear@1 | 9 struct arrdesc { |
| nuclear@1 | 10 int nelem, szelem; |
| nuclear@1 | 11 int max_elem; |
| nuclear@1 | 12 int bufsz; /* not including the descriptor */ |
| nuclear@1 | 13 }; |
| nuclear@1 | 14 |
| nuclear@1 | 15 #define DESC(x) ((struct arrdesc*)((char*)(x) - sizeof(struct arrdesc))) |
| nuclear@1 | 16 |
| nuclear@1 | 17 void *dynarr_alloc(int elem, int szelem) |
| nuclear@1 | 18 { |
| nuclear@1 | 19 struct arrdesc *desc; |
| nuclear@1 | 20 |
| nuclear@1 | 21 if(!(desc = malloc(elem * szelem + sizeof *desc))) { |
| nuclear@1 | 22 return 0; |
| nuclear@1 | 23 } |
| nuclear@1 | 24 desc->nelem = desc->max_elem = elem; |
| nuclear@1 | 25 desc->szelem = szelem; |
| nuclear@1 | 26 desc->bufsz = elem * szelem; |
| nuclear@1 | 27 return (char*)desc + sizeof *desc; |
| nuclear@1 | 28 } |
| nuclear@1 | 29 |
| nuclear@1 | 30 void dynarr_free(void *da) |
| nuclear@1 | 31 { |
| nuclear@1 | 32 if(da) { |
| nuclear@1 | 33 free(DESC(da)); |
| nuclear@1 | 34 } |
| nuclear@1 | 35 } |
| nuclear@1 | 36 |
| nuclear@1 | 37 void *dynarr_resize(void *da, int elem) |
| nuclear@1 | 38 { |
| nuclear@1 | 39 int newsz; |
| nuclear@1 | 40 void *tmp; |
| nuclear@1 | 41 struct arrdesc *desc; |
| nuclear@1 | 42 |
| nuclear@1 | 43 if(!da) return 0; |
| nuclear@1 | 44 desc = DESC(da); |
| nuclear@1 | 45 |
| nuclear@1 | 46 newsz = desc->szelem * elem; |
| nuclear@1 | 47 |
| nuclear@1 | 48 if(!(tmp = realloc(desc, newsz + sizeof *desc))) { |
| nuclear@1 | 49 return 0; |
| nuclear@1 | 50 } |
| nuclear@1 | 51 desc = tmp; |
| nuclear@1 | 52 |
| nuclear@1 | 53 desc->nelem = desc->max_elem = elem; |
| nuclear@1 | 54 desc->bufsz = newsz; |
| nuclear@1 | 55 return (char*)desc + sizeof *desc; |
| nuclear@1 | 56 } |
| nuclear@1 | 57 |
| nuclear@1 | 58 int dynarr_empty(void *da) |
| nuclear@1 | 59 { |
| nuclear@1 | 60 return DESC(da)->nelem ? 0 : 1; |
| nuclear@1 | 61 } |
| nuclear@1 | 62 |
| nuclear@1 | 63 int dynarr_size(void *da) |
| nuclear@1 | 64 { |
| nuclear@1 | 65 return DESC(da)->nelem; |
| nuclear@1 | 66 } |
| nuclear@1 | 67 |
| nuclear@1 | 68 |
| nuclear@1 | 69 /* stack semantics */ |
| nuclear@1 | 70 void *dynarr_push(void *da, void *item) |
| nuclear@1 | 71 { |
| nuclear@1 | 72 struct arrdesc *desc; |
| nuclear@1 | 73 int nelem; |
| nuclear@1 | 74 |
| nuclear@1 | 75 desc = DESC(da); |
| nuclear@1 | 76 nelem = desc->nelem; |
| nuclear@1 | 77 |
| nuclear@1 | 78 if(nelem >= desc->max_elem) { |
| nuclear@1 | 79 /* need to resize */ |
| nuclear@1 | 80 struct arrdesc *tmp; |
| nuclear@1 | 81 int newsz = desc->max_elem ? desc->max_elem * 2 : 1; |
| nuclear@1 | 82 |
| nuclear@1 | 83 if(!(tmp = dynarr_resize(da, newsz))) { |
| nuclear@1 | 84 fprintf(stderr, "failed to resize\n"); |
| nuclear@1 | 85 return da; |
| nuclear@1 | 86 } |
| nuclear@1 | 87 da = tmp; |
| nuclear@1 | 88 desc = DESC(da); |
| nuclear@1 | 89 desc->nelem = nelem; |
| nuclear@1 | 90 } |
| nuclear@1 | 91 |
| nuclear@1 | 92 memcpy((char*)da + desc->nelem++ * desc->szelem, item, desc->szelem); |
| nuclear@1 | 93 return da; |
| nuclear@1 | 94 } |
| nuclear@1 | 95 |
| nuclear@1 | 96 void *dynarr_pop(void *da) |
| nuclear@1 | 97 { |
| nuclear@1 | 98 struct arrdesc *desc; |
| nuclear@1 | 99 int nelem; |
| nuclear@1 | 100 |
| nuclear@1 | 101 desc = DESC(da); |
| nuclear@1 | 102 nelem = desc->nelem; |
| nuclear@1 | 103 |
| nuclear@1 | 104 if(!nelem) return da; |
| nuclear@1 | 105 |
| nuclear@1 | 106 if(nelem <= desc->max_elem / 3) { |
| nuclear@1 | 107 /* reclaim space */ |
| nuclear@1 | 108 struct arrdesc *tmp; |
| nuclear@1 | 109 int newsz = desc->max_elem / 2; |
| nuclear@1 | 110 |
| nuclear@1 | 111 if(!(tmp = dynarr_resize(da, newsz))) { |
| nuclear@1 | 112 fprintf(stderr, "failed to resize\n"); |
| nuclear@1 | 113 return da; |
| nuclear@1 | 114 } |
| nuclear@1 | 115 da = tmp; |
| nuclear@1 | 116 desc = DESC(da); |
| nuclear@1 | 117 desc->nelem = nelem; |
| nuclear@1 | 118 } |
| nuclear@1 | 119 desc->nelem--; |
| nuclear@1 | 120 |
| nuclear@1 | 121 return da; |
| nuclear@1 | 122 } |