Mercurial > hg > ucx / file comparison

comparison: src/array_list.c

src/array_list.c

changeset 628
1e2be40f0cb5
parent 627
cc8cbabd27cd
child 629
6c81ee4f11ad
equal deleted inserted replaced
627:cc8cbabd27cd 628:1e2be40f0cb5
29 #include "cx/array_list.h" 29 #include "cx/array_list.h"
30 #include <assert.h> 30 #include <assert.h>
31 #include <string.h> 31 #include <string.h>
32 #include <stdint.h> 32 #include <stdint.h>
33 33
34 /* LOW LEVEL ARRAY LIST FUNCTIONS */ 34 // LOW LEVEL ARRAY LIST FUNCTIONS
35 35
36 enum cx_array_copy_result cx_array_copy( 36 enum cx_array_copy_result cx_array_copy(
37 void **target, 37 void **target,
38 size_t *size, 38 size_t *size,
39 size_t *capacity, 39 size_t *capacity,
41 void const *src, 41 void const *src,
42 size_t elem_size, 42 size_t elem_size,
43 size_t elem_count, 43 size_t elem_count,
44 struct cx_array_reallocator_s *reallocator 44 struct cx_array_reallocator_s *reallocator
45 ) { 45 ) {
46 /* assert pointers */ 46 // assert pointers
47 assert(target != NULL); 47 assert(target != NULL);
48 assert(size != NULL); 48 assert(size != NULL);
49 assert(src != NULL); 49 assert(src != NULL);
50 50
51 /* determine capacity */ 51 // determine capacity
52 size_t cap = capacity == NULL ? *size : *capacity; 52 size_t cap = capacity == NULL ? *size : *capacity;
53 53
54 /* check if resize is required */ 54 // check if resize is required
55 size_t minsize = index + elem_count; 55 size_t minsize = index + elem_count;
56 size_t newsize = *size < minsize ? minsize : *size; 56 size_t newsize = *size < minsize ? minsize : *size;
57 bool needrealloc = newsize > cap; 57 bool needrealloc = newsize > cap;
58 58
59 /* reallocate if possible */ 59 // reallocate if possible
60 if (needrealloc) { 60 if (needrealloc) {
61 /* a reallocator and a capacity variable must be available */ 61 // a reallocator and a capacity variable must be available
62 if (reallocator == NULL || capacity == NULL) { 62 if (reallocator == NULL || capacity == NULL) {
63 return CX_ARRAY_COPY_REALLOC_NOT_SUPPORTED; 63 return CX_ARRAY_COPY_REALLOC_NOT_SUPPORTED;
64 } 64 }
65 65
66 /* check, if we need to repair the src pointer */ 66 // check, if we need to repair the src pointer
67 uintptr_t targetaddr = (uintptr_t) *target; 67 uintptr_t targetaddr = (uintptr_t) *target;
68 uintptr_t srcaddr = (uintptr_t) src; 68 uintptr_t srcaddr = (uintptr_t) src;
69 bool repairsrc = targetaddr <= srcaddr 69 bool repairsrc = targetaddr <= srcaddr
70 && srcaddr < targetaddr + cap * elem_size; 70 && srcaddr < targetaddr + cap * elem_size;
71 71
72 /* calculate new capacity (next number divisible by 16) */ 72 // calculate new capacity (next number divisible by 16)
73 cap = newsize - (newsize % 16) + 16; 73 cap = newsize - (newsize % 16) + 16;
74 assert(cap > newsize); 74 assert(cap > newsize);
75 75
76 /* perform reallocation */ 76 // perform reallocation
77 void *newmem = reallocator->realloc( 77 void *newmem = reallocator->realloc(
78 *target, cap, elem_size, reallocator 78 *target, cap, elem_size, reallocator
79 ); 79 );
80 if (newmem == NULL) { 80 if (newmem == NULL) {
81 return CX_ARRAY_COPY_REALLOC_FAILED; 81 return CX_ARRAY_COPY_REALLOC_FAILED;
82 } 82 }
83 83
84 /* repair src pointer, if necessary */ 84 // repair src pointer, if necessary
85 if (repairsrc) { 85 if (repairsrc) {
86 src = ((char *) newmem) + (srcaddr - targetaddr); 86 src = ((char *) newmem) + (srcaddr - targetaddr);
87 } 87 }
88 88
89 /* store new pointer and capacity */ 89 // store new pointer and capacity
90 *target = newmem; 90 *target = newmem;
91 *capacity = cap; 91 *capacity = cap;
92 } 92 }
93 93
94 /* determine target pointer */ 94 // determine target pointer
95 char *start = *target; 95 char *start = *target;
96 start += index * elem_size; 96 start += index * elem_size;
97 97
98 /* copy elements and set new size */ 98 // copy elements and set new size
99 memmove(start, src, elem_count * elem_size); 99 memmove(start, src, elem_count * elem_size);
100 *size = newsize; 100 *size = newsize;
101 101
102 /* return successfully */ 102 // return successfully
103 return CX_ARRAY_COPY_SUCCESS; 103 return CX_ARRAY_COPY_SUCCESS;
104 } 104 }
105 105
106 #define CX_ARRAY_SWAP_SBO_SIZE 512 106 #define CX_ARRAY_SWAP_SBO_SIZE 512
107 107
109 void *arr, 109 void *arr,
110 size_t elem_size, 110 size_t elem_size,
111 size_t idx1, 111 size_t idx1,
112 size_t idx2 112 size_t idx2
113 ) { 113 ) {
114 /* short circuit */ 114 // short circuit
115 if (idx1 == idx2) return; 115 if (idx1 == idx2) return;
116 116
117 char sbo_mem[CX_ARRAY_SWAP_SBO_SIZE]; 117 char sbo_mem[CX_ARRAY_SWAP_SBO_SIZE];
118 void *tmp; 118 void *tmp;
119 119
120 /* decide if we can use the local buffer */ 120 // decide if we can use the local buffer
121 if (elem_size > CX_ARRAY_SWAP_SBO_SIZE) { 121 if (elem_size > CX_ARRAY_SWAP_SBO_SIZE) {
122 tmp = malloc(elem_size); 122 tmp = malloc(elem_size);
123 /* we don't want to enforce error handling */ 123 // we don't want to enforce error handling
124 if (tmp == NULL) abort(); 124 if (tmp == NULL) abort();
125 } else { 125 } else {
126 tmp = sbo_mem; 126 tmp = sbo_mem;
127 } 127 }
128 128
129 /* calculate memory locations */ 129 // calculate memory locations
130 char *left = arr, *right = arr; 130 char *left = arr, *right = arr;
131 left += idx1 * elem_size; 131 left += idx1 * elem_size;
132 right += idx2 * elem_size; 132 right += idx2 * elem_size;
133 133
134 /* three-way swap */ 134 // three-way swap
135 memcpy(tmp, left, elem_size); 135 memcpy(tmp, left, elem_size);
136 memcpy(left, right, elem_size); 136 memcpy(left, right, elem_size);
137 memcpy(right, tmp, elem_size); 137 memcpy(right, tmp, elem_size);
138 138
139 /* free dynamic memory, if it was needed */ 139 // free dynamic memory, if it was needed
140 if (tmp != sbo_mem) { 140 if (tmp != sbo_mem) {
141 free(tmp); 141 free(tmp);
142 } 142 }
143 } 143 }
144 144
145 /* HIGH LEVEL ARRAY LIST FUNCTIONS */ 145 // HIGH LEVEL ARRAY LIST FUNCTIONS
146 146
147 typedef struct { 147 typedef struct {
148 struct cx_list_s base; 148 struct cx_list_s base;
149 void *data; 149 void *data;
150 struct cx_array_reallocator_s reallocator; 150 struct cx_array_reallocator_s reallocator;
154 void *array, 154 void *array,
155 size_t capacity, 155 size_t capacity,
156 size_t elem_size, 156 size_t elem_size,
157 struct cx_array_reallocator_s *alloc 157 struct cx_array_reallocator_s *alloc
158 ) { 158 ) {
159 /* retrieve the pointer to the list allocator */ 159 // retrieve the pointer to the list allocator
160 CxAllocator const *al = alloc->ptr1; 160 CxAllocator const *al = alloc->ptr1;
161 161
162 /* use the list allocator to reallocate the memory */ 162 // use the list allocator to reallocate the memory
163 return cxRealloc(al, array, capacity * elem_size); 163 return cxRealloc(al, array, capacity * elem_size);
164 } 164 }
165 165
166 static void cx_arl_destructor(struct cx_list_s *list) { 166 static void cx_arl_destructor(struct cx_list_s *list) {
167 cx_array_list *arl = (cx_array_list *) list; 167 cx_array_list *arl = (cx_array_list *) list;
195 } else if (index == list->size) { 195 } else if (index == list->size) {
196 return cx_arl_add(list, elem); 196 return cx_arl_add(list, elem);
197 } else { 197 } else {
198 cx_array_list *arl = (cx_array_list *) list; 198 cx_array_list *arl = (cx_array_list *) list;
199 199
200 /* move elements starting at index to the right */ 200 // move elements starting at index to the right
201 if (cx_array_copy( 201 if (cx_array_copy(
202 &arl->data, 202 &arl->data,
203 &list->size, 203 &list->size,
204 &list->capacity, 204 &list->capacity,
205 index + 1, 205 index + 1,
209 &arl->reallocator 209 &arl->reallocator
210 )) { 210 )) {
211 return 1; 211 return 1;
212 } 212 }
213 213
214 /* place the element */ 214 // place the element
215 memcpy(((char *) arl->data) + index * list->itemsize, 215 memcpy(((char *) arl->data) + index * list->itemsize,
216 elem, list->itemsize); 216 elem, list->itemsize);
217 217
218 return 0; 218 return 0;
219 } 219 }
245 245
246 static int cx_arl_remove( 246 static int cx_arl_remove(
247 struct cx_list_s *list, 247 struct cx_list_s *list,
248 size_t index 248 size_t index
249 ) { 249 ) {
250 /* out-of-bounds check */ 250 // out-of-bounds check
251 if (index >= list->size) { 251 if (index >= list->size) {
252 return 1; 252 return 1;
253 } 253 }
254 254
255 /* short-circuit removal of last element */ 255 // short-circuit removal of last element
256 if (index == list->size - 1) { 256 if (index == list->size - 1) {
257 list->size--; 257 list->size--;
258 return 0; 258 return 0;
259 } 259 }
260 260
261 /* just move the elements starting at index to the left */ 261 // just move the elements starting at index to the left
262 cx_array_list *arl = (cx_array_list *) list; 262 cx_array_list *arl = (cx_array_list *) list;
263 int result = cx_array_copy( 263 int result = cx_array_copy(
264 &arl->data, 264 &arl->data,
265 &list->size, 265 &list->size,
266 &list->capacity, 266 &list->capacity,
269 list->itemsize, 269 list->itemsize,
270 list->size - index - 1, 270 list->size - index - 1,
271 &arl->reallocator 271 &arl->reallocator
272 ); 272 );
273 if (result == 0) { 273 if (result == 0) {
274 /* decrease the size */ 274 // decrease the size
275 list->size--; 275 list->size--;
276 } 276 }
277 return result; 277 return result;
278 } 278 }
279 279
415 list->base.allocator = allocator; 415 list->base.allocator = allocator;
416 list->base.cmpfunc = comparator; 416 list->base.cmpfunc = comparator;
417 list->base.itemsize = item_size; 417 list->base.itemsize = item_size;
418 list->base.capacity = initial_capacity; 418 list->base.capacity = initial_capacity;
419 419
420 /* configure the reallocator */ 420 // configure the reallocator
421 list->reallocator.realloc = cx_arl_realloc; 421 list->reallocator.realloc = cx_arl_realloc;
422 list->reallocator.ptr1 = (void *) allocator; 422 list->reallocator.ptr1 = (void *) allocator;
423 423
424 return (CxList *) list; 424 return (CxList *) list;
425 } 425 }

Mercurial Repository: ucx

mercurial