src/array_list.c

Fri, 27 Dec 2024 13:01:31 +0100

author
Mike Becker <universe@uap-core.de>
date
Fri, 27 Dec 2024 13:01:31 +0100
changeset 1060
0a7c1bb2372d
parent 1047
40aad3f0bc9e
permissions
-rw-r--r--

avoid copying the filled data in the json parser when possible - fixes #530

606
314e9288af2f add array list tests
Mike Becker <universe@uap-core.de>
parents:
diff changeset
1 /*
314e9288af2f add array list tests
Mike Becker <universe@uap-core.de>
parents:
diff changeset
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
314e9288af2f add array list tests
Mike Becker <universe@uap-core.de>
parents:
diff changeset
3 *
314e9288af2f add array list tests
Mike Becker <universe@uap-core.de>
parents:
diff changeset
4 * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
314e9288af2f add array list tests
Mike Becker <universe@uap-core.de>
parents:
diff changeset
5 *
314e9288af2f add array list tests
Mike Becker <universe@uap-core.de>
parents:
diff changeset
6 * Redistribution and use in source and binary forms, with or without
314e9288af2f add array list tests
Mike Becker <universe@uap-core.de>
parents:
diff changeset
7 * modification, are permitted provided that the following conditions are met:
314e9288af2f add array list tests
Mike Becker <universe@uap-core.de>
parents:
diff changeset
8 *
314e9288af2f add array list tests
Mike Becker <universe@uap-core.de>
parents:
diff changeset
9 * 1. Redistributions of source code must retain the above copyright
314e9288af2f add array list tests
Mike Becker <universe@uap-core.de>
parents:
diff changeset
10 * notice, this list of conditions and the following disclaimer.
314e9288af2f add array list tests
Mike Becker <universe@uap-core.de>
parents:
diff changeset
11 *
314e9288af2f add array list tests
Mike Becker <universe@uap-core.de>
parents:
diff changeset
12 * 2. Redistributions in binary form must reproduce the above copyright
314e9288af2f add array list tests
Mike Becker <universe@uap-core.de>
parents:
diff changeset
13 * notice, this list of conditions and the following disclaimer in the
314e9288af2f add array list tests
Mike Becker <universe@uap-core.de>
parents:
diff changeset
14 * documentation and/or other materials provided with the distribution.
314e9288af2f add array list tests
Mike Becker <universe@uap-core.de>
parents:
diff changeset
15 *
314e9288af2f add array list tests
Mike Becker <universe@uap-core.de>
parents:
diff changeset
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
314e9288af2f add array list tests
Mike Becker <universe@uap-core.de>
parents:
diff changeset
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
314e9288af2f add array list tests
Mike Becker <universe@uap-core.de>
parents:
diff changeset
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
314e9288af2f add array list tests
Mike Becker <universe@uap-core.de>
parents:
diff changeset
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
314e9288af2f add array list tests
Mike Becker <universe@uap-core.de>
parents:
diff changeset
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
314e9288af2f add array list tests
Mike Becker <universe@uap-core.de>
parents:
diff changeset
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
314e9288af2f add array list tests
Mike Becker <universe@uap-core.de>
parents:
diff changeset
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
314e9288af2f add array list tests
Mike Becker <universe@uap-core.de>
parents:
diff changeset
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
314e9288af2f add array list tests
Mike Becker <universe@uap-core.de>
parents:
diff changeset
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
314e9288af2f add array list tests
Mike Becker <universe@uap-core.de>
parents:
diff changeset
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
314e9288af2f add array list tests
Mike Becker <universe@uap-core.de>
parents:
diff changeset
26 * POSSIBILITY OF SUCH DAMAGE.
314e9288af2f add array list tests
Mike Becker <universe@uap-core.de>
parents:
diff changeset
27 */
314e9288af2f add array list tests
Mike Becker <universe@uap-core.de>
parents:
diff changeset
28
314e9288af2f add array list tests
Mike Becker <universe@uap-core.de>
parents:
diff changeset
29 #include "cx/array_list.h"
763
741a2040fa33 make cx_cmp_ptr default comparator for pointer lists - relates to #340
Mike Becker <universe@uap-core.de>
parents: 735
diff changeset
30 #include "cx/compare.h"
610
de5d3ee6435f #219 array list: implement add and at
Mike Becker <universe@uap-core.de>
parents: 607
diff changeset
31 #include <assert.h>
de5d3ee6435f #219 array list: implement add and at
Mike Becker <universe@uap-core.de>
parents: 607
diff changeset
32 #include <string.h>
998
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
33 #include <errno.h>
606
314e9288af2f add array list tests
Mike Becker <universe@uap-core.de>
parents:
diff changeset
34
817
949908c97474 add cx_array_default_reallocator
Mike Becker <universe@uap-core.de>
parents: 807
diff changeset
35 // Default array reallocator
949908c97474 add cx_array_default_reallocator
Mike Becker <universe@uap-core.de>
parents: 807
diff changeset
36
949908c97474 add cx_array_default_reallocator
Mike Becker <universe@uap-core.de>
parents: 807
diff changeset
37 static void *cx_array_default_realloc(
949908c97474 add cx_array_default_reallocator
Mike Becker <universe@uap-core.de>
parents: 807
diff changeset
38 void *array,
949908c97474 add cx_array_default_reallocator
Mike Becker <universe@uap-core.de>
parents: 807
diff changeset
39 size_t capacity,
949908c97474 add cx_array_default_reallocator
Mike Becker <universe@uap-core.de>
parents: 807
diff changeset
40 size_t elem_size,
985
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 968
diff changeset
41 cx_attr_unused CxArrayReallocator *alloc
817
949908c97474 add cx_array_default_reallocator
Mike Becker <universe@uap-core.de>
parents: 807
diff changeset
42 ) {
1040
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
43 size_t n;
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
44 if (cx_szmul(capacity, elem_size, &n)) {
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
45 errno = EOVERFLOW;
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
46 return NULL;
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
47 }
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
48 return realloc(array, n);
817
949908c97474 add cx_array_default_reallocator
Mike Becker <universe@uap-core.de>
parents: 807
diff changeset
49 }
949908c97474 add cx_array_default_reallocator
Mike Becker <universe@uap-core.de>
parents: 807
diff changeset
50
953
581ad4fd01e9 add function to create array reallocator that can move arrays from stack to heap
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
51 CxArrayReallocator cx_array_default_reallocator_impl = {
817
949908c97474 add cx_array_default_reallocator
Mike Becker <universe@uap-core.de>
parents: 807
diff changeset
52 cx_array_default_realloc, NULL, NULL, 0, 0
949908c97474 add cx_array_default_reallocator
Mike Becker <universe@uap-core.de>
parents: 807
diff changeset
53 };
949908c97474 add cx_array_default_reallocator
Mike Becker <universe@uap-core.de>
parents: 807
diff changeset
54
953
581ad4fd01e9 add function to create array reallocator that can move arrays from stack to heap
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
55 CxArrayReallocator *cx_array_default_reallocator = &cx_array_default_reallocator_impl;
581ad4fd01e9 add function to create array reallocator that can move arrays from stack to heap
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
56
581ad4fd01e9 add function to create array reallocator that can move arrays from stack to heap
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
57 // Stack-aware array reallocator
581ad4fd01e9 add function to create array reallocator that can move arrays from stack to heap
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
58
581ad4fd01e9 add function to create array reallocator that can move arrays from stack to heap
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
59 static void *cx_array_advanced_realloc(
581ad4fd01e9 add function to create array reallocator that can move arrays from stack to heap
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
60 void *array,
581ad4fd01e9 add function to create array reallocator that can move arrays from stack to heap
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
61 size_t capacity,
581ad4fd01e9 add function to create array reallocator that can move arrays from stack to heap
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
62 size_t elem_size,
985
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 968
diff changeset
63 cx_attr_unused CxArrayReallocator *alloc
953
581ad4fd01e9 add function to create array reallocator that can move arrays from stack to heap
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
64 ) {
1040
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
65 // check for overflow
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
66 size_t n;
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
67 if (cx_szmul(capacity, elem_size, &n)) {
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
68 errno = EOVERFLOW;
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
69 return NULL;
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
70 }
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
71
953
581ad4fd01e9 add function to create array reallocator that can move arrays from stack to heap
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
72 // retrieve the pointer to the actual allocator
581ad4fd01e9 add function to create array reallocator that can move arrays from stack to heap
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
73 const CxAllocator *al = alloc->ptr1;
581ad4fd01e9 add function to create array reallocator that can move arrays from stack to heap
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
74
581ad4fd01e9 add function to create array reallocator that can move arrays from stack to heap
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
75 // check if the array is still located on the stack
581ad4fd01e9 add function to create array reallocator that can move arrays from stack to heap
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
76 void *newmem;
581ad4fd01e9 add function to create array reallocator that can move arrays from stack to heap
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
77 if (array == alloc->ptr2) {
1040
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
78 newmem = cxMalloc(al, n);
995
d3d4f245b843 fix cx_array_advanced_realloc to handle reallocation of NULL arrays, consistent with standard realloc behavior
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 986
diff changeset
79 if (newmem != NULL && array != NULL) {
1040
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
80 memcpy(newmem, array, n);
953
581ad4fd01e9 add function to create array reallocator that can move arrays from stack to heap
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
81 }
581ad4fd01e9 add function to create array reallocator that can move arrays from stack to heap
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
82 } else {
1040
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
83 newmem = cxRealloc(al, array, n);
953
581ad4fd01e9 add function to create array reallocator that can move arrays from stack to heap
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
84 }
581ad4fd01e9 add function to create array reallocator that can move arrays from stack to heap
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
85 return newmem;
581ad4fd01e9 add function to create array reallocator that can move arrays from stack to heap
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
86 }
581ad4fd01e9 add function to create array reallocator that can move arrays from stack to heap
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
87
581ad4fd01e9 add function to create array reallocator that can move arrays from stack to heap
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
88 struct cx_array_reallocator_s cx_array_reallocator(
581ad4fd01e9 add function to create array reallocator that can move arrays from stack to heap
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
89 const struct cx_allocator_s *allocator,
581ad4fd01e9 add function to create array reallocator that can move arrays from stack to heap
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
90 const void *stackmem
581ad4fd01e9 add function to create array reallocator that can move arrays from stack to heap
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
91 ) {
581ad4fd01e9 add function to create array reallocator that can move arrays from stack to heap
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
92 if (allocator == NULL) {
581ad4fd01e9 add function to create array reallocator that can move arrays from stack to heap
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
93 allocator = cxDefaultAllocator;
581ad4fd01e9 add function to create array reallocator that can move arrays from stack to heap
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
94 }
581ad4fd01e9 add function to create array reallocator that can move arrays from stack to heap
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
95 return (struct cx_array_reallocator_s) {
581ad4fd01e9 add function to create array reallocator that can move arrays from stack to heap
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
96 cx_array_advanced_realloc,
581ad4fd01e9 add function to create array reallocator that can move arrays from stack to heap
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
97 (void*) allocator, (void*) stackmem,
581ad4fd01e9 add function to create array reallocator that can move arrays from stack to heap
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
98 0, 0
581ad4fd01e9 add function to create array reallocator that can move arrays from stack to heap
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
99 };
581ad4fd01e9 add function to create array reallocator that can move arrays from stack to heap
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
100 }
818
2be8fe3d5a2d add cx_array_add() + fix type of cx_array_default_reallocator
Mike Becker <universe@uap-core.de>
parents: 817
diff changeset
101
628
1e2be40f0cb5 use //-style single line comments everywhere
Mike Becker <universe@uap-core.de>
parents: 627
diff changeset
102 // LOW LEVEL ARRAY LIST FUNCTIONS
607
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
103
1040
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
104 static size_t cx_array_align_capacity(
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
105 size_t cap,
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
106 size_t alignment,
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
107 size_t max
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
108 ) {
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
109 if (cap > max - alignment) {
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
110 return cap;
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
111 } else {
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
112 return cap - (cap % alignment) + alignment;
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
113 }
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
114 }
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
115
999
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
116 int cx_array_reserve(
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
117 void **array,
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
118 void *size,
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
119 void *capacity,
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
120 unsigned width,
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
121 size_t elem_size,
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
122 size_t elem_count,
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
123 CxArrayReallocator *reallocator
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
124 ) {
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
125 // assert pointers
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
126 assert(array != NULL);
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
127 assert(size != NULL);
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
128 assert(capacity != NULL);
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
129 assert(reallocator != NULL);
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
130
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
131 // determine size and capacity
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
132 size_t oldcap;
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
133 size_t oldsize;
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
134 size_t max_size;
1047
40aad3f0bc9e don't trust that size_t always has word width
Mike Becker <universe@uap-core.de>
parents: 1040
diff changeset
135 if (width == 0 || width == 8*sizeof(size_t)) {
999
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
136 oldcap = *(size_t*) capacity;
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
137 oldsize = *(size_t*) size;
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
138 max_size = SIZE_MAX;
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
139 } else if (width == 16) {
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
140 oldcap = *(uint16_t*) capacity;
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
141 oldsize = *(uint16_t*) size;
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
142 max_size = UINT16_MAX;
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
143 } else if (width == 8) {
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
144 oldcap = *(uint8_t*) capacity;
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
145 oldsize = *(uint8_t*) size;
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
146 max_size = UINT8_MAX;
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
147 }
1018
c773da859bad fix compilation for compilers which don't set __WORDSIZE
Mike Becker <universe@uap-core.de>
parents: 999
diff changeset
148 #if CX_WORDSIZE == 64
999
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
149 else if (width == 32) {
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
150 oldcap = *(uint32_t*) capacity;
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
151 oldsize = *(uint32_t*) size;
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
152 max_size = UINT32_MAX;
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
153 }
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
154 #endif
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
155 else {
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
156 errno = EINVAL;
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
157 return 1;
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
158 }
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
159
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
160 // assert that the array is allocated when it has capacity
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
161 assert(*array != NULL || oldcap == 0);
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
162
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
163 // check for overflow
1040
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
164 if (elem_count > max_size - oldsize) {
999
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
165 errno = EOVERFLOW;
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
166 return 1;
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
167 }
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
168
1040
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
169 // determine new capacity
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
170 size_t newcap = oldsize + elem_count;
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
171
999
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
172 // reallocate if possible
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
173 if (newcap > oldcap) {
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
174 // calculate new capacity (next number divisible by 16)
1040
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
175 newcap = cx_array_align_capacity(newcap, 16, max_size);
999
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
176
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
177 // perform reallocation
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
178 void *newmem = reallocator->realloc(
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
179 *array, newcap, elem_size, reallocator
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
180 );
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
181 if (newmem == NULL) {
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
182 return 1;
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
183 }
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
184
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
185 // store new pointer
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
186 *array = newmem;
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
187
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
188 // store new capacity
1047
40aad3f0bc9e don't trust that size_t always has word width
Mike Becker <universe@uap-core.de>
parents: 1040
diff changeset
189 if (width == 0 || width == 8*sizeof(size_t)) {
999
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
190 *(size_t*) capacity = newcap;
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
191 } else if (width == 16) {
1019
09c6fe8fe3b9 add explicit casts to silence warnings
Mike Becker <universe@uap-core.de>
parents: 1018
diff changeset
192 *(uint16_t*) capacity = (uint16_t) newcap;
999
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
193 } else if (width == 8) {
1019
09c6fe8fe3b9 add explicit casts to silence warnings
Mike Becker <universe@uap-core.de>
parents: 1018
diff changeset
194 *(uint8_t*) capacity = (uint8_t) newcap;
999
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
195 }
1018
c773da859bad fix compilation for compilers which don't set __WORDSIZE
Mike Becker <universe@uap-core.de>
parents: 999
diff changeset
196 #if CX_WORDSIZE == 64
999
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
197 else if (width == 32) {
1019
09c6fe8fe3b9 add explicit casts to silence warnings
Mike Becker <universe@uap-core.de>
parents: 1018
diff changeset
198 *(uint32_t*) capacity = (uint32_t) newcap;
999
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
199 }
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
200 #endif
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
201 }
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
202
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
203 return 0;
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
204 }
84fc42b04d3b add cx_array_reserve() and several more array convenience functions
Mike Becker <universe@uap-core.de>
parents: 998
diff changeset
205
986
38fa7e41194c simplify cx_array_copy() - fixes #474
Mike Becker <universe@uap-core.de>
parents: 985
diff changeset
206 int cx_array_copy(
610
de5d3ee6435f #219 array list: implement add and at
Mike Becker <universe@uap-core.de>
parents: 607
diff changeset
207 void **target,
998
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
208 void *size,
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
209 void *capacity,
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
210 unsigned width,
610
de5d3ee6435f #219 array list: implement add and at
Mike Becker <universe@uap-core.de>
parents: 607
diff changeset
211 size_t index,
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 889
diff changeset
212 const void *src,
610
de5d3ee6435f #219 array list: implement add and at
Mike Becker <universe@uap-core.de>
parents: 607
diff changeset
213 size_t elem_size,
de5d3ee6435f #219 array list: implement add and at
Mike Becker <universe@uap-core.de>
parents: 607
diff changeset
214 size_t elem_count,
953
581ad4fd01e9 add function to create array reallocator that can move arrays from stack to heap
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
215 CxArrayReallocator *reallocator
610
de5d3ee6435f #219 array list: implement add and at
Mike Becker <universe@uap-core.de>
parents: 607
diff changeset
216 ) {
628
1e2be40f0cb5 use //-style single line comments everywhere
Mike Becker <universe@uap-core.de>
parents: 627
diff changeset
217 // assert pointers
610
de5d3ee6435f #219 array list: implement add and at
Mike Becker <universe@uap-core.de>
parents: 607
diff changeset
218 assert(target != NULL);
de5d3ee6435f #219 array list: implement add and at
Mike Becker <universe@uap-core.de>
parents: 607
diff changeset
219 assert(size != NULL);
986
38fa7e41194c simplify cx_array_copy() - fixes #474
Mike Becker <universe@uap-core.de>
parents: 985
diff changeset
220 assert(capacity != NULL);
610
de5d3ee6435f #219 array list: implement add and at
Mike Becker <universe@uap-core.de>
parents: 607
diff changeset
221 assert(src != NULL);
986
38fa7e41194c simplify cx_array_copy() - fixes #474
Mike Becker <universe@uap-core.de>
parents: 985
diff changeset
222 assert(reallocator != NULL);
607
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
223
998
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
224 // determine size and capacity
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
225 size_t oldcap;
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
226 size_t oldsize;
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
227 size_t max_size;
1047
40aad3f0bc9e don't trust that size_t always has word width
Mike Becker <universe@uap-core.de>
parents: 1040
diff changeset
228 if (width == 0 || width == 8*sizeof(size_t)) {
998
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
229 oldcap = *(size_t*) capacity;
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
230 oldsize = *(size_t*) size;
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
231 max_size = SIZE_MAX;
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
232 } else if (width == 16) {
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
233 oldcap = *(uint16_t*) capacity;
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
234 oldsize = *(uint16_t*) size;
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
235 max_size = UINT16_MAX;
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
236 } else if (width == 8) {
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
237 oldcap = *(uint8_t*) capacity;
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
238 oldsize = *(uint8_t*) size;
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
239 max_size = UINT8_MAX;
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
240 }
1018
c773da859bad fix compilation for compilers which don't set __WORDSIZE
Mike Becker <universe@uap-core.de>
parents: 999
diff changeset
241 #if CX_WORDSIZE == 64
998
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
242 else if (width == 32) {
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
243 oldcap = *(uint32_t*) capacity;
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
244 oldsize = *(uint32_t*) size;
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
245 max_size = UINT32_MAX;
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
246 }
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
247 #endif
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
248 else {
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
249 errno = EINVAL;
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
250 return 1;
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
251 }
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
252
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
253 // assert that the array is allocated when it has capacity
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
254 assert(*target != NULL || oldcap == 0);
610
de5d3ee6435f #219 array list: implement add and at
Mike Becker <universe@uap-core.de>
parents: 607
diff changeset
255
1040
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
256 // check for overflow
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
257 if (index > max_size || elem_count > max_size - index) {
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
258 errno = EOVERFLOW;
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
259 return 1;
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
260 }
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
261
628
1e2be40f0cb5 use //-style single line comments everywhere
Mike Becker <universe@uap-core.de>
parents: 627
diff changeset
262 // check if resize is required
627
cc8cbabd27cd fix cx_array_copy() unintentionally shrinking the array
Mike Becker <universe@uap-core.de>
parents: 626
diff changeset
263 size_t minsize = index + elem_count;
998
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
264 size_t newsize = oldsize < minsize ? minsize : oldsize;
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
265
628
1e2be40f0cb5 use //-style single line comments everywhere
Mike Becker <universe@uap-core.de>
parents: 627
diff changeset
266 // reallocate if possible
998
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
267 size_t newcap = oldcap;
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
268 if (newsize > oldcap) {
628
1e2be40f0cb5 use //-style single line comments everywhere
Mike Becker <universe@uap-core.de>
parents: 627
diff changeset
269 // check, if we need to repair the src pointer
611
77efa5163ae5 #219 array list: implement insert
Mike Becker <universe@uap-core.de>
parents: 610
diff changeset
270 uintptr_t targetaddr = (uintptr_t) *target;
77efa5163ae5 #219 array list: implement insert
Mike Becker <universe@uap-core.de>
parents: 610
diff changeset
271 uintptr_t srcaddr = (uintptr_t) src;
77efa5163ae5 #219 array list: implement insert
Mike Becker <universe@uap-core.de>
parents: 610
diff changeset
272 bool repairsrc = targetaddr <= srcaddr
998
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
273 && srcaddr < targetaddr + oldcap * elem_size;
611
77efa5163ae5 #219 array list: implement insert
Mike Becker <universe@uap-core.de>
parents: 610
diff changeset
274
628
1e2be40f0cb5 use //-style single line comments everywhere
Mike Becker <universe@uap-core.de>
parents: 627
diff changeset
275 // calculate new capacity (next number divisible by 16)
1040
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
276 newcap = cx_array_align_capacity(newsize, 16, max_size);
998
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
277 assert(newcap > newsize);
610
de5d3ee6435f #219 array list: implement add and at
Mike Becker <universe@uap-core.de>
parents: 607
diff changeset
278
628
1e2be40f0cb5 use //-style single line comments everywhere
Mike Becker <universe@uap-core.de>
parents: 627
diff changeset
279 // perform reallocation
610
de5d3ee6435f #219 array list: implement add and at
Mike Becker <universe@uap-core.de>
parents: 607
diff changeset
280 void *newmem = reallocator->realloc(
998
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
281 *target, newcap, elem_size, reallocator
610
de5d3ee6435f #219 array list: implement add and at
Mike Becker <universe@uap-core.de>
parents: 607
diff changeset
282 );
de5d3ee6435f #219 array list: implement add and at
Mike Becker <universe@uap-core.de>
parents: 607
diff changeset
283 if (newmem == NULL) {
986
38fa7e41194c simplify cx_array_copy() - fixes #474
Mike Becker <universe@uap-core.de>
parents: 985
diff changeset
284 return 1;
610
de5d3ee6435f #219 array list: implement add and at
Mike Becker <universe@uap-core.de>
parents: 607
diff changeset
285 }
de5d3ee6435f #219 array list: implement add and at
Mike Becker <universe@uap-core.de>
parents: 607
diff changeset
286
628
1e2be40f0cb5 use //-style single line comments everywhere
Mike Becker <universe@uap-core.de>
parents: 627
diff changeset
287 // repair src pointer, if necessary
611
77efa5163ae5 #219 array list: implement insert
Mike Becker <universe@uap-core.de>
parents: 610
diff changeset
288 if (repairsrc) {
77efa5163ae5 #219 array list: implement insert
Mike Becker <universe@uap-core.de>
parents: 610
diff changeset
289 src = ((char *) newmem) + (srcaddr - targetaddr);
77efa5163ae5 #219 array list: implement insert
Mike Becker <universe@uap-core.de>
parents: 610
diff changeset
290 }
77efa5163ae5 #219 array list: implement insert
Mike Becker <universe@uap-core.de>
parents: 610
diff changeset
291
998
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
292 // store new pointer
610
de5d3ee6435f #219 array list: implement add and at
Mike Becker <universe@uap-core.de>
parents: 607
diff changeset
293 *target = newmem;
de5d3ee6435f #219 array list: implement add and at
Mike Becker <universe@uap-core.de>
parents: 607
diff changeset
294 }
de5d3ee6435f #219 array list: implement add and at
Mike Becker <universe@uap-core.de>
parents: 607
diff changeset
295
628
1e2be40f0cb5 use //-style single line comments everywhere
Mike Becker <universe@uap-core.de>
parents: 627
diff changeset
296 // determine target pointer
610
de5d3ee6435f #219 array list: implement add and at
Mike Becker <universe@uap-core.de>
parents: 607
diff changeset
297 char *start = *target;
de5d3ee6435f #219 array list: implement add and at
Mike Becker <universe@uap-core.de>
parents: 607
diff changeset
298 start += index * elem_size;
de5d3ee6435f #219 array list: implement add and at
Mike Becker <universe@uap-core.de>
parents: 607
diff changeset
299
628
1e2be40f0cb5 use //-style single line comments everywhere
Mike Becker <universe@uap-core.de>
parents: 627
diff changeset
300 // copy elements and set new size
1040
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
301 // note: no overflow check here, b/c we cannot get here w/o allocation
611
77efa5163ae5 #219 array list: implement insert
Mike Becker <universe@uap-core.de>
parents: 610
diff changeset
302 memmove(start, src, elem_count * elem_size);
998
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
303
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
304 // if any of size or capacity changed, store them back
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
305 if (newsize != oldsize || newcap != oldcap) {
1047
40aad3f0bc9e don't trust that size_t always has word width
Mike Becker <universe@uap-core.de>
parents: 1040
diff changeset
306 if (width == 0 || width == 8*sizeof(size_t)) {
998
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
307 *(size_t*) capacity = newcap;
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
308 *(size_t*) size = newsize;
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
309 } else if (width == 16) {
1019
09c6fe8fe3b9 add explicit casts to silence warnings
Mike Becker <universe@uap-core.de>
parents: 1018
diff changeset
310 *(uint16_t*) capacity = (uint16_t) newcap;
09c6fe8fe3b9 add explicit casts to silence warnings
Mike Becker <universe@uap-core.de>
parents: 1018
diff changeset
311 *(uint16_t*) size = (uint16_t) newsize;
998
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
312 } else if (width == 8) {
1019
09c6fe8fe3b9 add explicit casts to silence warnings
Mike Becker <universe@uap-core.de>
parents: 1018
diff changeset
313 *(uint8_t*) capacity = (uint8_t) newcap;
09c6fe8fe3b9 add explicit casts to silence warnings
Mike Becker <universe@uap-core.de>
parents: 1018
diff changeset
314 *(uint8_t*) size = (uint8_t) newsize;
998
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
315 }
1018
c773da859bad fix compilation for compilers which don't set __WORDSIZE
Mike Becker <universe@uap-core.de>
parents: 999
diff changeset
316 #if CX_WORDSIZE == 64
998
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
317 else if (width == 32) {
1019
09c6fe8fe3b9 add explicit casts to silence warnings
Mike Becker <universe@uap-core.de>
parents: 1018
diff changeset
318 *(uint32_t*) capacity = (uint32_t) newcap;
09c6fe8fe3b9 add explicit casts to silence warnings
Mike Becker <universe@uap-core.de>
parents: 1018
diff changeset
319 *(uint32_t*) size = (uint32_t) newsize;
998
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
320 }
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
321 #endif
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
322 }
610
de5d3ee6435f #219 array list: implement add and at
Mike Becker <universe@uap-core.de>
parents: 607
diff changeset
323
628
1e2be40f0cb5 use //-style single line comments everywhere
Mike Becker <universe@uap-core.de>
parents: 627
diff changeset
324 // return successfully
986
38fa7e41194c simplify cx_array_copy() - fixes #474
Mike Becker <universe@uap-core.de>
parents: 985
diff changeset
325 return 0;
610
de5d3ee6435f #219 array list: implement add and at
Mike Becker <universe@uap-core.de>
parents: 607
diff changeset
326 }
607
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
327
986
38fa7e41194c simplify cx_array_copy() - fixes #474
Mike Becker <universe@uap-core.de>
parents: 985
diff changeset
328 int cx_array_insert_sorted(
883
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
329 void **target,
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
330 size_t *size,
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
331 size_t *capacity,
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
332 cx_compare_func cmp_func,
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 889
diff changeset
333 const void *sorted_data,
883
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
334 size_t elem_size,
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
335 size_t elem_count,
953
581ad4fd01e9 add function to create array reallocator that can move arrays from stack to heap
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
336 CxArrayReallocator *reallocator
883
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
337 ) {
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
338 // assert pointers
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
339 assert(target != NULL);
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
340 assert(size != NULL);
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
341 assert(capacity != NULL);
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
342 assert(cmp_func != NULL);
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
343 assert(sorted_data != NULL);
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
344 assert(reallocator != NULL);
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
345
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
346 // corner case
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
347 if (elem_count == 0) return 0;
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
348
1040
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
349 // overflow check
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
350 if (elem_count > SIZE_MAX - *size) {
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
351 errno = EOVERFLOW;
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
352 return 1;
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
353 }
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
354
883
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
355 // store some counts
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
356 size_t old_size = *size;
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
357 size_t needed_capacity = old_size + elem_count;
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
358
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
359 // if we need more than we have, try a reallocation
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
360 if (needed_capacity > *capacity) {
1040
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 1022
diff changeset
361 size_t new_capacity = cx_array_align_capacity(needed_capacity, 16, SIZE_MAX);
883
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
362 void *new_mem = reallocator->realloc(
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
363 *target, new_capacity, elem_size, reallocator
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
364 );
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
365 if (new_mem == NULL) {
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
366 // give it up right away, there is no contract
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
367 // that requires us to insert as much as we can
986
38fa7e41194c simplify cx_array_copy() - fixes #474
Mike Becker <universe@uap-core.de>
parents: 985
diff changeset
368 return 1;
883
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
369 }
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
370 *target = new_mem;
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
371 *capacity = new_capacity;
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
372 }
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
373
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
374 // now we have guaranteed that we can insert everything
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
375 size_t new_size = old_size + elem_count;
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
376 *size = new_size;
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
377
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
378 // declare the source and destination indices/pointers
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
379 size_t si = 0, di = 0;
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 889
diff changeset
380 const char *src = sorted_data;
883
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
381 char *dest = *target;
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
382
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
383 // find the first insertion point
889
f549fd9fbd8f apply binary search in cx_array_insert_sorted()
Mike Becker <universe@uap-core.de>
parents: 888
diff changeset
384 di = cx_array_binary_search_sup(dest, old_size, elem_size, src, cmp_func);
f549fd9fbd8f apply binary search in cx_array_insert_sorted()
Mike Becker <universe@uap-core.de>
parents: 888
diff changeset
385 dest += di * elem_size;
883
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
386
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
387 // move the remaining elements in the array completely to the right
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
388 // we will call it the "buffer" for parked elements
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
389 size_t buf_size = old_size - di;
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
390 size_t bi = new_size - buf_size;
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
391 char *bptr = ((char *) *target) + bi * elem_size;
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
392 memmove(bptr, dest, buf_size * elem_size);
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
393
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
394 // while there are both source and buffered elements left,
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
395 // copy them interleaving
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
396 while (si < elem_count && bi < new_size) {
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
397 // determine how many source elements can be inserted
889
f549fd9fbd8f apply binary search in cx_array_insert_sorted()
Mike Becker <universe@uap-core.de>
parents: 888
diff changeset
398 size_t copy_len, bytes_copied;
f549fd9fbd8f apply binary search in cx_array_insert_sorted()
Mike Becker <universe@uap-core.de>
parents: 888
diff changeset
399 copy_len = cx_array_binary_search_sup(
f549fd9fbd8f apply binary search in cx_array_insert_sorted()
Mike Becker <universe@uap-core.de>
parents: 888
diff changeset
400 src,
f549fd9fbd8f apply binary search in cx_array_insert_sorted()
Mike Becker <universe@uap-core.de>
parents: 888
diff changeset
401 elem_count - si,
f549fd9fbd8f apply binary search in cx_array_insert_sorted()
Mike Becker <universe@uap-core.de>
parents: 888
diff changeset
402 elem_size,
f549fd9fbd8f apply binary search in cx_array_insert_sorted()
Mike Becker <universe@uap-core.de>
parents: 888
diff changeset
403 bptr,
f549fd9fbd8f apply binary search in cx_array_insert_sorted()
Mike Becker <universe@uap-core.de>
parents: 888
diff changeset
404 cmp_func
f549fd9fbd8f apply binary search in cx_array_insert_sorted()
Mike Becker <universe@uap-core.de>
parents: 888
diff changeset
405 );
883
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
406
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
407 // copy the source elements
889
f549fd9fbd8f apply binary search in cx_array_insert_sorted()
Mike Becker <universe@uap-core.de>
parents: 888
diff changeset
408 bytes_copied = copy_len * elem_size;
f549fd9fbd8f apply binary search in cx_array_insert_sorted()
Mike Becker <universe@uap-core.de>
parents: 888
diff changeset
409 memcpy(dest, src, bytes_copied);
f549fd9fbd8f apply binary search in cx_array_insert_sorted()
Mike Becker <universe@uap-core.de>
parents: 888
diff changeset
410 dest += bytes_copied;
f549fd9fbd8f apply binary search in cx_array_insert_sorted()
Mike Becker <universe@uap-core.de>
parents: 888
diff changeset
411 src += bytes_copied;
f549fd9fbd8f apply binary search in cx_array_insert_sorted()
Mike Becker <universe@uap-core.de>
parents: 888
diff changeset
412 si += copy_len;
f549fd9fbd8f apply binary search in cx_array_insert_sorted()
Mike Becker <universe@uap-core.de>
parents: 888
diff changeset
413
f549fd9fbd8f apply binary search in cx_array_insert_sorted()
Mike Becker <universe@uap-core.de>
parents: 888
diff changeset
414 // when all source elements are in place, we are done
f549fd9fbd8f apply binary search in cx_array_insert_sorted()
Mike Becker <universe@uap-core.de>
parents: 888
diff changeset
415 if (si >= elem_count) break;
883
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
416
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
417 // determine how many buffered elements need to be restored
889
f549fd9fbd8f apply binary search in cx_array_insert_sorted()
Mike Becker <universe@uap-core.de>
parents: 888
diff changeset
418 copy_len = cx_array_binary_search_sup(
f549fd9fbd8f apply binary search in cx_array_insert_sorted()
Mike Becker <universe@uap-core.de>
parents: 888
diff changeset
419 bptr,
f549fd9fbd8f apply binary search in cx_array_insert_sorted()
Mike Becker <universe@uap-core.de>
parents: 888
diff changeset
420 new_size - bi,
f549fd9fbd8f apply binary search in cx_array_insert_sorted()
Mike Becker <universe@uap-core.de>
parents: 888
diff changeset
421 elem_size,
f549fd9fbd8f apply binary search in cx_array_insert_sorted()
Mike Becker <universe@uap-core.de>
parents: 888
diff changeset
422 src,
f549fd9fbd8f apply binary search in cx_array_insert_sorted()
Mike Becker <universe@uap-core.de>
parents: 888
diff changeset
423 cmp_func
f549fd9fbd8f apply binary search in cx_array_insert_sorted()
Mike Becker <universe@uap-core.de>
parents: 888
diff changeset
424 );
883
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
425
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
426 // restore the buffered elements
889
f549fd9fbd8f apply binary search in cx_array_insert_sorted()
Mike Becker <universe@uap-core.de>
parents: 888
diff changeset
427 bytes_copied = copy_len * elem_size;
f549fd9fbd8f apply binary search in cx_array_insert_sorted()
Mike Becker <universe@uap-core.de>
parents: 888
diff changeset
428 memmove(dest, bptr, bytes_copied);
f549fd9fbd8f apply binary search in cx_array_insert_sorted()
Mike Becker <universe@uap-core.de>
parents: 888
diff changeset
429 dest += bytes_copied;
f549fd9fbd8f apply binary search in cx_array_insert_sorted()
Mike Becker <universe@uap-core.de>
parents: 888
diff changeset
430 bptr += bytes_copied;
f549fd9fbd8f apply binary search in cx_array_insert_sorted()
Mike Becker <universe@uap-core.de>
parents: 888
diff changeset
431 bi += copy_len;
883
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
432 }
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
433
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
434 // still source elements left? simply append them
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
435 if (si < elem_count) {
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
436 memcpy(dest, src, elem_size * (elem_count - si));
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
437 }
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
438
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
439 // still buffer elements left?
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
440 // don't worry, we already moved them to the correct place
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
441
986
38fa7e41194c simplify cx_array_copy() - fixes #474
Mike Becker <universe@uap-core.de>
parents: 985
diff changeset
442 return 0;
883
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
443 }
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
444
884
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
445 size_t cx_array_binary_search_inf(
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 889
diff changeset
446 const void *arr,
884
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
447 size_t size,
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
448 size_t elem_size,
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 889
diff changeset
449 const void *elem,
884
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
450 cx_compare_func cmp_func
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
451 ) {
888
6f44b1f1275c fix for empty arrays
Mike Becker <universe@uap-core.de>
parents: 885
diff changeset
452 // special case: empty array
6f44b1f1275c fix for empty arrays
Mike Becker <universe@uap-core.de>
parents: 885
diff changeset
453 if (size == 0) return 0;
6f44b1f1275c fix for empty arrays
Mike Becker <universe@uap-core.de>
parents: 885
diff changeset
454
884
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
455 // declare a variable that will contain the compare results
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
456 int result;
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
457
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
458 // cast the array pointer to something we can use offsets with
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 889
diff changeset
459 const char *array = arr;
884
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
460
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
461 // check the first array element
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
462 result = cmp_func(elem, array);
885
878a450e79bd fixes incorrect result from cx_array_binary_search() when searched element is smaller than the entire array
Mike Becker <universe@uap-core.de>
parents: 884
diff changeset
463 if (result < 0) {
878a450e79bd fixes incorrect result from cx_array_binary_search() when searched element is smaller than the entire array
Mike Becker <universe@uap-core.de>
parents: 884
diff changeset
464 return size;
878a450e79bd fixes incorrect result from cx_array_binary_search() when searched element is smaller than the entire array
Mike Becker <universe@uap-core.de>
parents: 884
diff changeset
465 } else if (result == 0) {
884
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
466 return 0;
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
467 }
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
468
1022
2911c1f4a570 add shortcut to binary search when array size is one
Mike Becker <universe@uap-core.de>
parents: 1019
diff changeset
469 // special case: there is only one element and that is smaller
2911c1f4a570 add shortcut to binary search when array size is one
Mike Becker <universe@uap-core.de>
parents: 1019
diff changeset
470 if (size == 1) return 0;
2911c1f4a570 add shortcut to binary search when array size is one
Mike Becker <universe@uap-core.de>
parents: 1019
diff changeset
471
884
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
472 // check the last array element
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
473 result = cmp_func(elem, array + elem_size * (size - 1));
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
474 if (result >= 0) {
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
475 return size - 1;
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
476 }
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
477
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
478 // the element is now guaranteed to be somewhere in the list
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
479 // so start the binary search
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
480 size_t left_index = 1;
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
481 size_t right_index = size - 1;
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
482 size_t pivot_index;
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
483
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
484 while (left_index <= right_index) {
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
485 pivot_index = left_index + (right_index - left_index) / 2;
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 889
diff changeset
486 const char *arr_elem = array + pivot_index * elem_size;
884
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
487 result = cmp_func(elem, arr_elem);
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
488 if (result == 0) {
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
489 // found it!
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
490 return pivot_index;
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
491 } else if (result < 0) {
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
492 // element is smaller than pivot, continue search left
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
493 right_index = pivot_index - 1;
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
494 } else {
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
495 // element is larger than pivot, continue search right
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
496 left_index = pivot_index + 1;
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
497 }
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
498 }
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
499
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
500 // report the largest upper bound
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
501 return result < 0 ? (pivot_index - 1) : pivot_index;
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
502 }
d375d8056262 add cx_array_binary_search() - fixes #424
Mike Becker <universe@uap-core.de>
parents: 883
diff changeset
503
985
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 968
diff changeset
504 size_t cx_array_binary_search(
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 968
diff changeset
505 const void *arr,
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 968
diff changeset
506 size_t size,
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 968
diff changeset
507 size_t elem_size,
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 968
diff changeset
508 const void *elem,
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 968
diff changeset
509 cx_compare_func cmp_func
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 968
diff changeset
510 ) {
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 968
diff changeset
511 size_t index = cx_array_binary_search_inf(
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 968
diff changeset
512 arr, size, elem_size, elem, cmp_func
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 968
diff changeset
513 );
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 968
diff changeset
514 if (index < size &&
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 968
diff changeset
515 cmp_func(((const char *) arr) + index * elem_size, elem) == 0) {
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 968
diff changeset
516 return index;
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 968
diff changeset
517 } else {
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 968
diff changeset
518 return size;
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 968
diff changeset
519 }
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 968
diff changeset
520 }
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 968
diff changeset
521
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 968
diff changeset
522 size_t cx_array_binary_search_sup(
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 968
diff changeset
523 const void *arr,
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 968
diff changeset
524 size_t size,
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 968
diff changeset
525 size_t elem_size,
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 968
diff changeset
526 const void *elem,
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 968
diff changeset
527 cx_compare_func cmp_func
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 968
diff changeset
528 ) {
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 968
diff changeset
529 size_t inf = cx_array_binary_search_inf(
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 968
diff changeset
530 arr, size, elem_size, elem, cmp_func
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 968
diff changeset
531 );
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 968
diff changeset
532 if (inf == size) {
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 968
diff changeset
533 // no infimum means, first element is supremum
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 968
diff changeset
534 return 0;
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 968
diff changeset
535 } else if (cmp_func(((const char *) arr) + inf * elem_size, elem) == 0) {
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 968
diff changeset
536 return inf;
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 968
diff changeset
537 } else {
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 968
diff changeset
538 return inf + 1;
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 968
diff changeset
539 }
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 968
diff changeset
540 }
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 968
diff changeset
541
643
5700ba9154ab #228 make buffer sizes adjustable at compile time
Mike Becker <universe@uap-core.de>
parents: 641
diff changeset
542 #ifndef CX_ARRAY_SWAP_SBO_SIZE
735
b686d0c98c62 unify the list swap SBO sizes
Mike Becker <universe@uap-core.de>
parents: 708
diff changeset
543 #define CX_ARRAY_SWAP_SBO_SIZE 128
643
5700ba9154ab #228 make buffer sizes adjustable at compile time
Mike Becker <universe@uap-core.de>
parents: 641
diff changeset
544 #endif
926
8fdd8d78c14b fix several survivors of east-const and some missing consts
Mike Becker <universe@uap-core.de>
parents: 919
diff changeset
545 const unsigned cx_array_swap_sbo_size = CX_ARRAY_SWAP_SBO_SIZE;
804
5136f2fc32ec add CX_DISABLE_ARRAY_LIST_SWAP_SBO flag
Mike Becker <universe@uap-core.de>
parents: 764
diff changeset
546
623
21082350a590 #219 array list: implement reverse
Mike Becker <universe@uap-core.de>
parents: 622
diff changeset
547 void cx_array_swap(
21082350a590 #219 array list: implement reverse
Mike Becker <universe@uap-core.de>
parents: 622
diff changeset
548 void *arr,
21082350a590 #219 array list: implement reverse
Mike Becker <universe@uap-core.de>
parents: 622
diff changeset
549 size_t elem_size,
21082350a590 #219 array list: implement reverse
Mike Becker <universe@uap-core.de>
parents: 622
diff changeset
550 size_t idx1,
21082350a590 #219 array list: implement reverse
Mike Becker <universe@uap-core.de>
parents: 622
diff changeset
551 size_t idx2
21082350a590 #219 array list: implement reverse
Mike Becker <universe@uap-core.de>
parents: 622
diff changeset
552 ) {
660
4738a9065907 add some asserts
Mike Becker <universe@uap-core.de>
parents: 655
diff changeset
553 assert(arr != NULL);
4738a9065907 add some asserts
Mike Becker <universe@uap-core.de>
parents: 655
diff changeset
554
628
1e2be40f0cb5 use //-style single line comments everywhere
Mike Becker <universe@uap-core.de>
parents: 627
diff changeset
555 // short circuit
623
21082350a590 #219 array list: implement reverse
Mike Becker <universe@uap-core.de>
parents: 622
diff changeset
556 if (idx1 == idx2) return;
21082350a590 #219 array list: implement reverse
Mike Becker <universe@uap-core.de>
parents: 622
diff changeset
557
21082350a590 #219 array list: implement reverse
Mike Becker <universe@uap-core.de>
parents: 622
diff changeset
558 char sbo_mem[CX_ARRAY_SWAP_SBO_SIZE];
21082350a590 #219 array list: implement reverse
Mike Becker <universe@uap-core.de>
parents: 622
diff changeset
559 void *tmp;
21082350a590 #219 array list: implement reverse
Mike Becker <universe@uap-core.de>
parents: 622
diff changeset
560
628
1e2be40f0cb5 use //-style single line comments everywhere
Mike Becker <universe@uap-core.de>
parents: 627
diff changeset
561 // decide if we can use the local buffer
807
c8d692131b1e remove flags to disable SBO in tests - fix #343 fix #358
Mike Becker <universe@uap-core.de>
parents: 804
diff changeset
562 if (elem_size > CX_ARRAY_SWAP_SBO_SIZE) {
623
21082350a590 #219 array list: implement reverse
Mike Becker <universe@uap-core.de>
parents: 622
diff changeset
563 tmp = malloc(elem_size);
628
1e2be40f0cb5 use //-style single line comments everywhere
Mike Becker <universe@uap-core.de>
parents: 627
diff changeset
564 // we don't want to enforce error handling
623
21082350a590 #219 array list: implement reverse
Mike Becker <universe@uap-core.de>
parents: 622
diff changeset
565 if (tmp == NULL) abort();
21082350a590 #219 array list: implement reverse
Mike Becker <universe@uap-core.de>
parents: 622
diff changeset
566 } else {
21082350a590 #219 array list: implement reverse
Mike Becker <universe@uap-core.de>
parents: 622
diff changeset
567 tmp = sbo_mem;
21082350a590 #219 array list: implement reverse
Mike Becker <universe@uap-core.de>
parents: 622
diff changeset
568 }
21082350a590 #219 array list: implement reverse
Mike Becker <universe@uap-core.de>
parents: 622
diff changeset
569
628
1e2be40f0cb5 use //-style single line comments everywhere
Mike Becker <universe@uap-core.de>
parents: 627
diff changeset
570 // calculate memory locations
623
21082350a590 #219 array list: implement reverse
Mike Becker <universe@uap-core.de>
parents: 622
diff changeset
571 char *left = arr, *right = arr;
21082350a590 #219 array list: implement reverse
Mike Becker <universe@uap-core.de>
parents: 622
diff changeset
572 left += idx1 * elem_size;
21082350a590 #219 array list: implement reverse
Mike Becker <universe@uap-core.de>
parents: 622
diff changeset
573 right += idx2 * elem_size;
21082350a590 #219 array list: implement reverse
Mike Becker <universe@uap-core.de>
parents: 622
diff changeset
574
628
1e2be40f0cb5 use //-style single line comments everywhere
Mike Becker <universe@uap-core.de>
parents: 627
diff changeset
575 // three-way swap
623
21082350a590 #219 array list: implement reverse
Mike Becker <universe@uap-core.de>
parents: 622
diff changeset
576 memcpy(tmp, left, elem_size);
21082350a590 #219 array list: implement reverse
Mike Becker <universe@uap-core.de>
parents: 622
diff changeset
577 memcpy(left, right, elem_size);
21082350a590 #219 array list: implement reverse
Mike Becker <universe@uap-core.de>
parents: 622
diff changeset
578 memcpy(right, tmp, elem_size);
21082350a590 #219 array list: implement reverse
Mike Becker <universe@uap-core.de>
parents: 622
diff changeset
579
628
1e2be40f0cb5 use //-style single line comments everywhere
Mike Becker <universe@uap-core.de>
parents: 627
diff changeset
580 // free dynamic memory, if it was needed
623
21082350a590 #219 array list: implement reverse
Mike Becker <universe@uap-core.de>
parents: 622
diff changeset
581 if (tmp != sbo_mem) {
21082350a590 #219 array list: implement reverse
Mike Becker <universe@uap-core.de>
parents: 622
diff changeset
582 free(tmp);
21082350a590 #219 array list: implement reverse
Mike Becker <universe@uap-core.de>
parents: 622
diff changeset
583 }
21082350a590 #219 array list: implement reverse
Mike Becker <universe@uap-core.de>
parents: 622
diff changeset
584 }
21082350a590 #219 array list: implement reverse
Mike Becker <universe@uap-core.de>
parents: 622
diff changeset
585
628
1e2be40f0cb5 use //-style single line comments everywhere
Mike Becker <universe@uap-core.de>
parents: 627
diff changeset
586 // HIGH LEVEL ARRAY LIST FUNCTIONS
607
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
587
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
588 typedef struct {
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
589 struct cx_list_s base;
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
590 void *data;
677
b09aae58bba4 refactoring of collections to make use of destructors in map implementations
Mike Becker <universe@uap-core.de>
parents: 676
diff changeset
591 size_t capacity;
953
581ad4fd01e9 add function to create array reallocator that can move arrays from stack to heap
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
592 CxArrayReallocator reallocator;
607
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
593 } cx_array_list;
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
594
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
595 static void cx_arl_destructor(struct cx_list_s *list) {
610
de5d3ee6435f #219 array list: implement add and at
Mike Becker <universe@uap-core.de>
parents: 607
diff changeset
596 cx_array_list *arl = (cx_array_list *) list;
708
1caed6c9ba68 fix inconsistent destructor requirements for list and map classes
Mike Becker <universe@uap-core.de>
parents: 699
diff changeset
597
1caed6c9ba68 fix inconsistent destructor requirements for list and map classes
Mike Becker <universe@uap-core.de>
parents: 699
diff changeset
598 char *ptr = arl->data;
1caed6c9ba68 fix inconsistent destructor requirements for list and map classes
Mike Becker <universe@uap-core.de>
parents: 699
diff changeset
599
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
600 if (list->collection.simple_destructor) {
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
601 for (size_t i = 0; i < list->collection.size; i++) {
708
1caed6c9ba68 fix inconsistent destructor requirements for list and map classes
Mike Becker <universe@uap-core.de>
parents: 699
diff changeset
602 cx_invoke_simple_destructor(list, ptr);
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
603 ptr += list->collection.elem_size;
708
1caed6c9ba68 fix inconsistent destructor requirements for list and map classes
Mike Becker <universe@uap-core.de>
parents: 699
diff changeset
604 }
1caed6c9ba68 fix inconsistent destructor requirements for list and map classes
Mike Becker <universe@uap-core.de>
parents: 699
diff changeset
605 }
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
606 if (list->collection.advanced_destructor) {
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
607 for (size_t i = 0; i < list->collection.size; i++) {
708
1caed6c9ba68 fix inconsistent destructor requirements for list and map classes
Mike Becker <universe@uap-core.de>
parents: 699
diff changeset
608 cx_invoke_advanced_destructor(list, ptr);
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
609 ptr += list->collection.elem_size;
708
1caed6c9ba68 fix inconsistent destructor requirements for list and map classes
Mike Becker <universe@uap-core.de>
parents: 699
diff changeset
610 }
1caed6c9ba68 fix inconsistent destructor requirements for list and map classes
Mike Becker <universe@uap-core.de>
parents: 699
diff changeset
611 }
1caed6c9ba68 fix inconsistent destructor requirements for list and map classes
Mike Becker <universe@uap-core.de>
parents: 699
diff changeset
612
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
613 cxFree(list->collection.allocator, arl->data);
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
614 cxFree(list->collection.allocator, list);
607
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
615 }
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
616
638
eafb45eefc51 add cxListInsertArray() - fixes #224
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
617 static size_t cx_arl_insert_array(
629
6c81ee4f11ad #224 add cxListAddArray()
Mike Becker <universe@uap-core.de>
parents: 628
diff changeset
618 struct cx_list_s *list,
638
eafb45eefc51 add cxListInsertArray() - fixes #224
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
619 size_t index,
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 889
diff changeset
620 const void *array,
629
6c81ee4f11ad #224 add cxListAddArray()
Mike Becker <universe@uap-core.de>
parents: 628
diff changeset
621 size_t n
6c81ee4f11ad #224 add cxListAddArray()
Mike Becker <universe@uap-core.de>
parents: 628
diff changeset
622 ) {
638
eafb45eefc51 add cxListInsertArray() - fixes #224
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
623 // out of bounds and special case check
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
624 if (index > list->collection.size || n == 0) return 0;
638
eafb45eefc51 add cxListInsertArray() - fixes #224
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
625
eafb45eefc51 add cxListInsertArray() - fixes #224
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
626 // get a correctly typed pointer to the list
629
6c81ee4f11ad #224 add cxListAddArray()
Mike Becker <universe@uap-core.de>
parents: 628
diff changeset
627 cx_array_list *arl = (cx_array_list *) list;
638
eafb45eefc51 add cxListInsertArray() - fixes #224
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
628
eafb45eefc51 add cxListInsertArray() - fixes #224
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
629 // do we need to move some elements?
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
630 if (index < list->collection.size) {
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 889
diff changeset
631 const char *first_to_move = (const char *) arl->data;
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
632 first_to_move += index * list->collection.elem_size;
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
633 size_t elems_to_move = list->collection.size - index;
638
eafb45eefc51 add cxListInsertArray() - fixes #224
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
634 size_t start_of_moved = index + n;
eafb45eefc51 add cxListInsertArray() - fixes #224
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
635
986
38fa7e41194c simplify cx_array_copy() - fixes #474
Mike Becker <universe@uap-core.de>
parents: 985
diff changeset
636 if (cx_array_copy(
638
eafb45eefc51 add cxListInsertArray() - fixes #224
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
637 &arl->data,
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
638 &list->collection.size,
677
b09aae58bba4 refactoring of collections to make use of destructors in map implementations
Mike Becker <universe@uap-core.de>
parents: 676
diff changeset
639 &arl->capacity,
998
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
640 0,
638
eafb45eefc51 add cxListInsertArray() - fixes #224
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
641 start_of_moved,
eafb45eefc51 add cxListInsertArray() - fixes #224
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
642 first_to_move,
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
643 list->collection.elem_size,
638
eafb45eefc51 add cxListInsertArray() - fixes #224
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
644 elems_to_move,
eafb45eefc51 add cxListInsertArray() - fixes #224
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
645 &arl->reallocator
eafb45eefc51 add cxListInsertArray() - fixes #224
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
646 )) {
eafb45eefc51 add cxListInsertArray() - fixes #224
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
647 // if moving existing elems is unsuccessful, abort
eafb45eefc51 add cxListInsertArray() - fixes #224
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
648 return 0;
eafb45eefc51 add cxListInsertArray() - fixes #224
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
649 }
eafb45eefc51 add cxListInsertArray() - fixes #224
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
650 }
eafb45eefc51 add cxListInsertArray() - fixes #224
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
651
eafb45eefc51 add cxListInsertArray() - fixes #224
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
652 // note that if we had to move the elements, the following operation
eafb45eefc51 add cxListInsertArray() - fixes #224
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
653 // is guaranteed to succeed, because we have the memory already allocated
eafb45eefc51 add cxListInsertArray() - fixes #224
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
654 // therefore, it is impossible to leave this function with an invalid array
eafb45eefc51 add cxListInsertArray() - fixes #224
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
655
eafb45eefc51 add cxListInsertArray() - fixes #224
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
656 // place the new elements
986
38fa7e41194c simplify cx_array_copy() - fixes #474
Mike Becker <universe@uap-core.de>
parents: 985
diff changeset
657 if (cx_array_copy(
629
6c81ee4f11ad #224 add cxListAddArray()
Mike Becker <universe@uap-core.de>
parents: 628
diff changeset
658 &arl->data,
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
659 &list->collection.size,
677
b09aae58bba4 refactoring of collections to make use of destructors in map implementations
Mike Becker <universe@uap-core.de>
parents: 676
diff changeset
660 &arl->capacity,
998
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
661 0,
638
eafb45eefc51 add cxListInsertArray() - fixes #224
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
662 index,
629
6c81ee4f11ad #224 add cxListAddArray()
Mike Becker <universe@uap-core.de>
parents: 628
diff changeset
663 array,
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
664 list->collection.elem_size,
629
6c81ee4f11ad #224 add cxListAddArray()
Mike Becker <universe@uap-core.de>
parents: 628
diff changeset
665 n,
6c81ee4f11ad #224 add cxListAddArray()
Mike Becker <universe@uap-core.de>
parents: 628
diff changeset
666 &arl->reallocator
6c81ee4f11ad #224 add cxListAddArray()
Mike Becker <universe@uap-core.de>
parents: 628
diff changeset
667 )) {
6c81ee4f11ad #224 add cxListAddArray()
Mike Becker <universe@uap-core.de>
parents: 628
diff changeset
668 // array list implementation is "all or nothing"
6c81ee4f11ad #224 add cxListAddArray()
Mike Becker <universe@uap-core.de>
parents: 628
diff changeset
669 return 0;
986
38fa7e41194c simplify cx_array_copy() - fixes #474
Mike Becker <universe@uap-core.de>
parents: 985
diff changeset
670 } else {
38fa7e41194c simplify cx_array_copy() - fixes #474
Mike Becker <universe@uap-core.de>
parents: 985
diff changeset
671 return n;
629
6c81ee4f11ad #224 add cxListAddArray()
Mike Becker <universe@uap-core.de>
parents: 628
diff changeset
672 }
6c81ee4f11ad #224 add cxListAddArray()
Mike Becker <universe@uap-core.de>
parents: 628
diff changeset
673 }
6c81ee4f11ad #224 add cxListAddArray()
Mike Becker <universe@uap-core.de>
parents: 628
diff changeset
674
881
1dbbf8c1c42f add optimized implementation of insert_sorted for array lists
Mike Becker <universe@uap-core.de>
parents: 876
diff changeset
675 static size_t cx_arl_insert_sorted(
1dbbf8c1c42f add optimized implementation of insert_sorted for array lists
Mike Becker <universe@uap-core.de>
parents: 876
diff changeset
676 struct cx_list_s *list,
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 889
diff changeset
677 const void *sorted_data,
881
1dbbf8c1c42f add optimized implementation of insert_sorted for array lists
Mike Becker <universe@uap-core.de>
parents: 876
diff changeset
678 size_t n
1dbbf8c1c42f add optimized implementation of insert_sorted for array lists
Mike Becker <universe@uap-core.de>
parents: 876
diff changeset
679 ) {
883
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
680 // get a correctly typed pointer to the list
881
1dbbf8c1c42f add optimized implementation of insert_sorted for array lists
Mike Becker <universe@uap-core.de>
parents: 876
diff changeset
681 cx_array_list *arl = (cx_array_list *) list;
1dbbf8c1c42f add optimized implementation of insert_sorted for array lists
Mike Becker <universe@uap-core.de>
parents: 876
diff changeset
682
986
38fa7e41194c simplify cx_array_copy() - fixes #474
Mike Becker <universe@uap-core.de>
parents: 985
diff changeset
683 if (cx_array_insert_sorted(
883
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
684 &arl->data,
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
685 &list->collection.size,
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
686 &arl->capacity,
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
687 list->collection.cmpfunc,
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
688 sorted_data,
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
689 list->collection.elem_size,
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
690 n,
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
691 &arl->reallocator
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
692 )) {
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
693 // array list implementation is "all or nothing"
3012e9b4214e add low level cx_array_insert_sorted() and convenience macros
Mike Becker <universe@uap-core.de>
parents: 881
diff changeset
694 return 0;
986
38fa7e41194c simplify cx_array_copy() - fixes #474
Mike Becker <universe@uap-core.de>
parents: 985
diff changeset
695 } else {
38fa7e41194c simplify cx_array_copy() - fixes #474
Mike Becker <universe@uap-core.de>
parents: 985
diff changeset
696 return n;
881
1dbbf8c1c42f add optimized implementation of insert_sorted for array lists
Mike Becker <universe@uap-core.de>
parents: 876
diff changeset
697 }
1dbbf8c1c42f add optimized implementation of insert_sorted for array lists
Mike Becker <universe@uap-core.de>
parents: 876
diff changeset
698 }
1dbbf8c1c42f add optimized implementation of insert_sorted for array lists
Mike Becker <universe@uap-core.de>
parents: 876
diff changeset
699
641
d402fead3386 add new pointer list wrapper - resolves #234
Mike Becker <universe@uap-core.de>
parents: 640
diff changeset
700 static int cx_arl_insert_element(
d402fead3386 add new pointer list wrapper - resolves #234
Mike Becker <universe@uap-core.de>
parents: 640
diff changeset
701 struct cx_list_s *list,
d402fead3386 add new pointer list wrapper - resolves #234
Mike Becker <universe@uap-core.de>
parents: 640
diff changeset
702 size_t index,
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 889
diff changeset
703 const void *element
641
d402fead3386 add new pointer list wrapper - resolves #234
Mike Becker <universe@uap-core.de>
parents: 640
diff changeset
704 ) {
d402fead3386 add new pointer list wrapper - resolves #234
Mike Becker <universe@uap-core.de>
parents: 640
diff changeset
705 return 1 != cx_arl_insert_array(list, index, element, 1);
d402fead3386 add new pointer list wrapper - resolves #234
Mike Becker <universe@uap-core.de>
parents: 640
diff changeset
706 }
d402fead3386 add new pointer list wrapper - resolves #234
Mike Becker <universe@uap-core.de>
parents: 640
diff changeset
707
607
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
708 static int cx_arl_insert_iter(
853
d4baf4dd55c3 simplify iterator structures
Mike Becker <universe@uap-core.de>
parents: 850
diff changeset
709 struct cx_iterator_s *iter,
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 889
diff changeset
710 const void *elem,
607
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
711 int prepend
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
712 ) {
853
d4baf4dd55c3 simplify iterator structures
Mike Becker <universe@uap-core.de>
parents: 850
diff changeset
713 struct cx_list_s *list = iter->src_handle.m;
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
714 if (iter->index < list->collection.size) {
641
d402fead3386 add new pointer list wrapper - resolves #234
Mike Becker <universe@uap-core.de>
parents: 640
diff changeset
715 int result = cx_arl_insert_element(
619
5e58187ac707 #219 array list: implement insert via iterator
Mike Becker <universe@uap-core.de>
parents: 616
diff changeset
716 list,
5e58187ac707 #219 array list: implement insert via iterator
Mike Becker <universe@uap-core.de>
parents: 616
diff changeset
717 iter->index + 1 - prepend,
641
d402fead3386 add new pointer list wrapper - resolves #234
Mike Becker <universe@uap-core.de>
parents: 640
diff changeset
718 elem
619
5e58187ac707 #219 array list: implement insert via iterator
Mike Becker <universe@uap-core.de>
parents: 616
diff changeset
719 );
874
cdce47f34d48 fix inserting via iterator correctly increases element count
Mike Becker <universe@uap-core.de>
parents: 856
diff changeset
720 if (result == 0) {
cdce47f34d48 fix inserting via iterator correctly increases element count
Mike Becker <universe@uap-core.de>
parents: 856
diff changeset
721 iter->elem_count++;
cdce47f34d48 fix inserting via iterator correctly increases element count
Mike Becker <universe@uap-core.de>
parents: 856
diff changeset
722 if (prepend != 0) {
cdce47f34d48 fix inserting via iterator correctly increases element count
Mike Becker <universe@uap-core.de>
parents: 856
diff changeset
723 iter->index++;
cdce47f34d48 fix inserting via iterator correctly increases element count
Mike Becker <universe@uap-core.de>
parents: 856
diff changeset
724 iter->elem_handle = ((char *) iter->elem_handle) + list->collection.elem_size;
cdce47f34d48 fix inserting via iterator correctly increases element count
Mike Becker <universe@uap-core.de>
parents: 856
diff changeset
725 }
619
5e58187ac707 #219 array list: implement insert via iterator
Mike Becker <universe@uap-core.de>
parents: 616
diff changeset
726 }
5e58187ac707 #219 array list: implement insert via iterator
Mike Becker <universe@uap-core.de>
parents: 616
diff changeset
727 return result;
5e58187ac707 #219 array list: implement insert via iterator
Mike Becker <universe@uap-core.de>
parents: 616
diff changeset
728 } else {
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
729 int result = cx_arl_insert_element(list, list->collection.size, elem);
874
cdce47f34d48 fix inserting via iterator correctly increases element count
Mike Becker <universe@uap-core.de>
parents: 856
diff changeset
730 if (result == 0) {
cdce47f34d48 fix inserting via iterator correctly increases element count
Mike Becker <universe@uap-core.de>
parents: 856
diff changeset
731 iter->elem_count++;
cdce47f34d48 fix inserting via iterator correctly increases element count
Mike Becker <universe@uap-core.de>
parents: 856
diff changeset
732 iter->index = list->collection.size;
cdce47f34d48 fix inserting via iterator correctly increases element count
Mike Becker <universe@uap-core.de>
parents: 856
diff changeset
733 }
619
5e58187ac707 #219 array list: implement insert via iterator
Mike Becker <universe@uap-core.de>
parents: 616
diff changeset
734 return result;
5e58187ac707 #219 array list: implement insert via iterator
Mike Becker <universe@uap-core.de>
parents: 616
diff changeset
735 }
607
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
736 }
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
737
919
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
738 static size_t cx_arl_remove(
607
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
739 struct cx_list_s *list,
919
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
740 size_t index,
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
741 size_t num,
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
742 void *targetbuf
607
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
743 ) {
664
af5bf4603a5d add cxListClear and fix missing destructor invocations - #241 #246
Mike Becker <universe@uap-core.de>
parents: 662
diff changeset
744 cx_array_list *arl = (cx_array_list *) list;
af5bf4603a5d add cxListClear and fix missing destructor invocations - #241 #246
Mike Becker <universe@uap-core.de>
parents: 662
diff changeset
745
628
1e2be40f0cb5 use //-style single line comments everywhere
Mike Becker <universe@uap-core.de>
parents: 627
diff changeset
746 // out-of-bounds check
919
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
747 size_t remove;
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
748 if (index >= list->collection.size) {
919
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
749 remove = 0;
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
750 } else if (index + num > list->collection.size) {
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
751 remove = list->collection.size - index;
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
752 } else {
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
753 remove = num;
613
85c08391a090 #219 array list: implement remove
Mike Becker <universe@uap-core.de>
parents: 612
diff changeset
754 }
85c08391a090 #219 array list: implement remove
Mike Becker <universe@uap-core.de>
parents: 612
diff changeset
755
919
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
756 // easy exit
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
757 if (remove == 0) return 0;
664
af5bf4603a5d add cxListClear and fix missing destructor invocations - #241 #246
Mike Becker <universe@uap-core.de>
parents: 662
diff changeset
758
919
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
759 // destroy or copy contents
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
760 if (targetbuf == NULL) {
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
761 for (size_t idx = index; idx < index + remove; idx++) {
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
762 cx_invoke_destructor(
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
763 list,
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
764 ((char *) arl->data) + idx * list->collection.elem_size
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
765 );
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
766 }
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
767 } else {
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
768 memcpy(
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
769 targetbuf,
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
770 ((char *) arl->data) + index * list->collection.elem_size,
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
771 remove * list->collection.elem_size
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
772 );
624
b0bdff7d8203 #219: cx_arl_remove short-circuit for last element
Mike Becker <universe@uap-core.de>
parents: 623
diff changeset
773 }
613
85c08391a090 #219 array list: implement remove
Mike Becker <universe@uap-core.de>
parents: 612
diff changeset
774
919
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
775 // short-circuit removal of last elements
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
776 if (index + remove == list->collection.size) {
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
777 list->collection.size -= remove;
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
778 return remove;
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
779 }
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
780
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
781 // just move the elements to the left
613
85c08391a090 #219 array list: implement remove
Mike Becker <universe@uap-core.de>
parents: 612
diff changeset
782 int result = cx_array_copy(
85c08391a090 #219 array list: implement remove
Mike Becker <universe@uap-core.de>
parents: 612
diff changeset
783 &arl->data,
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
784 &list->collection.size,
677
b09aae58bba4 refactoring of collections to make use of destructors in map implementations
Mike Becker <universe@uap-core.de>
parents: 676
diff changeset
785 &arl->capacity,
998
bb196054f3fd make cx_array_copy() support different types for size/capacity - fixes #492
Mike Becker <universe@uap-core.de>
parents: 995
diff changeset
786 0,
613
85c08391a090 #219 array list: implement remove
Mike Becker <universe@uap-core.de>
parents: 612
diff changeset
787 index,
919
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
788 ((char *) arl->data) + (index + remove) * list->collection.elem_size,
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
789 list->collection.elem_size,
919
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
790 list->collection.size - index - remove,
613
85c08391a090 #219 array list: implement remove
Mike Becker <universe@uap-core.de>
parents: 612
diff changeset
791 &arl->reallocator
85c08391a090 #219 array list: implement remove
Mike Becker <universe@uap-core.de>
parents: 612
diff changeset
792 );
820
8b86ee2e09bb remove check that is always true in cx_arl_remove()
Mike Becker <universe@uap-core.de>
parents: 819
diff changeset
793
8b86ee2e09bb remove check that is always true in cx_arl_remove()
Mike Becker <universe@uap-core.de>
parents: 819
diff changeset
794 // cx_array_copy cannot fail, array cannot grow
8b86ee2e09bb remove check that is always true in cx_arl_remove()
Mike Becker <universe@uap-core.de>
parents: 819
diff changeset
795 assert(result == 0);
8b86ee2e09bb remove check that is always true in cx_arl_remove()
Mike Becker <universe@uap-core.de>
parents: 819
diff changeset
796
8b86ee2e09bb remove check that is always true in cx_arl_remove()
Mike Becker <universe@uap-core.de>
parents: 819
diff changeset
797 // decrease the size
919
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
798 list->collection.size -= remove;
820
8b86ee2e09bb remove check that is always true in cx_arl_remove()
Mike Becker <universe@uap-core.de>
parents: 819
diff changeset
799
919
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
800 return remove;
607
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
801 }
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
802
664
af5bf4603a5d add cxListClear and fix missing destructor invocations - #241 #246
Mike Becker <universe@uap-core.de>
parents: 662
diff changeset
803 static void cx_arl_clear(struct cx_list_s *list) {
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
804 if (list->collection.size == 0) return;
664
af5bf4603a5d add cxListClear and fix missing destructor invocations - #241 #246
Mike Becker <universe@uap-core.de>
parents: 662
diff changeset
805
af5bf4603a5d add cxListClear and fix missing destructor invocations - #241 #246
Mike Becker <universe@uap-core.de>
parents: 662
diff changeset
806 cx_array_list *arl = (cx_array_list *) list;
af5bf4603a5d add cxListClear and fix missing destructor invocations - #241 #246
Mike Becker <universe@uap-core.de>
parents: 662
diff changeset
807 char *ptr = arl->data;
af5bf4603a5d add cxListClear and fix missing destructor invocations - #241 #246
Mike Becker <universe@uap-core.de>
parents: 662
diff changeset
808
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
809 if (list->collection.simple_destructor) {
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
810 for (size_t i = 0; i < list->collection.size; i++) {
677
b09aae58bba4 refactoring of collections to make use of destructors in map implementations
Mike Becker <universe@uap-core.de>
parents: 676
diff changeset
811 cx_invoke_simple_destructor(list, ptr);
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
812 ptr += list->collection.elem_size;
664
af5bf4603a5d add cxListClear and fix missing destructor invocations - #241 #246
Mike Becker <universe@uap-core.de>
parents: 662
diff changeset
813 }
677
b09aae58bba4 refactoring of collections to make use of destructors in map implementations
Mike Becker <universe@uap-core.de>
parents: 676
diff changeset
814 }
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
815 if (list->collection.advanced_destructor) {
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
816 for (size_t i = 0; i < list->collection.size; i++) {
677
b09aae58bba4 refactoring of collections to make use of destructors in map implementations
Mike Becker <universe@uap-core.de>
parents: 676
diff changeset
817 cx_invoke_advanced_destructor(list, ptr);
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
818 ptr += list->collection.elem_size;
664
af5bf4603a5d add cxListClear and fix missing destructor invocations - #241 #246
Mike Becker <universe@uap-core.de>
parents: 662
diff changeset
819 }
af5bf4603a5d add cxListClear and fix missing destructor invocations - #241 #246
Mike Becker <universe@uap-core.de>
parents: 662
diff changeset
820 }
666
b5dd654deb3b add unit test for cxListClear + fix destructor functions not always invoked with the correct pointer
Mike Becker <universe@uap-core.de>
parents: 664
diff changeset
821
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
822 memset(arl->data, 0, list->collection.size * list->collection.elem_size);
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
823 list->collection.size = 0;
664
af5bf4603a5d add cxListClear and fix missing destructor invocations - #241 #246
Mike Becker <universe@uap-core.de>
parents: 662
diff changeset
824 }
af5bf4603a5d add cxListClear and fix missing destructor invocations - #241 #246
Mike Becker <universe@uap-core.de>
parents: 662
diff changeset
825
647
2e6e9d9f2159 implement swap function for list elements - fixes #218
Mike Becker <universe@uap-core.de>
parents: 643
diff changeset
826 static int cx_arl_swap(
2e6e9d9f2159 implement swap function for list elements - fixes #218
Mike Becker <universe@uap-core.de>
parents: 643
diff changeset
827 struct cx_list_s *list,
2e6e9d9f2159 implement swap function for list elements - fixes #218
Mike Becker <universe@uap-core.de>
parents: 643
diff changeset
828 size_t i,
2e6e9d9f2159 implement swap function for list elements - fixes #218
Mike Becker <universe@uap-core.de>
parents: 643
diff changeset
829 size_t j
2e6e9d9f2159 implement swap function for list elements - fixes #218
Mike Becker <universe@uap-core.de>
parents: 643
diff changeset
830 ) {
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
831 if (i >= list->collection.size || j >= list->collection.size) return 1;
647
2e6e9d9f2159 implement swap function for list elements - fixes #218
Mike Becker <universe@uap-core.de>
parents: 643
diff changeset
832 cx_array_list *arl = (cx_array_list *) list;
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
833 cx_array_swap(arl->data, list->collection.elem_size, i, j);
647
2e6e9d9f2159 implement swap function for list elements - fixes #218
Mike Becker <universe@uap-core.de>
parents: 643
diff changeset
834 return 0;
2e6e9d9f2159 implement swap function for list elements - fixes #218
Mike Becker <universe@uap-core.de>
parents: 643
diff changeset
835 }
2e6e9d9f2159 implement swap function for list elements - fixes #218
Mike Becker <universe@uap-core.de>
parents: 643
diff changeset
836
610
de5d3ee6435f #219 array list: implement add and at
Mike Becker <universe@uap-core.de>
parents: 607
diff changeset
837 static void *cx_arl_at(
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 889
diff changeset
838 const struct cx_list_s *list,
607
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
839 size_t index
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
840 ) {
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
841 if (index < list->collection.size) {
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 889
diff changeset
842 const cx_array_list *arl = (const cx_array_list *) list;
610
de5d3ee6435f #219 array list: implement add and at
Mike Becker <universe@uap-core.de>
parents: 607
diff changeset
843 char *space = arl->data;
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
844 return space + index * list->collection.elem_size;
610
de5d3ee6435f #219 array list: implement add and at
Mike Becker <universe@uap-core.de>
parents: 607
diff changeset
845 } else {
de5d3ee6435f #219 array list: implement add and at
Mike Becker <universe@uap-core.de>
parents: 607
diff changeset
846 return NULL;
de5d3ee6435f #219 array list: implement add and at
Mike Becker <universe@uap-core.de>
parents: 607
diff changeset
847 }
607
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
848 }
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
849
764
ccbdbd088455 add cxListFindRemove and cx_linked_list_find_node
Mike Becker <universe@uap-core.de>
parents: 763
diff changeset
850 static ssize_t cx_arl_find_remove(
ccbdbd088455 add cxListFindRemove and cx_linked_list_find_node
Mike Becker <universe@uap-core.de>
parents: 763
diff changeset
851 struct cx_list_s *list,
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 889
diff changeset
852 const void *elem,
764
ccbdbd088455 add cxListFindRemove and cx_linked_list_find_node
Mike Becker <universe@uap-core.de>
parents: 763
diff changeset
853 bool remove
607
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
854 ) {
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
855 assert(list->collection.cmpfunc != NULL);
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
856 assert(list->collection.size < SIZE_MAX / 2);
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 889
diff changeset
857 char *cur = ((const cx_array_list *) list)->data;
614
7aaec630cf15 #219 array list: implement find
Mike Becker <universe@uap-core.de>
parents: 613
diff changeset
858
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
859 for (ssize_t i = 0; i < (ssize_t) list->collection.size; i++) {
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
860 if (0 == list->collection.cmpfunc(elem, cur)) {
764
ccbdbd088455 add cxListFindRemove and cx_linked_list_find_node
Mike Becker <universe@uap-core.de>
parents: 763
diff changeset
861 if (remove) {
919
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
862 if (1 == cx_arl_remove(list, i, 1, NULL)) {
764
ccbdbd088455 add cxListFindRemove and cx_linked_list_find_node
Mike Becker <universe@uap-core.de>
parents: 763
diff changeset
863 return i;
ccbdbd088455 add cxListFindRemove and cx_linked_list_find_node
Mike Becker <universe@uap-core.de>
parents: 763
diff changeset
864 } else {
ccbdbd088455 add cxListFindRemove and cx_linked_list_find_node
Mike Becker <universe@uap-core.de>
parents: 763
diff changeset
865 return -1;
ccbdbd088455 add cxListFindRemove and cx_linked_list_find_node
Mike Becker <universe@uap-core.de>
parents: 763
diff changeset
866 }
ccbdbd088455 add cxListFindRemove and cx_linked_list_find_node
Mike Becker <universe@uap-core.de>
parents: 763
diff changeset
867 } else {
ccbdbd088455 add cxListFindRemove and cx_linked_list_find_node
Mike Becker <universe@uap-core.de>
parents: 763
diff changeset
868 return i;
ccbdbd088455 add cxListFindRemove and cx_linked_list_find_node
Mike Becker <universe@uap-core.de>
parents: 763
diff changeset
869 }
614
7aaec630cf15 #219 array list: implement find
Mike Becker <universe@uap-core.de>
parents: 613
diff changeset
870 }
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
871 cur += list->collection.elem_size;
614
7aaec630cf15 #219 array list: implement find
Mike Becker <universe@uap-core.de>
parents: 613
diff changeset
872 }
7aaec630cf15 #219 array list: implement find
Mike Becker <universe@uap-core.de>
parents: 613
diff changeset
873
699
35b2b99ee523 make list find return a negative value when elem not found
Mike Becker <universe@uap-core.de>
parents: 678
diff changeset
874 return -1;
607
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
875 }
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
876
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
877 static void cx_arl_sort(struct cx_list_s *list) {
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
878 assert(list->collection.cmpfunc != NULL);
615
b52b66dcd44b #219 array list: implement sort
Mike Becker <universe@uap-core.de>
parents: 614
diff changeset
879 qsort(((cx_array_list *) list)->data,
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
880 list->collection.size,
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
881 list->collection.elem_size,
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
882 list->collection.cmpfunc
615
b52b66dcd44b #219 array list: implement sort
Mike Becker <universe@uap-core.de>
parents: 614
diff changeset
883 );
607
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
884 }
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
885
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
886 static int cx_arl_compare(
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 889
diff changeset
887 const struct cx_list_s *list,
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 889
diff changeset
888 const struct cx_list_s *other
607
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
889 ) {
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
890 assert(list->collection.cmpfunc != NULL);
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
891 if (list->collection.size == other->collection.size) {
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 889
diff changeset
892 const char *left = ((const cx_array_list *) list)->data;
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 889
diff changeset
893 const char *right = ((const cx_array_list *) other)->data;
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
894 for (size_t i = 0; i < list->collection.size; i++) {
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
895 int d = list->collection.cmpfunc(left, right);
622
3d93cd78aa20 #219 array list: implement compare member func
Mike Becker <universe@uap-core.de>
parents: 620
diff changeset
896 if (d != 0) {
3d93cd78aa20 #219 array list: implement compare member func
Mike Becker <universe@uap-core.de>
parents: 620
diff changeset
897 return d;
3d93cd78aa20 #219 array list: implement compare member func
Mike Becker <universe@uap-core.de>
parents: 620
diff changeset
898 }
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
899 left += list->collection.elem_size;
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
900 right += other->collection.elem_size;
622
3d93cd78aa20 #219 array list: implement compare member func
Mike Becker <universe@uap-core.de>
parents: 620
diff changeset
901 }
3d93cd78aa20 #219 array list: implement compare member func
Mike Becker <universe@uap-core.de>
parents: 620
diff changeset
902 return 0;
3d93cd78aa20 #219 array list: implement compare member func
Mike Becker <universe@uap-core.de>
parents: 620
diff changeset
903 } else {
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
904 return list->collection.size < other->collection.size ? -1 : 1;
622
3d93cd78aa20 #219 array list: implement compare member func
Mike Becker <universe@uap-core.de>
parents: 620
diff changeset
905 }
607
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
906 }
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
907
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
908 static void cx_arl_reverse(struct cx_list_s *list) {
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
909 if (list->collection.size < 2) return;
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 889
diff changeset
910 void *data = ((const cx_array_list *) list)->data;
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
911 size_t half = list->collection.size / 2;
623
21082350a590 #219 array list: implement reverse
Mike Becker <universe@uap-core.de>
parents: 622
diff changeset
912 for (size_t i = 0; i < half; i++) {
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
913 cx_array_swap(data, list->collection.elem_size, i, list->collection.size - 1 - i);
623
21082350a590 #219 array list: implement reverse
Mike Becker <universe@uap-core.de>
parents: 622
diff changeset
914 }
607
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
915 }
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
916
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 889
diff changeset
917 static bool cx_arl_iter_valid(const void *it) {
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 889
diff changeset
918 const struct cx_iterator_s *iter = it;
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 889
diff changeset
919 const struct cx_list_s *list = iter->src_handle.c;
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
920 return iter->index < list->collection.size;
616
af7d8a29fbc5 #219 array list: add iterator
Mike Becker <universe@uap-core.de>
parents: 615
diff changeset
921 }
af7d8a29fbc5 #219 array list: add iterator
Mike Becker <universe@uap-core.de>
parents: 615
diff changeset
922
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 889
diff changeset
923 static void *cx_arl_iter_current(const void *it) {
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 889
diff changeset
924 const struct cx_iterator_s *iter = it;
616
af7d8a29fbc5 #219 array list: add iterator
Mike Becker <universe@uap-core.de>
parents: 615
diff changeset
925 return iter->elem_handle;
af7d8a29fbc5 #219 array list: add iterator
Mike Becker <universe@uap-core.de>
parents: 615
diff changeset
926 }
af7d8a29fbc5 #219 array list: add iterator
Mike Becker <universe@uap-core.de>
parents: 615
diff changeset
927
630
ac5e7f789048 separate iterators and mutating iterators
Mike Becker <universe@uap-core.de>
parents: 629
diff changeset
928 static void cx_arl_iter_next(void *it) {
853
d4baf4dd55c3 simplify iterator structures
Mike Becker <universe@uap-core.de>
parents: 850
diff changeset
929 struct cx_iterator_s *iter = it;
854
fe0d69d72bcd fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents: 853
diff changeset
930 if (iter->base.remove) {
fe0d69d72bcd fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents: 853
diff changeset
931 iter->base.remove = false;
919
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
932 cx_arl_remove(iter->src_handle.m, iter->index, 1, NULL);
616
af7d8a29fbc5 #219 array list: add iterator
Mike Becker <universe@uap-core.de>
parents: 615
diff changeset
933 } else {
af7d8a29fbc5 #219 array list: add iterator
Mike Becker <universe@uap-core.de>
parents: 615
diff changeset
934 iter->index++;
620
f220695aded6 #219 improve cx_arl_iter_next
Mike Becker <universe@uap-core.de>
parents: 619
diff changeset
935 iter->elem_handle =
f220695aded6 #219 improve cx_arl_iter_next
Mike Becker <universe@uap-core.de>
parents: 619
diff changeset
936 ((char *) iter->elem_handle)
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 889
diff changeset
937 + ((const struct cx_list_s *) iter->src_handle.c)->collection.elem_size;
616
af7d8a29fbc5 #219 array list: add iterator
Mike Becker <universe@uap-core.de>
parents: 615
diff changeset
938 }
af7d8a29fbc5 #219 array list: add iterator
Mike Becker <universe@uap-core.de>
parents: 615
diff changeset
939 }
af7d8a29fbc5 #219 array list: add iterator
Mike Becker <universe@uap-core.de>
parents: 615
diff changeset
940
655
7340c4255f1f implement backwards iterator - fixes #238
Mike Becker <universe@uap-core.de>
parents: 654
diff changeset
941 static void cx_arl_iter_prev(void *it) {
853
d4baf4dd55c3 simplify iterator structures
Mike Becker <universe@uap-core.de>
parents: 850
diff changeset
942 struct cx_iterator_s *iter = it;
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 889
diff changeset
943 const cx_array_list *list = iter->src_handle.c;
854
fe0d69d72bcd fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents: 853
diff changeset
944 if (iter->base.remove) {
fe0d69d72bcd fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents: 853
diff changeset
945 iter->base.remove = false;
919
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
946 cx_arl_remove(iter->src_handle.m, iter->index, 1, NULL);
655
7340c4255f1f implement backwards iterator - fixes #238
Mike Becker <universe@uap-core.de>
parents: 654
diff changeset
947 }
7340c4255f1f implement backwards iterator - fixes #238
Mike Becker <universe@uap-core.de>
parents: 654
diff changeset
948 iter->index--;
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
949 if (iter->index < list->base.collection.size) {
655
7340c4255f1f implement backwards iterator - fixes #238
Mike Becker <universe@uap-core.de>
parents: 654
diff changeset
950 iter->elem_handle = ((char *) list->data)
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
951 + iter->index * list->base.collection.elem_size;
655
7340c4255f1f implement backwards iterator - fixes #238
Mike Becker <universe@uap-core.de>
parents: 654
diff changeset
952 }
7340c4255f1f implement backwards iterator - fixes #238
Mike Becker <universe@uap-core.de>
parents: 654
diff changeset
953 }
7340c4255f1f implement backwards iterator - fixes #238
Mike Becker <universe@uap-core.de>
parents: 654
diff changeset
954
630
ac5e7f789048 separate iterators and mutating iterators
Mike Becker <universe@uap-core.de>
parents: 629
diff changeset
955
607
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
956 static struct cx_iterator_s cx_arl_iterator(
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 889
diff changeset
957 const struct cx_list_s *list,
655
7340c4255f1f implement backwards iterator - fixes #238
Mike Becker <universe@uap-core.de>
parents: 654
diff changeset
958 size_t index,
7340c4255f1f implement backwards iterator - fixes #238
Mike Becker <universe@uap-core.de>
parents: 654
diff changeset
959 bool backwards
607
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
960 ) {
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
961 struct cx_iterator_s iter;
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
962
616
af7d8a29fbc5 #219 array list: add iterator
Mike Becker <universe@uap-core.de>
parents: 615
diff changeset
963 iter.index = index;
853
d4baf4dd55c3 simplify iterator structures
Mike Becker <universe@uap-core.de>
parents: 850
diff changeset
964 iter.src_handle.c = list;
616
af7d8a29fbc5 #219 array list: add iterator
Mike Becker <universe@uap-core.de>
parents: 615
diff changeset
965 iter.elem_handle = cx_arl_at(list, index);
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
966 iter.elem_size = list->collection.elem_size;
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
967 iter.elem_count = list->collection.size;
854
fe0d69d72bcd fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents: 853
diff changeset
968 iter.base.valid = cx_arl_iter_valid;
fe0d69d72bcd fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents: 853
diff changeset
969 iter.base.current = cx_arl_iter_current;
fe0d69d72bcd fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents: 853
diff changeset
970 iter.base.next = backwards ? cx_arl_iter_prev : cx_arl_iter_next;
fe0d69d72bcd fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents: 853
diff changeset
971 iter.base.remove = false;
fe0d69d72bcd fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents: 853
diff changeset
972 iter.base.mutating = false;
630
ac5e7f789048 separate iterators and mutating iterators
Mike Becker <universe@uap-core.de>
parents: 629
diff changeset
973
ac5e7f789048 separate iterators and mutating iterators
Mike Becker <universe@uap-core.de>
parents: 629
diff changeset
974 return iter;
ac5e7f789048 separate iterators and mutating iterators
Mike Becker <universe@uap-core.de>
parents: 629
diff changeset
975 }
616
af7d8a29fbc5 #219 array list: add iterator
Mike Becker <universe@uap-core.de>
parents: 615
diff changeset
976
607
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
977 static cx_list_class cx_array_list_class = {
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
978 cx_arl_destructor,
641
d402fead3386 add new pointer list wrapper - resolves #234
Mike Becker <universe@uap-core.de>
parents: 640
diff changeset
979 cx_arl_insert_element,
638
eafb45eefc51 add cxListInsertArray() - fixes #224
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
980 cx_arl_insert_array,
881
1dbbf8c1c42f add optimized implementation of insert_sorted for array lists
Mike Becker <universe@uap-core.de>
parents: 876
diff changeset
981 cx_arl_insert_sorted,
607
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
982 cx_arl_insert_iter,
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
983 cx_arl_remove,
664
af5bf4603a5d add cxListClear and fix missing destructor invocations - #241 #246
Mike Becker <universe@uap-core.de>
parents: 662
diff changeset
984 cx_arl_clear,
647
2e6e9d9f2159 implement swap function for list elements - fixes #218
Mike Becker <universe@uap-core.de>
parents: 643
diff changeset
985 cx_arl_swap,
607
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
986 cx_arl_at,
764
ccbdbd088455 add cxListFindRemove and cx_linked_list_find_node
Mike Becker <universe@uap-core.de>
parents: 763
diff changeset
987 cx_arl_find_remove,
607
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
988 cx_arl_sort,
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
989 cx_arl_compare,
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
990 cx_arl_reverse,
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
991 cx_arl_iterator,
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
992 };
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
993
670
4ad8ea3aee49 allow NULL for allocator and comparator
Mike Becker <universe@uap-core.de>
parents: 667
diff changeset
994 CxList *cxArrayListCreate(
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 889
diff changeset
995 const CxAllocator *allocator,
677
b09aae58bba4 refactoring of collections to make use of destructors in map implementations
Mike Becker <universe@uap-core.de>
parents: 676
diff changeset
996 cx_compare_func comparator,
855
35bcb3216c0d fix inconsistent use of item_size and elem_size
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
997 size_t elem_size,
606
314e9288af2f add array list tests
Mike Becker <universe@uap-core.de>
parents:
diff changeset
998 size_t initial_capacity
314e9288af2f add array list tests
Mike Becker <universe@uap-core.de>
parents:
diff changeset
999 ) {
670
4ad8ea3aee49 allow NULL for allocator and comparator
Mike Becker <universe@uap-core.de>
parents: 667
diff changeset
1000 if (allocator == NULL) {
4ad8ea3aee49 allow NULL for allocator and comparator
Mike Becker <universe@uap-core.de>
parents: 667
diff changeset
1001 allocator = cxDefaultAllocator;
4ad8ea3aee49 allow NULL for allocator and comparator
Mike Becker <universe@uap-core.de>
parents: 667
diff changeset
1002 }
4ad8ea3aee49 allow NULL for allocator and comparator
Mike Becker <universe@uap-core.de>
parents: 667
diff changeset
1003
607
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
1004 cx_array_list *list = cxCalloc(allocator, 1, sizeof(cx_array_list));
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
1005 if (list == NULL) return NULL;
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
1006
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
1007 list->base.cl = &cx_array_list_class;
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
1008 list->base.collection.allocator = allocator;
677
b09aae58bba4 refactoring of collections to make use of destructors in map implementations
Mike Becker <universe@uap-core.de>
parents: 676
diff changeset
1009 list->capacity = initial_capacity;
607
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
1010
855
35bcb3216c0d fix inconsistent use of item_size and elem_size
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
1011 if (elem_size > 0) {
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
1012 list->base.collection.elem_size = elem_size;
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
1013 list->base.collection.cmpfunc = comparator;
667
2f88a7c13a28 add CX_STORE_POINTERS special "item size" for lists
Mike Becker <universe@uap-core.de>
parents: 666
diff changeset
1014 } else {
855
35bcb3216c0d fix inconsistent use of item_size and elem_size
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
1015 elem_size = sizeof(void *);
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
1016 list->base.collection.cmpfunc = comparator == NULL ? cx_cmp_ptr : comparator;
667
2f88a7c13a28 add CX_STORE_POINTERS special "item size" for lists
Mike Becker <universe@uap-core.de>
parents: 666
diff changeset
1017 cxListStorePointers((CxList *) list);
2f88a7c13a28 add CX_STORE_POINTERS special "item size" for lists
Mike Becker <universe@uap-core.de>
parents: 666
diff changeset
1018 }
2f88a7c13a28 add CX_STORE_POINTERS special "item size" for lists
Mike Becker <universe@uap-core.de>
parents: 666
diff changeset
1019
855
35bcb3216c0d fix inconsistent use of item_size and elem_size
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
1020 // allocate the array after the real elem_size is known
35bcb3216c0d fix inconsistent use of item_size and elem_size
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
1021 list->data = cxCalloc(allocator, initial_capacity, elem_size);
676
d0680a23d850 fix initial storage allocation for array lists created with CX_STORE_POINTERS
Mike Becker <universe@uap-core.de>
parents: 670
diff changeset
1022 if (list->data == NULL) {
d0680a23d850 fix initial storage allocation for array lists created with CX_STORE_POINTERS
Mike Becker <universe@uap-core.de>
parents: 670
diff changeset
1023 cxFree(allocator, list);
d0680a23d850 fix initial storage allocation for array lists created with CX_STORE_POINTERS
Mike Becker <universe@uap-core.de>
parents: 670
diff changeset
1024 return NULL;
d0680a23d850 fix initial storage allocation for array lists created with CX_STORE_POINTERS
Mike Becker <universe@uap-core.de>
parents: 670
diff changeset
1025 }
d0680a23d850 fix initial storage allocation for array lists created with CX_STORE_POINTERS
Mike Becker <universe@uap-core.de>
parents: 670
diff changeset
1026
628
1e2be40f0cb5 use //-style single line comments everywhere
Mike Becker <universe@uap-core.de>
parents: 627
diff changeset
1027 // configure the reallocator
953
581ad4fd01e9 add function to create array reallocator that can move arrays from stack to heap
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
1028 list->reallocator = cx_array_reallocator(allocator, NULL);
610
de5d3ee6435f #219 array list: implement add and at
Mike Becker <universe@uap-core.de>
parents: 607
diff changeset
1029
607
2d99e978dc34 implement array list ctor and dtor
Mike Becker <universe@uap-core.de>
parents: 606
diff changeset
1030 return (CxList *) list;
606
314e9288af2f add array list tests
Mike Becker <universe@uap-core.de>
parents:
diff changeset
1031 }

mercurial