1 /******************************************************** 2 Array Library, a simple module for handling arrays of data 3 4 Copyright (C) 2007-2014 Brian Langenberger 5 6 The Array Library is free software; you can redistribute it and/or modify 7 it under the terms of either: 8 9 * the GNU Lesser General Public License as published by the Free 10 Software Foundation; either version 3 of the License, or (at your 11 option) any later version. 12 13 or 14 15 * the GNU General Public License as published by the Free Software 16 Foundation; either version 2 of the License, or (at your option) any 17 later version. 18 19 or both in parallel, as here. 20 21 The Array Library is distributed in the hope that it will be useful, but 22 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 23 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 24 for more details. 25 26 You should have received copies of the GNU General Public License and the 27 GNU Lesser General Public License along with the GNU MP Library. If not, 28 see https://www.gnu.org/licenses/. 29 *******************************************************/ 30 31 #ifndef __ARRAYLIB_H__ 32 #define __ARRAYLIB_H__ 33 34 #include <stdarg.h> 35 #include <stdio.h> 36 37 /*arrays are thin wrappers around malloc'ed data 38 in order to provide a consistent interface for common array operations 39 40 all have a "_" attribute to access the array's raw data, 41 an unsigned "len" attribute for the array's current size 42 and various methods to perform array-wise operations 43 44 for example: 45 46 int total = 0; 47 a_int* a = a_int_new(); //initialize a new integer array 48 a->vappend(a, 3, 1, 2, 3); //append three integer values 49 for (i = 0; i < a->len; i++) { //iterate over the array 50 total += a->_[i]; //sum the values in the array 51 } 52 a->print(a, stdout); //display the array 53 a->del(a); //deallocate it once finished 54 55 by providing internal methods with consistent naming, 56 one doesn't have to remember different function names 57 to perform the same function on arrays of different types 58 */ 59 60 61 /*appends a single value to the given array 62 "array" is evaluated twice, while "value" is evaluated only once 63 this presumes array has been resized in advance for additional items: 64 65 array->reset_for(array, count); 66 for (i = 0; i < count; i++) 67 a_append(array, data[i]); 68 69 it works equally well for array_i and array_f 70 */ 71 #define a_append(array, value)((array)->_[(array)->len++] = (value)) 72 73 74 /******************************************************************/ 75 /*arrays of plain C primitives such as int, double, unsigned, etc.*/ 76 /******************************************************************/ 77 78 #define ARRAY_TYPE_DEFINITION(TYPE, CONTENT_TYPE, LINK_TYPE) \ 79 struct LINK_TYPE##_s; \ 80 struct TYPE##_s { \ 81 CONTENT_TYPE *_; \ 82 unsigned len; \ 83 unsigned total_size; \ 84 \ 85 /*deletes the array and any allocated data it contains*/ \ 86 void (*del)(struct TYPE##_s *self); \ 87 \ 88 /*resizes the array to fit at least "minimum" items*/ \ 89 void (*resize)(struct TYPE##_s *self, unsigned minimum); \ 90 \ 91 /*resizes the array to fit "additional_items"*/ \ 92 void (*resize_for)(struct TYPE##_s *self, \ 93 unsigned additional_items); \ 94 \ 95 /*deletes any data in the array and resets its contents*/ \ 96 /*so that it can be re-populated with new data*/ \ 97 void (*reset)(struct TYPE##_s *self); \ 98 \ 99 /*deletes any data in the array,*/ \ 100 /*resizes its contents to fit "minimum" number of items,*/ \ 101 /*and resets it contents so it can be re-populated*/ \ 102 void (*reset_for)(struct TYPE##_s *self, \ 103 unsigned minimum); \ 104 \ 105 /*appends a single value to the array*/ \ 106 void (*append)(struct TYPE##_s *self, CONTENT_TYPE value); \ 107 \ 108 /*appends several values to the array*/ \ 109 void (*vappend)(struct TYPE##_s *self, unsigned count, ...); \ 110 \ 111 /*appends "value", "count" number of times*/ \ 112 void (*mappend)(struct TYPE##_s *self, unsigned count, \ 113 CONTENT_TYPE value); \ 114 \ 115 void (*insert)(struct TYPE##_s *self, unsigned index, \ 116 CONTENT_TYPE value); \ 117 \ 118 /*sets the array to new values, removing any old ones*/ \ 119 void (*vset)(struct TYPE##_s *self, unsigned count, ...); \ 120 \ 121 /*sets the array to single values, removing any old ones*/ \ 122 void (*mset)(struct TYPE##_s *self, unsigned count, \ 123 CONTENT_TYPE value); \ 124 \ 125 /*appends all the items in "to_add" to this array*/ \ 126 void (*extend)(struct TYPE##_s *self, \ 127 const struct TYPE##_s *to_add); \ 128 \ 129 /*returns 1 if all items in array equal those in compare,*/ \ 130 /*returns 0 if not*/ \ 131 int (*equals)(const struct TYPE##_s *self, \ 132 const struct TYPE##_s *compare); \ 133 \ 134 /*returns the smallest value in the array,*/ \ 135 /*or INT_MAX if the array is empty*/ \ 136 CONTENT_TYPE (*min)(const struct TYPE##_s *self); \ 137 \ 138 /*returns the largest value in the array,*/ \ 139 /*or INT_MIN if the array is empty*/ \ 140 CONTENT_TYPE (*max)(const struct TYPE##_s *self); \ 141 \ 142 /*returns the sum of all items in the array*/ \ 143 CONTENT_TYPE (*sum)(const struct TYPE##_s *self); \ 144 \ 145 /*makes "copy" a duplicate of this array*/ \ 146 void (*copy)(const struct TYPE##_s *self, \ 147 struct TYPE##_s *copy); \ 148 \ 149 /*links the contents of this array to a read-only array*/ \ 150 void (*link)(const struct TYPE##_s *self, \ 151 struct LINK_TYPE##_s *link); \ 152 \ 153 /*swaps the contents of this array with another array*/ \ 154 void (*swap)(struct TYPE##_s *self, struct TYPE##_s *swap); \ 155 \ 156 /*moves "count" number of items from the start of this array*/ \ 157 /*to "head", or as many as possible*/ \ 158 void (*head)(const struct TYPE##_s *self, unsigned count, \ 159 struct TYPE##_s *head); \ 160 \ 161 /*moves "count" number of items from the end of this array*/ \ 162 /*to "tail", or as many as possible*/ \ 163 void (*tail)(const struct TYPE##_s *self, unsigned count, \ 164 struct TYPE##_s *tail); \ 165 \ 166 /*moves all except the first "count" number of items*/ \ 167 /*from this array to "tail", or as many as possible*/ \ 168 void (*de_head)(const struct TYPE##_s *self, unsigned count, \ 169 struct TYPE##_s *tail); \ 170 \ 171 /*moves all except the last "count" number of items*/ \ 172 /*from this array to "head", or as many as possible*/ \ 173 void (*de_tail)(const struct TYPE##_s *self, unsigned count, \ 174 struct TYPE##_s *head); \ 175 \ 176 /*splits the array into "head" and "tail" arrays*/ \ 177 /*such that "head" contains a copy of up to "count" items*/ \ 178 /*while "tail" contains the rest*/ \ 179 void (*split)(const struct TYPE##_s *self, unsigned count, \ 180 struct TYPE##_s *head, struct TYPE##_s *tail); \ 181 \ 182 /*concatenates "self" and "tail" into a single array*/ \ 183 /*and places the result in "combined"*/ \ 184 void (*concat)(const struct TYPE##_s *self, \ 185 const struct TYPE##_s *tail, \ 186 struct TYPE##_s *combined); \ 187 \ 188 /*reverses the items in the array*/ \ 189 void (*reverse)(struct TYPE##_s *self); \ 190 \ 191 /*sorts the items in the array*/ \ 192 void (*sort)(struct TYPE##_s *self); \ 193 \ 194 void (*print)(const struct TYPE##_s *self, FILE* output); \ 195 }; \ 196 typedef struct TYPE##_s TYPE; \ 197 \ 198 struct LINK_TYPE##_s { \ 199 const CONTENT_TYPE *_; \ 200 unsigned len; \ 201 \ 202 /*deletes the array and any allocated data it contains*/ \ 203 void (*del)(struct LINK_TYPE##_s *self); \ 204 \ 205 /*deletes any data in the array and resets its contents*/ \ 206 /*so that it can be linked to new data*/ \ 207 void (*reset)(struct LINK_TYPE##_s *self); \ 208 \ 209 /*returns 1 if all items in array equal those in compare,*/ \ 210 /*returns 0 if not*/ \ 211 int (*equals)(const struct LINK_TYPE##_s *self, \ 212 const struct LINK_TYPE##_s *compare); \ 213 \ 214 /*returns the smallest value in the array,*/ \ 215 CONTENT_TYPE (*min)(const struct LINK_TYPE##_s *self); \ 216 \ 217 /*returns the largest value in the array,*/ \ 218 CONTENT_TYPE (*max)(const struct LINK_TYPE##_s *self); \ 219 \ 220 /*returns the sum of all items in the array*/ \ 221 CONTENT_TYPE (*sum)(const struct LINK_TYPE##_s *self); \ 222 \ 223 /*makes "copy" a duplicate of this array*/ \ 224 void (*copy)(const struct LINK_TYPE##_s *self, \ 225 struct TYPE##_s *copy); \ 226 \ 227 /*links the contents of this array to a read-only array*/ \ 228 void (*link)(const struct LINK_TYPE##_s *self, \ 229 struct LINK_TYPE##_s *link); \ 230 \ 231 /*swaps the contents of this array with another array*/ \ 232 void (*swap)(struct LINK_TYPE##_s *self, \ 233 struct LINK_TYPE##_s *swap); \ 234 \ 235 /*moves "count" number of items from the start of this array*/ \ 236 /*to "head", or as many as possible*/ \ 237 void (*head)(const struct LINK_TYPE##_s *self, unsigned count, \ 238 struct LINK_TYPE##_s *head); \ 239 \ 240 /*moves "count" number of items from the start of this array*/ \ 241 /*to "head", or as many as possible*/ \ 242 void (*tail)(const struct LINK_TYPE##_s *self, unsigned count, \ 243 struct LINK_TYPE##_s *tail); \ 244 \ 245 /*moves all except the first "count" number of items*/ \ 246 /*from this array to "tail", or as many as possible*/ \ 247 void (*de_head)(const struct LINK_TYPE##_s *self, unsigned count, \ 248 struct LINK_TYPE##_s *tail); \ 249 \ 250 /*moves all except the last "count" number of items*/ \ 251 /*from this array to "head", or as many as possible*/ \ 252 void (*de_tail)(const struct LINK_TYPE##_s *self, unsigned count, \ 253 struct LINK_TYPE##_s *head); \ 254 \ 255 /*splits the array into "head" and "tail" arrays*/ \ 256 /*such that "head" contains a copy of up to "count" items*/ \ 257 /*while "tail" contains the rest*/ \ 258 void (*split)(const struct LINK_TYPE##_s *self, unsigned count, \ 259 struct LINK_TYPE##_s *head, struct LINK_TYPE##_s *tail); \ 260 \ 261 void (*print)(const struct LINK_TYPE##_s *self, FILE* output); \ 262 }; \ 263 typedef struct LINK_TYPE##_s LINK_TYPE; \ 264 \ 265 struct TYPE##_s* \ 266 TYPE##_new(void); \ 267 \ 268 LINK_TYPE* \ 269 LINK_TYPE##_new(void); 270 271 ARRAY_TYPE_DEFINITION(a_int, int, l_int) 272 ARRAY_TYPE_DEFINITION(a_double, double, l_double) 273 ARRAY_TYPE_DEFINITION(a_unsigned, unsigned, l_unsigned) 274 275 276 /******************************************************************/ 277 /* arrays of arrays such as a_int, a_double etc. */ 278 /******************************************************************/ 279 280 #define ARRAY_A_TYPE_DEFINITION(TYPE, ARRAY_TYPE) \ 281 struct TYPE##_s { \ 282 struct ARRAY_TYPE##_s **_; \ 283 unsigned len; \ 284 unsigned total_size; \ 285 \ 286 /*deletes the array and any allocated data it contains*/ \ 287 void (*del)(struct TYPE##_s *self); \ 288 \ 289 /*resizes the array to fit at least "minimum" items*/ \ 290 void (*resize)(struct TYPE##_s *self, unsigned minimum); \ 291 \ 292 /*deletes any data in the array and resets its contents*/ \ 293 /*so that it can be re-populated with new data*/ \ 294 void (*reset)(struct TYPE##_s *self); \ 295 \ 296 /*returns a freshly appended array which values can be added to*/ \ 297 /*this array should *not* be deleted once it is done being used*/ \ 298 struct ARRAY_TYPE##_s* (*append)(struct TYPE##_s *self); \ 299 \ 300 /*appends all the items in "to_add" to this array*/ \ 301 void (*extend)(struct TYPE##_s *self, \ 302 const struct TYPE##_s *to_add); \ 303 \ 304 /*returns 1 if all items in array equal those in compare,*/ \ 305 /*returns 0 if not*/ \ 306 int (*equals)(const struct TYPE##_s *self, \ 307 const struct TYPE##_s *compare); \ 308 \ 309 /*makes "copy" a duplicate of this array*/ \ 310 void (*copy)(const struct TYPE##_s *self, struct TYPE##_s *copy); \ 311 \ 312 /*swaps the contents of this array with another array*/ \ 313 void (*swap)(struct TYPE##_s *self, struct TYPE##_s *swap); \ 314 \ 315 /*splits the array into "head" and "tail" arrays*/ \ 316 /*such that "head" contains a copy of up to "count" items*/ \ 317 /*while "tail" contains the rest*/ \ 318 void (*split)(const struct TYPE##_s *self, unsigned count, \ 319 struct TYPE##_s *head, struct TYPE##_s *tail); \ 320 \ 321 /*splits each sub-array into "head" and "tail" arrays*/ \ 322 /*such that each "head" contains a copy of up to "count" items*/ \ 323 /*while each "tail" contains the rest*/ \ 324 void (*cross_split)(const struct TYPE##_s *self, unsigned count, \ 325 struct TYPE##_s *head, struct TYPE##_s *tail); \ 326 \ 327 /*reverses the items in the array*/ \ 328 void (*reverse)(struct TYPE##_s *self); \ 329 \ 330 void (*print)(const struct TYPE##_s *self, FILE* output); \ 331 }; \ 332 typedef struct TYPE##_s TYPE; \ 333 \ 334 TYPE* \ 335 TYPE##_new(void); 336 337 ARRAY_A_TYPE_DEFINITION(aa_int, a_int) 338 ARRAY_A_TYPE_DEFINITION(aa_double, a_double) 339 ARRAY_A_TYPE_DEFINITION(al_int, l_int) 340 ARRAY_A_TYPE_DEFINITION(al_double, l_double) 341 342 /******************************************************************/ 343 /* arrays of arrays of arrays such as aa_int, aa_double, etc. */ 344 /******************************************************************/ 345 346 #define ARRAY_AA_TYPE_DEFINITION(TYPE, ARRAY_TYPE) \ 347 struct TYPE##_s { \ 348 struct ARRAY_TYPE##_s **_; \ 349 unsigned len; \ 350 unsigned total_size; \ 351 \ 352 /*deletes the array and any allocated data it contains*/ \ 353 void (*del)(struct TYPE##_s *self); \ 354 \ 355 /*resizes the array to fit at least "minimum" items*/ \ 356 void (*resize)(struct TYPE##_s *self, unsigned minimum); \ 357 \ 358 /*deletes any data in the array and resets its contents*/ \ 359 /*so that it can be re-populated with new data*/ \ 360 void (*reset)(struct TYPE##_s *self); \ 361 \ 362 /*returns a freshly appended array_i which values can be added to*/ \ 363 /*this array should *not* be deleted once it is done being used*/ \ 364 struct ARRAY_TYPE##_s* (*append)(struct TYPE##_s *self); \ 365 \ 366 /*appends all the items in "to_add" to this array*/ \ 367 void (*extend)(struct TYPE##_s *self, \ 368 const struct TYPE##_s *to_add); \ 369 \ 370 /*returns 1 if all items in array equal those in compare,*/ \ 371 /*returns 0 if not*/ \ 372 int (*equals)(const struct TYPE##_s *self, \ 373 const struct TYPE##_s *compare); \ 374 \ 375 /*makes "copy" a duplicate of this array*/ \ 376 void (*copy)(const struct TYPE##_s *self, \ 377 struct TYPE##_s *copy); \ 378 \ 379 /*swaps the contents of this array with another array*/ \ 380 void (*swap)(struct TYPE##_s *self, struct TYPE##_s *swap); \ 381 \ 382 /*splits the array into "head" and "tail" arrays*/ \ 383 /*such that "head" contains a copy of up to "count" items*/ \ 384 /*while "tail" contains the rest*/ \ 385 void (*split)(const struct TYPE##_s *self, unsigned count, \ 386 struct TYPE##_s *head, struct TYPE##_s *tail); \ 387 \ 388 /*reverses the items in the array*/ \ 389 void (*reverse)(struct TYPE##_s *self); \ 390 \ 391 void (*print)(const struct TYPE##_s *self, FILE* output); \ 392 }; \ 393 typedef struct TYPE##_s TYPE; \ 394 \ 395 struct TYPE##_s* \ 396 TYPE##_new(void); 397 398 ARRAY_AA_TYPE_DEFINITION(aaa_int, aa_int) 399 ARRAY_AA_TYPE_DEFINITION(aaa_double, aa_double) 400 401 /*************************************************************** 402 * object arrays * 403 * [ptr1*, ptr2*, ptr3*, ...] * 404 ***************************************************************/ 405 406 struct a_obj_s { 407 void **_; 408 unsigned len; 409 unsigned total_size; 410 411 /*called when an object is duplicated between arrays*/ 412 void* (*copy_obj)(void* obj); 413 414 /*called when an object is removed from the array 415 may be NULL, meaning no free is performed*/ 416 void (*free_obj)(void* obj); 417 418 /*called by the a->print(a, FILE) method to display an object 419 may be NULL, meaning some default is printed*/ 420 void (*print_obj)(void* obj, FILE* output); 421 422 /*deletes the array and any allocated data it contains*/ 423 void (*del)(struct a_obj_s *self); 424 425 /*resizes the array to fit at least "minimum" number of items, 426 if necessary*/ 427 void (*resize)(struct a_obj_s *self, unsigned minimum); 428 429 /*resizes the array to fit "additional_items" number of new items, 430 if necessary*/ 431 void (*resize_for)(struct a_obj_s *self, unsigned additional_items); 432 433 /*deletes any data in the array and resets its contents 434 so that it can be re-populated with new data*/ 435 void (*reset)(struct a_obj_s *self); 436 437 /*deletes any data in the array, 438 resizes its contents to fit "minimum" number of items, 439 and resets it contents so it can be re-populated with new data*/ 440 void (*reset_for)(struct a_obj_s *self, unsigned minimum); 441 442 /*appends a single value to the array*/ 443 void (*append)(struct a_obj_s *self, void* value); 444 445 /*appends several values to the array*/ 446 void (*vappend)(struct a_obj_s *self, unsigned count, ...); 447 448 /*appends "value", "count" number of times*/ 449 void (*mappend)(struct a_obj_s *self, unsigned count, void* value); 450 451 /*deletes the item at the given index 452 and sets it to the new value*/ 453 void (*set)(struct a_obj_s *self, unsigned index, void* value); 454 455 /*sets the array to new values, removing any old ones*/ 456 void (*vset)(struct a_obj_s *self, unsigned count, ...); 457 458 /*sets the array to single values, removing any old ones*/ 459 void (*mset)(struct a_obj_s *self, unsigned count, void* value); 460 461 /*appends all the items in "to_add" to this array*/ 462 void (*extend)(struct a_obj_s *self, const struct a_obj_s *to_add); 463 464 /*makes "copy" a duplicate of this array*/ 465 void (*copy)(const struct a_obj_s *self, struct a_obj_s *copy); 466 467 /*swaps the contents of this array with another array*/ 468 void (*swap)(struct a_obj_s *self, struct a_obj_s *swap); 469 470 /*moves "count" number of items from the start of this array 471 to "head", or as many as possible*/ 472 void (*head)(const struct a_obj_s *self, unsigned count, 473 struct a_obj_s *head); 474 475 /*moves "count" number of items from the end of this array 476 to "tail", or as many as possible*/ 477 void (*tail)(const struct a_obj_s *self, unsigned count, 478 struct a_obj_s *tail); 479 480 /*moves all except the first "count" number of items 481 from this array to "tail", or as many as possible*/ 482 void (*de_head)(const struct a_obj_s *self, unsigned count, 483 struct a_obj_s *tail); 484 485 /*moves all except the last "count" number of items 486 from this array to "head", or as many as possible*/ 487 void (*de_tail)(const struct a_obj_s *self, unsigned count, 488 struct a_obj_s *head); 489 490 /*splits the array into "head" and "tail" arrays 491 such that "head" contains a copy of up to "count" items 492 while "tail" contains the rest*/ 493 void (*split)(const struct a_obj_s *self, unsigned count, 494 struct a_obj_s *head, struct a_obj_s *tail); 495 496 /*concatenates "array" and "tail" into a single array*/ 497 /*and places the result in "combined"*/ 498 void (*concat)(const struct a_obj_s *self, 499 const struct a_obj_s *tail, 500 struct a_obj_s *combined); 501 502 void (*print)(const struct a_obj_s *self, FILE* output); 503 }; 504 505 typedef struct a_obj_s a_obj; 506 507 typedef void* (*ARRAY_COPY_FUNC)(void* obj); 508 typedef void (*ARRAY_FREE_FUNC)(void* obj); 509 typedef void (*ARRAY_PRINT_FUNC)(void* obj, FILE* output); 510 511 /*some placeholder functions for a_obj objects*/ 512 void* 513 a_obj_dummy_copy(void* obj); 514 void 515 a_obj_dummy_free(void* obj); 516 void 517 a_obj_dummy_print(void* obj, FILE* output); 518 519 /*copy, free and print functions may be NULL, 520 indicating no copy, free or print operations are necessary for object*/ 521 a_obj* 522 a_obj_new(void* (*copy)(void* obj), 523 void (*free)(void* obj), 524 void (*print)(void* obj, FILE* output)); 525 526 #endif 527