/* Copyright 2014 Adobe Systems Incorporated (http://www.adobe.com/). All Rights Reserved.
   This software is licensed as OpenSource, under the Apache License, Version 2.0.
   This license is available at: http://opensource.org/licenses/Apache-2.0. */

#ifndef DYNARR_H
#define DYNARR_H

#include "ctlshare.h"

#define DNA_VERSION CTL_MAKE_VERSION(2, 0, 4)

#ifdef __cplusplus
extern "C" {
#endif

/* Dynamic Array Library
   =====================
   The dynamic array library provides simple and flexible support for
   homogeneous arrays that automatically grow to accommodate new elements.

   Dynamic arrays or da's are particularly useful in situations where the size
   of the array isn't known at compile or run time until the last element has
   been stored, and no suitable default size can be determined. Such situations
   occur, for example, when data is being read from a file and loaded into an
   array. The traditional way of handling this situation has been to make
   multiple passes over the data but this can be expensive, especially if
   parsing is complicated. Dynamic arrays can provide a cheaper alternative.

   da's are also useful in situations where the same array is used repeatedly
   with different data sets. The traditional way of handling this situation has
   been to allocate and deallocate memory for each data set but this can also
   be expensive. Dynamic arrays can simply be reused with each data set and no
   further allocation becomes necessary after the largest data set has been
   encountered.

   da's can also lead to a different programming style where programs no longer
   have to handle unusually large data sets (normally by fatal error) but
   rather "just work" irrespective of the data. This is particularly useful
   when working with poorly specified data sets.

   A da is implemented as a C structure that contains a pointer to a
   dynamically allocated array plus a few fields to control (re)allocation, and
   optional initialization, of elements of that array. da's are created by
   declaring them with the dnaDCL() macro described below.

   Once a da has been declared it must be initialized by the dnaINIT() or
   dnaINIT_FIRST() macros. This process associates values chosen by the
   client with the da that are used to control subsequent allocation.

   After initialization the da is accessed using a number of macros described
   below. These check if the desired index is within the array and, if not, the
   array is grown (reallocated) to accommodate it. The possibility of
   reallocation means that the array may be moved in memory outside of client
   control and it is therefore NOT permitted to save element POINTERS during
   the time that the da is growing. A client can, however, save element INDEXES
   reliably since these aren't dependent on memory addresses.

   After the da has been grown and loaded with data it may be accessed
   without restriction.

   Finally, when a client has finished with a da it is freed by a call to
   dnaFREE().

   The following describes the interface to the library. */

typedef struct dnaCtx_ *dnaCtx;

#define dnaDCL(type, da)                               \
    struct                                             \
    {                                                  \
        dnaCtx ctx;                                    \
        type *array;                                   \
        long cnt;                                      \
        long size;                                     \
        long incr;                                     \
        void (*func)(void *ctx, long cnt, type *base); \
    } da

/* dnaDCL() declares a dynamic array object with elements of type "type". */

dnaCtx dnaNew(ctlMemoryCallbacks *mem_cb, CTL_CHECK_ARGS_DCL);

#define DNA_CHECK_ARGS CTL_CHECK_ARGS_CALL(DNA_VERSION)

/* dnaNew() initializes the library and returns an opaque context that is
   subsequently passed to dnaINIT() or dnaINIT_FIRST(). It must be the first
   function in the library to be called by the client. The client passes a set
   memory callback functions (described in ctlshare.h) to the library via the
   mem_cb parameters.

   The DNA_CHECK_ARGS macro is passed as the last parameter to dnaNew() and is
   concerned with checking client call compatibility with the library's version
   and interface structure sizes. If a mismatch is found dnaNew() returns NULL
   to indicate the initialization failed.

   A client uses the dynamic array library almost exclusively through the
   macros described below. Macros are necessary because the C language doesn't
   permit types to be manipulated flexibly enough for this implementation.

   The macro interface to the library doesn't handle memory allocation
   failures, but since clients normally supply memory callback functions that
   handle allocation errors by setjmp/longjmp, and therefore never return NULL,
   this isn't a problem.

   However, sometimes the overhead of setjmp is too high for the task being
   performed. In such cases the client can choose to supply memory callback
   functions that don't handle allocation errors and can return NULL. The
   client must then use the dnaGrow() function to access the da (see below). */

void dnaInit(dnaCtx ctx, void *object, size_t init, size_t incr, int check);

#define dnaINIT(ctx, da, init, incr) \
    dnaInit(ctx, (void *)(&(da)), init, incr, 0)

/* dnaINIT() initializes the dynamic array before its first use. The "init"
   parameter specifies the initial number of elements to be allocated to the
   array when first accessed. The "incr" parameter specifies the number of
   additional elements allocated to the array on subsequent accesses. Note
   that indexes that exceed the init or init+incr sizes are accommodated by
   allocating to the next multiple of the incr size that accommodates the index.

   Sometimes it is necessary to initialize the the newly created elements when
   they are first allocated. This can be achieved by attaching an element
   initializer function to the da by explicitly initializing the "func" field
   of the da object with the address of the initializer function after the
   calling dnaINIT() or dnaINIT_FIRST() and before first use of the da.

   The initializer function's "cnt" parameter specifies the number of elements
   to be initialized and the "base" parameter (whose type must match the da
   declaration) specifies the address of the first element in the sub-array to
   be initialized. The client context is also made available via the "ctx"
   parameter and is simply a copy of the client context provided to the dna
   library in ctlMemoryCallbacks.ctx field. */

#define dnaINIT_FIRST(ctx, da, init, incr) \
    dnaInit(ctx, (void *)(&(da)), init, incr, 1)

/* dnaINIT_FIRST() is identical to dnaINIT() except that it will only
   initialize the dynamic array on its first call. */

long dnaSetCnt(void *object, size_t elemsize, long cnt);
long dnaGrow(void *object, size_t elemsize, long index);
long dnaIndex(void *object, size_t elemsize, long index);
long dnaMax(void *object, size_t elemsize, long index);
long dnaNext(void *object, size_t elemsize);
long dnaExtend(void *object, size_t elemsize, long length);

/* These functions are used to grow a da according to different access schemes
   that suit a wide variety of usages. In all functions the object parameter is
   the address of the da to be accessed and the element parameter specifies the
   size (in bytes) of an element in the da.

   In normal operation these functions behave as follows.

   function         arg     action                          normal return
   ---------------  ------  ------------------------------  -----------------
   dnaSetCnt        cnt     da.cnt=cnt                      0
   dnaGrow          index   -                               0
   dnaIndex         index   -                               index
   dnaMax           index   if(index>=da.cnt)da.cnt=index+1 index
   dnaNext          -       da.cnt++                        da.cnt
   dnaExtend        length  da.cnt+=length                  da.cnt

   The functions return -1 if memory allocation failure occurs, that is if
   either the malloc or realloc functions return NULL.

   These function are normally used indirectly through the macros described
   below. Direct usage is only necessary when the memory callback functions can
   return NULL to indicate failure rather than handling the failure within the
   callback, for example by longjmp() or exit(). */

#define DNA_DA_ADDR_(da) \
    ((void *)(&(da)))

#define DNA_ELEM_SIZE_(da) \
    (sizeof((da).array[0]))

#define DNA_ELEM_ADDR_(da, i) \
    (&(da).array[(i)])

#define dnaSET_CNT(da, n) \
    (void)dnaSetCnt(DNA_DA_ADDR_(da), DNA_ELEM_SIZE_(da), (n))

/* dnaSET_CNT() grows the array to accommodate a total of "n" elements and
   sets the da.cnt field to "n". */

#define dnaGROW(da, i) \
    ((void)dnaGrow(DNA_DA_ADDR_(da), DNA_ELEM_SIZE_(da), (i)), (da).array)

/* dnaGROW() grows the array to accommodate the "i"th element and returns
   the address of the first element of the array. The da.cnt field is
   unaltered. */

#define dnaINDEX(da, i) \
    ((void)dnaIndex(DNA_DA_ADDR_(da), DNA_ELEM_SIZE_(da), (i)), DNA_ELEM_ADDR_((da), (i)))

/* dnaINDEX() grow the array to accommodate the "i"th element and returns
   its address. The da.cnt field is unaltered. */

#define dnaMAX(da, i) \
    ((void)dnaMax(DNA_DA_ADDR_(da), DNA_ELEM_SIZE_(da), (i)), DNA_ELEM_ADDR_((da), (i)))

/* dnaMAX() is the same as dnaINDEX() except that the da.cnt field is set to
   be one greater than the maximum index accommodated. */

#define dnaNEXT(da) \
    ((void)dnaNext(DNA_DA_ADDR_(da), DNA_ELEM_SIZE_(da)), DNA_ELEM_ADDR_((da), (da).cnt - 1))

/* dnaNEXT() grows the array to accommodate the next element (da.cnt) and
   returns its address. The da.cnt field is incremented by 1. */

#define dnaEXTEND(da, len) \
    ((void)dnaExtend(DNA_DA_ADDR_(da), DNA_ELEM_SIZE_(da), (len)), DNA_ELEM_ADDR_((da), (da).cnt - (len)))

/* dnaEXTEND() extends the dynamic array by "len" elements and returns the
   address of the first element of the extension. The da.cnt fields is
   increment by "len". */

void dnaFreeObj(void *object);
#define dnaFREE(da) (dnaFreeObj)(DNA_DA_ADDR_(da))

/* dnaFREE() frees resources allocated to the dynamic array. It may be
   safely applied to dynamic array objects that have been declared and
   initialized but never used. */

void dnaSetDebug(dnaCtx h, int level);

void dnaFree(dnaCtx h);

/* dnaFree() destroys the library context and all the resources allocated to
   it. */

void dnaGetVersion(ctlVersionCallbacks *cb);

/* dnaGetVersion() returns the library version number and name via the client
   callbacks passed with the "cb" parameter (see ctlshare.h). This*/

/* ------------------------ Discussion and Examples ------------------------

   Declaration
   ===========
   da's are declared with the dnaDCL() macro:

     dnaDCL(int, integers);

   Declares a da called "integers" with elements of type "int".

     dnaDCL(char *, strings);

   Declares a da called "strings" with elements of type "char *".

     typedef struct
         {
         float x
         float y
         } Coord;
     dnaDCL(Coord, coords);

   Declares a da called "coords" with elements of type "Coord".

     typedef dnaDCL(char, GrowBuf);
     GrowBuf tmp;

   Declares a type called "GrowBuf" that is a da with elements of type "char"
   and defines an object called "tmp" of this type. This could be used as a
   temporary char buffer for string manipulation, for example.

   Initialization
   ==============
   Once they have been declared, da's must be initialized before being used by
   calling the dnaINIT() or dnaINIT_FIRST() macros:

     dnaINIT(dactx, coords, 1000, 500);

   Initializes the "coords" da with an initial size of 1000 elements and an
   increment size of 500 elements. The "dactx" parameter is the pointer
   returned dnaNew() when the library was initialized.

   If the code fragment is executed multiple times, for example with multiple
   data sets, the initialization must only occur the first time otherwise the
   previously allocated array will be leaked. First time initialization can be
   conveniently handled by calling the dnaINIT_FIRST() macro in place of
   dnaINIT():

     dnaINIT_FIRST(dactx, coords, 1000, 500);

   Sometimes it is necessary to initialize the the newly created elements when
   they are first allocated. This can be achieved by attaching an element
   initializer function (of matching type) to the da:

     void initStrings(void *ctx, long cnt, char **base)
       {
       while (cnt--)
           *base++ = NULL;
       }
     ...
     dnaINIT(dactx, strings, 250, 50);
     strings.func = initStrings;

   Growing and Loading
   ===================
   Once a da has been declared and initialized it may be accessed so that
   elements of the underlying array can be loaded. This is accomplished by a
   number of macros that are tailored to particular types of access.

   The simplest of these is dnaSET_CNT() which is used to grow the array to the
   specified size and set the cnt field to that size. This would normally be
   used for multiple data sets whose size was known in advance. The array is
   then simply reused for each data set.

   Next in complexity is dnaGROW() which simply grows the array to accommodate
   an index and returns the address of the first element of the array. This can
   be useful when inserting an element into the middle of a da, for example
   when implementing an insertion sort.

   Random elements in the da can be loaded using dnaINDEX(). This grows the
   array to accommodate the index and returns a pointer to the indexed element.
   This might be used when loading a sparse array, but in this case it is
   imperative that an element initializer is specified so that elements may be
   suitably initialized. If this isn't done there will be no reliable way of
   determining which elements were loaded.

   dnaMAX() is a variation on dnaINDEX() that records one greater than the
   highest index in the da.cnt field which may be used to limit the subsequent
   search for loaded elements.

   A common requirement is to load the array sequentially, starting at index 0
   and ending when the data is exhausted. This is easily achieved using
   dnaNEXT() which returns a pointer to the next element and increments da.cnt
   automatically. The client must initialize da.cnt to 0 (or any other suitable
   starting index) before calling dnaNEXT(). The following example fills the
   strings da with strings returned from the nextString() function which
   returns NULL when its supply of strings is exhausted.

     char *string;
     strings.cnt = 0;
     while ((string = nextString()) != NULL)
         *dnaNEXT(strings) = string;

   Finally, dnaEXTEND() is used to add a specified number of elements to the
   end of the array and returns the address of the first element of this
   extension. This function is useful for appending strings to a buffer
   as shown in the example below:

     char *string;
     tmp.cnt = 0;
     while ((string = nextString()) != NULL)
         {
         size_t len = strlen(string);
         memmove(dnaEXTEND(tmp, len), string, len);
         }

   Note: strings have null termination removed in this example.

   Access
   ======
   Once the da is loaded the elements in the array may be accessed using
   conventional techniques and even the addresses of elements can be used
   since the array will not be reallocated again. Generally, the da.cnt field
   records the number of elements in the array so that the following code may
   be used to find the maximum element in an array of integers. For brevity
   this example assumes that there is at least 1 element in the array.

     long i;
     long max = integers.array[0];
     for (i = 1; i < integers.cnt; i++)
         if (integers.array[i] > max)
             max = integers.array[i];

   The following example sorts the string da after it is loaded.

     int cmpStrings(const void *first, const void *second)
         {
         return strcmp(*(char**)first, *(char **)second);
         }
     ...
     qsort(strings.array, strings.cnt, sizeof(char *), cmpStrings);

 */

#ifdef __cplusplus
}
#endif

#endif /* DYNARR_H */
