Arrays and strings are simple things. Made simpler in c

  • By being safe: buffer overflow and other errors give clear messages
  • generic: arrays can have any datatype
  • fast: optionally uses less memory too
  • and simple: as first priority
Quick example:
char* arr = NULL;
aAppend(&arr, 'I', ' ', 'w', 'a', 'n', 't');
aMap(arr, capitalize_char); // capitializes each char
arr[3] = 'O';        // standard assignment
aAt2(arr, 5, ' ');   // same as arr[5] = ' ', but overflow safe
// Append a null terminated array and 5 items from a second array
aAppendArray(&arr, SIZE_MAX, "chunky ", 5, "bacon, francis");
// At position 0 replace 1 item with a null terminated array
aReplaceArray(&arr, 0, 1, SIZE_MAX, "Everyone");
aWrite(stdout, arr); // prints "Everyone WON chunky bacon"
aFree(&arr);

The char* could equally be int* or any other datatype; and still be a transparent drop in for c arrays and malloc/free

Some disadvantages are

  • It is impossible to implement aArray without macros. They are side-effect safe, and pre-reduced; so you see the minimum. But compiler messages due to missing commas, or type mismatches can be very unhelpful. Thankfully these are easy to fix, and more problematic errors, such as buffer overflow, are clear and you can extend them with backtraces:
example_error.c:300: removal is out of bounds (length=10 but pos=8 removal=30)
  • This library has also only been used in a few programs, though it passes many unittests, valgrind, has been fuzzed, and even bootstraps itself

It runs as c99 under clang, gcc, and tcc; on DragonFly, Linux, macOS, and Windows in 32 and 64bit. It compiles with -pedantic -Wall -Wextra -Weverything

It is one header, with documentation, and most happily, a FREE license

Download aArray.h or pull

You are free to do whatever you like with this

You may re-license it under any license; there is no need to give me credit

As freely as you have received, freely give — Jesus

WARRANTY:

  Things go wrong

i.e. this code is public domain, BSD, MIT, gpl, cc-0, whatever you want. Simply delete the license header and replace it with your own

Even when writing aArray, I wasn't aware it would be possible; so the library has slowly transformed over a couple of years

Here are some comments on how it all works. Many implementation details come from stackoverflow, bithacks, hackersdelight, BonzaiThePenguin, and the initial idea from sglib

How can c functions take an unknown number of arguments?

Normally functions with a variable number of arguments need a marker to show how many arguments they're given, such as with stdargs.h or varargs.h

aArray functions don't need a marker, yet their number of arguments is known. Allowing them to be allocated and memcpy'd in one go, rather than iterated. This means less effort for the programmer, and a faster runtime

It is side-effect safe and done through __VA_ARGS__. This exapnds to a list of a macro's arguments, which (type[]){__VA_ARGS__} turns into an array, and sizeof((type[]){__VA_ARGS__}) / sizeof(type) uses to calculate the array length

How can c functions be polymorphic?

Different types take up different amounts of space, and so specialized functions are required for each type. But aAppend can take any type

How much space each item of an array takes can be calculated with sizeofType = sizeof(*array). So we can have a function for each type; then select the correct one with typed_functions[sizeofType] Polymorphism and variable number of arguments combine together something like this:

// get number of var-arg arguments, and make them generic
// results in:  arrayLength, (type[]){array}
#define AARRAY_Args(sizeofType, ...) \
  (sizeofType==1? sizeof((int8_t []){__VA_ARGS__}) / sizeof(int8_t ) : \
   sizeofType==2? sizeof((int16_t[]){__VA_ARGS__}) / sizeof(int16_t) : \
   sizeofType==4? sizeof((int32_t[]){__VA_ARGS__}) / sizeof(int32_t) : \
                  sizeof((int64_t[]){__VA_ARGS__}) / sizeof(int64_t)), \
  (sizeofType==1? (void*)(int8_t []){__VA_ARGS__} : \
   sizeofType==2? (void*)(int16_t[]){__VA_ARGS__} : \
   sizeofType==4? (void*)(int32_t[]){__VA_ARGS__} : \
                  (void*)(int64_t[]){__VA_ARGS__})
// select the correctly typed function from an array
#define aExample(arr, ...) \
  AARRAY_aExample_typed_functions[sizeof(*arr)](arr, \
  AARRAY_Args(sizeof(*arr), __VA_ARGS__))

This code selects which function to call, then passes it both arrayLength, and the typecast array. It should get compile time reduced to a single function call

How can aArrays be zero-indexed c arrays and aArrays at the same time?

In memory, a c array looks like {item0, item1, item2, ...}

And an aArray looks like {length, item0, item1, item2, ...}

Which can't be zero-indexed. But rather than returning a pointer to aArray's beginning, the api returns a pointer to item0; making it appear the same as an array, so long as realloc/free isn't used

Then when aArray needs to get an array's length; it simply moves the pointer back to the true beginning

How can arrays only store their length — what about their capacity?

Knowing capacity is useful, and is the normal way of doing things. But this also makes arrays larger; since an extra variable is needed for each one

Happily capacity can be safely guessed from an array's length

Capacity always grows in a fixed progression. So capacity is always one of 8, 16, 32, 64, 128, etc. This means we can assume the array's capacity is it's length rounded up to the next number in the progression, i.e. a length of 7 means the array's capacity must be at least 8, while a length of 9 fits into a capacity of 16

But if the array length drops a lot, then goes up a little; it may well cause a realloc; since the length now fits into a smaller capacity

You could call this an unnecessary realloc, or you could call not doing it an unnecessary waste of space

How does aSearch work?

aSearch is standard binary search

aSearchF_ALT though is arguably a new. I like to call it pingpong, because it works like table-tennis. The ball is secant — a poor man’s version of newton-raphson’s method — this bounces around, using the last two bounces (array lookups), to predict where it should bounce next

This normally finds the answer in less steps than binary search. But has the less than helpful property that it may also bounce for ever, or even bounce off the table. Pingpong solves this by adding two bats. These provide a reducing range, squeezing the ball in at every bounce; so it will always find an answer, and with less array lookups than secant alone

So pingpong uses many less array lookups than binary search... But also spends a lot longer deciding where to look... Which is faster in a real sense is a very hard question to answer

You would think that searching short arrays of integers would be a best case scenario for binary search — but evern here there is not a clear winner

Tell me something fun

aArray bootstraps itself with a 'c-PRE-pre-processor' cppp to produce the final aArray.h. In no way related to ppap

silly film

Internally aArray functions are written out many times for each type. For instance aFold is written out 48 times: once for each array type * each return type * 3. The 3 because it can be passed a c function, block, or c++ lambda. This duplication is most easily done with macros

But when a syntax error occurs, the compiler would print out all of those macros — which looks messy — so cppp pre-pre-processes them away

And since cppp is written using aArray.h, and aArray.h is written using cppp, we have a bootstrap loop, which forms part of the unittests each time aArray is regenerated

std::sort is slower

This shows the relative speed of different sort functions on macOS. They are tested against 10 different types of dataset, and the average score is taken. This is why qsort is slightly slower that mergesort. For datasets above 30000 items: mergesort becomes faster than aSort when the data is pre-ordered, and qsort becomes faster when the data has many duplicates. In general though aSort performs extremely well at all array lengths, and is the fastest across a range of datasets

It was written by BonzaiThePenguin. He's done seriously good work. It is a stable sort and operates in a fixed amount of memory

#define AARRAY_sortCache fixes the memory to 512, but you can redefine this to larger values; possibly improving aSort's performance for larger datasets

Now lets look at search using bsearch from Linux and BSD, and aSearch from aArray

aSearch is fastest
aSearchF_ALT is fastest

I've profiled a range of situations and hardware, but the writers of the other algorithms will of done so aswell, so aSearch may look fast, but the difference with BSD is small

aSearchF_ALT though does the worst in the first graph, and best in the second. Actually both graphs attempt to put it in the worst light possible... It is an algorithm I like to call pingpong which should be worth using as arrays become longer, comparisons become slower, or as the dataset becomes more uniform

The graphs are of short arrays, with fast comparisons, and completely un-uniform data — the first graph uses random int64_t integers, and the second random int32_t. The reason for being fastest on the second (and easily the fastest for int16_t) is I believe due to the shorter integers containing a shorter range of data — and that shorter range necessarily being more uniform

Another fun factoid is that if an array is partially sorted, then pingpong becomes a heuristc; returning a guess at the correct answer

If that was fun, I'd like to suggest an alternative search algorithm that I haven't implemented, but may be faster still:

Binary search jumps through large arrays in a set order. Each iteration loading disparate parts of the array into memory (which is slow). What you could do is reorder the array; not from lowest to highest; but into the order where the places binary search test come first. It is still binary search, but the first index tested is no-longer the middle, but the first. The second index tested would be either the second or third. Then from the second it would test either the 4th or 5th, and from the third it would test either the 6th or 7th

As this sequence becomes longer than a cacheline, you would split off the child search locations into a new block (with that block still placed into the same array, but so the cachelines get minmally loaded, and maximally used)

I would be surprized if that was not faster than existing binary search — but it would need someone to write both a custom search and sort alogrithm

NOCAPACITY

NOCAPACITY functions stop arrays from tracking their capacity. This saves about 8 bytes per array and occasionally causes the array to resize, reducing its length

NOCAPACITY (and STATIC) functions are simply variants of aAppend, aReplace, aAppendArray, aReplaceArray, aDelete, aConcat, aMulti, and aFree (aAppend_NOCAPACITY, aReplace_NOCAPACITY, ...)

You cannot mix NOCAPACITY, STATIC and normal api functions on the same array. An array created with a NOCAPACITY function must continue to use them, until it is freed with aFree_NOCAPACITY

STATIC

Sometimes you may want a STATIC array that gets created once and always remains the same length. You can get this by using the aAppend_STATIC aConcat_STATIC, etc variants of the normal api functions

These create an array once, and can throw "array is STATIC" in addition to their other exceptions

arrSTATIC = aAppend_STATIC((int**)NULL, 1, 2, 3, 4);
aReplaceArray_STATIC(&arrSTATIC, 0, 1, 5, replacement); // throws "array is STATIC"

It is not safe to mix STATIC NOCAPACITY and normal functions on the same array

arrSTATIC = aAppend_STATIC((int**)NULL, 1, 2, 3, 4);
aReplaceArray(&arrSTATIC, 0, 1, 5, replacement); // undetected memory corruption!!!

But you can convert between the array types, for instance with aConcat aConcat_STATIC and aConcat_NOCAPACITY

#define AARRAY_NOTYPEOF

aArray functions can return a mixture of types. Which would require manual type casting; but aArray assumes your compiler supports __typeof (or __decltype for c++). This allows the function's return type to be automatically fixed

If your compiler doesn't support __typeof or __decltype, then you can disable this automatic fixing with #define AARRAY_NOTYPEOF

clang and gcc support __typeof, but will also sometimes emit warnings about unused returns. You can silence these warnings by placing (void) infront of the function, for instance

(void)aAt2(somewhere, 1, over_the_rainbow);

#define AARRAY_WARN

aArray functions can recieve a mixture of types. Which would require manual type casting; aArray silences the specific clang and msvc warnings for just those parameters. But this is not possible for gcc. If you prefer to type cast manually for all compilers, then you can set #define AARRAY_WARN

If you then have a lot of manual type casts, you may prefer AARRAY_nowarn_start

AARRAY_nowarn_start

Anything between AARRAY_nowarn_start/AARRAY_nowarn_end has their C4047 differing level of indirection warning suppresed (for msvc), or -Wconversion, -Wint-conversion, -Wpointer-to-int-cast, and -Wbad-function-cast (for clang and gcc). They don't both need these, but it's simpler if they both get the same

This may save some casts when using gcc or AARRAY_WARN

For example bad-function-cast is disabled under -Wall and -Wextra. Enabling it has no effect on gcc but clang would then require aAt(mystructs, N)->this to be rewritten as ((mystruct)aAt((uintptr_t*)mystructs, N))->this

If compiling for clang with c++ then you may also want AARRAY_nowarn_pedantic_cpp_start/AARRAY_nowarn_pedantic_cpp_end. But in general don't use aArray with c++

aArray aims to use the same function calls for different array types, but c++ restricts function type casts. For instance f(int) to f(unsigned int), and f(char*) to f(void*) is actually undefined behaviour. So while aArray does unittest for c++ conformity, it is not something I advise. Using c does not have this issue (or any other known ub, etc problems)

#define AARRAY_UNSAFE

Defining this before including aArray.h removes the bounds and other safety checks, for a possible speed increase

#define AARRAY_c AARRAY_h

aArray.h can be included as a single header. But if you prefer, it can also be a dual header/implementation pair

#include "aArray.h"

Becomes

#define AARRAY_h
#include "aArray.h"

And a separately compiled .c file contains

#define AARRAY_c
#include "aArray.h"

#define AARRAY_NOCONVENIENCE

Under the assumption that you use aArray so much it becomes tiresome to see it everywhere, some mnemonics are defined for your convenience. These can be turned off with #define AARRAY_NOCONVENIENCE

The most useful is probably aStr("string") which converts "string" into an aArray string. Note that the terminating NULL is dropped. This simplifies concatenation, but means you probably want to print them with aWrite, or aFmt with "%v%c", or append '\0' by hand with aA(&str, '\0')

Also aMap aFilter aFold aLoop aSortF aSearchF and aSearchF_ALT can take either c-functions, blocks, or c++ lambdas. They do this with their underlying aMap_FUNC, aMap_BLOCK, and aMap_LAMBDA. You can call them explicitly, or use aMap which simply links to whichever of those is enabled by your compiler settings. So if blocks are enabled, but you are passing a c-function, you will need to be explicit and call aMap_FUNC, since aMap will link to aMap_BLOCK

Then for those of us who like acronyms, there are
aAaAppend
aRaReplace
aAAaAppendArray
aRAaReplaceArray
aDaDelete
aCaConcat
aMaMulti

aLaLength
aL2aLength2

aFaFmt
aFEaFmtE
aFFaFmtF
aFAaFmtA
aWaWrite

In the compiler I'm writing, 65.5% of function calls are from aArray! So this library is surprizingly useful; and the above acronyms help keep my code succinct

This would not of been possible without my family. I wouldn't even of begun programming without them. And thankyou to my lovely wife who is so generous to me

Many tools were used in creating aArray. Particularly helpful ones include Beautiful Soup, ninja, afl (especially the rabbit photos), fossil (safety+usability), and Kakoune

My life

Our pastor imprisoned, for ‘attempting to overthrow the government’ Joy in prison
We could see them running around, screaming... There was nothing I could do Lira’s rain
My first animated short, of some simple miracles Animation
Genesis is different. Vegetarianism explains why Creative Snails

any * aAppend (any **aArray, any items,...)
 
any * aReplace (any **aArray, size_t pos, size_t removeAmount, any items,...)
 
any * aAppendArray (any **aArray, size_t arrayLen, any *array,...)
 
any * aReplaceArray (any **aArray, size_t pos, size_t removeAmount, size_t arrayLen, any *array,...)
 
any * aDelete (any **aArray, size_t pos, size_t amount)
 
any * aConcat (any **aArray, any *next_aArray,...)
 
any * aMulti (any **aArray, size_t pos, size_t removeAmount, size_t arrayTimes, size_t arrayLen, any *array,...)
 
void aFree (any **aArray)
 
size_t aLength (any *aArray)
 
any aLength2 (any *aArray, size_t len)
 
any aZLength2 (any *aArray, size_t len)
 
any aAt (any *aArray, size_t pos)
 
any aZAt (any *aArray, size_t pos)
 
any aAt2 (any *aArray, size_t pos, any newItem)
 
any aZAt2 (any *aArray, size_t pos, any newItem)
 
any * aAtPtr (any *aArray, size_t pos)
 
any * aZAtPtr (any *aArray, size_t pos)
 
size_t aIndexOf (any *aArray, any item)
 
size_t aZIndexOf (any *aArray, any item)
 
void aMap (any *aArray, void(*f)(any *item))
 
any * aFilter (any *aArray, int(*f)(any *item))
 
anyB aFold (any *aArray, anyB base, anyB(*f)(anyB base, any item))
 
int aLoop (any *aArray, size_t startPos, int(*f)(size_t pos))
 
int aCmp (any *aArray, any *next_aArray,...)
 
any * aSort (any *aArray)
 
any * aSortF (any *aArray, int(*f)(any *key, any *item))
 
int aSearch (any *array, size_t *index, any key)
 
int aSearchF (any *array, size_t *index, any key, any(*f)(any key, any item))
 
int aFmt (char *format,...)
 
int aFmtE (char *format,...)
 
int aFmtF (FILE *file, char *format,...)
 
int aFmtA (char **aArray, char *format,...)
 
int aWrite (FILE *file, any *aArray,...)
 
void aError (char *errorLocation, char *errorMsg)
 
any* aAppend ( any **  aArray,
any  items,
  ... 
)

Appends one or more items to aArray

any represents any type other than void upto 8 bytes in width; be it char, double, clock_t, FILE*, long long, etc

If aArray is NULL, it will be initialized. A zero-length aArray is equivalent to a NULL aArray — as in api calls on either have the same effect. This should result in less NULL pointer checking, as it is a safe value

aAppend can take an arbitrary number of arguments. It is not necesary to give the number of arguments, or mark their end

Returns
The aArray, with new items added. If the aArray had to be moved in memory (to accomodate the new items) then *aArray will be updated to point to it
Exceptions
"out of memory", "array type is wide"

Exceptions are not c++ exceptions, but rather aError being passed the ‘exception’ as a parameter. See aError for more on exception handling

int *arr = NULL;
aAppend(&arr, 1, 2);
aAppend(&arr, 99, 100);
aFmt("{%v, %i}[0] is %i", arr, arr[0]); // "{+1, +2, +99, +100}[0] is +1"
any* aReplace ( any **  aArray,
size_t  pos,
size_t  removeAmount,
any  items,
  ... 
)

Replaces removeAmount items at position pos in aArray with one or more items

Returns
The updated aArray, and *aArray now pointing to it
Exceptions
"out of memory", "array type is wide", "out of bounds", "removal is out of bounds"
unsigned int *joy = aAppend((unsigned int**)NULL, 10, 5, 0, -5, -20);
aFmt("[%v, %u]", aReplace(&joy, 2, 3, 10, 20)); // prints "[10, 5, 10, 20]"
any* aAppendArray ( any **  aArray,
size_t  arrayLen,
any *  array,
  ... 
)

Appends one or more arrays to the end of aArray

arrayLen is the number of array items to be appended. If arrayLen is SIZE_MAX then array is appended up until the first NULL. This makes it easy to append char* strings for instance

Multiple arrays can be passed to aAppendArray; each array must be preceded by it's own arrayLen

Returns
The updated aArray, and *aArray now pointing to it
Exceptions
"out of memory", "array type is wide", "wrong arg count", "array is NULL"

The last three exceptions simply check parameter validity

int ages[3] = {0, 5, 10};
aAppendArray((int**)NULL,
  3, ages,
  3, ages,
  2, (int[]){12, 14}); // (int*){0, 5, 10, 0, 5, 10, 12, 14}

There are convenience macros that abbreviate aAppendArray to aAA and for instance aReplace to aR

You can switch them off by defining AARRAY_NOCONVENIENCE. But there is also an abbreviation of aAppendArray to aStr, which simplifies strings

char *hi = aStr("hello world");
aR(&hi, 0, 1, 'j'); // "jello world"
any* aReplaceArray ( any **  aArray,
size_t  pos,
size_t  removeAmount,
size_t  arrayLen,
any *  array,
  ... 
)

Replaces removeAmount items at position pos in aArray with one or more arrays

arrayLen is the number of array items to be inserted

Multiple arrays can be passed; each must be preceded by it's own arrayLen

Returns
The updated aArray, and *aArray now pointing to it
Exceptions
"out of memory", "array type is wide", "out of bounds", "removal is out of bounds", "wrong arg count", "array is NULL"
int* nums = NULL;
aAppend(&nums, 1, 2, 3, 4, 100);
aReplaceArray(&nums, 2, 2,
  2, nums,
  1, nums); // {1, 2, 1, 2, 1, 100}
any* aDelete ( any **  aArray,
size_t  pos,
size_t  amount 
)

Removes amount items from aArray at position pos

Returns
The updated aArray, and *aArray now pointing to it
Exceptions
"out of bounds", "array type is wide", "removal is out of bounds"
long *medalsWonBy_aArray = aAppend((long**)NULL, 15, 26, (long)-1);
aDelete(&medalsWonBy_aArray, 0, 3);
// length of array is now sadly zero
any* aConcat ( any **  aArray,
any *  next_aArray,
  ... 
)

Appends one or more next_aArrays to the end of aArray

Really this is a simple convenience – it does the same as aAppendArray, but without needing to specify each next_aArray length

Returns
The updated aArray, and *aArray now pointing to it
Exceptions
"out of memory", "array type is wide"
char* example = aStr("A ");
char* silly = aStr("silly ");
aConcat(&example, silly, silly, example, example);
// "A silly silly A A "
any* aMulti ( any **  aArray,
size_t  pos,
size_t  removeAmount,
size_t  arrayTimes,
size_t  arrayLen,
any *  array,
  ... 
)

Other than making your code look complex, aMulti lets you

  1. Create un-initialized aArrays
  2. Create aArrays with repeating items
  3. Combine multiple aArray updates into a single step

arrayTimes is the amount of times to insert arrayLen from array into aArray

If arrayTimes is 0 then arrayLen un-initialized items will be inserted

Returns
The updated aArray, and *aArray now pointing to it
Exceptions
"out of memory", "array type is wide", "out of bounds", "removal is out of bounds", "wrong arg count", "array is NULL"
// length=200, every item is 0
aMulti(&data, 0, 0, 200, 1, (int8_t[]){0});
  
// length=200, every item is uninitialized
aMulti(&data, 0, 0, 0, 200, NULL);
// set length=0, but capacity is now preallocated
aLength2(data, 0);

Also

// Combine aArray updates reduced to a single call
unsigned int *va = NULL;
aAppend(&va, 1, 2, 3);
aReplace(&va, 0, 0, -2, -1, 0);
aReplaceArray(&va, 1, 3, 1, (unsigned int[]){5});
aDelete(&va, aLength(va)-1, 1);
// va now {-2, 5, 2}
unsigned int * vb = NULL;
aMulti(&vb,
  0, 0, 1, 3, (unsigned int[]){1, 2, 3},
  0, 0, 1, 3, (unsigned int[]){-2, -1, 0},
  1, 3, 1, 1, (unsigned int[]){5},
  3, 1, 0, 0, NULL);
// vb now {-2, 5, 2}, but done in one malloc
void aFree ( any **  aArray)

Frees aArray, setting it to NULL

Note
Remember to & de-reference the pointer to aArray. I used to forget this, so now it forces a compiler error
any* myArr = aAppend((any**)NULL, 'x');
aFree(&myArr); // myArr is now NULL
size_t aLength ( any *  aArray)
Returns
The length of aArray

aLength(nullvar) returns 0 — since NULL is considered equivalent to a zero-length aArray

any aLength2 ( any *  aArray,
size_t  len 
)

Sets aArray length to an equal, or shorter len

Returns
The last item still in aArray. I.e. aArray[aLength(aArray)-1], or 0, if aArray is empty
Exceptions
"out of bounds", "array type is wide"
int* fib = NULL; aAppend(&fib, 1, 1, 2, 3, 5);
aFmt("Prev fib = %uz", aLength2(fib, aLength(fib)-1));
// fib length reduced by one, and 3 printed
  
aFmt("\nlen = %uz", aLength(fib)); // 4
aLength2(fib, 2);
aFmt("\nlen = %uz", aLength(fib)); // 2
any aZLength2 ( any *  aArray,
size_t  len 
)

Reduces aArray length by len to an equal, or shorter length

Returns
The last item still in aArray. I.e. aArray[aLength(aArray)-1], or 0, if aArray is empty
Exceptions
"out of bounds", "array type is wide"
int* fib = NULL; aAppend(&fib, 1, 1, 2, 3, 5);
aZLength2(fib, 1); // removes 5
aFmt("last item = %u", aZLength2(fib, 1)); // removes 3, prints 'last item = 2'
any aAt ( any *  aArray,
size_t  pos 
)
Returns
The item at position pos in aArray, indexing from zero
Exceptions
"out of bounds", "array type is wide"

A pos past the end of aArray throws an exception. Otherwise aArray[pos] is identical

char* equal = aAppend((char**)NULL, 'a', 'b');
// NOTE: cast not needed if your compiler has __typeof or __decltype
if(equal[0] == (char)aAt(equal, 0)) printf("equal"); // "equal"
any aZAt ( any *  aArray,
size_t  pos 
)
Returns
The item at position pos from the end of aArray, indexing from zero
Exceptions
"out of bounds", "array type is wide"

A pos past the beginning of aArray throws an exception

char* letters = aAppend((char**)NULL, 'a', 'r', 't');
aReplace(&letters, 0, 0, aZAt(letters, 0));
aFmt("%v %c", letters); // "t a r t"
any aAt2 ( any *  aArray,
size_t  pos,
any  newItem 
)

Sets the item at position pos in aArray to newItem

Returns
newItem
Exceptions
"out of bounds", "array type is wide"
char* letters = aAppend((char**)NULL, 'a', 'b');
aAt2(letters, 1, 'd'); // ['a', 'd']
any aZAt2 ( any *  aArray,
size_t  pos,
any  newItem 
)

Sets the item at position pos from the end of aArray to newItem

Returns
newItem
Exceptions
"out of bounds", "array type is wide"
char* letters = aAppend((char**)NULL, 'a', 'b');
aZAt2(letters, 0, 'd'); // 'a', 'd'
any* aAtPtr ( any *  aArray,
size_t  pos 
)
Returns
A pointer to the item at position pos in aArray
Exceptions
"out of bounds", "array type is wide"
char* equal = aAppend((char**)NULL, 'a', 'b');
// NOTE: casts not needed if your compiler has __typeof or __decltype
*(char*)aAtPtr(equal, 0) = 'b';
if(equal[0] == (char)aAt(equal, 1)) aFmt("equal"); // "equal"
any* aZAtPtr ( any *  aArray,
size_t  pos 
)
Returns
A pointer to the item at position pos from the end of aArray
Exceptions
"out of bounds", "array type is wide"
char* letters = aAppend((char**)NULL, 'n', 'o', '\0');
*(char*)aZAtPtr(letters, 2) = 'l';
printf(letters); // "lo"
size_t aIndexOf ( any *  aArray,
any  item 
)

Finds the first index of item in aArray

Returns
first index of item in aArray, or -1
Exceptions
"array type is wide"
int* PPS_array = aAppendArray((int**)NULL, numPidgeons, pidgeonPeckSpeed_data);
aIndexOf(PPS_array, 200); // first occuring pidgeon with a peck speed of 200
size_t aZIndexOf ( any *  aArray,
any  item 
)

Finds the last index of item in aArray

Returns
last index of item in aArray, or -1
Exceptions
"array type is wide"
int* PPS_array = aAppendArray((int**)NULL, numPidgeons, pidgeonPeckSpeed_data);
aZIndexOf(PPS_array, 190); // last occuring pidgeon with a speed of 190
void aMap ( any *  aArray,
void(*)(any *item)  f 
)

Apply f to every item in aArray

f can be a block, c++11 lambda, or function-pointer

Exceptions
"parameter is NULL", "array type is wide"

There are actually 4 api functions here. aMap_BLOCK, aMap_LAMBDA, aMap_FUNC, and aMap. aMap simply maps to whichever of the first 3 are available. If the environment has blocks, then aMap_BLOCK, if it has lambdas, then aMap_LAMBDA, and otherwise aMap_FUNC. You can always call the specific function directly if you prefer

aFilter, aFold, and aLoop handle blocks, lambdas, and function-pointers in the same way

void (*ride_a_pony)(pony*) = oh_what_fun_function;
aMap_FUNC(my_little_ponies, ride_a_pony);
any* aFilter ( any *  aArray,
int(*)(any *item)  f 
)

Apply f to every item in aArray. Keep the item in aArray if f returns true

f can be a block, c++11 lambda, or function-pointer

Exceptions
"parameter is NULL", "array type is wide"
int* n1 = aAppend((int**)NULL, 4,5,6,7,8);
aFilter_FUNC(n1, isEven);  // n2 = [4,6,8]
aFilter_BLOCK(n1, ^(int* item){ return *item > 5; });  // n3 = [6,8]
aFilter_LAMBDA(n1, [](void* item){ *(int*)item += 20; return true; });  // n4 = [26,28]
anyB aFold ( any *  aArray,
anyB  base,
anyB(*)(anyB base, any item)  f 
)

Do base = f(base, item) for every item in aArray

f can be a block, c++11 lambda, or function-pointer

This is a nice simple way to combine every item of an aArray into a single result

Returns
the final base
Exceptions
"parameter is NULL", "array type is wide"
int* numbers = aAppendArray((int**)NULL, 10, numbersArray);
aFmt("\nSum     = %u64", aFold_FUNC(numbers, 0, add_function));
aFmt("\nProduct = %u64", aFold_BLOCK(numbers, (size_t)1, ^(size_t base, int item){ return base*item; }));
auto f = [](bool base, int item) { return base&&item; };
aFmt("\nAllTrue = %u8", (uintptr_t)aFold_LAMBDA(numbers, true, f));
char* baseB = NULL;
aFmt("\nString  = %v%c", *aFold_BLOCK(numbers, &baseB,
  ^(char** baseBPtr, int item){ (void)aAppend(baseBPtr, (char)(item+64)); return baseBPtr; }));
int aLoop ( any *  aArray,
size_t  startPos,
int(*)(size_t pos)  f 
)

This is a while loop that hopefully keeps your code safer and cleaner

Starting from startPos, and until out of bounds, or f returns 0, do pos += f(pos)

f can be a block, c++11 lambda, or function-pointer

Returns
f's last returned value
Exceptions
"parameter is NULL", "array type is wide"

It is like:

size_t pos = startPos, deltaPos;
while(pos < aLength(array)) {
  deltaPos = f(pos); // do my stuff
  aF("%i ", array[pos]);
  if(!deltaPos) break; // f returning 0 breaks the loop
  // play safe with int promotion
  // i.e. where deltaPos is negative, but added to an unsigned type
  if(deltaPos > 0) pos +=  deltaPos;
  else             pos -= -deltaPos; }
Note
Even with safe int promotion, this while loop can still integer overflow at pos += deltaPos, and loop back through zero

aLoop is safe for both these rare issues and buffer overflow. With blocks it becomes:

aLoop(aArray, startPos, ^(size_t pos){
  // do my stuff
  return deltaPos; } );
unsigned int* a = aAppend((unsigned int**)NULL, 1, 2, 3, 4);
// print index 0 and 2
aLoop(a, 0, ^(size_t n) {
// (uintptr_t) cast here even for clang, because it can miss _Pragmas
aFmt((uintptr_t)"a[%ull] == %ui\n", n, aAt(a, n)); return 2; });
// print index 3 and 1, then set them to new values
aLoop(a, 3, ^(size_t n){
aFmt((uintptr_t)"Doing a[%ull] = %ui\n", n, aAt(a, n-1));
(void)aAt2(a, n, aAt(a, n-1));
return -2; }); // a becomes {1, 1, 3, 3}
Results in:
v[0] == 1
v[2] == 3
Doing v[2] = 4
Doing v[0] = 2
int aCmp ( any *  aArray,
any *  next_aArray,
  ... 
)

Compares aArray against one or more next_Arrays

The any type width is assumed to be the same – i.e. both char*, or short*, etc

Returns
1 if equal, 0 otherwise
int
  *black = NULL,
  *white = NULL;
if(aCmp(black, white)) aFmt("We are all family");
any* aSort ( any *  aArray)

Orders array items as ascending unsigned integers

Returns
The re-ordered array
int*filmBoredomLevel = aAppend((int**)NULL, 300, 600, 200, 100);
aSort(filmBoredomLevel);
aFmt("[%v, %ui]", filmBoredomLevel); // prints "[100, 200, 300, 600]"
any* aSortF ( any *  aArray,
int(*)(any *key, any *item)  f 
)

Orders array items according to the function f

f must return true/false, i.e. using < or >

f can be a block, c++11 lambda, or function-pointer

Returns
The re-ordered array
int sort_strcmp(char*a, char*b) { return strcmp(a,b) < 0; }
// ...
char**verses = NULL;
aAppend(&verses, "There is no greater love", "You are my beloved", "Because of His great love");
aSortF_FUNC(verses, sort_strcmp);
aFmt("%v\n%s", verses);
int aSearch ( any *  array,
size_t *  index,
any  key 
)

Searches a sorted array for key

If key is present, then index is set to its position, otherwise index is set to the position where key would of been

The array items must be ordered as ascending unsigned integers

Returns
1 if key found, 0 otherwise. And updates *index
size_t index;
if(aSearch(filmBoredomLevel, &index, 600))
  printf("Most boring film 'Peppa Pig Goes on Holiday' is at index %zu", index);
int aSearchF ( any *  array,
size_t *  index,
any  key,
any(*)(any key, any item)  f 
)

Searches a sorted array for key

If key is present, then index is set to its position, otherwise index is set to the position where key would of been

f must return the difference, i.e. -1 0 or +1

f can be a block, c++11 lambda, or function-pointer

Returns
1 if key found, 0 otherwise. And updates *index

aSearchF_ALT is also available as an alternative for aSearchF. It uses the pingpong algorithm, rather than binary search. It becomes faster for longer arrays, slower compare functions, or more uniform data. It's here for your enjoyment

For aSearchF_ALT, f should return the degree of difference, i.e. item - key. Note that strcmp does this, but it is not a good example as it only returns a byte of difference

char*search_strcmp(char*a, char*b) { return (char*)strcmp(a,b); }
// ...
size_t index;
char*key = "He gives power to the weak and strength to the powerless";
if(aSearchF_FUNC(verses, &index, key, search_strcmp))
  printf("found verse at %zu", index);
aSearchF_BLOCK(verses, &index, key, ^(char*a, char*b){ return (char*)(uintptr_t)strcmp(a,b); });
aReplace(&verses, index, 0, key);
printf("inserted verse at %zu", index);
int aFmt ( char *  format,
  ... 
)

Prints aArrays; aswell as chars, strings, integers, and floats, according to format

format can contain plain text, or:

  • %% for %
  • %c for characters
  • %s for strings
aFmt("%s%c%s", "plat", 'y', "pus"); // prints 'platypus'
  • %AAiBB for integers
  • %AAuBB for unsigned integers

AA is any number from 2 - 64, and defaults to 10. It is the base to print in, such as binary or hex

BB is the integer's type, and defaults to (int). It can be: 8, 16, 32, 64, or c (char), s (short), i (int), l (long), ll (long long), z (size_t), m (intmax_t), p (intptr_t). So (unsigned long long) in base 16 would be %16ull; (uint32_t) in binary would be %2u32; and (signed short) in base 10 would be %is, though %i will always print the sign, whether + or -

aFmt("h%cpp%c %u8", 'i', 'o', (uint8_t)2); // prints 'hippo 2'
  • %f for floats
  • %d for doubles
float fa=0.01, fb=2.22;
double da=2.22*1000000;
// prints '0.01 2.22 -- 2.22e+06'
aF("%f %f -- %d",
    *(int32_t*)&fa,*(int32_t*)&fb,
    *(int64_t*)&da); // stop float->int conversion warnings
  • %vAA%BB for aArrays

AA is the text to print between each item. BB can be any of the % formatters, except %v. So '%v, %i' would print a comma separated list of ints

Returns
0 on success, -1 on I/O error
Exceptions
"format requires more arguments", "format is malformed"
char* abc = aAppend((char**)NULL, 'a', 'b', 'c');
aFmt("<%v, %c>", abc); //prints '<a, b, c>'
int* nums = aAppend((int**)NULL, 0, 1, 2);
aFmt("[%v | %2i]", nums); //prints '[+0 | +1 | +10]'
aFree(&abc); aFree(&nums);
int aFmtE ( char *  format,
  ... 
)

Prints aArrays, etc in format to stderr. First stdout, then stderr is flushed

This can be useful for quick debugging, particularly when not defining AARRAY_NOCONVENIENCE; letting it can be abreviated to aFE, saving a whole two letters

Returns
0 on success, -1 on I/O error
Exceptions
"format requires more arguments", "format is malformed"
// prints base 2, base 3, then base 4
aFmtE("as easy as %2ic %3is %4ii", (char)1, (short)2, (int)3);
int aFmtF ( FILE *  file,
char *  format,
  ... 
)

Prints aArrays, etc in format to file

Returns
0 on success, -1 on I/O error
Exceptions
"format requires more arguments", "format is malformed"
// aStr("") is simply a convenience to convert a string to an aArray
char* word = aStr("imperturbablorbably");
(void)aLength2(word, aLength(word));
FILE* file = fopen("hope.txt", "w");
aFmtF(file, "Let me spell it out for you: %v, %c", word);
fclose(file); // contains "Let me spell it out for you: i, m, p, e, r, t, u, r, b...."
int aFmtA ( char **  aArray,
char *  format,
  ... 
)

Prints aArrays, etc in format to a (char*) aArray — which is passed by reference

Returns
0 on success, -1 on I/O error
Exceptions
"format requires more arguments", "format is malformed"
char *out = NULL;
aFmt("%ui %ui miss a few %ii %ii", 1, 2, 99, 100);
int aWrite ( FILE *  file,
any *  aArray,
  ... 
)

Prints the full contents of aArray and any subsequent aArrays as char* text to file

Subsequent aArrays should have the same any type width as the first

It is faster than printf and does not require aArrays to be NULL terminated

Returns
0 on success, -1 on I/O error
aAppendArray(&string,
  SIZE_MAX, "A wonderful story of how",
  SIZE_MAX, ", my saviour died for me");
FILE* file = fopen("hope.txt", "w");
aWrite(file, string); // writes string to file
void aError ( char *  errorLocation,
char *  errorMsg 
)

The error handler. Prints error details and aborts, but can be replaced with a custom error handler

This error handler must be set per translation unit

errorLocation is where the error occurred in your code, i.e.: "file:lineNumber"

errorMsg is one of:
      "out of memory (allocating=...)",
      "out of bounds (length=. but ...)",
      "removal is out of bounds (length=. but ...)",
      "array is STATIC (length=...)",
      "array is NULL (array no=...)",
      "array type is wide (max 8 bytes)",
      "wrong arg count (args=. but ...)", and
      "infinite loop (jump=0)",
      "parameter is NULL",
      "format requires more arguments",
      "format is malformed"

If errorMsg formatting fails then (...) will be (no info). Except for a small easter egg, for when you truly manage to run out of memory

Here's a little game. It shows errors being thrown and caught using longjmp

#include "aArray.h"
#include <setjmp.h>
#include <time.h>
jmp_buf array_err;
void aError_jmp(char* line, char* msg) {
  // our custom error handler
  printf("Error at %s: %s\n", line, msg);
  // choices are exit or longjmp...
  longjmp(array_err, 1); }
int main() {
  printf("Lets play guess the array length\n");
  // guess too high, and an "out of bounds" exception will lose you the game
  char* aArray = NULL;
  srand(time(NULL));
  aMulti(&aArray, 0, 0,
         // a 0-99 length array
         rand() % 100, 1, (uintptr_t)(char[]){0});
  // aError exceptions are caught here
  aError = &aError_jmp;
  if(setjmp(array_err))
    printf("Oops, too far! Goodbye\n"), aFree(&aArray), exit(0);
  
  for(;;) {
    printf("Guess a length: ");
    size_t guess;
    int input_err = scanf("%zu", &guess);
    if (input_err == 0 || input_err == EOF)
      printf("Oh dear, I didn't understand! Goodbye\n"), aFree(&aArray), exit(0);
    
    // if guess is out of bounds, aAt will call aError_jmp
    // and aError_jmp behaves like an exception
    // i.e. it longjmps to setjmp(array_err) where the error is handled
    aAt(aArray, guess);
    
    // good luck with winning
    printf("The array might be longer...\n"); } }
It produces something like:
cc game.c && ./a.out
Lets play guess the array length
Guess a length: 20
The array might be longer...
Guess a length: 30
The array might be longer...
Guess a length: 40
Error at game.c:35: out of bounds (length=36 but pos=40)
Oops, too far! Goodbye
1 /** FREE:
2  You are free to do whatever you like with this
3  You may re-license it under any license; there is no need to give me credit
4  As freely as you have received, freely give -- Jesus
5 
6  WARRANTY: Things go wrong
7 
8  ABOUT:
9  An array and string library for c
10  Generated by c-pre-pre-processor: $exec date -u +"%d %b %Y **/"
11 
12 
13 
14 
15 #pragma once
16 
17 #include <stdlib.h>
18 #include <string.h>
19 #include <stdint.h>
20 #include <stdio.h>
21 #include <string.h> // for memcmp
22 #include <math.h> // for sqrt
23 #if defined(_MSC_VER)
24 #include <malloc.h> // for msvc realloc
25 #endif
26 #if defined(__cplusplus)
27 #include <functional> // for lambda
28 #include <utility>
29 #endif
30 
31 
32 
33 
34 //// handle warnings
35 // many parameters take an arbitrary mix of pointers/integers
36 // so optionally suppress warnings only for those parameters
37 $define pragmaWarnings(NAME)
38  // these are slightly redundant, but handle both clang and gcc
39  #if defined(__cplusplus)
40  #define AARRAY_nowarn_start \
41  _Pragma("NAME diagnostic push") \
42  _Pragma("NAME diagnostic ignored \"-Wconversion\"") \
43  _Pragma("NAME diagnostic ignored \"-Wconversion-null\"") \
44  _Pragma("NAME diagnostic ignored \"-Woverflow\"") /* older versions of gcc */ \
45  _Pragma("NAME diagnostic ignored \"-Wnarrowing\"")
46  #else
47  #define AARRAY_nowarn_start \
48  _Pragma("NAME diagnostic push") \
49  _Pragma("NAME diagnostic ignored \"-Wconversion\"") \
50  _Pragma("NAME diagnostic ignored \"-Wint-conversion\"") \
51  _Pragma("NAME diagnostic ignored \"-Wpointer-to-int-cast\"") \
52  _Pragma("NAME diagnostic ignored \"-Wbad-function-cast\"")
53  #endif
54  #define AARRAY_nowarn_end _Pragma("NAME diagnostic pop")
55 
56 // start-end block suppress some c++ warnings
57 // i.e. (cast) not being static_cast<cast>(), c++98-compat, etc
58 #define AARRAY_nowarn_pedantic_cpp_start
59 #define AARRAY_nowarn_pedantic_cpp_end
60 #define AARRAY_nowarn_align(STATEMENT) STATEMENT
61 #if defined(__clang__)
62  pragmaWarnings(clang)
63  #if defined(__cplusplus)
64  #undef AARRAY_nowarn_pedantic_cpp_start
65  #define AARRAY_nowarn_pedantic_cpp_start_helper \
66  _Pragma("clang diagnostic push") \
67  _Pragma("clang diagnostic ignored \"-Wc99-extensions\"") \
68  _Pragma("clang diagnostic ignored \"-Wc++98-compat-pedantic\"") \
69  _Pragma("clang diagnostic ignored \"-Wold-style-cast\"") \
70  _Pragma("clang diagnostic ignored \"-Wcast-qual\"")
71  #if __clang_major__ < 5
72  #define AARRAY_nowarn_pedantic_cpp_start \
73  AARRAY_nowarn_pedantic_cpp_start_helper
74  #else
75  #define AARRAY_nowarn_pedantic_cpp_start \
76  AARRAY_nowarn_pedantic_cpp_start_helper \
77  _Pragma("clang diagnostic ignored \"-Wzero-as-null-pointer-constant\"")
78  #endif
79  #undef AARRAY_nowarn_pedantic_cpp_end
80  #define AARRAY_nowarn_pedantic_cpp_end _Pragma("clang diagnostic pop")
81  #endif
82  #undef AARRAY_nowarn_align
83  #define AARRAY_nowarn_align(STATEMENT) \
84  _Pragma("clang diagnostic push") \
85  _Pragma("clang diagnostic ignored \"-Wcast-align\"") \
86  STATEMENT _Pragma("clang diagnostic pop")
87 #elif defined(__GNUC__)
88  pragmaWarnings(GCC)
89  #if defined(__cplusplus)
90  #undef AARRAY_nowarn_pedantic_cpp_start
91  #undef AARRAY_nowarn_pedantic_cpp_end
92  #define AARRAY_nowarn_pedantic_cpp_start \
93  _Pragma("GCC diagnostic push") \
94  _Pragma("GCC diagnostic ignored \"-Wpedantic\"")
95  #define AARRAY_nowarn_pedantic_cpp_end _Pragma("GCC diagnostic pop")
96  #endif
97 #elif defined(_MSC_VER)
98  #define AARRAY_nowarn_start \
99  __pragma(warning(push)) \
100  __pragma(warning(disable:4047))
101  #define AARRAY_nowarn_end __pragma(warning(pop))
102 #else
103  // dont hide int-pointer conversion warnings for this compiler
104  #define AARRAY_nowarn_start
105  #define AARRAY_nowarn_end
106 #endif
107 
108 #if defined(__cplusplus)
109  AARRAY_nowarn_pedantic_cpp_start
110  #define AARRAY_move std::move
111 #else
112  #define AARRAY_move
113 #endif
114 
115 
116 
117 
118 //// compile as .c .h, or as a single header with 'static inline' functions
119 #if defined(AARRAY_c)
120 #define AARRAY_define(name, ...) name __VA_ARGS__
121 #elif defined(AARRAY_h)
122 #define AARRAY_define(name, ...) extern name;
123 #else
124 #define AARRAY_define(name, ...) static inline name __VA_ARGS__
125 #endif
126 
127 //// general compiler compatibility
128 #if !defined(__has_feature)
129 #define __has_feature(x) 0
130 #endif
131 #if !defined(__has_extension)
132 // pre-3.0 clang
133 #define __has_extension __has_feature
134 #endif
135 
136 #if defined(__builtin_prefetch)
137 #define AARRAY_prefetch(A, B, C) __builtin_prefetch(A, B, C)
138 #else
139 #define AARRAY_prefetch(A, B, C)
140 #endif
141 
142 //// switch on/off safety checks
143 #if defined(AARRAY_UNSAFE)
144 #define AARRAY_safety(UNSAFE, ...) UNSAFE
145 #else
146 #define AARRAY_safety(UNSAFE, ...) __VA_ARGS__
147 #endif
148 
149 //// switch on/off type warnings for generics
150 #if defined(AARRAY_WARN) || (defined(__GNUC__) && !defined(__clang__))
151  // gcc can't handle pragmas within expressions
152  #define AARRAY_nowarn_internal_start
153  #define AARRAY_nowarn_internal_end
154 #else
155  #define AARRAY_nowarn_internal_start AARRAY_nowarn_start
156  #define AARRAY_nowarn_internal_end AARRAY_nowarn_end
157 #endif
158 
159 //// set the size of aSort's cache
160 #if !defined(AARRAY_sortCache)
161  #define AARRAY_sortCache 512
162 #endif
163 
164 
165 
166 
167 //// error handling
168 AARRAY_define(__attribute((noreturn))
169 void AARRAY_aError(char errLocation[], char errMsg[]), {
170  fflush(stdout); fprintf(stderr, "%s: %s\n", errLocation, errMsg); abort(); })
171 // set the default handler
172 #if defined(AARRAY_c)
173 void (*aError)(char[], char[]) = &AARRAY_aError;
174 #elif defined(AARRAY_h)
175 extern void (*aError)(char[], char[]);
176 #else
177 static void (*aError)(char[], char[]) = &AARRAY_aError;
178 #endif
179 
180 // generate "file.c:line_number" for error messages
181 #define AARRAY_STRINGIFY(x) #x
182 #define AARRAY_TOSTRING(x) AARRAY_STRINGIFY(x)
183 #define AARRAY_LINE (char*)__FILE__ ":" AARRAY_TOSTRING(__LINE__)
184 
185 // generate error messages
186 #define AARRAY_aError_MsgLen 52 + 3*20 + 1 /* 52 characters + 3*size_t + NULL */
187 #define AARRAY_aError_CALL(MSG) { aError(errLoc, MSG); abort(); }
188 #define AARRAY_Error_OutOfMemory(SIZE) \
189  { char AARRAY_aError_Msg[AARRAY_aError_MsgLen]; \
190  if(0>snprintf(AARRAY_aError_Msg, AARRAY_aError_MsgLen, \
191  "out of memory (allocating=%zu)", \
192  SIZE)) \
193  AARRAY_aError_CALL((char*)"out of memory " \
194  "(can I interest you in a banana instead? 🍌 )") \
195  else AARRAY_aError_CALL(AARRAY_aError_Msg) }
196 #define AARRAY_Error_OutOfBounds(LENGTH, POS) \
197  { char AARRAY_aError_Msg[AARRAY_aError_MsgLen]; \
198  if(0>snprintf(AARRAY_aError_Msg, AARRAY_aError_MsgLen, \
199  "out of bounds (length=%zu but pos=%zu)", \
200  LENGTH, POS)) \
201  AARRAY_aError_CALL((char*)"out of bounds (no info)") \
202  else AARRAY_aError_CALL(AARRAY_aError_Msg) }
203 #define AARRAY_Error_RemovalIsOutOfBounds(LENGTH, POS, RLEN) \
204  { char AARRAY_aError_Msg[AARRAY_aError_MsgLen]; \
205  if(0>snprintf(AARRAY_aError_Msg, AARRAY_aError_MsgLen, \
206  "removal is out of bounds (length=%zu but pos=%zu removal=%zu)", \
207  LENGTH, POS, RLEN)) \
208  AARRAY_aError_CALL((char*)"removal is out of bounds (no info)") \
209  else AARRAY_aError_CALL(AARRAY_aError_Msg) }
210 #define AARRAY_Error_ArrayIsStatic(LENGTH) \
211  { char AARRAY_aError_Msg[AARRAY_aError_MsgLen]; \
212  if(0>snprintf(AARRAY_aError_Msg, AARRAY_aError_MsgLen, \
213  "array is STATIC (length=%zu)", LENGTH)) \
214  AARRAY_aError_CALL((char*)"array is STATIC (no info)") \
215  else AARRAY_aError_CALL(AARRAY_aError_Msg) }
216 #define AARRAY_Error_ArrayIsNull(ARRAY_NO) \
217  { char AARRAY_aError_Msg[AARRAY_aError_MsgLen]; \
218  if(0>snprintf(AARRAY_aError_Msg, AARRAY_aError_MsgLen, \
219  "array is NULL (array no=%zu)", ARRAY_NO)) \
220  AARRAY_aError_CALL((char*)"array is NULL (no info)") \
221  else AARRAY_aError_CALL(AARRAY_aError_Msg) }
222 #define AARRAY_Error_ArrayIsWide \
223  (aError(AARRAY_LINE, (char*)"array type is wide (max 8 bytes)"), 0)
224 #define AARRAY_Error_WrongArgCount(ARG_NUM, MULTIPLE, ADDITION) \
225  { char AARRAY_aError_Msg[AARRAY_aError_MsgLen]; \
226  if(0>snprintf(AARRAY_aError_Msg, AARRAY_aError_MsgLen, \
227  "wrong arg count (args=%zu but should be %i + multiple of %i)", \
228  ARG_NUM, ADDITION, MULTIPLE)) \
229  AARRAY_aError_CALL((char*)"wrong arg count (no info)") \
230  else AARRAY_aError_CALL(AARRAY_aError_Msg) }
231 #define AARRAY_Error_InfiniteLoop \
232  AARRAY_aError_CALL((char*)"infinite loop (jump=0)")
233 #define AARRAY_Error_FormatStringArgs \
234  AARRAY_aError_CALL((char*)"format requires more arguments")
235 #define AARRAY_Error_FormatStringMalformed \
236  AARRAY_aError_CALL((char*)"format is malformed")
237 #define AARRAY_Error_NullParameter \
238  AARRAY_aError_CALL((char*)"parameter is NULL")
239 
240 
241 
242 
243 //// foundations for array allocation
244 AARRAY_define(size_t AARRAY_upper_power_of_two(size_t v), {
245  // from: graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
246  // very slightly faster than: 1<<(64-AARRAY_BUILTIN_LL(clz,v-1))
247  ////if __LP64__ >> 32
248  v--; v |= v >> 1; v |= v >> 2; v |= v >> 4; v |= v >> 8;
249  v |= v >> 16; if(sizeof(size_t)==8) v |= v >> 32; v++; return v; })
250 // cross platform count-leading-zeros
251 #if defined(__GNUC__)
252 #define AARRAY_builtin_ll(name,with) \
253  (sizeof(with)<=sizeof(int)?__builtin_##name(with) : \
254  (sizeof(with)<=sizeof(long)?__builtin_##name##l(with) : \
255  __builtin_##name##ll(with)))
256 AARRAY_define(int AARRAY_clz(size_t value), {
257  return AARRAY_builtin_ll(clz,value); })
258 #elif defined(_MSC_VER)
259 #include <intrin.h>
260 #if defined(_WIN64)
261 #pragma intrinsic(_BitScanReverse,_BitScanReverse64)
262 AARRAY_define(int AARRAY_clz(size_t value), {
263  unsigned long result;
264  return (int)(sizeof(size_t) <= 4?
265  (_BitScanReverse(&result, (unsigned long)value)? 31-result : 32) :
266  _BitScanReverse64(&result, value)? 63-result : 64); })
267 #else
268 #pragma intrinsic(_BitScanReverse)
269 AARRAY_define(int AARRAY_clz(size_t value), {
270  unsigned long result;
271  return (int)(_BitScanReverse(&result, value)? 31-result : 32); })
272 #endif
273 #else
274 // originally from: www.hackersdelight.org/hdcodetxt/nlz.c.txt
275 AARRAY_define(int AARRAY_clz(size_t x), {
276  int n = 0;
277  if(sizeof(size_t)==8 &&
278  x <= 0x00000000FFFFFFFF) { n += 32; x <<= 32; }
279  if(x <= 0x0000FFFFFFFFFFFF) { n += 16; x <<= 16; }
280  if(x <= 0x00FFFFFFFFFFFFFF) { n += 8; x <<= 8; }
281  if(x <= 0x0FFFFFFFFFFFFFFF) { n += 4; x <<= 4; }
282  if(x <= 0x3FFFFFFFFFFFFFFF) { n += 2; x <<= 2; }
283  if(x <= 0x7FFFFFFFFFFFFFFF) { n += 1; x <<= 1; }
284  return n; })
285 #endif
286 
287 //// array allocators, for 3 types of array
288 // fix pointers to realloced memory, to point back into memory
289 #define AARRAY_FIX_POINTERS(TYPE) \
290  if(!*vec) *length = 0; \
291  else if(vecsIncr) { \
292  /* parameters can contain pointers \
293  so update any that overlaped vec's old position */ \
294  size_t m = vecsIncr==5? 2: vecsIncr-1; \
295  while(m < vecsCount) { \
296  if(vecs[m] >= (uintptr_t)(*vec) && \
297  vecs[m] < (uintptr_t)(*vec)+(*length)*sizeof(TYPE)) \
298  AARRAY_nowarn_align(vecs[m] += \
299  (uintptr_t)length-(uintptr_t)((size_t*)*vec-1);) \
300  m += vecsIncr; } }
301 
302 // calculate capacity from length
303 #define AARRAY_ALLOC_NOCAPACITY(TYPE) \
304  size_t curSize = (*length) * sizeof(TYPE) + sizeof(size_t); \
305  size_t newSize = ((*length) + (ilen-rlen)) * sizeof(TYPE) + sizeof(size_t); \
306  if((!*vec || AARRAY_clz(newSize-1) < AARRAY_clz(curSize-1))) { \
307  length = (size_t*)realloc(!*vec? NULL : length, \
308  AARRAY_upper_power_of_two(newSize)); \
309  AARRAY_safety(, if(!length) AARRAY_Error_OutOfMemory(newSize)); \
310  AARRAY_FIX_POINTERS(TYPE) } \
311  *vec = (TYPE*)(length+1);
312 
313 // allocate minimum, and any future length change throws an error
314 #define AARRAY_ALLOC_STATIC(TYPE) \
315  size_t curSize = (*length) * sizeof(TYPE) + sizeof(size_t); \
316  size_t newSize = ((*length) + (ilen-rlen)) * sizeof(TYPE) + sizeof(size_t); \
317  if(*vec) { AARRAY_safety((void)curSize;, \
318  if(newSize!=curSize) AARRAY_nowarn_align( \
319  AARRAY_Error_ArrayIsStatic(*((size_t*)*vec-1)))) } \
320  else { length = (size_t*)realloc(NULL, newSize); \
321  AARRAY_safety(, if(!length) AARRAY_Error_OutOfMemory(newSize)); \
322  AARRAY_FIX_POINTERS(TYPE) } \
323  *vec = (TYPE*)(length+1);
324 
325 // store capacity
326 #define AARRAY_ALLOC_STD(TYPE) \
327  AARRAY_nowarn_align(size_t curSize = *vec? *((size_t*)*vec-2) : 0;) \
328  size_t newSize = ((*length) + (ilen-rlen)) * sizeof(TYPE) + \
329  sizeof(size_t) + sizeof(size_t); \
330  if((!*vec || newSize > curSize)) { \
331  newSize = AARRAY_upper_power_of_two(newSize); \
332  length = (size_t*)realloc(!*vec? NULL : length-1, newSize); \
333  AARRAY_safety(, if(!length) AARRAY_Error_OutOfMemory(newSize)); \
334  *length = newSize; \
335  length += 1; \
336  AARRAY_FIX_POINTERS(TYPE) } \
337  *vec = (TYPE*)(length+1);
338 
339 //// handle array allocation
340 #define AARRAY_Expand(TYPE, GROWTH) \
341  /* use rlen (remove length) and ilen (insert length), \
342  to setup vec ready for any new data to be inserted/appended \
343  -- essentially a realloc + a memmove */ \
344  size_t*length, lengthHolder = 0; \
345  if(!*vec) length = &lengthHolder; \
346  else AARRAY_nowarn_align(length = (size_t*)*vec-1;) \
347  AARRAY_safety((void)errLoc;, \
348  if(pos > *length) AARRAY_Error_OutOfBounds(*length, pos) \
349  if(rlen > (*length) - pos) \
350  AARRAY_Error_RemovalIsOutOfBounds(*length, pos, rlen)) \
351  if(rlen > ilen && (*length)-(pos+rlen)) \
352  /* move when still have items (before realloc clips them) */ \
353  memmove(&((*vec)[pos+ilen]), &((*vec)[pos+rlen]), \
354  sizeof(TYPE) * ((*length) - (pos+rlen))); \
355  /* calculate curSize and newSize */ \
356  AARRAY_ALLOC_##GROWTH(TYPE) \
357  if(rlen < ilen && (*length)-(pos+rlen)) { \
358  /* move when have space to put items (after realloc creates it) */ \
359  memmove(&((*vec)[pos+ilen]), &((*vec)[pos+rlen]), \
360  sizeof(TYPE) * ((*length) - (pos+rlen))); }
361 
362 
363 
364 
365 //// generate type specific and growth-strategy specific functions
366 $define AARRAY_Replace(TYPE, GROWTH,)
367 AARRAY_define(TYPE*AARRAY_Replace_$##GROWTH$##_$##TYPE(char errLoc[],
368  TYPE*vec[], size_t pos, size_t rlen, size_t ilen, TYPE items[]), {
369  //// replaces section of a array with N items
370  if(vec) { AARRAY_prefetch((size_t*)*vec-1, 1, 1); }
371  // vecs is {array1 ... arrayN}, but doesn't contain pointers;
372  // so vsIncr skipped with setting it to 0
373  size_t vecsCount = 1; size_t vecsIncr = 0;
374  AARRAY_nowarn_align(uintptr_t*vecs = (uintptr_t*)items;)
375  TYPE*vecHolder = NULL; if(!vec) vec = &vecHolder;
376  AARRAY_Expand(TYPE, GROWTH);
377  if(*vec) {
378  if(ilen) memcpy(&((*vec)[pos]), vecs, sizeof(TYPE) * ilen);
379  AARRAY_nowarn_align(*((size_t*)(*vec)-1) += ilen-rlen;) }
380  return *vec; })
381 
382 //// GENERATE_GENERICS creates functions for each data type,
383 // FTYPE also make it specific to a block|lambda|function-pointer
384 // These functions are then put into an array,
385 // letting us select the right one at compile time
386 $define GENERATE_GENERICS(GENERATOR, GROWTH, FTYPE)
387 GENERATOR(int8_t, GROWTH, FTYPE)
388 GENERATOR(int16_t, GROWTH, FTYPE)
389 GENERATOR(int32_t, GROWTH, FTYPE)
390 GENERATOR(int64_t, GROWTH, FTYPE)
391 static void(*const GENERATOR$##_$##GROWTH$##_FUNCTIONS[8])(void) = {
392  (void(*)(void))&GENERATOR$##_$##GROWTH$##_int8_t,
393  (void(*)(void))&GENERATOR$##_$##GROWTH$##_int16_t, 0,
394  (void(*)(void))&GENERATOR$##_$##GROWTH$##_int32_t, 0, 0, 0,
395  (void(*)(void))&GENERATOR$##_$##GROWTH$##_int64_t };
396 
397 $define GENERATE_GENERICS_GROWTH(FNAME)
398 GENERATE_GENERICS(AARRAY_$##FNAME,NOCAPACITY)
399 GENERATE_GENERICS(AARRAY_$##FNAME,STATIC)
400 GENERATE_GENERICS(AARRAY_$##FNAME,STD)
401 
402 GENERATE_GENERICS_GROWTH(Replace)
403 
404 $define AARRAY_Append(TYPE, GROWTH,)
405 AARRAY_define(TYPE*AARRAY_Append_$##GROWTH$##_$##TYPE(char errLoc[],
406  TYPE*vec[], size_t ilen, TYPE items[]), {
407  AARRAY_nowarn_align(size_t pos = vec && *vec?
408  // get array length
409  *((size_t*)*vec-1) : 0;)
410  return AARRAY_Replace_$##GROWTH$##_$##TYPE(
411  errLoc, vec, pos, 0, ilen, items); })
412 
413 GENERATE_GENERICS_GROWTH(Append)
414 
415 $define AARRAY_Concat(TYPE, GROWTH,)
416 AARRAY_define(TYPE*AARRAY_Concat_$##GROWTH$##_$##TYPE(char errLoc[],
417  TYPE*vec[], size_t vecsCount, TYPE*vecs_[]), {
418  if(vec) { AARRAY_prefetch((size_t*)*vec-1, 1, 1); }
419  uintptr_t*vecs = (uintptr_t*)vecs_;
420  size_t rlen = 0; size_t ilen = 0;
421  size_t n = (size_t)-1;
422  while(++n < vecsCount) if(vecs[n])
423  ilen += *((size_t*)vecs[n]-1);
424  // vecs is {vec0, ... ,vecN}, so vsIncr is 1
425  size_t vecsIncr = 1;
426  TYPE*vecHolder = NULL; if(!vec) vec = &vecHolder;
427  AARRAY_nowarn_align(size_t pos = *vec? *((size_t*)*vec-1) : 0;)
428  AARRAY_Expand(TYPE, GROWTH);
429  if(*vec) {
430  AARRAY_nowarn_align(size_t vLen = *((size_t*)*vec-1);)
431  n = (size_t)-1; while(++n < vecsCount) {
432  if(!vecs[n]) continue;
433  size_t ns = (size_t)-1, vsnLen;
434  vsnLen = *((size_t*)vecs[n]-1);
435  while(++ns < vsnLen) (*vec)[vLen+ns] = vecs_[n][ns];
436  vLen += vsnLen; }
437  AARRAY_nowarn_align(*((size_t*)*vec-1) += ilen;) }
438  return *vec; })
439 
440 GENERATE_GENERICS_GROWTH(Concat)
441 
442 $define AARRAY_GenericArray(TYPE, GROWTH,)
443 AARRAY_define(TYPE*AARRAY_GenericArray_$##GROWTH$##_$##TYPE(char errLoc[],
444  TYPE*vec[], size_t pos, size_t rlen, size_t vecsCount, uintptr_t vecs[]), {
445  size_t n = 0; size_t alen, ilen = 0;
446  size_t vecsIncr = 2;
447  while(n < vecsCount) {
448  alen = vecs[n];
449  AARRAY_safety(, if(alen && vecs[n+1]==(uintptr_t)NULL)
450  AARRAY_Error_ArrayIsNull((n+2)/2));
451  if(alen==SIZE_MAX) { while(((TYPE*)vecs[n+1])[++alen]) { }
452  vecs[n] = alen; }
453  ilen += alen; n+=vecsIncr; }
454  // vecs is {len0, array0, ... lenN, arrayN}, so vsIncr is 2
455  TYPE*vecHolder = NULL; if(!vec) vec = &vecHolder;
456  AARRAY_Expand(TYPE, GROWTH);
457  if(*vec) {
458  n = 0; while(n < vecsCount) {
459  alen = vecs[n];
460  if(alen) {
461  memcpy(&((*vec)[pos]), (void*)vecs[n+1], sizeof(TYPE)*alen);
462  pos += alen; } n+=vecsIncr; }
463  AARRAY_nowarn_align(*((size_t*)*vec-1) += ilen-rlen;) }
464  return *vec; })
465 
466 GENERATE_GENERICS_GROWTH(GenericArray)
467 
468 $define AARRAY_ReplaceArray(TYPE, GROWTH,)
469 AARRAY_define(TYPE*AARRAY_ReplaceArray_$##GROWTH$##_$##TYPE(char errLoc[],
470  TYPE*vec[], size_t pos, size_t rlen, size_t vecsCount, uintptr_t vecs[]), {
471  if(vec) { AARRAY_prefetch((size_t*)*vec-1, 1, 1); }
472  AARRAY_safety(, if((vecsCount+3) % 2 != 1)
473  AARRAY_Error_WrongArgCount(vecsCount+3, 2, 3));
474  return AARRAY_GenericArray_$##GROWTH$##_$##TYPE(
475  errLoc, vec, pos, rlen, vecsCount, vecs); })
476 
477 GENERATE_GENERICS_GROWTH(ReplaceArray)
478 
479 $define AARRAY_AppendArray(TYPE, GROWTH,)
480 AARRAY_define(TYPE*AARRAY_AppendArray_$##GROWTH$##_$##TYPE(char errLoc[],
481  TYPE*vec[], size_t vecsCount, uintptr_t vecs[]), {
482  if(vec) { AARRAY_prefetch((size_t*)*vec-1, 1, 1); }
483  AARRAY_safety(, if((vecsCount+1) % 2 != 1)
484  AARRAY_Error_WrongArgCount(vecsCount+1, 2, 1));
485  AARRAY_nowarn_align(size_t pos = vec && *vec? *((size_t*)*vec-1) : 0;)
486  return AARRAY_GenericArray_$##GROWTH$##_$##TYPE(
487  errLoc, vec, pos, 0, vecsCount, vecs); })
488 
489 GENERATE_GENERICS_GROWTH(AppendArray)
490 
491 $define AARRAY_Multi(TYPE, GROWTH,)
492 AARRAY_define(TYPE*AARRAY_Multi_$##GROWTH$##_$##TYPE(char errLoc[],
493  TYPE*vec[], size_t pos, size_t rlen, size_t vecsCount, uintptr_t vecs[]), {
494  if(vec) { AARRAY_prefetch((size_t*)*vec-1, 1, 1); }
495  size_t*length, lengthHolder = 0;
496  if(!vec || !*vec) length = &lengthHolder;
497  else AARRAY_nowarn_align(length = (size_t*)*vec-1;)
498  size_t n = 0, alen, ilen = 0, atimes, newlen = *length, maxlen = newlen;
499  size_t saved_pos = pos, saved_rlen = rlen;
500  size_t vecsIncr = 5;
501  AARRAY_safety(, if((vecsCount+3) % 5 != 1)
502  AARRAY_Error_WrongArgCount(vecsCount+3, 5, 1));
503  while(n < vecsCount) {
504  atimes = vecs[n]; alen = vecs[n+1];
505  AARRAY_safety(, if(atimes && alen && !vecs[n+2])
506  AARRAY_Error_ArrayIsNull(n/5+1));
507  if(alen==SIZE_MAX) { while(((TYPE*)vecs[n+2])[++alen]) { }
508  vecs[n+1] = alen; }
509  // check input, and work out max length required for array
510  if(n) { pos = vecs[n-2]; rlen = vecs[n-1]; }
511  if(pos > newlen) AARRAY_Error_OutOfBounds(*length, pos)
512  if(rlen > newlen - pos) AARRAY_Error_RemovalIsOutOfBounds(newlen, pos, rlen)
513  ilen = atimes? atimes * alen : alen;
514  newlen += ilen - rlen;
515  if(newlen > maxlen) maxlen = newlen;
516  n+=vecsIncr; }
517  ilen = maxlen - *length; rlen = 0;
518  // vecs is {times0, len0, array0, ... timesN, lenN, arrayN}, so vsIncr is 3
519  TYPE*vecHolder = NULL; if(!vec) vec = &vecHolder;
520  AARRAY_ALLOC_$##GROWTH(TYPE)
521  if(*vec) {
522  n = 0; pos = saved_pos; rlen = saved_rlen;
523  do {
524  atimes = vecs[n]; alen = vecs[n+1];
525  if(n) { pos = vecs[n-2]; rlen = vecs[n-1]; }
526  ilen = atimes? atimes * alen : alen;
527  if(ilen-rlen) {
528  memmove(&((*vec)[pos+ilen]), &((*vec)[pos+rlen]),
529  sizeof(TYPE) * ((*length) - (pos+rlen)));
530  *length += ilen-rlen; }
531  if(!atimes) {}
532  else while(atimes--) {
533  memcpy(&((*vec)[pos]), (void*)vecs[n+2], sizeof(TYPE) * alen);
534  pos += alen; }
535  n+=vecsIncr;
536  } while(n < vecsCount); }
537  return *vec; })
538 
539 GENERATE_GENERICS_GROWTH(Multi)
540 
541 //// cppp macros to be pre-pre-processed
542 // if this is aArray.h, they will have become the final exposed api:
543 // each of their internals pre expanded by cppp; so your compiler
544 // syntax warnings/errors are clearer
545 
546 // cppp to get the number of var-arg arguments, and make them generic
547 $define AARRAY_Args(sizeofType, ...) AARRAY_nowarn_internal_start \
548  (sizeofType==1? sizeof((uint8_t[] ){(uint8_t)__VA_ARGS__}) : \
549  sizeofType==2? sizeof((uint16_t[]){(uint16_t)__VA_ARGS__}) : \
550  sizeofType<=4? sizeof((uint32_t[]){(uint32_t)__VA_ARGS__}) : \
551  sizeofType<=8? sizeof((uint64_t[]){(uint64_t)__VA_ARGS__}) : \
552  AARRAY_Error_ArrayIsWide) / sizeofType, \
553  (sizeofType==1? (void*)AARRAY_move((uint8_t []){(uint8_t)__VA_ARGS__}) : \
554  sizeofType==2? (void*)AARRAY_move((uint16_t[]){(uint16_t)__VA_ARGS__}) : \
555  sizeofType<=4? (void*)AARRAY_move((uint32_t[]){(uint32_t)__VA_ARGS__}) : \
556  (void*)AARRAY_move((uint64_t[]){(uint64_t)__VA_ARGS__})) \
557  AARRAY_nowarn_internal_end
558 
559 
560 // as above, but for 64 bit only, such as aFmt
561 $define AARRAY_64bitArgs(...) AARRAY_nowarn_internal_start \
562 sizeof((uint64_t[]){(uint64_t)__VA_ARGS__}) / sizeof(uint64_t), \
563  (uint64_t*)AARRAY_move((uint64_t[]){(uint64_t)__VA_ARGS__}) \
564  AARRAY_nowarn_internal_end
565 
566 // make c++ happy
567 $define AARRAY_PtrArgs_WARN(...) \
568  sizeof((void*[]){(void*)__VA_ARGS__}) / sizeof(void*), \
569  (uintptr_t*)AARRAY_move((void*[]){(void*)__VA_ARGS__})
570 
571 // as above, but hide compiler warnings for mixed int/pointer arrays
572 // uintptr_t conversion of first arg resolves gcc issue
573 $define AARRAY_PtrArgs(...) AARRAY_nowarn_internal_start \
574  sizeof((uintptr_t[]){(uintptr_t)__VA_ARGS__}) / sizeof(uintptr_t), \
575  (uintptr_t*)AARRAY_move((uintptr_t[]){(uintptr_t)__VA_ARGS__}) \
576  AARRAY_nowarn_internal_end
577 
578 // get around requirement for __VA_ARGS__ to not be empty
579 #define AARRAY_ArgsTail(A, ...) __VA_ARGS__
580 
581 #if defined(AARRAY_NOTYPEOF) \
582  || (defined(_MSC_VER) && !__has_feature(cxx_decltype))
583 // create api functions without type-casts
584 #define AARRAY_typeof(TYPE, EXPR) EXPR
585 #elif __has_feature(cxx_decltype)
586 // +0 resolves c++ compliance
587 #define AARRAY_typeof(TYPE, EXPR) (__decltype(TYPE+0))(EXPR)
588 #else
589 #define AARRAY_typeof(TYPE, EXPR) \
590  AARRAY_nowarn_internal_start (__typeof(TYPE))(EXPR) AARRAY_nowarn_internal_end
591 #endif
592 
593 //// generate the main apis for c, c++, and compilers without __typeof support
594 $define GENERATE_api(NAME, GROWTH)
595 #define aAppend$##NAME(vec, ...) \
596  (AARRAY_typeof(*vec, (void*(*)(char[], void**, size_t, void*)) \
597  AARRAY_Append_$##GROWTH$##_FUNCTIONS[sizeof(**vec)-1]) \
598  (AARRAY_LINE, (void**)vec, AARRAY_Args(sizeof(**vec), __VA_ARGS__)))
599 #define aReplace$##NAME(vec, pos, rlen, ...) \
600  (AARRAY_typeof(*vec, (void*(*)( \
601  char[], void**, size_t, size_t, size_t, void*)) \
602  AARRAY_Replace_$##GROWTH$##_FUNCTIONS[sizeof(**vec)-1]) \
603  (AARRAY_LINE, (void**)vec, pos, rlen, \
604  AARRAY_Args(sizeof(**vec), __VA_ARGS__)))
605 #define aDelete$##NAME(vec, pos, rlen) \
606  (AARRAY_typeof(*vec, (void*(*)( \
607  char[], void**, size_t, size_t, size_t, void*)) \
608  AARRAY_Replace_$##GROWTH$##_FUNCTIONS[sizeof(**vec)-1]) \
609  (AARRAY_LINE, (void**)vec, pos, rlen, 0, NULL))
610 #define aConcat$##NAME(vec, ...) \
611  (AARRAY_typeof(*vec, (void*(*)(char[], void**, size_t, uintptr_t*)) \
612  AARRAY_Concat_$##GROWTH$##_FUNCTIONS[sizeof(**vec)-1]) \
613  (AARRAY_LINE, (void**)vec, AARRAY_PtrArgs_WARN(__VA_ARGS__)))
614 #define aAppendArray$##NAME(vec, ...) \
615  (AARRAY_typeof(*vec, (void*(*)(char[], void**, size_t, uintptr_t*)) \
616  AARRAY_AppendArray_$##GROWTH$##_FUNCTIONS[sizeof(**vec)-1]) \
617  (AARRAY_LINE, (void**)vec, AARRAY_PtrArgs(__VA_ARGS__)))
618 #define aReplaceArray$##NAME(vec, pos, rlen, ...) \
619  (AARRAY_typeof(*vec, (void*(*)( \
620  char[], void**, size_t, size_t, size_t, uintptr_t*)) \
621  AARRAY_ReplaceArray_$##GROWTH$##_FUNCTIONS[sizeof(**vec)-1]) \
622  (AARRAY_LINE, (void**)vec, pos, rlen, AARRAY_PtrArgs(__VA_ARGS__)))
623 #define aMulti$##NAME(vec, pos, rlen, arrTimes, ...) \
624  (AARRAY_typeof(*vec, (void*(*)( \
625  char[], void**, size_t, size_t, size_t, uintptr_t*)) \
626  AARRAY_Multi_$##GROWTH$##_FUNCTIONS[sizeof(**vec)-1]) \
627  (AARRAY_LINE, (void**)vec, pos, rlen, \
628  AARRAY_PtrArgs(arrTimes, __VA_ARGS__)))
629 
630 GENERATE_api(_NOCAPACITY, NOCAPACITY)
631 GENERATE_api(_STATIC, STATIC)
632 GENERATE_api(, STD)
633 
634 // make pointer casts safer: ensuring data can become (void$##stars)data
635 $define safe_void(stars, data)
636 0?(void$##stars)(uintptr_t)sizeof( \
637  stars$##data/* stars$##ptr check failed */ \
638  ):(void$##stars)data
639 
640 AARRAY_define(void AARRAY_Free(void*vec[]), {
641  if(*vec) { free((size_t*)*vec-2); *vec = NULL; } })
642 #define aFree(vec) \
643  AARRAY_Free(safe_void(**,vec))
644 AARRAY_define(void AARRAY_Free_NOCAPACITY(void*vec[]), {
645  if(*vec) { free((size_t*)*vec-1); *vec = NULL; } })
646 AARRAY_define(void AARRAY_Free_STATIC(void*vec[]), {
647  AARRAY_Free_NOCAPACITY(vec); }) // to make stack traces clearer
648 #define aFree_NOCAPACITY(vec) \
649  AARRAY_Free_NOCAPACITY(safe_void(**,vec))
650 #define aFree_STATIC(vec) \
651  AARRAY_Free_STATIC(safe_void(**,vec))
652 
653 
654 
655 
656 //// supporting api
657 AARRAY_define(size_t AARRAY_aLength(void*vec), {
658  return !vec? 0 : *((size_t*)vec-1); })
659 #define aLength(vec) AARRAY_aLength(safe_void(*,vec))
660 
661 $define AARRAY_Length2(TYPE, ...)
662 AARRAY_define(TYPE AARRAY_Length2__$##TYPE(
663  char errLoc[], TYPE vec[], size_t pos), {
664  if(!vec) AARRAY_safety(return 0; (void)errLoc;,
665  { if(pos==0) return 0; else AARRAY_Error_OutOfBounds(aLength(vec), pos); })
666  AARRAY_nowarn_align(size_t*length = (size_t*)vec-1;)
667  AARRAY_safety(, if(pos > *length)
668  AARRAY_Error_OutOfBounds(aLength(vec), pos));
669  *length = pos;
670  // if(pos==0) { pos-1 will index into *length (which is 0);
671  // so vec[pos-1] is safe and returns 0 }
672  return vec[pos-1]; })
673 
674 GENERATE_GENERICS(AARRAY_Length2)
675 #define aLength2(vec, len) \
676  (AARRAY_typeof(*vec, (uint64_t(*)(char[], void*, size_t)) \
677  AARRAY_Length2__FUNCTIONS[sizeof(*vec)-1]) \
678  (AARRAY_LINE, (void*)vec, len))
679 
680 $define AARRAY_ZLength2(TYPE, ...)
681 AARRAY_define(TYPE AARRAY_ZLength2__$##TYPE(
682  char errLoc[], TYPE vec[], size_t pos), {
683  return AARRAY_Length2__$##TYPE(errLoc, vec, aLength(vec) - pos); })
684 
685 GENERATE_GENERICS(AARRAY_ZLength2)
686 #define aZLength2(vec, len) \
687  (AARRAY_typeof(*vec, (uint64_t(*)(char[], void*, size_t)) \
688  AARRAY_ZLength2__FUNCTIONS[sizeof(*vec)-1]) \
689  (AARRAY_LINE, (void*)vec, len))
690 
691 $define AARRAY_AtPtr(TYPE, ...)
692 AARRAY_define(TYPE*AARRAY_AtPtr__$##TYPE(
693  char errLoc[], TYPE vec[], size_t pos), {
694  AARRAY_safety((void)errLoc;,
695  if(pos >= aLength(vec)) AARRAY_Error_OutOfBounds(aLength(vec), pos));
696  return &(vec[pos]); })
697 
698 GENERATE_GENERICS(AARRAY_AtPtr)
699 #define aAtPtr(vec, pos) \
700  (AARRAY_typeof(vec, (uint64_t*(*)(char[], void*, size_t)) \
701  AARRAY_AtPtr__FUNCTIONS[sizeof(*vec)-1]) \
702  (AARRAY_LINE, (void*)vec, pos))
703 
704 $define AARRAY_ZAtPtr(TYPE, ...)
705 AARRAY_define(TYPE*AARRAY_ZAtPtr__$##TYPE(
706  char errLoc[], TYPE vec[], size_t pos), {
707  return AARRAY_AtPtr__$##TYPE(errLoc, vec, aLength(vec) - (pos+1)); })
708 
709 GENERATE_GENERICS(AARRAY_ZAtPtr)
710 #define aZAtPtr(vec, pos) \
711  (AARRAY_typeof(vec, (uint64_t*(*)(char[], void*, size_t)) \
712  AARRAY_ZAtPtr__FUNCTIONS[sizeof(*vec)-1]) \
713  (AARRAY_LINE, (void*)vec, pos))
714 
715 $define AARRAY_At(TYPE, ...)
716 AARRAY_define(TYPE AARRAY_At__$##TYPE(
717  char errLoc[], TYPE vec[], size_t pos), {
718  AARRAY_safety((void)errLoc;,
719  if(pos >= aLength(vec)) AARRAY_Error_OutOfBounds(aLength(vec), pos));
720  return vec[pos]; })
721 
722 GENERATE_GENERICS(AARRAY_At)
723 #define aAt(vec, pos) \
724  (AARRAY_typeof(*vec, (uint64_t(*)(char[], void*, size_t)) \
725  AARRAY_At__FUNCTIONS[sizeof(*vec)-1]) \
726  (AARRAY_LINE, (void*)vec, pos))
727 
728 $define AARRAY_ZAt(TYPE, ...)
729 AARRAY_define(TYPE AARRAY_ZAt__$##TYPE(
730  char errLoc[], TYPE vec[], size_t pos), {
731  return AARRAY_At__$##TYPE(errLoc, vec, aLength(vec) - (pos+1)); })
732 
733 GENERATE_GENERICS(AARRAY_ZAt)
734 #define aZAt(vec, pos) \
735  (AARRAY_typeof(*vec, (uint64_t(*)(char[], void*, size_t)) \
736  AARRAY_ZAt__FUNCTIONS[sizeof(*vec)-1]) \
737  (AARRAY_LINE, (void*)vec, pos))
738 
739 $define AARRAY_At2(TYPE, ...)
740 AARRAY_define(TYPE AARRAY_At2__$##TYPE(
741  char errLoc[], TYPE vec[], size_t pos, TYPE item), {
742  AARRAY_safety((void)errLoc;,
743  if(pos >= aLength(vec)) AARRAY_Error_OutOfBounds(aLength(vec), pos));
744  vec[pos] = item;
745  return item; })
746 
747 GENERATE_GENERICS(AARRAY_At2)
748 #define aAt2(vec, pos, item) \
749  (AARRAY_typeof(*vec, (uint64_t(*)(char[], void*, size_t, uint64_t)) \
750  AARRAY_At2__FUNCTIONS[sizeof(*vec)-1]) \
751  (AARRAY_LINE, (void*)vec, pos, \
752  AARRAY_nowarn_internal_start (uint64_t)item AARRAY_nowarn_internal_end))
753 
754 $define AARRAY_ZAt2(TYPE, ...)
755 AARRAY_define(TYPE AARRAY_ZAt2__$##TYPE(
756  char errLoc[], TYPE vec[], size_t pos, TYPE item), {
757  return AARRAY_At2__$##TYPE(errLoc, vec, aLength(vec) - (pos+1), item); })
758 
759 GENERATE_GENERICS(AARRAY_ZAt2)
760 #define aZAt2(vec, pos, item) \
761  (AARRAY_typeof(*vec, (uint64_t(*)(char[], void*, size_t, uint64_t)) \
762  AARRAY_ZAt2__FUNCTIONS[sizeof(*vec)-1]) \
763  (AARRAY_LINE, (void*)vec, pos, \
764  AARRAY_nowarn_internal_start item AARRAY_nowarn_internal_end))
765 
766 $define AARRAY_Cmp(TYPE, ...)
767 AARRAY_define(int AARRAY_Cmp__$##TYPE(
768  TYPE vec[], size_t n, TYPE*vecs[]), {
769  while(n--) {
770  if(vec == vecs[n]) continue;
771  if(aLength(vec) != aLength(vecs[n])) return 0;
772  if(aLength(vec)==0) continue;
773  // surely memcmp would work, but this upsets MSan
774  //memcmp(((size_t*)(uintptr_t)vec-1), ((size_t*)(uintptr_t)vecs[n]-1),
775  // aLength(vec)*sizeof(TYPE)+sizeof(size_t));
776  size_t m = 0; while(++m < aLength(vec)) if(vec[m]!=vecs[n][m]) return 0; }
777  return 1; })
778 
779 GENERATE_GENERICS(AARRAY_Cmp)
780 #define aCmp(vec, ...) \
781  (((int(*)(void*, size_t, void*)) \
782  AARRAY_Cmp__FUNCTIONS[sizeof(*vec)-1]) \
783  ((void*)vec, AARRAY_PtrArgs_WARN(__VA_ARGS__)))
784 
785 
786 
787 
788 $define AARRAY_IndexOf(TYPE, ...)
789 AARRAY_define(size_t AARRAY_IndexOf__$##TYPE(TYPE vec[], TYPE item), {
790  size_t length = aLength(vec), i = (size_t)-1;
791  while(++i < length) if(vec[i]==item) return i;
792  return (size_t)-1; })
793 
794 GENERATE_GENERICS(AARRAY_IndexOf,)
795 #define aIndexOf(vec, item) \
796  ((size_t(*)(void*, uint64_t)) \
797  AARRAY_IndexOf__FUNCTIONS[sizeof(*vec)-1])(vec, \
798  AARRAY_nowarn_internal_start item AARRAY_nowarn_internal_end)
799 
800 $define AARRAY_ZIndexOf(TYPE, ...)
801 AARRAY_define(size_t AARRAY_ZIndexOf__$##TYPE(TYPE vec[], TYPE item), {
802  size_t i = aLength(vec);
803  while(i--) if(vec[i]==item) return i;
804  return (size_t)-1; })
805 
806 GENERATE_GENERICS(AARRAY_ZIndexOf,)
807 #define aZIndexOf(vec, item) \
808  ((size_t(*)(void*, uint64_t)) \
809  AARRAY_ZIndexOf__FUNCTIONS[sizeof(*vec)-1])(vec, \
810  AARRAY_nowarn_internal_start item AARRAY_nowarn_internal_end)
811 
812 
813 
814 
815 $define AARRAY_Map(TYPE, FNAME, FTYPE)
816 AARRAY_define(void AARRAY_Map_$##FNAME$##_$##TYPE(
817  char errLoc[], TYPE vec[], FTYPE(TYPE)), {
818  AARRAY_safety((void)errLoc, if(!f) AARRAY_Error_NullParameter);
819  size_t n = (size_t)-1;
820  while(++n < aLength(vec)) f(&(vec[n])); })
821 
822 $define AARRAY_Loop(TYPE, FNAME, FTYPE)
823 AARRAY_define(int AARRAY_Loop_$##FNAME$##_$##TYPE(
824  char errLoc[], TYPE vec[], size_t pos, FTYPE), {
825  AARRAY_safety((void)errLoc, if(!f) AARRAY_Error_NullParameter);
826  int offset = 0;
827  while(pos < aLength(vec)) {
828  if((offset > 0 && pos < (size_t)offset) ||
829  (offset < 0 && pos > (size_t)offset)) return offset;
830  offset = f(pos);
831  if(!offset) return 0;
832  // play safe with int promotion
833  if(offset > 0) pos += (size_t) offset;
834  else pos -= (size_t)-offset; }
835  return offset; })
836 
837 $define AARRAY_Filter(TYPE, FNAME, FTYPE)
838 AARRAY_define(TYPE* AARRAY_Filter_$##FNAME$##_$##TYPE(
839  char errLoc[], TYPE*vec, FTYPE(TYPE)), {
840  AARRAY_safety((void)errLoc, if(!f) AARRAY_Error_NullParameter);
841  size_t n = (size_t)-1, nn = (size_t)-1;
842  while(++n < aLength(vec)) {
843  if(f(&(vec[n]))) vec[++nn] = vec[n]; }
844  (void)aLength2(vec, nn+1);
845  return vec; })
846 
847 $define FUNC_void_ptrT(TYPE) void(*f)(TYPE*)
848 
849 $define FUNC_int_ptrT(TYPE) int(*f)(TYPE*)
850 
851 GENERATE_GENERICS(AARRAY_Map, FUNC, FUNC_void_ptrT)
852 #define aMap_FUNC(vec, f) \
853  ((void(*)(char[], void*, void(*)(void))) \
854  AARRAY_Map_FUNC_FUNCTIONS[sizeof(*vec)-1])(AARRAY_LINE, vec, (void(*)(void))f)
855 GENERATE_GENERICS(AARRAY_Loop, FUNC, int(*f)(size_t))
856 #define aLoop_FUNC(vec, pos, f) \
857  ((int(*)(char[], void*, size_t, int(*)(size_t))) \
858  AARRAY_Loop_FUNC_FUNCTIONS[sizeof(*vec)-1])(AARRAY_LINE, vec, pos, f)
859 
860 GENERATE_GENERICS(AARRAY_Filter, FUNC, FUNC_int_ptrT)
861 #define aFilter_FUNC(vec, f) \
862  (AARRAY_typeof(vec, (uint64_t*(*)(char[], void*, void(*)(void))) \
863  AARRAY_Filter_FUNC_FUNCTIONS[sizeof(*vec)-1]) \
864  (AARRAY_LINE, vec,(void(*)(void))f))
865 
866 #if __has_extension(blocks)
867 $define BLOCK_void_ptrT(TYPE) void(^f)(TYPE*)
868 
869 $define BLOCK_int_ptrT(TYPE) int(^f)(TYPE*)
870 
871 GENERATE_GENERICS(AARRAY_Map, BLOCK, BLOCK_void_ptrT)
872 #define aMap_BLOCK(vec, f) \
873  ((void(*)(char[], void*, void(^)(void*))) \
874  AARRAY_Map_BLOCK_FUNCTIONS[sizeof(*vec)-1]) \
875  (AARRAY_LINE, vec, (void(^)(void*))f)
876 GENERATE_GENERICS(AARRAY_Loop, BLOCK, int (^f)(size_t))
877 #define aLoop_BLOCK(vec, pos, f) \
878  ((int(*)(char[], void*, size_t, int(^)(size_t))) \
879  AARRAY_Loop_BLOCK_FUNCTIONS[sizeof(*vec)-1])(AARRAY_LINE, vec, pos, f)
880 
881 GENERATE_GENERICS(AARRAY_Filter, BLOCK, BLOCK_int_ptrT)
882 #define aFilter_BLOCK(vec, f) \
883  (AARRAY_typeof(vec, (uint64_t*(*)(char[], void*, int(^)(uint64_t*))) \
884  AARRAY_Filter_BLOCK_FUNCTIONS[sizeof(*vec)-1]) \
885  (AARRAY_LINE, vec,(int(^)(uint64_t*))f))
886 #endif
887 
888 #if defined(__cplusplus)
889 $define LAMBDA_void_ptrT(TYPE) std::function<void(TYPE*)> f
890 
891 $define LAMBDA_int_ptrT(TYPE) std::function<int(TYPE*)> f
892 
893 GENERATE_GENERICS(AARRAY_Map, LAMBDA, LAMBDA_void_ptrT)
894 #define aMap_LAMBDA(vec, f) \
895  ((void(*)(char[], void*, std::function<void(void*)>)) \
896  AARRAY_Map_LAMBDA_FUNCTIONS[sizeof(*vec)-1])(AARRAY_LINE, vec, f)
897 GENERATE_GENERICS(AARRAY_Loop, LAMBDA, std::function<int(size_t)> f)
898 #define aLoop_LAMBDA(vec, pos, f) \
899  ((int(*)(char[], void*, size_t, std::function<int(size_t)>)) \
900  AARRAY_Loop_LAMBDA_FUNCTIONS[sizeof(*vec)-1])(AARRAY_LINE, vec, pos, f)
901 
902 GENERATE_GENERICS(AARRAY_Filter, LAMBDA, LAMBDA_int_ptrT)
903 #define aFilter_LAMBDA(vec, f) \
904  (AARRAY_typeof(vec, (uint64_t*(*)(char[], void*, std::function<int(void*)>))\
905  AARRAY_Filter_LAMBDA_FUNCTIONS[sizeof(*vec)-1])(AARRAY_LINE, vec, f))
906 #endif
907 
908 
909 
910 
911 // aFold is generic over array_type, function_type, AND base_type
912 // Rather than make previous cppp macros more generic, we treat aFold as unique
913 // Though it's possible to create macros that genericize any c function
914 // Which would be useful...
915 $define AARRAY_Fold(TYPEB, TYPE, FNAME, FTYPE)
916 AARRAY_define(TYPEB AARRAY_Fold_$##FNAME$##_$##TYPEB$##_$##TYPE(
917  char errLoc[], TYPE*vec, TYPEB base,
918  FTYPE(TYPEB,TYPE)), {
919  AARRAY_safety((void)errLoc, if(!f) AARRAY_Error_NullParameter);
920  size_t n = (size_t)-1;
921  while(++n < aLength(vec)) base = f(base,vec[n]);
922  return base; })
923 
924 $define AARRAY_Fold_TYPEB(TYPE, FNAME, FTYPE)
925 AARRAY_Fold(int8_t, TYPE, FNAME, FTYPE)
926 AARRAY_Fold(int16_t, TYPE, FNAME, FTYPE)
927 AARRAY_Fold(int32_t, TYPE, FNAME, FTYPE)
928 AARRAY_Fold(int64_t, TYPE, FNAME, FTYPE)
929 
930 $define AARRAY_Fold_FNAME(FNAME, FTYPE)
931 AARRAY_Fold_TYPEB(int8_t, FNAME, FTYPE)
932 AARRAY_Fold_TYPEB(int16_t, FNAME, FTYPE)
933 AARRAY_Fold_TYPEB(int32_t, FNAME, FTYPE)
934 AARRAY_Fold_TYPEB(int64_t, FNAME, FTYPE)
935 static void(*const AARRAY_Fold_$##FNAME$##_FUNCTIONS[8][8])(void) = { {
936  (void(*)(void))&AARRAY_Fold_$##FNAME$##_int8_t_int8_t,
937  (void(*)(void))&AARRAY_Fold_$##FNAME$##_int8_t_int16_t, 0,
938  (void(*)(void))&AARRAY_Fold_$##FNAME$##_int8_t_int32_t, 0, 0, 0,
939  (void(*)(void))&AARRAY_Fold_$##FNAME$##_int8_t_int64_t }, {
940  (void(*)(void))&AARRAY_Fold_$##FNAME$##_int16_t_int8_t,
941  (void(*)(void))&AARRAY_Fold_$##FNAME$##_int16_t_int16_t, 0,
942  (void(*)(void))&AARRAY_Fold_$##FNAME$##_int16_t_int32_t, 0, 0, 0,
943  (void(*)(void))&AARRAY_Fold_$##FNAME$##_int16_t_int64_t }, {0}, {
944  (void(*)(void))&AARRAY_Fold_$##FNAME$##_int32_t_int8_t,
945  (void(*)(void))&AARRAY_Fold_$##FNAME$##_int32_t_int16_t, 0,
946  (void(*)(void))&AARRAY_Fold_$##FNAME$##_int32_t_int32_t, 0, 0, 0,
947  (void(*)(void))&AARRAY_Fold_$##FNAME$##_int32_t_int64_t }, {0}, {0}, {0}, {
948  (void(*)(void))&AARRAY_Fold_$##FNAME$##_int64_t_int8_t,
949  (void(*)(void))&AARRAY_Fold_$##FNAME$##_int64_t_int16_t, 0,
950  (void(*)(void))&AARRAY_Fold_$##FNAME$##_int64_t_int32_t, 0, 0, 0,
951  (void(*)(void))&AARRAY_Fold_$##FNAME$##_int64_t_int64_t } };
952 
953 $define AARRAY_FUNCTION_TB_TB_T(TYPEB, TYPE) TYPEB(*f)(TYPEB,TYPE)
954 
955 AARRAY_Fold_FNAME(FUNC, AARRAY_FUNCTION_TB_TB_T)
956 #define aFold_FUNC(vec, base, f) \
957  (AARRAY_typeof(base, (uint64_t(*)(char[], void*, uint64_t, void(*)(void))) \
958  AARRAY_Fold_FUNC_FUNCTIONS[sizeof(base)-1][sizeof(*vec)-1]) \
959  (AARRAY_LINE, vec, (uint64_t)base, (void(*)(void))f))
960 
961 
962 #if __has_extension(blocks)
963 $define AARRAY_BLOCK_TB_TB_T(TYPEB, TYPE) TYPEB(^f)(TYPEB,TYPE)
964 
965 AARRAY_Fold_FNAME(BLOCK, AARRAY_BLOCK_TB_TB_T)
966 #define aFold_BLOCK(vec, base, f) \
967  (AARRAY_typeof(base, (uint64_t(*)(char[], void*, uint64_t, \
968  uint64_t(^)(uint64_t,uint64_t))) \
969  AARRAY_Fold_BLOCK_FUNCTIONS[sizeof(base)-1][sizeof(*vec)-1]) \
970  (AARRAY_LINE, vec, (uint64_t)base, (uint64_t(^)(uint64_t,uint64_t))f))
971 #endif
972 #if defined(__cplusplus)
973 $define AARRAY_LAMBDA_TB_TB_T(TYPEB, TYPE) std::function<TYPEB(TYPEB,TYPE)>f
974 
975 AARRAY_Fold_FNAME(LAMBDA, AARRAY_LAMBDA_TB_TB_T)
976 #define aFold_LAMBDA(vec, base, f) \
977  (AARRAY_typeof(base, (uint64_t(*)(char[], void*, uint64_t, \
978  std::function<uint64_t(uint64_t,uint64_t)>)) \
979  AARRAY_Fold_LAMBDA_FUNCTIONS[sizeof(base)-1][sizeof(*vec)-1]) \
980  (AARRAY_LINE, vec, (uint64_t)base, f))
981 #endif
982 
983 
984 
985 
986 //// search and sort
987 // aSort needs a whole bunch of helper macros and functions
988 // thanks goes to: https://github.com/BonzaiThePenguin/WikiSort
989 $define AARRAY_swap(TYPE, a, b) { TYPE temp = a;
990  a = b;
991  b = temp; }
992 
993 $define AARRAY_SWAP(TYPE, x, y) \
994  if(f(array[sRange+y], array[sRange+x]) ||
995  (order[x] > order[y] && !f(array[sRange+x], array[sRange+y]))) {
996  AARRAY_swap(TYPE, array[sRange+x], array[sRange+y]);
997  AARRAY_swap(uint8_t, order[x], order[y]); }
998 
999 $define AARRAY_blockSwap(TYPE, array, start1, start2, block_size)
1000  for(size_t n = 0; n < block_size; n++)
1001  AARRAY_swap(TYPE, array[start1+n], array[start2+n])
1002 
1003 $define AARRAY_PULL(_to) \
1004  pull[pull_index].sRange = sA; \
1005  pull[pull_index].eRange = eB; \
1006  pull[pull_index].count = count; \
1007  pull[pull_index].from = index; \
1008  pull[pull_index].to = _to;
1009 
1010 $define AARRAY_sortFindFirstForward(FNAME, value, start, end, unique)
1011  if(end-start == 0) index = start;
1012  else {
1013  int indexSet = 0;
1014  size_t skip = (end-start)/(unique);
1015  if(!skip) skip = 1;
1016  for(index = start+skip; f(array[index-1], value); index += skip)
1017  if(index >= end-skip) {
1018  index = AARRAY_aSortBinaryFirst_$##FNAME(array, value, index, end, f);
1019  indexSet = 1; break; }
1020  if(!indexSet) index =
1021  AARRAY_aSortBinaryFirst_$##FNAME(array, value, index-skip, index, f); }
1022 
1023 $define AARRAY_sortFindLastForward(FNAME, value, start, end, unique)
1024  if(end-start == 0) index = start;
1025  else {
1026  int indexSet = 0;
1027  size_t skip = (end-start)/(unique);
1028  if(!skip) skip = 1;
1029  for(index = start+skip; !f(value, array[index-1]); index += skip)
1030  if(index >= end-skip) {
1031  index = AARRAY_aSortBinaryLast_$##FNAME(array, value, index, end, f);
1032  indexSet = 1; break; }
1033  if(!indexSet) index =
1034  AARRAY_aSortBinaryLast_$##FNAME(array, value, index-skip, index, f); }
1035 
1036 $define AARRAY_sortFindFirstBackward(FNAME, value, start, end, unique)
1037  if(end-start == 0) index = start;
1038  else {
1039  int indexSet = 0;
1040  size_t skip = (end-start)/(unique);
1041  if(!skip) skip = 1;
1042  for(index = end-skip; index > start
1043  && !f(array[index-1], value); index -= skip)
1044  if(index < start+skip) {
1045  index = AARRAY_aSortBinaryFirst_$##FNAME(array, value, start, index, f);
1046  indexSet = 1; break; }
1047  if(!indexSet) index =
1048  AARRAY_aSortBinaryFirst_$##FNAME(array, value, index, index+skip, f); }
1049 
1050 $define AARRAY_sortFindLastBackward(FNAME, value, start, end, unique)
1051  if(end-start == 0) index = start;
1052  else {
1053  int indexSet = 0;
1054  size_t skip = (end-start)/(unique);
1055  if(!skip) skip = 1;
1056  for(index = end-skip; index > start
1057  && f(value, array[index-1]); index -= skip)
1058  if(index < start+skip) {
1059  index = AARRAY_aSortBinaryLast_$##FNAME(array, value, start, index, f);
1060  indexSet = 1; break; }
1061  if(!indexSet) index =
1062  AARRAY_aSortBinaryLast_$##FNAME(array, value, index, index+skip, f); }
1063 
1064 $define AARRAY_sortReverse(TYPE, ...)
1065 AARRAY_define(void AARRAY_sortReverse__$##TYPE(
1066  TYPE vec[], size_t start, size_t end), {
1067  TYPE temp;
1068  for(size_t n = (end-start)/2; n > 0; n--) {
1069  temp = vec[start+n-1];
1070  vec[start+n-1] = vec[end-n];
1071  vec[end-n] = temp; } })
1072 
1073 $define AARRAY_sortBinaryFirst(TYPE, FNAME, FTYPE)
1074 AARRAY_define(size_t AARRAY_sortBinaryFirst_$##FNAME$##_$##TYPE(
1075  const TYPE array[], const TYPE value,
1076  size_t start, size_t end, FTYPE(TYPE)), {
1077  size_t rend = end;
1078  end -= 1;
1079  if(start >= rend) return start;
1080  while(start < end) {
1081  size_t mid = start+(end-start)/2;
1082  if(f(array[mid], value)) start = mid+1;
1083  else end = mid; }
1084  if(start == rend-1 && f(array[start], value)) start++;
1085  return start; })
1086 
1087 $define AARRAY_sortBinaryLast(TYPE, FNAME, FTYPE)
1088 AARRAY_define(size_t AARRAY_sortBinaryLast_$##FNAME$##_$##TYPE(
1089  const TYPE array[], const TYPE value,
1090  size_t start, size_t end, FTYPE(TYPE)), {
1091  size_t rend = end;
1092  end -= 1;
1093  if(start >= rend) return end;
1094  while(start < end) {
1095  size_t mid = start+(end-start)/2;
1096  if(!f(value, array[mid])) start = mid+1;
1097  else end = mid; }
1098  if(start == rend-1 && !f(value, array[start])) start++;
1099  return start; })
1100 
1101 typedef struct {
1102  size_t size, power_of_two;
1103  size_t numerator, decimal;
1104  size_t denominator, decimal_step, numerator_step; } AARRAY_sortIt;
1105 $define AARRAY_sortNextRange(TYPE, ...)
1106 AARRAY_define(void AARRAY_sortNextRange__$##TYPE(
1107  AARRAY_sortIt*it, size_t*start, size_t*end), {
1108  *start = it->decimal;
1109  it->decimal += it->decimal_step;
1110  it->numerator += it->numerator_step;
1111  if(it->numerator >= it->denominator) {
1112  it->numerator -= it->denominator;
1113  it->decimal++; }
1114  *end = it->decimal; })
1115 
1116 $define AARRAY_sortNextLevel(TYPE, ...)
1117 AARRAY_define(int AARRAY_sortNextLevel__$##TYPE(AARRAY_sortIt*it), {
1118  it->decimal_step += it->decimal_step;
1119  it->numerator_step += it->numerator_step;
1120  if(it->numerator_step >= it->denominator) {
1121  it->numerator_step -= it->denominator;
1122  it->decimal_step++; }
1123  return it->decimal_step < it->size; })
1124 
1125 GENERATE_GENERICS(AARRAY_sortReverse)
1126 #define AARRAY_aSortReverse(vec, start, end) \
1127  (((int(*)(void*, size_t, size_t)) \
1128  AARRAY_sortReverse__FUNCTIONS[sizeof(*vec)-1])((void*)vec, start, end))
1129 
1130 $define AARRAY_sortRotate(TYPE, ...)
1131 AARRAY_define(void AARRAY_sortRotate__$##TYPE(
1132  TYPE array[], const size_t amount, size_t start, size_t end,
1133  TYPE cache[], const size_t cacheSize), {
1134  if(end-start == 0) return;
1135  size_t sA = start, eA = start+amount, sB = start+amount, eB = end;
1136  if(eA-sA <= eB-sB) {
1137  if(eA-sA <= cacheSize) {
1138  memcpy(&cache[0], &array[sA], (eA-sA)*sizeof(array[0]));
1139  memmove(&array[sA], &array[sB], (eB-sB)*sizeof(array[0]));
1140  memcpy(&array[sA+(eB-sB)], &cache[0], (eA-sA)*sizeof(array[0]));
1141  return; } }
1142  else {
1143  if(eB-sB <= cacheSize) {
1144  memcpy(&cache[0], &array[sB], (eB-sB)*sizeof(array[0]));
1145  memmove(&array[eB-(eA-sA)], &array[sA], (eA-sA)*sizeof(array[0]));
1146  memcpy(&array[sA], &cache[0], (eB-sB)*sizeof(array[0]));
1147  return; } }
1148  AARRAY_aSortReverse(array, sA, eA);
1149  AARRAY_aSortReverse(array, sB, eB);
1150  AARRAY_aSortReverse(array, start, end); })
1151 
1152 $define AARRAY_sortMergeInto(TYPE, FNAME, FTYPE)
1153 AARRAY_define(void AARRAY_sortMergeInto_$##FNAME$##_$##TYPE(
1154  TYPE from[], size_t sA, size_t eA, size_t sB, size_t eB,
1155  FTYPE(TYPE), TYPE into[]), {
1156  TYPE*A_index = &from[sA], *B_index = &from[sB];
1157  TYPE*A_last = &from[eA], *B_last = &from[eB];
1158  TYPE*insert_index = &into[0];
1159  while(1) {
1160  if(!f(*B_index, *A_index)) {
1161  *insert_index = *A_index;
1162  A_index++;
1163  insert_index++;
1164  if(A_index == A_last) {
1165  memcpy(insert_index, B_index, (size_t)(B_last-B_index)*sizeof(from[0]));
1166  break; } }
1167  else {
1168  *insert_index = *B_index;
1169  B_index++;
1170  insert_index++;
1171  if(B_index == B_last) {
1172  memcpy(insert_index, A_index, (size_t)(A_last-A_index)*sizeof(from[0]));
1173  break; } } } })
1174 
1175 $define AARRAY_sortMergeExternal(TYPE, FNAME, FTYPE)
1176 AARRAY_define(void AARRAY_sortMergeExternal_$##FNAME$##_$##TYPE(
1177  TYPE array[], size_t sA, size_t eA, size_t sB, size_t eB,
1178  FTYPE(TYPE), TYPE cache[]), {
1179  TYPE*A_index = &cache[0];
1180  TYPE*B_index = &array[sB];
1181  TYPE*insert_index = &array[sA];
1182  TYPE*A_last = &cache[eA-sA];
1183  TYPE*B_last = &array[eB];
1184  if(eB-sB > 0 && eA-sA > 0) {
1185  while(1) {
1186  if(!f(*B_index, *A_index)) {
1187  *insert_index = *A_index;
1188  A_index++;
1189  insert_index++;
1190  if(A_index == A_last) break; }
1191  else {
1192  *insert_index = *B_index;
1193  B_index++;
1194  insert_index++;
1195  if(B_index == B_last) break; } } }
1196  memcpy(insert_index, A_index, (size_t)(A_last-A_index)*sizeof(array[0])); })
1197 
1198 $define AARRAY_sortMergeInternal(TYPE, FNAME, FTYPE)
1199 AARRAY_define(void AARRAY_sortMergeInternal_$##FNAME$##_$##TYPE(
1200  TYPE array[], size_t sA, size_t eA, size_t sB, size_t eB,
1201  FTYPE(TYPE), size_t sBuff), {
1202  size_t A_count = 0, B_count = 0, insert = 0;
1203  if(eB-sB > 0 && eA-sA > 0) {
1204  while(1) {
1205  if(!f(array[sB+B_count], array[sBuff+A_count])) {
1206  AARRAY_swap(TYPE, array[sA+insert], array[sBuff+A_count]);
1207  A_count++;
1208  insert++;
1209  if(A_count >= eA-sA) break; }
1210  else {
1211  AARRAY_swap(TYPE, array[sA+insert], array[sB+B_count]);
1212  B_count++;
1213  insert++;
1214  if(B_count >= eB-sB) break; } } }
1215  AARRAY_blockSwap(TYPE, array, sBuff+A_count, sA+insert, (eA-sA)-A_count); })
1216 
1217 $define FUNC_int_TT(TYPE) int(*f)(TYPE,TYPE)
1218 
1219 $define BLOCK_int_TT(TYPE) int(^f)(TYPE,TYPE)
1220 
1221 $define LAMBDA_int_TT(TYPE) std::function<int(TYPE, TYPE)>f
1222 
1223 GENERATE_GENERICS(AARRAY_sortRotate)
1224 #define AARRAY_aSortRotate(vec, value, start, end, vecb, cacheSize) \
1225  (((void(*)(void*, size_t, size_t, size_t, void*, size_t)) \
1226  AARRAY_sortRotate__FUNCTIONS[sizeof(*vec)-1]) \
1227  ((void*)vec, value, start, end, vecb, cacheSize))
1228 GENERATE_GENERICS(AARRAY_sortBinaryFirst, FUNC, FUNC_int_TT)
1229 GENERATE_GENERICS(AARRAY_sortBinaryLast, FUNC, FUNC_int_TT)
1230 #define AARRAY_aSortBinaryFirst_FUNC(vec, value, start, end, f) \
1231  (((size_t(*)(void*, int64_t, size_t, size_t, void(*)(void))) \
1232  AARRAY_sortBinaryFirst_FUNC_FUNCTIONS[sizeof(*vec)-1]) \
1233  ((void*)vec, value, start, end, (void(*)(void))f))
1234 #define AARRAY_aSortBinaryLast_FUNC(vec, value, start, end, f) \
1235  (((size_t(*)(void*, int64_t, size_t, size_t, void(*)(void))) \
1236  AARRAY_sortBinaryLast_FUNC_FUNCTIONS[sizeof(*vec)-1]) \
1237  ((void*)vec, value, start, end, (void(*)(void))f))
1238 
1239 #if __has_extension(blocks)
1240 GENERATE_GENERICS(AARRAY_sortBinaryFirst, BLOCK, BLOCK_int_TT)
1241 GENERATE_GENERICS(AARRAY_sortBinaryLast, BLOCK, BLOCK_int_TT)
1242 #define AARRAY_aSortBinaryFirst_BLOCK(vec, value, start, end, f) \
1243  (((size_t(*)(void*, int64_t, size_t, size_t, void*)) \
1244  AARRAY_sortBinaryFirst_BLOCK_FUNCTIONS[sizeof(*vec)-1]) \
1245  ((void*)vec, value, start, end, (void*)f))
1246 #define AARRAY_aSortBinaryLast_BLOCK(vec, value, start, end, f) \
1247  (((size_t(*)(void*, int64_t, size_t, size_t, void*)) \
1248  AARRAY_sortBinaryLast_BLOCK_FUNCTIONS[sizeof(*vec)-1]) \
1249  ((void*)vec, value, start, end, (void*)f))
1250 #endif
1251 #if defined(__cplusplus)
1252 GENERATE_GENERICS(AARRAY_sortBinaryFirst, LAMBDA, LAMBDA_int_TT)
1253 GENERATE_GENERICS(AARRAY_sortBinaryLast, LAMBDA, LAMBDA_int_TT)
1254 #define AARRAY_aSortBinaryFirst_LAMBDA(vec, value, start, end, f) \
1255  (((size_t(*)(void*, int64_t, size_t, size_t, std::function<int(int,int)>)) \
1256  AARRAY_sortBinaryFirst_LAMBDA_FUNCTIONS[sizeof(*vec)-1]) \
1257  ((void*)vec, value, start, end, (std::function<int(int,int)>)f))
1258 #define AARRAY_aSortBinaryLast_LAMBDA(vec, value, start, end, f) \
1259  (((size_t(*)(void*, int64_t, size_t, size_t, std::function<int(int,int)>)) \
1260  AARRAY_sortBinaryLast_LAMBDA_FUNCTIONS[sizeof(*vec)-1]) \
1261  ((void*)vec, value, start, end, (std::function<int(int,int)>)f))
1262 #endif
1263 
1264 $define AARRAY_sortMergeInPlace(TYPE, FNAME, FTYPE)
1265 AARRAY_define(void AARRAY_sortMergeInPlace_$##FNAME$##_$##TYPE(
1266  TYPE array[], size_t sA, size_t eA, size_t sB, size_t eB,
1267  FTYPE(TYPE), TYPE cache[]), {
1268  if(eA-sA == 0 || eB-sB == 0) return;
1269  while(1) {
1270  size_t mid = AARRAY_aSortBinaryFirst_$##FNAME(array, array[sA], sB, eB, f);
1271  size_t amount = mid-eA;
1272  AARRAY_aSortRotate(array, eA-sA, sA, mid, cache, AARRAY_sortCache);
1273  if(eB == mid) break;
1274  sB = mid;
1275  sA = sA+amount; eA = sB;
1276  sA = AARRAY_aSortBinaryLast_$##FNAME(array, array[sA], sA, eA, f);
1277  if(eA-sA == 0) break; } })
1278 
1279 GENERATE_GENERICS(AARRAY_sortNextRange)
1280 GENERATE_GENERICS(AARRAY_sortNextLevel)
1281 #define AARRAY_aSortNextRange(vec, iter, start, end) \
1282  (((void(*)(AARRAY_sortIt*, size_t*, size_t*)) \
1283  AARRAY_sortNextRange__FUNCTIONS[sizeof(*vec)-1])(iter, start, end))
1284 #define AARRAY_aSortNextLevel(vec, iter) \
1285  (((int (*)(AARRAY_sortIt*)) \
1286  AARRAY_sortNextLevel__FUNCTIONS[sizeof(*vec)-1])(iter))
1287 GENERATE_GENERICS(AARRAY_sortMergeInto, FUNC, FUNC_int_TT)
1288 GENERATE_GENERICS(AARRAY_sortMergeExternal, FUNC, FUNC_int_TT)
1289 GENERATE_GENERICS(AARRAY_sortMergeInternal, FUNC, FUNC_int_TT)
1290 GENERATE_GENERICS(AARRAY_sortMergeInPlace, FUNC, FUNC_int_TT)
1291 #define AARRAY_aSortMergeInto_FUNC(vec, s1, s2, s3, s4, f, vecb) \
1292  (((void(*)(void*, size_t, size_t, size_t, size_t, void(*)(void), void*)) \
1293  AARRAY_sortMergeInto_FUNC_FUNCTIONS[sizeof(*vec)-1]) \
1294  ((void*)vec, s1, s2, s3, s4, (void(*)(void))f, vecb))
1295 #define AARRAY_aSortMergeExternal_FUNC(vec, s1, s2, s3, s4, f, vecb) \
1296  (((void(*)(void*, size_t, size_t, size_t, size_t, void(*)(void), void*)) \
1297  AARRAY_sortMergeExternal_FUNC_FUNCTIONS[sizeof(*vec)-1]) \
1298  ((void*)vec, s1, s2, s3, s4, (void(*)(void))f, vecb))
1299 #define AARRAY_aSortMergeInternal_FUNC(vec, s1, s2, s3, s4, f, s5) \
1300  (((void(*)(void*, size_t, size_t, size_t, size_t, void(*)(void), size_t)) \
1301  AARRAY_sortMergeInternal_FUNC_FUNCTIONS[sizeof(*vec)-1]) \
1302  ((void*)vec, s1, s2, s3, s4, (void(*)(void))f, s5))
1303 #define AARRAY_aSortMergeInPlace_FUNC(vec, s1, s2, s3, s4, f, vecb) \
1304  (((void(*)(void*, size_t, size_t, size_t, size_t, void(*)(void), void*)) \
1305  AARRAY_sortMergeInPlace_FUNC_FUNCTIONS[sizeof(*vec)-1]) \
1306  ((void*)vec, s1, s2, s3, s4, (void(*)(void))f, vecb))
1307 
1308 #if __has_extension(blocks)
1309 GENERATE_GENERICS(AARRAY_sortMergeInto, BLOCK, BLOCK_int_TT)
1310 GENERATE_GENERICS(AARRAY_sortMergeExternal, BLOCK, BLOCK_int_TT)
1311 GENERATE_GENERICS(AARRAY_sortMergeInternal, BLOCK, BLOCK_int_TT)
1312 GENERATE_GENERICS(AARRAY_sortMergeInPlace, BLOCK, BLOCK_int_TT)
1313 #define AARRAY_aSortMergeInto_BLOCK(vec, s1, s2, s3, s4, f, vecb) \
1314  (((void(*)(void*, size_t, size_t, size_t, size_t, void*, void*)) \
1315  AARRAY_sortMergeInto_BLOCK_FUNCTIONS[sizeof(*vec)-1]) \
1316  ((void*)vec, s1, s2, s3, s4, (void*)f, vecb))
1317 #define AARRAY_aSortMergeExternal_BLOCK(vec, s1, s2, s3, s4, f, vecb) \
1318  (((void(*)(void*, size_t, size_t, size_t, size_t, void*, void*)) \
1319  AARRAY_sortMergeExternal_BLOCK_FUNCTIONS[sizeof(*vec)-1]) \
1320  ((void*)vec, s1, s2, s3, s4, (void*)f, vecb))
1321 #define AARRAY_aSortMergeInternal_BLOCK(vec, s1, s2, s3, s4, f, s5) \
1322  (((void(*)(void*, size_t, size_t, size_t, size_t, void*, size_t)) \
1323  AARRAY_sortMergeInternal_BLOCK_FUNCTIONS[sizeof(*vec)-1]) \
1324  ((void*)vec, s1, s2, s3, s4, (void*)f, s5))
1325 #define AARRAY_aSortMergeInPlace_BLOCK(vec, s1, s2, s3, s4, f, vecb) \
1326  (((void(*)(void*, size_t, size_t, size_t, size_t, void*, void*)) \
1327  AARRAY_sortMergeInPlace_BLOCK_FUNCTIONS[sizeof(*vec)-1]) \
1328  ((void*)vec, s1, s2, s3, s4, (void*)f, vecb))
1329 #endif
1330 #if defined(__cplusplus)
1331 GENERATE_GENERICS(AARRAY_sortMergeInto, LAMBDA, LAMBDA_int_TT)
1332 GENERATE_GENERICS(AARRAY_sortMergeExternal, LAMBDA, LAMBDA_int_TT)
1333 GENERATE_GENERICS(AARRAY_sortMergeInternal, LAMBDA, LAMBDA_int_TT)
1334 GENERATE_GENERICS(AARRAY_sortMergeInPlace, LAMBDA, LAMBDA_int_TT)
1335 #define AARRAY_aSortMergeInto_LAMBDA(vec, s1, s2, s3, s4, f, vecb) \
1336  (((void(*)(void*, size_t, size_t, size_t, size_t, \
1337  std::function<int(int,int)>, void*)) \
1338  AARRAY_sortMergeInto_LAMBDA_FUNCTIONS[sizeof(*vec)-1]) \
1339  ((void*)vec, s1, s2, s3, s4, (std::function<int(int,int)>)f, vecb))
1340 #define AARRAY_aSortMergeExternal_LAMBDA(vec, s1, s2, s3, s4, f, vecb) \
1341  (((void(*)(void*, size_t, size_t, size_t, size_t, \
1342  std::function<int(int,int)>, void*)) \
1343  AARRAY_sortMergeExternal_LAMBDA_FUNCTIONS[sizeof(*vec)-1]) \
1344  ((void*)vec, s1, s2, s3, s4, (std::function<int(int,int)>)f, vecb))
1345 #define AARRAY_aSortMergeInternal_LAMBDA(vec, s1, s2, s3, s4, f, s5) \
1346  (((void(*)(void*, size_t, size_t, size_t, size_t, \
1347  std::function<int(int,int)>, size_t)) \
1348  AARRAY_sortMergeInternal_LAMBDA_FUNCTIONS[sizeof(*vec)-1]) \
1349  ((void*)vec, s1, s2, s3, s4, (std::function<int(int,int)>)f, s5))
1350 #define AARRAY_aSortMergeInPlace_LAMBDA(vec, s1, s2, s3, s4, f, vecb) \
1351  (((void(*)(void*, size_t, size_t, size_t, size_t, \
1352  std::function<int(int,int)>, void*)) \
1353  AARRAY_sortMergeInPlace_LAMBDA_FUNCTIONS[sizeof(*vec)-1]) \
1354  ((void*)vec, s1, s2, s3, s4, (std::function<int(int,int)>)f, vecb))
1355 #endif
1356 
1357 // all that work, just to support this beast
1358 // I'm glad I didn't write it myself
1359 $define AARRAY_sort(TYPE, FNAME, FTYPE)
1360 AARRAY_define(TYPE*AARRAY_sort_$##FNAME$##_$##TYPE(
1361  TYPE array[], FTYPE(TYPE)), {
1362  size_t size = aLength(array);
1363  TYPE cache[AARRAY_sortCache];
1364  AARRAY_sortIt it;
1365  if(size < 4) {
1366  if(size == 3) {
1367  if(f(array[1], array[0])) AARRAY_swap(TYPE, array[0], array[1]);
1368  if(f(array[2], array[1])) {
1369  AARRAY_swap(TYPE, array[1], array[2]);
1370  if(f(array[1], array[0])) AARRAY_swap(TYPE, array[0], array[1]); } }
1371  else if(size == 2) {
1372  if(f(array[1], array[0])) AARRAY_swap(TYPE, array[0], array[1]); }
1373  return array; }
1374  // new it
1375  it.size = size;
1376  // floor_power_of_2(size)
1377  size_t s = size;
1378  s = s | (s >> 1); s = s | (s >> 2); s = s | (s >> 4);
1379  s = s | (s >> 8); s = s | (s >> 16);
1380  if(sizeof(size_t)==8) s = s | (s >> 32);
1381  s = s-(s >> 1);
1382  it.power_of_two = s;
1383  it.denominator = it.power_of_two/4;
1384  it.numerator_step = it.size % it.denominator;
1385  it.decimal_step = it.size/it.denominator;
1386  it.numerator = it.decimal = 0;
1387  while(!(it.decimal >= it.size)) {
1388  uint8_t order[] = { 0, 1, 2, 3, 4, 5, 6, 7 };
1389  size_t sRange, eRange;
1390  AARRAY_aSortNextRange(array, &it, &sRange, &eRange);
1391  if(eRange-sRange==8) {
1392  AARRAY_SWAP(TYPE, 0, 1); AARRAY_SWAP(TYPE, 2, 3); AARRAY_SWAP(TYPE, 4, 5);
1393  AARRAY_SWAP(TYPE, 6, 7); AARRAY_SWAP(TYPE, 0, 2); AARRAY_SWAP(TYPE, 1, 3);
1394  AARRAY_SWAP(TYPE, 4, 6); AARRAY_SWAP(TYPE, 5, 7); AARRAY_SWAP(TYPE, 1, 2);
1395  AARRAY_SWAP(TYPE, 5, 6); AARRAY_SWAP(TYPE, 0, 4); AARRAY_SWAP(TYPE, 3, 7);
1396  AARRAY_SWAP(TYPE, 1, 5); AARRAY_SWAP(TYPE, 2, 6); AARRAY_SWAP(TYPE, 1, 4);
1397  AARRAY_SWAP(TYPE, 3, 6); AARRAY_SWAP(TYPE, 2, 4); AARRAY_SWAP(TYPE, 3, 5);
1398  AARRAY_SWAP(TYPE, 3, 4);
1399  } else if(eRange-sRange==7) {
1400  AARRAY_SWAP(TYPE, 1, 2); AARRAY_SWAP(TYPE, 3, 4); AARRAY_SWAP(TYPE, 5, 6);
1401  AARRAY_SWAP(TYPE, 0, 2); AARRAY_SWAP(TYPE, 3, 5); AARRAY_SWAP(TYPE, 4, 6);
1402  AARRAY_SWAP(TYPE, 0, 1); AARRAY_SWAP(TYPE, 4, 5); AARRAY_SWAP(TYPE, 2, 6);
1403  AARRAY_SWAP(TYPE, 0, 4); AARRAY_SWAP(TYPE, 1, 5); AARRAY_SWAP(TYPE, 0, 3);
1404  AARRAY_SWAP(TYPE, 2, 5); AARRAY_SWAP(TYPE, 1, 3); AARRAY_SWAP(TYPE, 2, 4);
1405  AARRAY_SWAP(TYPE, 2, 3);
1406  } else if(eRange-sRange==6) {
1407  AARRAY_SWAP(TYPE, 1, 2); AARRAY_SWAP(TYPE, 4, 5); AARRAY_SWAP(TYPE, 0, 2);
1408  AARRAY_SWAP(TYPE, 3, 5); AARRAY_SWAP(TYPE, 0, 1); AARRAY_SWAP(TYPE, 3, 4);
1409  AARRAY_SWAP(TYPE, 2, 5); AARRAY_SWAP(TYPE, 0, 3); AARRAY_SWAP(TYPE, 1, 4);
1410  AARRAY_SWAP(TYPE, 2, 4); AARRAY_SWAP(TYPE, 1, 3); AARRAY_SWAP(TYPE, 2, 3);
1411  } else if(eRange-sRange==5) {
1412  AARRAY_SWAP(TYPE, 0, 1); AARRAY_SWAP(TYPE, 3, 4); AARRAY_SWAP(TYPE, 2, 4);
1413  AARRAY_SWAP(TYPE, 2, 3); AARRAY_SWAP(TYPE, 1, 4); AARRAY_SWAP(TYPE, 0, 3);
1414  AARRAY_SWAP(TYPE, 0, 2); AARRAY_SWAP(TYPE, 1, 3); AARRAY_SWAP(TYPE, 1, 2);
1415  } else if(eRange-sRange==4) {
1416  AARRAY_SWAP(TYPE, 0, 1); AARRAY_SWAP(TYPE, 2, 3); AARRAY_SWAP(TYPE, 0, 2);
1417  AARRAY_SWAP(TYPE, 1, 3); AARRAY_SWAP(TYPE, 1, 2); } }
1418  if(size < 8) return array;
1419  while(1) {
1420  if(it.decimal_step < AARRAY_sortCache) {
1421  if((it.decimal_step+1)*4 <= AARRAY_sortCache
1422  && it.decimal_step*4 <= size) {
1423  it.numerator = it.decimal = 0;
1424  while(!(it.decimal >= it.size)) {
1425  size_t
1426  sA1, sB1, sA2, sB2, sA3, sB3,
1427  eA1, eB1, eA2, eB2, eA3, eB3;
1428  AARRAY_aSortNextRange(array, &it, &sA1, &eA1);
1429  AARRAY_aSortNextRange(array, &it, &sB1, &eB1);
1430  AARRAY_aSortNextRange(array, &it, &sA2, &eA2);
1431  AARRAY_aSortNextRange(array, &it, &sB2, &eB2);
1432  if(f(array[eB1-1], array[sA1])) {
1433  memcpy(&cache[eB1-sB1], &array[sA1], (eA1-sA1)*sizeof(array[0]));
1434  memcpy(&cache[0], &array[sB1], (eB1-sB1)*sizeof(array[0])); }
1435  else if(f(array[sB1], array[eA1-1])) {
1436  AARRAY_aSortMergeInto_$##FNAME(
1437  array, sA1, eA1, sB1, eB1, f, &cache[0]); }
1438  else {
1439  if(!f(array[sB2], array[eA2-1])
1440  && !f(array[sA2], array[eB1-1])) continue;
1441  memcpy(&cache[0], &array[sA1], (eA1-sA1)*sizeof(array[0]));
1442  memcpy(&cache[(eA1-sA1)], &array[sB1],
1443  (eB1-sB1)*sizeof(array[0])); }
1444  eA1 = eB1;
1445  if(f(array[eB2-1], array[sA2])) {
1446  memcpy(&cache[(eA1-sA1)+(eB2-sB2)], &array[sA2],
1447  (eA2-sA2)*sizeof(array[0]));
1448  memcpy(&cache[eA1-sA1], &array[sB2], (eB2-sB2)*sizeof(array[0])); }
1449  else if(f(array[sB2], array[eA2-1])) {
1450  AARRAY_aSortMergeInto_$##FNAME(
1451  array, sA2, eA2, sB2, eB2, f, &cache[eA1-sA1]); }
1452  else {
1453  memcpy(&cache[eA1-sA1], &array[sA2], (eA2-sA2)*sizeof(array[0]));
1454  memcpy(&cache[(eA1-sA1)+(eA2-sA2)], &array[sB2],
1455  (eB2-sB2)*sizeof(array[0])); }
1456  eA2 = eB2;
1457  sA3 = 0; eA3 = eA1-sA1;
1458  sB3 = eA1-sA1; eB3 = (eA1-sA1)+(eA2-sA2);
1459  if(f(cache[eB3-1], cache[sA3])) {
1460  memcpy(&array[sA1+(eA2-sA2)], &cache[sA3],
1461  (eA3-sA3)*sizeof(array[0]));
1462  memcpy(&array[sA1], &cache[sB3], (eB3-sB3)*sizeof(array[0])); }
1463  else if(f(cache[sB3], cache[eA3-1])) {
1464  AARRAY_aSortMergeInto_$##FNAME(
1465  cache, sA3, eA3, sB3, eB3, f, &array[sA1]); }
1466  else {
1467  memcpy(&array[sA1], &cache[sA3], (eA3-sA3)*sizeof(array[0]));
1468  memcpy(&array[sA1+(eA1-sA1)], &cache[sB3],
1469  (eB3-sB3)*sizeof(array[0])); } }
1470  AARRAY_aSortNextLevel(array, &it); }
1471  else {
1472  it.numerator = it.decimal = 0;
1473  while(!(it.decimal >= it.size)) {
1474  size_t sA, eA, sB, eB;
1475  AARRAY_aSortNextRange(array, &it, &sA, &eA);
1476  AARRAY_aSortNextRange(array, &it, &sB, &eB);
1477  if(f(array[eB-1], array[sA]))
1478  AARRAY_aSortRotate(array, eA-sA, sA, eB, cache, AARRAY_sortCache);
1479  else if(f(array[sB], array[eA-1])) {
1480  memcpy(&cache[0], &array[sA], (eA-sA)*sizeof(array[0]));
1481  AARRAY_aSortMergeExternal_$##FNAME(
1482  array, sA, eA, sB, eB, f, cache); } } } }
1483  else {
1484  double block_size_d = sqrt(it.decimal_step);
1485  size_t block_size = (size_t)block_size_d;
1486  size_t buffer_size = it.decimal_step/block_size+1;
1487  int find_separately;
1488  size_t sBuff1, eBuff1, sBuff2, eBuff2, sA, eA, sB, eB;
1489  size_t index, last, count, find, start, pull_index = 0;
1490  struct { size_t from, to, count, sRange, eRange; } pull[2];
1491  pull[0].from = pull[0].to = pull[0].count = 0;
1492  pull[1].from = pull[1].to = pull[1].count = 0;
1493  pull[0].sRange = pull[0].eRange = 0;
1494  pull[1].sRange = pull[1].eRange = 0;
1495  sBuff1 = 0; eBuff1 = 0;
1496  sBuff2 = 0; eBuff2 = 0;
1497  find_separately = 0;
1498  find = buffer_size+buffer_size;
1499  if(block_size <= AARRAY_sortCache)
1500  find = buffer_size;
1501  else if(find > it.decimal_step) {
1502  find = buffer_size;
1503  find_separately = 1; }
1504  it.numerator = it.decimal = 0;
1505  while(!(it.decimal >= it.size)) {
1506  AARRAY_aSortNextRange(array, &it, &sA, &eA);
1507  AARRAY_aSortNextRange(array, &it, &sB, &eB);
1508  for(last = sA, count = 1; count < find; last = index, count++) {
1509  AARRAY_sortFindLastForward(
1510  FNAME, array[last], (last+1), eA, find-count);
1511  if(index == eA) break; }
1512  index = last;
1513  if(count >= buffer_size) {
1514  AARRAY_PULL(sA);
1515  pull_index = 1;
1516  if(count == buffer_size+buffer_size) {
1517  sBuff1 = sA; eBuff1 = sA+buffer_size;
1518  sBuff2 = sA+buffer_size; eBuff2 = sA+count;
1519  break; }
1520  else if(find == buffer_size+buffer_size) {
1521  sBuff1 = sA; eBuff1 = sA+count;
1522  find = buffer_size; }
1523  else if(block_size <= AARRAY_sortCache) {
1524  sBuff1 = sA; eBuff1 = sA+count;
1525  break; }
1526  else if(find_separately) {
1527  sBuff1 = sA; eBuff1 = sA+count;
1528  find_separately = 0; }
1529  else {
1530  sBuff2 = sA; eBuff2 = sA+count;
1531  break; } }
1532  else if(pull_index == 0 && count > eBuff1-sBuff1) {
1533  sBuff1 = sA; eBuff1 = sA+count;
1534  AARRAY_PULL(sA); }
1535  for(last = eB-1, count = 1; count < find; last = index-1, count++) {
1536  AARRAY_sortFindFirstBackward(
1537  FNAME, array[last], sB, last, find-count);
1538  if(index == sB) break; }
1539  index = last;
1540  if(count >= buffer_size) {
1541  AARRAY_PULL(eB);
1542  pull_index = 1;
1543  if(count == buffer_size+buffer_size) {
1544  sBuff1 = eB-count; eBuff1 = eB-buffer_size;
1545  sBuff2 = eB-buffer_size; eBuff2 = eB;
1546  break; }
1547  else if(find == buffer_size+buffer_size) {
1548  sBuff1 = eB-count; eBuff1 = eB;
1549  find = buffer_size; }
1550  else if(block_size <= AARRAY_sortCache) {
1551  sBuff1 = eB-count; eBuff1 = eB;
1552  break; }
1553  else if(find_separately) {
1554  sBuff1 = eB-count; eBuff1 = eB;
1555  find_separately = 0; }
1556  else {
1557  if(pull[0].sRange == sA) pull[0].eRange -= pull[1].count;
1558  sBuff2 = eB-count; eBuff2 = eB;
1559  break; } }
1560  else if(pull_index == 0 && count > (eBuff1-sBuff1)) {
1561  sBuff1 = eB-count; eBuff1 = eB;
1562  AARRAY_PULL(eB); } }
1563  for(pull_index = 0; pull_index < 2; pull_index++) {
1564  size_t sRange, eRange;
1565  size_t length = pull[pull_index].count;
1566  if(pull[pull_index].to < pull[pull_index].from) {
1567  index = pull[pull_index].from;
1568  for(count = 1; count < length; count++) {
1569  size_t index_ = index;
1570  AARRAY_sortFindFirstBackward(
1571  FNAME, array[index_-1], pull[pull_index].to,
1572  (pull[pull_index].from-(count-1)), length-count);
1573  sRange = index+1; eRange = pull[pull_index].from+1;
1574  AARRAY_aSortRotate(array, (eRange-sRange)-count, sRange, eRange,
1575  cache, AARRAY_sortCache);
1576  pull[pull_index].from = index+count; } }
1577  else if(pull[pull_index].to > pull[pull_index].from) {
1578  index = pull[pull_index].from+1;
1579  for(count = 1; count < length; count++) {
1580  AARRAY_sortFindLastForward(
1581  FNAME, array[index], index, pull[pull_index].to, length-count);
1582  sRange = pull[pull_index].from; eRange = index-1;
1583  AARRAY_aSortRotate(
1584  array, count, sRange, eRange, cache, AARRAY_sortCache);
1585  pull[pull_index].from = index-1-count; } } }
1586  buffer_size = eBuff1-sBuff1;
1587  block_size = it.decimal_step/buffer_size+1;
1588  it.numerator = it.decimal = 0;
1589  while(!(it.decimal >= it.size)) {
1590  AARRAY_aSortNextRange(array, &it, &sA, &eA);
1591  AARRAY_aSortNextRange(array, &it, &sB, &eB);
1592  start = sA;
1593  if(start == pull[0].sRange) {
1594  if(pull[0].from > pull[0].to) {
1595  sA += pull[0].count;
1596  if(eA-sA == 0) continue; }
1597  else if(pull[0].from < pull[0].to) {
1598  eB -= pull[0].count;
1599  if(eB-sB == 0) continue; } }
1600  if(start == pull[1].sRange) {
1601  if(pull[1].from > pull[1].to) {
1602  sA += pull[1].count;
1603  if(eA-sA == 0) continue; }
1604  else if(pull[1].from < pull[1].to) {
1605  eB -= pull[1].count;
1606  if(eB-sB == 0) continue; ; } }
1607  if(f(array[eB-1], array[sA]))
1608  AARRAY_aSortRotate(array, eA-sA, sA, eB, cache, AARRAY_sortCache);
1609  else if(f(array[eA], array[eA-1])) {
1610  size_t
1611  sBlockA, eBlockA, sFirstA, eFirstA, sLastA,
1612  eLastA, sLastB, eLastB, sBlockB, eBlockB;
1613  size_t indexA, findA;
1614  sBlockA = sA; eBlockA = eA;
1615  sFirstA = sA; eFirstA = sA+(eBlockA-sBlockA) % block_size;
1616  for(indexA = sBuff1, index = eFirstA; index < eBlockA;
1617  indexA++, index += block_size)
1618  AARRAY_swap(TYPE, array[indexA], array[index]);
1619  sLastA = sFirstA;
1620  eLastA = eFirstA;
1621  sLastB = 0; eLastB = 0;
1622  sBlockB = sB; eBlockB = sB+(block_size < eB-sB? block_size : eB-sB);
1623  sBlockA += eFirstA-sFirstA;
1624  indexA = sBuff1;
1625  if(eLastA-sLastA <= AARRAY_sortCache)
1626  memcpy(&cache[0], &array[sLastA], (eLastA-sLastA)*sizeof(array[0]));
1627  else if(eBuff2-sBuff2 > 0)
1628  AARRAY_blockSwap(TYPE, array, sLastA, sBuff2, eLastA-sLastA);
1629  if(eBlockA-sBlockA > 0) {
1630  while(1) {
1631  if((eLastB-sLastB > 0 && !f(array[eLastB-1], array[indexA]))
1632  || eBlockB-sBlockB == 0) {
1633  size_t B_split = AARRAY_aSortBinaryFirst_$##FNAME(
1634  array, array[indexA], sLastB, eLastB, f);
1635  size_t B_remaining = eLastB-B_split;
1636  size_t minA = sBlockA;
1637  for(findA = minA+block_size; findA < eBlockA;
1638  findA += block_size)
1639  if(f(array[findA], array[minA])) minA = findA;
1640  AARRAY_blockSwap(TYPE, array, sBlockA, minA, block_size);
1641  AARRAY_swap(TYPE, array[sBlockA], array[indexA]);
1642  indexA++;
1643  if(eLastA-sLastA <= AARRAY_sortCache)
1644  AARRAY_aSortMergeExternal_$##FNAME(
1645  array, sLastA, eLastA, eLastA, B_split, f, cache);
1646  else if(eBuff2-sBuff2 > 0)
1647  AARRAY_aSortMergeInternal_$##FNAME(
1648  array, sLastA, eLastA, eLastA, B_split, f, sBuff2);
1649  else
1650  AARRAY_aSortMergeInPlace_$##FNAME(
1651  array, sLastA, eLastA, eLastA, B_split, f, cache);
1652  if(eBuff2-sBuff2 > 0 || block_size <= AARRAY_sortCache) {
1653  if(block_size <= AARRAY_sortCache)
1654  memcpy(&cache[0], &array[sBlockA],
1655  block_size*sizeof(array[0]));
1656  else AARRAY_blockSwap(TYPE, array, sBlockA, sBuff2,
1657  block_size);
1658  AARRAY_blockSwap(TYPE, array, B_split,
1659  sBlockA+block_size-B_remaining,
1660  B_remaining); }
1661  else
1662  AARRAY_aSortRotate(array, sBlockA-B_split, B_split,
1663  sBlockA+block_size, cache, AARRAY_sortCache);
1664  sLastA = sBlockA-B_remaining; eLastA =
1665  sBlockA-B_remaining+block_size;
1666  sLastB = eLastA; eLastB = eLastA+B_remaining;
1667  sBlockA += block_size;
1668  if(eBlockA-sBlockA == 0) break; }
1669  else if(eBlockB-sBlockB < block_size) {
1670  AARRAY_aSortRotate(
1671  array, sBlockB-sBlockA, sBlockA, eBlockB, cache, 0);
1672  sLastB = sBlockA; eLastB = sBlockA+(eBlockB-sBlockB);
1673  sBlockA += eBlockB-sBlockB;
1674  eBlockA += eBlockB-sBlockB;
1675  eBlockB = sBlockB; }
1676  else {
1677  AARRAY_blockSwap(TYPE, array, sBlockA, sBlockB, block_size);
1678  sLastB = sBlockA; eLastB = sBlockA+block_size;
1679  sBlockA += block_size;
1680  eBlockA += block_size;
1681  sBlockB += block_size;
1682  if(eBlockB > eB-block_size) eBlockB = eB;
1683  else eBlockB += block_size; } } }
1684  if(eLastA-sLastA <= AARRAY_sortCache)
1685  AARRAY_aSortMergeExternal_$##FNAME(
1686  array, sLastA, eLastA, eLastA, eB, f, cache);
1687  else if(eBuff2-sBuff2 > 0)
1688  AARRAY_aSortMergeInternal_$##FNAME(
1689  array, sLastA, eLastA, eLastA, eB, f, sBuff2);
1690  else
1691  AARRAY_aSortMergeInPlace_$##FNAME(
1692  array, sLastA, eLastA, eLastA, eB, f, cache); } }
1693  // insertion sort
1694  size_t i, j;
1695  for(i = sBuff2+1; i < eBuff2; i++) {
1696  const TYPE temp = array[i];
1697  for(j = i; j > sBuff2 && f(temp, array[j-1]); j--)
1698  array[j] = array[j-1];
1699  array[j] = temp; }
1700  for(pull_index = 0; pull_index < 2; pull_index++) {
1701  size_t amount, unique = pull[pull_index].count*2;
1702  if(pull[pull_index].from > pull[pull_index].to) {
1703  size_t
1704  sBuff = pull[pull_index].sRange,
1705  eBuff = pull[pull_index].sRange+pull[pull_index].count;
1706  while(eBuff-sBuff > 0) {
1707  AARRAY_sortFindFirstForward(FNAME, array[sBuff], eBuff,
1708  pull[pull_index].eRange, unique);
1709  amount = index-eBuff;
1710  AARRAY_aSortRotate(array, eBuff-sBuff, sBuff, index,
1711  cache, AARRAY_sortCache);
1712  sBuff += (amount+1);
1713  eBuff += amount;
1714  unique -= 2; } }
1715  else if(pull[pull_index].from < pull[pull_index].to) {
1716  size_t
1717  sBuff = pull[pull_index].eRange-pull[pull_index].count,
1718  eBuff = pull[pull_index].eRange;
1719  while(eBuff-sBuff > 0) {
1720  AARRAY_sortFindLastBackward(FNAME, array[eBuff-1],
1721  pull[pull_index].sRange,
1722  sBuff, unique);
1723  amount = sBuff-index;
1724  AARRAY_aSortRotate(
1725  array, amount, index, eBuff, cache, AARRAY_sortCache);
1726  sBuff -= amount;
1727  eBuff -= (amount+1);
1728  unique -= 2; } } } }
1729  if(!AARRAY_aSortNextLevel(array, &it)) break; }
1730  return array; })
1731 
1732 $define AARRAY_sortCompare(TYPE,,)
1733 AARRAY_define(int AARRAY_sortCompare__$##TYPE(TYPE a, TYPE b), {
1734  return a<b; })
1735 
1736 GENERATE_GENERICS(AARRAY_sortCompare,,)
1737 GENERATE_GENERICS(AARRAY_sort, FUNC, FUNC_int_TT)
1738 #define aSort(vec) \
1739  (AARRAY_typeof(vec, (uint64_t*(*)(void*,void(*)(void))) \
1740  AARRAY_sort_FUNC_FUNCTIONS[sizeof(*vec)-1])((void*)vec, (void(*)(void)) \
1741  AARRAY_sortCompare__FUNCTIONS[sizeof(*vec)-1]))
1742 #define aSortF_FUNC(vec, f) \
1743  (AARRAY_typeof(vec, (uint64_t*(*)(void*,void(*)(void))) \
1744  AARRAY_sort_FUNC_FUNCTIONS[sizeof(*vec)-1])((void*)vec, (void(*)(void))f))
1745 
1746 #if __has_extension(blocks)
1747 GENERATE_GENERICS(AARRAY_sort, BLOCK, BLOCK_int_TT)
1748 #define aSortF_BLOCK(vec, f) \
1749  (AARRAY_typeof(vec, (uint64_t*(*)(void*, void*)) \
1750  AARRAY_sort_BLOCK_FUNCTIONS[sizeof(*vec)-1])((void*)vec, (void*)f))
1751 #endif
1752 #if defined(__cplusplus)
1753 GENERATE_GENERICS(AARRAY_sort, LAMBDA, LAMBDA_int_TT)
1754 #define aSortF_LAMBDA(vec, f) \
1755  (AARRAY_typeof(vec, (uint64_t*(*)(void*, \
1756  std::function<int(int64_t,int64_t)>)) \
1757  AARRAY_sort_LAMBDA_FUNCTIONS[sizeof(*vec)-1]) \
1758  ((void*)vec, (std::function<int(int64_t,int64_t)>)f))
1759 #endif
1760 
1761 
1762 
1763 
1764 $define AARRAY_searchCompare(TYPE,,)
1765 AARRAY_define(TYPE AARRAY_searchCompare__$##TYPE(TYPE a, TYPE b), {
1766  return a-b; })
1767 
1768 $define AARRAY_binary10(TYPE, FNAME, FTYPE)
1769 AARRAY_define(int AARRAY_binary10_$##FNAME$##_$##TYPE(
1770  TYPE*vec, size_t*index, TYPE key, FTYPE(TYPE)), {
1771  size_t min = 0, mid = 0, max = aLength(vec);
1772  if(!max) { *index = 0; return 0; } // protect initial lookups
1773  while(min < max) {
1774  mid = (min + max) >> 1; // potential integer overflow
1775  TYPE cmp = f(key, vec[mid]);
1776  if(cmp == 0) { *index = mid; return 1; }
1777  if(cmp < 0) max = mid;
1778  else min = ++mid; }
1779  *index = mid; return 0; })
1780 
1781 $define AARRAY_pingpong(TYPE, FNAME, FTYPE)
1782 AARRAY_define(int AARRAY_pingpong_$##FNAME$##_$##TYPE(
1783  TYPE*vec, size_t*index, TYPE key, FTYPE(TYPE)), {
1784  size_t min = 0, max = aLength(vec);
1785  if(!max) { *index = 0; return 0; }
1786  // start secant 1/8th of the way into the array, because why not
1787  size_t a = min+(max>>3), b = max-1-(max>>3), c;
1788  TYPE fa = f(key, vec[a]), fb = f(key, vec[b]);
1789  while(min < max) {
1790  // divide by non-zero? interpolate : bisect
1791  c = fb-fa? (size_t)(b - fb * (double)(b-a) / (fb-fa)) : max-((max-min)>>1);
1792  // keep the pingpong ball on the table
1793  a = b; b = c < min ? min : c >= max ? max-1 : c;
1794  fa = fb; fb = f(key, vec[b]);
1795  if(fb > 0) min = b+1; else max = b;
1796  if(fb == 0) { *index = b; return 1; } }
1797  *index = max; return 0; })
1798 
1799 $define FUNC_T_TT(TYPE) TYPE(*f)(TYPE,TYPE)
1800 
1801 $define BLOCK_T_TT(TYPE) TYPE(^f)(TYPE,TYPE)
1802 
1803 $define LAMBDA_T_TT(TYPE) std::function<TYPE(TYPE, TYPE)>f
1804 
1805 GENERATE_GENERICS(AARRAY_searchCompare,,)
1806 GENERATE_GENERICS(AARRAY_binary10, FUNC, FUNC_T_TT)
1807 GENERATE_GENERICS(AARRAY_pingpong, FUNC, FUNC_T_TT)
1808 #define aSearch(vec, index, key) \
1809  ((int(*)(void*, size_t*, uint64_t, void(*)(void))) \
1810  AARRAY_binary10_FUNC_FUNCTIONS[sizeof(*vec)-1]) \
1811  (vec, index, (uint64_t)key, \
1812  (void(*)(void))AARRAY_searchCompare__FUNCTIONS[sizeof(*vec)-1])
1813 #define aSearchF_FUNC(vec, index, key, f) \
1814  ((int(*)(void*, size_t*, uint64_t, void(*)(void))) \
1815  AARRAY_binary10_FUNC_FUNCTIONS[sizeof(*vec)-1]) \
1816  (vec, index, (uint64_t)key, (void(*)(void))f)
1817 #define aSearchF_ALT_FUNC(vec, index, key, f) \
1818  ((int(*)(void*, size_t*, uint64_t, void(*)(void))) \
1819  AARRAY_pingpong_FUNC_FUNCTIONS[sizeof(*vec)-1]) \
1820  (vec, index, (uint64_t)key, (void(*)(void))f)
1821 
1822 #if __has_extension(blocks)
1823 GENERATE_GENERICS(AARRAY_binary10, BLOCK, BLOCK_T_TT)
1824 GENERATE_GENERICS(AARRAY_pingpong, BLOCK, BLOCK_T_TT)
1825 #define aSearchF_BLOCK(vec, index, key, f) \
1826  ((int(*)(void*, size_t*, uint64_t, void*)) \
1827  AARRAY_binary10_BLOCK_FUNCTIONS[sizeof(*vec)-1]) \
1828  (vec, index, (uint64_t)key, (void*)f)
1829 #define aSearchF_ALT_BLOCK(vec, index, key, f) \
1830  ((int(*)(void*, size_t*, uint64_t, void*)) \
1831  AARRAY_pingpong_BLOCK_FUNCTIONS[sizeof(*vec)-1]) \
1832  (vec, index, (uint64_t)key, (void*)f)
1833 #endif
1834 #if defined(__cplusplus)
1835 GENERATE_GENERICS(AARRAY_binary10, LAMBDA, LAMBDA_T_TT)
1836 GENERATE_GENERICS(AARRAY_pingpong, LAMBDA, LAMBDA_T_TT)
1837 #define aSearchF_LAMBDA(vec, index, key, f) \
1838  ((int(*)(void*, size_t*, uint64_t, \
1839  std::function<uint64_t(uint64_t,uint64_t)>)) \
1840  AARRAY_binary10_LAMBDA_FUNCTIONS[sizeof(*vec)-1]) \
1841  (vec, index, (uint64_t)key, \
1842  (std::function<uint64_t(uint64_t,uint64_t)>)f)
1843 #define aSearchF_ALT_LAMBDA(vec, index, key, f) \
1844  ((int(*)(void*, size_t*, uint64_t, \
1845  std::function<uint64_t(uint64_t,uint64_t)>)) \
1846  AARRAY_pingpong_LAMBDA_FUNCTIONS[sizeof(*vec)-1]) \
1847  (vec, index, (uint64_t)key, \
1848  (std::function<uint64_t(uint64_t,uint64_t)>)f)
1849 #endif
1850 
1851 
1852 
1853 
1854 #if !defined(AARRAY_NOCONVENIENCE)
1855 #if __has_extension(blocks)
1856  #define aMap aMap_BLOCK
1857  #define aFilter aFilter_BLOCK
1858  #define aFold aFold_BLOCK
1859  #define aLoop aLoop_BLOCK
1860  #define aSortF aSortF_BLOCK
1861  #define aSearchF aSearchF_BLOCK
1862  #define aSearchF_ALT aSearchF_ALT_BLOCK
1863 #elif defined(__cplusplus)
1864  #define aMap aMap_LAMBDA
1865  #define aFilter aFilter_LAMBDA
1866  #define aFold aFold_LAMBDA
1867  #define aLoop aLoop_LAMBDA
1868  #define aSortF aSortF_LAMBDA
1869  #define aSearchF aSearchF_LAMBDA
1870  #define aSearchF_ALT aSearchF_ALT_LAMBDA
1871 #else
1872  #define aMap aMap_FUNC
1873  #define aFilter aFilter_FUNC
1874  #define aFold aFold_FUNC
1875  #define aLoop aLoop_FUNC
1876  #define aSortF aSortF_FUNC
1877  #define aSearchF aSearchF_FUNC
1878  #define aSearchF_ALT aSearchF_ALT_FUNC
1879 #endif
1880 #endif
1881 
1882 
1883 
1884 
1885 //// api to quickly print arrays without '\0' endings
1886 $define AARRAY_Write(TYPE, ...)
1887 AARRAY_define(int AARRAY_Write__$##TYPE(
1888  char errLoc[], FILE*file, size_t vecsCount, uintptr_t vecs[]), {
1889  AARRAY_safety((void)errLoc, if(!file) AARRAY_Error_NullParameter);
1890  size_t n = (size_t)-1; while(++n < vecsCount)
1891  if(vecs[n] &&
1892  *((size_t*)vecs[n]-1) >
1893  fwrite((void*)vecs[n], sizeof(TYPE), *((size_t*)vecs[n]-1), file))
1894  return -1;
1895  return 0; })
1896 
1897 GENERATE_GENERICS(AARRAY_Write,)
1898 
1899 #define AARRAY_ArgsHead(A, ...) A
1900 
1901 #define aWrite(file, ...) \
1902  ((int(*)(char[], FILE*, size_t, uintptr_t[])) \
1903  AARRAY_Write__FUNCTIONS[sizeof(*AARRAY_ArgsHead(__VA_ARGS__, NULL))-1]) \
1904  (AARRAY_LINE, file, /* for c++ */ \
1905  AARRAY_nowarn_internal_start AARRAY_PtrArgs(__VA_ARGS__) \
1906  AARRAY_nowarn_internal_end)
1907 
1908 
1909 
1910 
1911 //// api to emulate printf for arrays
1912 AARRAY_define(void AARRAY_percent_parse(
1913  char errLoc[], const char fmt[], size_t*pptr,
1914  char*pspecifier, unsigned long*pnum1, unsigned long*pnum2,
1915  size_t*pstart, size_t*pend, size_t*doublePercent), {
1916  // get parser values
1917  char specifier = *pspecifier; unsigned long num1 = *pnum1, num2 = *pnum2;
1918  size_t start = *pstart; size_t end = *pend; size_t ptr = *pptr;
1919  while(1) {
1920  if(fmt[ptr] == '\0') {
1921  end = ptr;
1922  specifier = 'e'; break; }
1923  else if(0==strncmp(fmt+ptr, "%v", 2)) {
1924  end = ptr;
1925  ptr = start = ptr+2;
1926  specifier = 'v'; break; }
1927  else if(0==strncmp(fmt+ptr, "%s", 2)) {
1928  end = ptr;
1929  ptr = start = ptr+2;
1930  specifier = 's'; break; }
1931  else if(0==strncmp(fmt+ptr, "%c", 2)) {
1932  end = ptr;
1933  ptr = start = ptr+2;
1934  specifier = 'c'; break; }
1935  else if(0==strncmp(fmt+ptr, "%%", 2)) {
1936  end = ptr;
1937  ptr = start = ptr+2;
1938  *doublePercent = ptr;
1939  specifier = '%'; break; }
1940  else if(fmt[ptr] == '%') {
1941  end = ptr;
1942  /* parse %u %i arguments == %base u|i bitwidth
1943  base == 2-64 bitwidth == c s i l ll 8 16 32 64 z m p */
1944  ptr++; size_t ptr_start = ptr;
1945  AARRAY_safety((void)errLoc;,
1946  if(fmt[ptr]=='\0') AARRAY_Error_FormatStringMalformed);
1947  num1 = 0; num2 = 0;
1948  // get base to print number in
1949  char num_str[] = "10";
1950  while(fmt[ptr] >= '0' && fmt[ptr] <= '9') ptr++;
1951  AARRAY_safety(, if(ptr-ptr_start > 2) AARRAY_Error_FormatStringMalformed
1952  else) if(ptr != ptr_start) {
1953  num_str[0] = fmt[ptr_start];
1954  num_str[1] = (ptr != ptr_start+1 ? fmt[ptr_start+1] : '\0');
1955  num1 = strtoul(num_str, NULL, 10); }
1956  else num1 = 10;
1957  // get number's type
1958  specifier = fmt[ptr++];
1959  AARRAY_safety(, if((specifier != 'i' && specifier != 'u' &&
1960  specifier != 'f' && specifier != 'd') ||
1961  (num1 < 2 || num1 > 64))
1962  AARRAY_Error_FormatStringMalformed);
1963  // get number's bit width
1964  if(specifier == 'i' || specifier == 'u') {
1965  if(0==strncmp(fmt+ptr, "ll", 2)) {
1966  num2 = sizeof(long long)*8; ptr+=2; }
1967  else if(0==strncmp(fmt+ptr, "16", 2)) { num2 = 16; ptr+=2; }
1968  else if(0==strncmp(fmt+ptr, "32", 2)) { num2 = 32; ptr+=2; }
1969  else if(0==strncmp(fmt+ptr, "64", 2)) { num2 = 64; ptr+=2; }
1970  else switch(fmt[ptr]) {
1971  case 'c': case '8': num2 = sizeof(char)*8; ptr++; break;
1972  case 's': num2 = sizeof(short)*8; ptr++; break;
1973  case 'i': num2 = sizeof(int)*8; ptr++; break;
1974  case 'l': num2 = sizeof(long)*8; ptr++; break;
1975  case 'z': num2 = sizeof(size_t)*8; ptr++; break;
1976  case 'm': num2 = sizeof(intmax_t)*8; ptr++; break;
1977  case 'p': num2 = sizeof(intptr_t)*8; ptr++; break;
1978  default: num2 = sizeof(int)*8; } }
1979  else if(specifier == 'f'){ num2 = sizeof(float)*8; }
1980  else if(specifier == 'd'){ num2 = sizeof(double)*8; }
1981  else { AARRAY_safety(, AARRAY_Error_FormatStringMalformed); }
1982  AARRAY_safety(,if(!num2) AARRAY_Error_FormatStringMalformed);
1983  // we only parse floats, not yet done code to print them...
1984  //AARRAY_safety(, if(specifier == 'f'/* || specifier == 'd'*/)
1985  // AARRAY_Error_FormatStringMalformed);
1986  start = ptr;
1987  break; }
1988  ptr++; }
1989  // return parser values
1990  *pspecifier = specifier; *pnum1 = num1; *pnum2 = num2;
1991  *pend = end; *pstart = start; *pptr = ptr; })
1992 
1993 static const char AARRAY_baseChars[] =
1994  "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUaWXYZ._";
1995 AARRAY_define(void AARRAY_u_to_str(
1996  uintmax_t value,
1997  /* can contain SIZE_MAX in binary */
1998  char str[(8 * sizeof(uintmax_t))+1], unsigned long base), {
1999  char*walkstr=str;
2000  // validate base
2001  if(base<2 || base>64) base = 10;
2002  // reverse number
2003  do *walkstr++ = AARRAY_baseChars[value%base]; while(value/=base);
2004  *walkstr='\0';
2005  char aux; while(--walkstr>str) aux=*walkstr, *walkstr=*str, *str++=aux; })
2006 AARRAY_define(void AARRAY_i_to_str(
2007  intmax_t value,
2008  char str[(8 * sizeof(uintmax_t))+1], unsigned long base), {
2009  char*walkstr=str;
2010  // validate base
2011  if(base<2 || base>64) base = 10;
2012  uint8_t sign = value < 0;
2013  if(sign) value = -value;
2014  // reverse number
2015  do *walkstr++ = AARRAY_baseChars[value%(int)base]; while(value/=base);
2016  if(sign) *walkstr++ = '-';
2017  else *walkstr++ = '+';
2018  *walkstr='\0';
2019  char aux; while(--walkstr>str) aux=*walkstr, *walkstr=*str, *str++=aux; })
2020 
2021 // cppp let Fmt be defined once, but output to both streams and arrays
2022 $define OUTPUT_A(A,B) A
2023 
2024 $define OUTPUT_B(A,B) B
2025 
2026 $define FMT_PRINT(isCHAR, isCHARptr, isINT8, isINT16, isINT32,
2027  isINT64, isFLOAT, isDOUBLE, OUTPUT_AB)
2028  case '%': {
2029  OUTPUT_AB(if(EOF==fputc('%', fmtOut)) return -1,
2030  (void)aAppend(fmtOut, '%'));
2031  break; }
2032  case 's': {
2033  AARRAY_safety(, if(vc>=vecCount) AARRAY_Error_FormatStringArgs);
2034  AARRAY_safety(, if(!vec[vc]) AARRAY_Error_NullParameter)
2035  OUTPUT_AB(if(EOF==fputs(isCHARptr, fmtOut)) return -1,
2036  (void)aAppendArray(fmtOut, SIZE_MAX,
2037  (uintptr_t)AARRAY_move(isCHARptr)));
2038  break; }
2039  case 'c': {
2040  AARRAY_safety(, if(vc>=vecCount) AARRAY_Error_FormatStringArgs);
2041  OUTPUT_AB(if(EOF==fputc(isCHAR, fmtOut)) return -1,
2042  (void)aAppend(fmtOut, (uint8_t)isCHAR));
2043  break; }
2044  case 'u': {
2045  AARRAY_safety(, if(vc>=vecCount) AARRAY_Error_FormatStringArgs);
2046  AARRAY_u_to_str((num2==8? isINT8 :
2047  (num2==16? isINT16 : (num2==32? isINT32 :isINT64))),
2048  buffer, num1);
2049  OUTPUT_AB(if(EOF==fputs(buffer, fmtOut)) return -1,
2050  (void)aAppendArray(fmtOut, SIZE_MAX,
2051  (uintptr_t)AARRAY_move(buffer)));
2052  break; }
2053  case 'i': {
2054  AARRAY_safety(, if(vc>=vecCount) AARRAY_Error_FormatStringArgs);
2055  AARRAY_i_to_str((num2==8? (int8_t)isINT8 :
2056  (num2==16? (int16_t)isINT16 :
2057  (num2==32? (int32_t)isINT32 : (int64_t)isINT64))),
2058  buffer, num1);
2059  OUTPUT_AB(if(EOF==fputs(buffer, fmtOut)) return -1,
2060  (void)aAppendArray(fmtOut, SIZE_MAX,
2061  (uintptr_t)AARRAY_move(buffer)));
2062  break; }
2063  case 'f': case 'd': {
2064  AARRAY_safety(, if(vc>=vecCount) AARRAY_Error_FormatStringArgs);
2065  OUTPUT_AB(if(EOF==fprintf(fmtOut, "%g",
2066  specifier=='f'?(double)isFLOAT:isDOUBLE)) return -1,
2067  int len = snprintf(*fmtOut, 0, "%g",
2068  specifier=='f'?(double)isFLOAT:isDOUBLE);
2069  // safe to assume no errors from snprintf
2070  size_t oldlen = aLength(*fmtOut);
2071  (void)aMulti(fmtOut, oldlen, 0, 0, (uintptr_t)len+1, 0);
2072  snprintf(&(*fmtOut)[oldlen], (size_t)len+1, "%g",
2073  specifier=='f'?(double)isFLOAT:isDOUBLE);
2074  (void)aZLength2(*fmtOut, 1));
2075  break; }
2076 
2077 $define GENERATE_Fmt(NAME, OUTPUT_AB)
2078 AARRAY_define(int AARRAY_Fmt_$##NAME(char errLoc[],
2079  OUTPUT_AB(FILE*, char**) fmtOut,
2080  size_t vecCount, uint64_t vec[]), {
2081  AARRAY_safety(, if(!fmtOut) AARRAY_Error_NullParameter);
2082  size_t ptr= 0, prevStart = 0, start = 0, end = 0, vc = 0;
2083  char specifier = 0; size_t doublePercent;
2084  unsigned long num1, num2;
2085  if(!vecCount) return 0;
2086  char*fmt = (char*)vec[vc++];
2087  AARRAY_safety(, if(!fmt) AARRAY_Error_NullParameter );
2088  // big enough for binary INTMAX_MAX
2089  char buffer[(8 * sizeof(intmax_t))+1];
2090  while(1) {
2091  prevStart = start;
2092  AARRAY_percent_parse(errLoc, fmt, &ptr,
2093  &specifier, &num1, &num2, &start, &end,
2094  &doublePercent);
2095  OUTPUT_AB(if(end-prevStart < fwrite(fmt+prevStart, sizeof(char),
2096  end-prevStart, fmtOut)) return -1,
2097  (void)aAppendArray(fmtOut, end-prevStart,
2098  (uintptr_t)AARRAY_move(&fmt[prevStart])));
2099  switch(specifier) {
2100  case 'e': return 0;
2101  FMT_PRINT((char)vec[vc], (char*)vec[vc], (uint8_t)vec[vc],
2102  (uint16_t)vec[vc], (uint32_t)vec[vc], (uint64_t)vec[vc],
2103  *(float*)&vec[vc], *(double*)&vec[vc], OUTPUT_AB)
2104  case 'v':
2105  AARRAY_safety(, if(vc>=vecCount) AARRAY_Error_FormatStringArgs);
2106  prevStart = end+2;
2107  doublePercent = 0;
2108  do {
2109  AARRAY_percent_parse(errLoc, fmt, &ptr,
2110  &specifier, &num1, &num2, &start, &end,
2111  &doublePercent); }
2112  while(specifier == '%');
2113  AARRAY_safety(, if(specifier=='e' || specifier=='v')
2114  AARRAY_Error_FormatStringMalformed);
2115  size_t nn = (size_t)-1; while(++nn < aLength((uintptr_t*)(vec[vc]))) {
2116  if(nn) {
2117  // resolving %% to % is a pain, since we now have to
2118  // loop through %v's separator again, doing the conversion
2119  if(doublePercent) {
2120  size_t ptr2 = prevStart; while(ptr2 < doublePercent)
2121  switch(fmt[ptr2]) {
2122  case '%': ptr2+=2; OUTPUT_AB(fputc('%', fmtOut),
2123  (void)aAppend(fmtOut, '%')); break;
2124  default: OUTPUT_AB(fputc(fmt[ptr2++], fmtOut),
2125  (void)aAppend(fmtOut, (uint8_t)fmt[ptr2++])); }
2126  prevStart = doublePercent; }
2127  OUTPUT_AB(if(end-prevStart <fwrite(fmt+prevStart, sizeof(char),
2128  end-prevStart, fmtOut)) return -1,
2129  (void)aAppendArray(fmtOut, end-prevStart,
2130  (uintptr_t)AARRAY_move(&fmt[prevStart]))); }
2131  switch(specifier) {
2132  FMT_PRINT(((char*)vec[vc])[nn], ((char**)vec[vc])[nn],
2133  ((uint8_t*)vec[vc])[nn], ((uint16_t*)vec[vc])[nn],
2134  ((uint32_t*)vec[vc])[nn], ((uint64_t*)vec[vc])[nn],
2135  ((float*)vec[vc])[nn], ((double*)vec[vc])[nn], OUTPUT_AB); } }
2136  break; }
2137  vc++;
2138  specifier = 0; }
2139  return 0; })
2140 
2141 GENERATE_Fmt(File, OUTPUT_A)
2142 GENERATE_Fmt(Array, OUTPUT_B)
2143 
2144 AARRAY_define(int AARRAY_Fmt_Error(
2145  char errLoc[], size_t vecCount, uint64_t vec[]), {
2146  fflush(stdout);
2147  int returnValue = AARRAY_Fmt_File(errLoc, stderr, vecCount, vec);
2148  fflush(stderr);
2149  return returnValue; })
2150 
2151 #define aFmtF(file, ...) AARRAY_Fmt_File (AARRAY_LINE, file, \
2152  AARRAY_64bitArgs(__VA_ARGS__))
2153 #define aFmt(...) AARRAY_Fmt_File (AARRAY_LINE, stdout, \
2154  AARRAY_64bitArgs(__VA_ARGS__))
2155 #define aFmtE(...) AARRAY_Fmt_Error(AARRAY_LINE, \
2156  AARRAY_64bitArgs(__VA_ARGS__))
2157 #define aFmtA(array, ...) AARRAY_Fmt_Array(AARRAY_LINE, array, \
2158  AARRAY_64bitArgs(__VA_ARGS__))
2159 
2160 
2161 
2162 
2163 #if !defined(AARRAY_NOCONVENIENCE)
2164  #define aA aAppend
2165  #define aR aReplace
2166  #define aAA aAppendArray
2167  #define aRA aReplaceArray
2168  #define aD aDelete
2169  #define aC aConcat
2170  #define aM aMulti
2171 
2172  #define aL aLength
2173  #define aL2 aLength2
2174  #define aZL2 aZLength2
2175 
2176  #define aF aFmt
2177  #define aFE aFmtE
2178  #define aFF aFmtF
2179  #define aFA aFmtA
2180  #define aW aWrite
2181 
2182  #define aStr(string) aAppendArray((char**)NULL, SIZE_MAX, (uintptr_t)string)
2183 #endif
2184 
2185 #if defined(__cplusplus)
2186  AARRAY_nowarn_pedantic_cpp_end
2187 #endif
any * aAppend(any **aArray, any items,...)
any aLength2(any *aArray, size_t len)
any * aMulti(any **aArray, size_t pos, size_t removeAmount, size_t arrayTimes, size_t arrayLen, any *array,...)
any * aAppendArray(any **aArray, size_t arrayLen, any *array,...)
size_t aLength(any *aArray)
void aError(char *errorLocation, char *errorMsg)
int aFmtF(FILE *file, char *format,...)
any aZLength2(any *aArray, size_t len)
void aFree(any **aArray)