26 #include <string.h> |
26 #include <string.h> |
27 |
27 |
28 #define MIN_VECTOR_CAPACITY 16 |
28 #define MIN_VECTOR_CAPACITY 16 |
29 |
29 |
30 struct _flib_vector { |
30 struct _flib_vector { |
31 void *data; |
31 void *data; |
32 size_t size; |
32 size_t size; |
33 size_t capacity; |
33 size_t capacity; |
34 }; |
34 }; |
35 |
35 |
36 flib_vector *flib_vector_create() { |
36 flib_vector *flib_vector_create() { |
37 flib_vector *result = NULL; |
37 flib_vector *result = NULL; |
38 flib_vector *tmpVector = flib_calloc(1, sizeof(flib_vector)); |
38 flib_vector *tmpVector = flib_calloc(1, sizeof(flib_vector)); |
39 if(tmpVector) { |
39 if(tmpVector) { |
40 tmpVector->data = flib_malloc(MIN_VECTOR_CAPACITY); |
40 tmpVector->data = flib_malloc(MIN_VECTOR_CAPACITY); |
41 if(tmpVector->data) { |
41 if(tmpVector->data) { |
42 tmpVector->size = 0; |
42 tmpVector->size = 0; |
43 tmpVector->capacity = MIN_VECTOR_CAPACITY; |
43 tmpVector->capacity = MIN_VECTOR_CAPACITY; |
44 result = tmpVector; |
44 result = tmpVector; |
45 tmpVector = NULL; |
45 tmpVector = NULL; |
46 } |
46 } |
47 } |
47 } |
48 flib_vector_destroy(tmpVector); |
48 flib_vector_destroy(tmpVector); |
49 return result; |
49 return result; |
50 } |
50 } |
51 |
51 |
52 void flib_vector_destroy(flib_vector *vec) { |
52 void flib_vector_destroy(flib_vector *vec) { |
53 if(vec) { |
53 if(vec) { |
54 free(vec->data); |
54 free(vec->data); |
55 free(vec); |
55 free(vec); |
56 } |
56 } |
57 } |
57 } |
58 |
58 |
59 static int setCapacity(flib_vector *vec, size_t newCapacity) { |
59 static int setCapacity(flib_vector *vec, size_t newCapacity) { |
60 if(newCapacity == vec->capacity) { |
60 if(newCapacity == vec->capacity) { |
61 return 0; |
61 return 0; |
62 } |
62 } |
63 void *newData = realloc(vec->data, newCapacity); |
63 void *newData = realloc(vec->data, newCapacity); |
64 if(newData) { |
64 if(newData) { |
65 vec->data = newData; |
65 vec->data = newData; |
66 vec->capacity = newCapacity; |
66 vec->capacity = newCapacity; |
67 return 0; |
67 return 0; |
68 } else { |
68 } else { |
69 return -1; |
69 return -1; |
70 } |
70 } |
71 } |
71 } |
72 |
72 |
73 static int allocateExtraCapacity(flib_vector *vec, size_t extraCapacity) { |
73 static int allocateExtraCapacity(flib_vector *vec, size_t extraCapacity) { |
74 if(extraCapacity <= SIZE_MAX - vec->capacity) { |
74 if(extraCapacity <= SIZE_MAX - vec->capacity) { |
75 return setCapacity(vec, vec->capacity + extraCapacity); |
75 return setCapacity(vec, vec->capacity + extraCapacity); |
76 } else { |
76 } else { |
77 return -1; |
77 return -1; |
78 } |
78 } |
79 } |
79 } |
80 |
80 |
81 int flib_vector_resize(flib_vector *vec, size_t newSize) { |
81 int flib_vector_resize(flib_vector *vec, size_t newSize) { |
82 if(log_badargs_if(vec==NULL)) { |
82 if(log_badargs_if(vec==NULL)) { |
83 return -1; |
83 return -1; |
84 } |
84 } |
85 |
85 |
86 if(vec->capacity < newSize) { |
86 if(vec->capacity < newSize) { |
87 // Resize exponentially for constant amortized time, |
87 // Resize exponentially for constant amortized time, |
88 // But at least by as much as we need of course |
88 // But at least by as much as we need of course |
89 size_t extraCapacity = (vec->capacity)/2; |
89 size_t extraCapacity = (vec->capacity)/2; |
90 size_t minExtraCapacity = newSize - vec->capacity; |
90 size_t minExtraCapacity = newSize - vec->capacity; |
91 if(extraCapacity < minExtraCapacity) { |
91 if(extraCapacity < minExtraCapacity) { |
92 extraCapacity = minExtraCapacity; |
92 extraCapacity = minExtraCapacity; |
93 } |
93 } |
94 |
94 |
95 if(allocateExtraCapacity(vec, extraCapacity)) { |
95 if(allocateExtraCapacity(vec, extraCapacity)) { |
96 allocateExtraCapacity(vec, minExtraCapacity); |
96 allocateExtraCapacity(vec, minExtraCapacity); |
97 } |
97 } |
98 } else if(vec->capacity/2 > newSize) { |
98 } else if(vec->capacity/2 > newSize) { |
99 size_t newCapacity = newSize+newSize/4; |
99 size_t newCapacity = newSize+newSize/4; |
100 if(newCapacity < MIN_VECTOR_CAPACITY) { |
100 if(newCapacity < MIN_VECTOR_CAPACITY) { |
101 newCapacity = MIN_VECTOR_CAPACITY; |
101 newCapacity = MIN_VECTOR_CAPACITY; |
102 } |
102 } |
103 setCapacity(vec, newCapacity); |
103 setCapacity(vec, newCapacity); |
104 } |
104 } |
105 |
105 |
106 if(vec->capacity >= newSize) { |
106 if(vec->capacity >= newSize) { |
107 vec->size = newSize; |
107 vec->size = newSize; |
108 return 0; |
108 return 0; |
109 } else { |
109 } else { |
110 return -1; |
110 return -1; |
111 } |
111 } |
112 } |
112 } |
113 |
113 |
114 int flib_vector_append(flib_vector *vec, const void *data, size_t len) { |
114 int flib_vector_append(flib_vector *vec, const void *data, size_t len) { |
115 if(!log_badargs_if2(vec==NULL, data==NULL && len>0) |
115 if(!log_badargs_if2(vec==NULL, data==NULL && len>0) |
116 && !log_oom_if(len > SIZE_MAX-vec->size)) { |
116 && !log_oom_if(len > SIZE_MAX-vec->size)) { |
117 size_t oldSize = vec->size; |
117 size_t oldSize = vec->size; |
118 if(!log_oom_if(flib_vector_resize(vec, vec->size+len))) { |
118 if(!log_oom_if(flib_vector_resize(vec, vec->size+len))) { |
119 memmove(((uint8_t*)vec->data) + oldSize, data, len); |
119 memmove(((uint8_t*)vec->data) + oldSize, data, len); |
120 return 0; |
120 return 0; |
121 } |
121 } |
122 } |
122 } |
123 return -1; |
123 return -1; |
124 } |
124 } |
125 |
125 |
126 int flib_vector_appendf(flib_vector *vec, const char *fmt, ...) { |
126 int flib_vector_appendf(flib_vector *vec, const char *fmt, ...) { |
127 int result = -1; |
127 int result = -1; |
128 if(!log_badargs_if2(vec==NULL, fmt==NULL)) { |
128 if(!log_badargs_if2(vec==NULL, fmt==NULL)) { |
129 va_list argp; |
129 va_list argp; |
130 va_start(argp, fmt); |
130 va_start(argp, fmt); |
131 char *formatted = flib_vasprintf(fmt, argp); |
131 char *formatted = flib_vasprintf(fmt, argp); |
132 va_end(argp); |
132 va_end(argp); |
133 |
133 |
134 |
134 |
135 if(formatted) { |
135 if(formatted) { |
136 size_t len = strlen(formatted); |
136 size_t len = strlen(formatted); |
137 result = flib_vector_append(vec, formatted, len); |
137 result = flib_vector_append(vec, formatted, len); |
138 } |
138 } |
139 } |
139 } |
140 return result; |
140 return result; |
141 } |
141 } |
142 |
142 |
143 flib_buffer flib_vector_as_buffer(flib_vector *vec) { |
143 flib_buffer flib_vector_as_buffer(flib_vector *vec) { |
144 if(log_badargs_if(vec==NULL)) { |
144 if(log_badargs_if(vec==NULL)) { |
145 flib_buffer result = {NULL, 0}; |
145 flib_buffer result = {NULL, 0}; |
146 return result; |
146 return result; |
147 } else { |
147 } else { |
148 flib_buffer result = {vec->data, vec->size}; |
148 flib_buffer result = {vec->data, vec->size}; |
149 return result; |
149 return result; |
150 } |
150 } |
151 } |
151 } |
152 |
152 |
153 flib_constbuffer flib_vector_as_constbuffer(flib_vector *vec) { |
153 flib_constbuffer flib_vector_as_constbuffer(flib_vector *vec) { |
154 if(log_badargs_if(vec==NULL)) { |
154 if(log_badargs_if(vec==NULL)) { |
155 flib_constbuffer result = {NULL, 0}; |
155 flib_constbuffer result = {NULL, 0}; |
156 return result; |
156 return result; |
157 } else { |
157 } else { |
158 flib_constbuffer result = {vec->data, vec->size}; |
158 flib_constbuffer result = {vec->data, vec->size}; |
159 return result; |
159 return result; |
160 } |
160 } |
161 } |
161 } |
162 |
162 |
163 void *flib_vector_data(flib_vector *vec) { |
163 void *flib_vector_data(flib_vector *vec) { |
164 if(log_badargs_if(vec==NULL)) { |
164 if(log_badargs_if(vec==NULL)) { |
165 return NULL; |
165 return NULL; |
166 } else { |
166 } else { |
167 return vec->data; |
167 return vec->data; |
168 } |
168 } |
169 } |
169 } |
170 |
170 |
171 size_t flib_vector_size(flib_vector *vec) { |
171 size_t flib_vector_size(flib_vector *vec) { |
172 if(log_badargs_if(vec==NULL)) { |
172 if(log_badargs_if(vec==NULL)) { |
173 return 0; |
173 return 0; |
174 } else { |
174 } else { |
175 return vec->size; |
175 return vec->size; |
176 } |
176 } |
177 } |
177 } |