1 /*
2 *
3 * Copyright (C) 2012-2018 by C.H. Huang
4 * plushuang.tw@gmail.com
5 *
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Lesser General Public
8 * License as published by the Free Software Foundation; either
9 * version 2.1 of the License, or (at your option) any later version.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
19 *
20 * ---
21 *
22 * In addition, as a special exception, the copyright holders give
23 * permission to link the code of portions of this program with the
24 * OpenSSL library under certain conditions as described in each
25 * individual source file, and distribute linked combinations
26 * including the two.
27 * You must obey the GNU Lesser General Public License in all respects
28 * for all of the code used other than OpenSSL. If you modify
29 * file(s) with this exception, you may extend this exception to your
30 * version of the file(s), but you are not obligated to do so. If you
31 * do not wish to do so, delete this exception statement from your
32 * version. If you delete this exception statement from all source
33 * files in the program, then also delete it here.
34 *
35 */
36
37 #ifndef UG_ARRAY_H
38 #define UG_ARRAY_H
39
40 // uintptr_t is an unsigned int that is guaranteed to be the same size as a pointer.
41 #include <stdint.h> // uintptr_t, int64_t
42 #include <stdlib.h> // qsort(), malloc(), free()
43 #include <string.h> // memmove()
44 #include <UgJson.h>
45 #include <UgEntry.h>
46
47 #ifdef __cplusplus
48 extern "C" {
49 #endif
50
51 // ----------------------------------------------------------------------------
52 // UgArray functions
53
54 void ug_array_init(void* array, int element_size, int allocated_len);
55 void ug_array_clear(void* array);
56 void* ug_array_alloc(void* array, int nElements);
57 void ug_array_foreach(void* array, UgForeachFunc func, void* data);
58 void ug_array_foreach_ptr(void* array, UgForeachFunc func, void* data);
59
60 // Binary search for sorted array
61 void* ug_array_find_sorted(void* array, const void* key,
62 UgCompareFunc func, int* index);
63
64 #define ug_array_foreach_str ug_array_foreach_ptr
65
66 #define ug_array_count(array, length) \
67 ( ((UgArrayChar*)(array))->element_size * (length) )
68
69 #define ug_array_addr(array, index) \
70 ( ((UgArrayChar*)(array))->at + ((UgArrayChar*)(array))->element_size * (index) )
71
72 #define ug_array_length(array) \
73 ( ((UgArrayChar*)(array))->length )
74
75 #define ug_array_allocated(array) \
76 ( ((UgArrayChar*)(array))->allocated )
77
78 #define ug_array_element_size(array) \
79 ( ((UgArrayChar*)(array))->element_size )
80
81 // Binary search:
82 // int compareFunc(const void *s1, const void *s2);
83 #define ug_array_bsearch(array, key, compareFunc) \
84 bsearch(key, (array)->at, (array)->length, (array)->element_size, compareFunc)
85
86 #define ug_array_append(array, values, len) \
87 memcpy(ug_array_alloc((array), len), values, ((UgArrayChar*)(array))->element_size * len)
88
89 #define ug_array_terminate0(array) \
90 memset(ug_array_alloc((array), 1), 0, ((UgArrayChar*)(array))->element_size)
91
92 #define ug_array_end0(array) \
93 *((char*) ug_array_alloc((array), 1)) = 0
94
95 int ug_array_compare_int(const void *s1, const void *s2);
96 int ug_array_compare_string(const void *s1, const void *s2);
97 int ug_array_compare_pointer(const void *s1, const void *s2);
98
99 #ifdef __cplusplus
100 }
101 #endif
102
103 // ----------------------------------------------------------------------------
104 // UgArrayMethod : a template C++ struct is used by UgArray and it's children.
105
106 #ifdef __cplusplus
107
108 // These definitions are used by UgArrayMethod
109 inline void* ug_array_insert(void* array, int index, int length);
110 inline void ug_array_erase(void* array, int index, int length);
111 inline void ug_array_sort(void* array, UgCompareFunc func);
112
113 // This one is for derived use only, no data members here.
114 // This one is NOT for directly use only, it must has UgArray data members.
115 // Your derived struct/class must be C++11 standard-layout.
116 template<class Type> struct UgArrayMethod
117 {
initUgArrayMethod118 inline void init(int allocated_len)
119 { ug_array_init(this, sizeof(Type), allocated_len); }
clearUgArrayMethod120 inline void clear(void)
121 { ug_array_clear(this); }
122
allocUgArrayMethod123 inline Type* alloc(int nElements)
124 { return (Type*) ug_array_alloc(this, nElements); }
eraseUgArrayMethod125 inline Type* erase(int index, int nElements)
126 { return (Type*) ug_array_erase(this, index, nElements); }
insertUgArrayMethod127 inline Type* insert(int index, int nElements)
128 { return (Type*) ug_array_insert(this, index, nElements); }
129
sortUgArrayMethod130 inline void sort(UgCompareFunc func)
131 { ug_array_sort(this, func); }
findSortedUgArrayMethod132 inline Type* findSorted(const Type* key, UgCompareFunc func, int* index)
133 { return (Type*) ug_array_find_sorted(this, key, func, index); }
findSortedUgArrayMethod134 inline Type* findSorted(const Type& key, UgCompareFunc func, int* index)
135 { return (Type*) ug_array_find_sorted(this, &key, func, index); }
136
137 // for specialization
138 void sort();
139 Type* findSorted(Type key, int* index);
140 };
141
142 // template specialization
sort()143 template<> inline void UgArrayMethod<int>::sort()
144 {
145 ug_array_sort(this, ug_array_compare_int);
146 };
147
findSorted(int key,int * index)148 template<> inline int* UgArrayMethod<int>::findSorted(int key, int* index)
149 {
150 int value = key;
151 return (int*) ug_array_find_sorted(this, &value, ug_array_compare_int, index);
152 };
153
sort()154 template<> inline void UgArrayMethod<char*>::sort()
155 {
156 ug_array_sort(this, ug_array_compare_string);
157 };
158
findSorted(char * key,int * index)159 template<> inline char** UgArrayMethod<char*>::findSorted(char* key, int* index)
160 {
161 return (char**) ug_array_find_sorted(this, &key, ug_array_compare_string, index);
162 };
163
sort()164 template<> inline void UgArrayMethod<void*>::sort()
165 {
166 ug_array_sort(this, ug_array_compare_pointer);
167 };
168
findSorted(void * key,int * index)169 template<> inline void** UgArrayMethod<void*>::findSorted(void* key, int* index)
170 {
171 return (void**) ug_array_find_sorted(this, &key, ug_array_compare_pointer, index);
172 };
173 #endif // __cplusplus
174
175 // ----------------------------------------------------------------------------
176 // UgArray is a template array. It used by UgEntry with UG_ENTRY_ARRAY.
177
178 #define UG_ARRAY_MEMBERS(Type) \
179 Type* at; \
180 int length; \
181 int allocated; \
182 int element_size
183
184 #ifdef __cplusplus
185 // C++ template works with C macro
186 template<class Type>
187 struct UgArray : UgArrayMethod<Type>
188 {
189 UG_ARRAY_MEMBERS(Type);
190 /* // ------ UgArray members ------
191 Type* at;
192 int length;
193 int allocated;
194 int element_size;
195 */
196 };
197 #define UG_ARRAY(Type) struct UgArray<Type>
198 #else
199 // implement C++ template by C macro
200 #define UG_ARRAY(Type) struct { UG_ARRAY_MEMBERS(Type); }
201 #endif // __cplusplus
202
203 typedef UG_ARRAY(char) UgArrayChar;
204 typedef UG_ARRAY(char*) UgArrayStr;
205 typedef UG_ARRAY(void*) UgArrayPtr;
206 typedef UG_ARRAY(int) UgArrayInt;
207 typedef UG_ARRAY(unsigned int) UgArrayUint;
208 typedef UG_ARRAY(int64_t) UgArrayInt64;
209 typedef UG_ARRAY(double) UgArrayDouble;
210
211 // ----------------------------------------------------------------------------
212 // C/C++ inline function
213
214 #if (defined(__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L)) || defined(__cplusplus)
215 // C99 or C++ inline functions
216
217 #ifdef __cplusplus // C++
218 inline
219 #else // C99
220 static inline
221 #endif
ug_array_insert(void * array,int index,int length)222 void* ug_array_insert(void* array, int index, int length)
223 {
224 char* addr;
225 ug_array_alloc(array, length);
226 memmove(ug_array_addr(array, index + length),
227 addr = ug_array_addr(array, index),
228 ug_array_count(array, ug_array_length(array) - index - 1));
229 return (void*)addr;
230 }
231
232 #ifdef __cplusplus // C++
233 inline
234 #else // C99
235 static inline
236 #endif
ug_array_erase(void * array,int index,int length)237 void ug_array_erase(void* array, int index, int length)
238 {
239 memmove(ug_array_addr(array, index),
240 ug_array_addr(array, index + length),
241 ug_array_count(array, ug_array_length(array) - index - 1));
242 ((UgArrayChar*)array)->length -= length;
243 }
244
245 #ifdef __cplusplus // C++
246 inline
247 #else // C99
248 static inline
249 #endif
ug_array_sort(void * array,UgCompareFunc compare)250 void ug_array_sort(void* array, UgCompareFunc compare)
251 {
252 qsort( ((UgArrayChar*)array)->at, ((UgArrayChar*)array)->length,
253 ((UgArrayChar*)array)->element_size, compare);
254 }
255
256 #else
257 // C functions
258 void* ug_array_insert(void* array, int index, int length);
259 void ug_array_erase(void* array, int index, int length);
260 void ug_array_sort(void* array, UgCompareFunc func); // Quick sort
261
262 #endif // __STDC_VERSION__ || __cplusplus
263
264 // ----------------------------------------------------------------------------
265 // UgJsonParseFunc for JSON array elements
266 UgJsonError ug_json_parse_array_bool(UgJson* json,
267 const char* name, const char* value,
268 void* array, void* none);
269 UgJsonError ug_json_parse_array_int(UgJson* json,
270 const char* name, const char* value,
271 void* array, void* none);
272 UgJsonError ug_json_parse_array_uint(UgJson* json,
273 const char* name, const char* value,
274 void* array, void* none);
275 UgJsonError ug_json_parse_array_int64(UgJson* json,
276 const char* name, const char* value,
277 void* array, void* none);
278 UgJsonError ug_json_parse_array_double(UgJson* json,
279 const char* name, const char* value,
280 void* array, void* none);
281 UgJsonError ug_json_parse_array_string(UgJson* json,
282 const char* name, const char* value,
283 void* array, void* none);
284
285 // ----------------------------------------------------------------------------
286 // write JSON array elements
287 void ug_json_write_array_bool(UgJson* json, UgArrayInt* array);
288 void ug_json_write_array_int(UgJson* json, UgArrayInt* array);
289 void ug_json_write_array_uint(UgJson* json, UgArrayUint* array);
290 void ug_json_write_array_int64(UgJson* json, UgArrayInt64* array);
291 void ug_json_write_array_double(UgJson* json, UgArrayDouble* array);
292 void ug_json_write_array_string(UgJson* json, UgArrayStr* array);
293
294 // ----------------------------------------------------------------------------
295 // C++11 standard-layout
296
297 #ifdef __cplusplus
298
299 namespace Ug
300 {
301 // Your derived struct/class must be C++11 standard-layout.
302 template<class Type> struct ArrayMethod : UgArrayMethod<Type> {};
303 template<class Type> struct Array : UgArray<Type>
304 {
305 // inline Array<Type>(int allocated_len = 0)
306 // { ug_array_init(this, sizeof(Type), allocated_len); }
307 // inline ~Array<Type>(void)
308 // { ug_array_clear(this); }
309 };
310
311 }; // namespace Ug
312
313 #endif // __cplusplus
314
315
316 #endif // UG_ARRAY_H
317
318