libresman

view src/dynarr.c @ 5:bd9b4ff19c93

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