Mercurial > hg > ucx / file comparison

comparison: src/array_list.c

src/array_list.c

changeset 998
bb196054f3fd
parent 995
d3d4f245b843
child 999
84fc42b04d3b
equal deleted inserted replaced
997:d14f3d5f47d1 998:bb196054f3fd
28 28
29 #include "cx/array_list.h" 29 #include "cx/array_list.h"
30 #include "cx/compare.h" 30 #include "cx/compare.h"
31 #include <assert.h> 31 #include <assert.h>
32 #include <string.h> 32 #include <string.h>
33 #include <errno.h>
33 34
34 // Default array reallocator 35 // Default array reallocator
35 36
36 static void *cx_array_default_realloc( 37 static void *cx_array_default_realloc(
37 void *array, 38 void *array,
88 89
89 // LOW LEVEL ARRAY LIST FUNCTIONS 90 // LOW LEVEL ARRAY LIST FUNCTIONS
90 91
91 int cx_array_copy( 92 int cx_array_copy(
92 void **target, 93 void **target,
93 size_t *size, 94 void *size,
94 size_t *capacity, 95 void *capacity,
96 unsigned width,
95 size_t index, 97 size_t index,
96 const void *src, 98 const void *src,
97 size_t elem_size, 99 size_t elem_size,
98 size_t elem_count, 100 size_t elem_count,
99 CxArrayReallocator *reallocator 101 CxArrayReallocator *reallocator
103 assert(size != NULL); 105 assert(size != NULL);
104 assert(capacity != NULL); 106 assert(capacity != NULL);
105 assert(src != NULL); 107 assert(src != NULL);
106 assert(reallocator != NULL); 108 assert(reallocator != NULL);
107 109
108 // determine capacity 110 // determine size and capacity
109 size_t cap = *capacity; 111 size_t oldcap;
110 assert(*target != NULL || cap == 0); 112 size_t oldsize;
113 size_t max_size;
114 if (width == 0 || width == __WORDSIZE) {
115 oldcap = *(size_t*) capacity;
116 oldsize = *(size_t*) size;
117 max_size = SIZE_MAX;
118 } else if (width == 16) {
119 oldcap = *(uint16_t*) capacity;
120 oldsize = *(uint16_t*) size;
121 max_size = UINT16_MAX;
122 } else if (width == 8) {
123 oldcap = *(uint8_t*) capacity;
124 oldsize = *(uint8_t*) size;
125 max_size = UINT8_MAX;
126 }
127 #if __WORDSIZE == 64
128 else if (width == 32) {
129 oldcap = *(uint32_t*) capacity;
130 oldsize = *(uint32_t*) size;
131 max_size = UINT32_MAX;
132 }
133 #endif
134 else {
135 errno = EINVAL;
136 return 1;
137 }
138
139 // assert that the array is allocated when it has capacity
140 assert(*target != NULL || oldcap == 0);
111 141
112 // check if resize is required 142 // check if resize is required
113 size_t minsize = index + elem_count; 143 size_t minsize = index + elem_count;
114 size_t newsize = *size < minsize ? minsize : *size; 144 size_t newsize = oldsize < minsize ? minsize : oldsize;
145
146 // check for overflow
147 if (newsize > max_size) {
148 errno = EOVERFLOW;
149 return 1;
150 }
115 151
116 // reallocate if possible 152 // reallocate if possible
117 if (newsize > cap) { 153 size_t newcap = oldcap;
154 if (newsize > oldcap) {
118 // check, if we need to repair the src pointer 155 // check, if we need to repair the src pointer
119 uintptr_t targetaddr = (uintptr_t) *target; 156 uintptr_t targetaddr = (uintptr_t) *target;
120 uintptr_t srcaddr = (uintptr_t) src; 157 uintptr_t srcaddr = (uintptr_t) src;
121 bool repairsrc = targetaddr <= srcaddr 158 bool repairsrc = targetaddr <= srcaddr
122 && srcaddr < targetaddr + cap * elem_size; 159 && srcaddr < targetaddr + oldcap * elem_size;
123 160
124 // calculate new capacity (next number divisible by 16) 161 // calculate new capacity (next number divisible by 16)
125 cap = newsize - (newsize % 16) + 16; 162 newcap = newsize - (newsize % 16) + 16;
126 assert(cap > newsize); 163 assert(newcap > newsize);
127 164
128 // perform reallocation 165 // perform reallocation
129 void *newmem = reallocator->realloc( 166 void *newmem = reallocator->realloc(
130 *target, cap, elem_size, reallocator 167 *target, newcap, elem_size, reallocator
131 ); 168 );
132 if (newmem == NULL) { 169 if (newmem == NULL) {
133 return 1; 170 return 1;
134 } 171 }
135 172
136 // repair src pointer, if necessary 173 // repair src pointer, if necessary
137 if (repairsrc) { 174 if (repairsrc) {
138 src = ((char *) newmem) + (srcaddr - targetaddr); 175 src = ((char *) newmem) + (srcaddr - targetaddr);
139 } 176 }
140 177
141 // store new pointer and capacity 178 // store new pointer
142 *target = newmem; 179 *target = newmem;
143 *capacity = cap;
144 } 180 }
145 181
146 // determine target pointer 182 // determine target pointer
147 char *start = *target; 183 char *start = *target;
148 start += index * elem_size; 184 start += index * elem_size;
149 185
150 // copy elements and set new size 186 // copy elements and set new size
151 memmove(start, src, elem_count * elem_size); 187 memmove(start, src, elem_count * elem_size);
152 *size = newsize; 188
189 // if any of size or capacity changed, store them back
190 if (newsize != oldsize || newcap != oldcap) {
191 if (width == 0 || width == __WORDSIZE) {
192 *(size_t*) capacity = newcap;
193 *(size_t*) size = newsize;
194 } else if (width == 16) {
195 *(uint16_t*) capacity = newcap;
196 *(uint16_t*) size = newsize;
197 } else if (width == 8) {
198 *(uint8_t*) capacity = newcap;
199 *(uint8_t*) size = newsize;
200 }
201 #if __WORDSIZE == 64
202 else if (width == 32) {
203 *(uint32_t*) capacity = newcap;
204 *(uint32_t*) size = newsize;
205 }
206 #endif
207 }
153 208
154 // return successfully 209 // return successfully
155 return 0; 210 return 0;
156 } 211 }
157 212
456 511
457 if (cx_array_copy( 512 if (cx_array_copy(
458 &arl->data, 513 &arl->data,
459 &list->collection.size, 514 &list->collection.size,
460 &arl->capacity, 515 &arl->capacity,
516 0,
461 start_of_moved, 517 start_of_moved,
462 first_to_move, 518 first_to_move,
463 list->collection.elem_size, 519 list->collection.elem_size,
464 elems_to_move, 520 elems_to_move,
465 &arl->reallocator 521 &arl->reallocator
476 // place the new elements 532 // place the new elements
477 if (cx_array_copy( 533 if (cx_array_copy(
478 &arl->data, 534 &arl->data,
479 &list->collection.size, 535 &list->collection.size,
480 &arl->capacity, 536 &arl->capacity,
537 0,
481 index, 538 index,
482 array, 539 array,
483 list->collection.elem_size, 540 list->collection.elem_size,
484 n, 541 n,
485 &arl->reallocator 542 &arl->reallocator
600 // just move the elements to the left 657 // just move the elements to the left
601 int result = cx_array_copy( 658 int result = cx_array_copy(
602 &arl->data, 659 &arl->data,
603 &list->collection.size, 660 &list->collection.size,
604 &arl->capacity, 661 &arl->capacity,
662 0,
605 index, 663 index,
606 ((char *) arl->data) + (index + remove) * list->collection.elem_size, 664 ((char *) arl->data) + (index + remove) * list->collection.elem_size,
607 list->collection.elem_size, 665 list->collection.elem_size,
608 list->collection.size - index - remove, 666 list->collection.size - index - remove,
609 &arl->reallocator 667 &arl->reallocator

Mercurial Repository: ucx

mercurial