/*
    See license.txt in the root of this project.
*/

# ifndef LMT_UTILITIES_SPARSEARRAY_H
# define LMT_UTILITIES_SPARSEARRAY_H

/*tex

    This file originally was called |managed-sa| but becauss it kind of a library and also used in
    \LUATEX\ it's better to use a different name. In this variant dumping is more sparse (resulting
    in somewhat smaller format files). This might be backported but only after testing it here for a
    long time. Of course the principles are the same, it's just extended.

*/

/*tex

    The next two sets of three had better match up exactly, but using bare numbers is easier on the
    \CCODE\ compiler. Here are some format sizes (for ConTeXt) with different values:

     64 : 17562942
    128 : 17548150 <= best value
    256 : 17681398

*/

# if (0) 

/* HHHHHHHMMMMMMMLLLLLLL */

# define LMT_SA_HIGHPART 128
# define LMT_SA_MIDPART  128
# define LMT_SA_LOWPART  128

# define LMT_SA_H_PART(a) ((((a)) >> 14) & 127)
# define LMT_SA_M_PART(a) ((((a)) >>  7) & 127)
# define LMT_SA_L_PART(a) ((((a))      ) & 127)

# else 

/* 40K less in 2023 */
/* 90K less in 2024 */

/* HHHHHHHMMMMMMMMLLLLLL */ /* This is about as small as we can go. */

# define LMT_SA_HIGHPART 128
# define LMT_SA_MIDPART  256
# define LMT_SA_LOWPART   64

# define LMT_SA_H_PART(a) ((((a)) >> 14) & 127)
# define LMT_SA_M_PART(a) ((((a)) >>  6) & 255)
# define LMT_SA_L_PART(a) ((((a))      ) &  63)

// # define LMT_SA_HIGHPART 256
// # define LMT_SA_MIDPART  128
// # define LMT_SA_LOWPART   64
//
// # define LMT_SA_H_PART(a) ((((a)) >>  6) & 255)
// # define LMT_SA_M_PART(a) ((((a)) >> 14) & 127)
// # define LMT_SA_L_PART(a) ((((a))      ) &  63)

# endif

/*tex
    The compiler will likely optimize this anyway btu a ot of abstraction doesn't
    hurt.
*/

# define sa_index_0(n) (((n) << 1)) /* n * 2 */
# define sa_index_1(n) (((n)     )) /* n / 1 */
# define sa_index_2(n) (((n) >> 1)) /* n / 2 */
# define sa_index_4(n) (((n) >> 2)) /* n / 4 */
# define sa_index_8(n) (((n) >> 3)) /* n / 8 */

# define sa_value_1(n) (((n)     )) /* n % 1 */
# define sa_value_2(n) (((n) &  1)) /* n % 2 */
# define sa_value_4(n) (((n) &  3)) /* n % 4 */
# define sa_value_8(n) (((n) &  7)) /* n % 8 */

/*tex

    In the early days of \LUATEX\ we had just simple items, all 32 bit values. Then we put the
    delcodes in trees too which saved memory and format size but it introduced 32 bit slack in all
    the other code arrays. We then also had to dump selectively, but it was no big deal. Eventually,
    once it became clear that the concepts would not change a variant was made for \LUAMETATEX: we
    just use a two times larger lower array when we have delimiters. This saves some memory. The
    price we pay is that a stack entry now has two values but that is not really an issue.

    By packing the math code values we loose the option to store an active state but that's no big
    deal. We have a special am codes for that so it's no real loss.

    The code here is somewhat messy because we generalized it a bit. Maybe I'll redo it some day,
    for instance with pointers to arrays. Also, names can be better (indicating the data type that
    is involved). I played with 64 bit structs but there is no gain and currently we dont'need them
    anyway. What I might do is plug in a restore message so that we can get rid of the kind of
    copies in the math stack unsave code. The current 32 bit approach also is better for the format
    file which is quite a bit smaller then.

 */

typedef struct sparse_state_info {
    memory_data sparse_data;
} sparse_state_info;

extern sparse_state_info lmt_sparse_state;

typedef struct sa_mathblob {
    unsigned int class_value:math_class_bits;
    unsigned int family_value:math_family_bits;
    unsigned int character_value:math_character_bits;
} sa_mathblob;

// typedef struct sa_mathspec {
//     unsigned short properties;
//     unsigned short group;
//     unsigned int   index;
// } sa_mathspec;

typedef struct packed_math_character {
    union {
        sa_mathblob sa_value;
        unsigned    ui_value;
    };
} packed_math_character;

typedef union sa_tree_item {
    unsigned int   uint_value;        /* 32 : 32       */
    int            int_value;         /* 32 : 32       */
    sa_mathblob    math_code_value;   /* 32 : 6 6 20   */
 // sa_mathspec    math_spec_value;   /* 64 : 16 16 32 */ /* outlier, can be a v1/v2 */
    unsigned short ushort_value[2];   /* 32 : 16 16    */
    unsigned char  uchar_value[4];    /* 32 : 8 8 8 8  */
    unsigned char  nibble_value;
} sa_tree_item;

typedef struct sa_stack_item {
    int          code;
    int          level;   /* negative is signal to skip */
    sa_tree_item value_1;
    sa_tree_item value_2;
} sa_stack_item;

typedef struct sa_tree_head {
    int              sa_stack_size;         /*tex initial stack size   */
    int              sa_stack_step;         /*tex increment stack step */
    int              sa_stack_ptr;          /*tex current stack point  */
    sa_tree_item     dflt;                  /*tex default item value   */
    sa_tree_item   **tree[LMT_SA_HIGHPART]; /*tex item tree head       */ /* we always have HIGH now cf mail by AK to luatex list, little gain */
    sa_stack_item   *stack;                 /*tex stack tree head      */
    int              bytes;                 /*tex the number of items per entry */
    int              identifier;
} sa_tree_head;

typedef sa_tree_head *sa_tree;

# define wipe_sa_tree_item(itemptr) memset(itemptr, 0, sizeof(sa_tree_item))

// static inline unsigned int set_nibble(unsigned int original, int position, int nibble)
// {
//     position = 4 * ((unsigned int) position % 8);
//     return (original & ~(0xF << position)) | ((nibble & 0xF) << position);
// }
//
// static inline unsigned int get_nibble(unsigned int original, int position)
// {
//     return (original >> (4 * ((unsigned int) position % 8))) & 0xF;
// }

/*tex The compiler will do this anyway so we keep the above commented: */

static inline unsigned int set_nibble(unsigned int original, int position, int nibble)
{
    unsigned int shift = ((unsigned int) position & 0x7) << 2;
    return (original & ~(0xFU << shift)) | ((unsigned int) (nibble & 0xF) << shift);
}

static inline unsigned int get_nibble(unsigned int original, int position)
{
    unsigned int shift = ((unsigned int) position & 0x7) << 2;
    return (original >> shift) & 0xF;
}

/*tex Maybe at soem point we can do this, but then we need to cast in the \LUA\ interface: */

// static inline unsigned int set_nibble(unsigned int original, unsigned int position, unsigned int nibble)
// {
//     unsigned int shift = (position & 0x7) << 2;
//     return (original & ~(0xFU << shift)) | ((nibble & 0xF) << shift);
// }
//
// static inline unsigned int get_nibble(unsigned int original, unsigned int position)
// {
//     return (original >> ((position & 0x7) << 2)) & 0xF;
// }

//     int     sa_get_item_0    (const sa_tree head, int n);                                     /* returns value or dflt */
//     int     sa_get_item_1    (const sa_tree head, int n);                                     /* returns value or dflt */
//     int     sa_get_item_2    (const sa_tree head, int n);                                     /* returns value or dflt */
extern int     sa_get_item_4    (const sa_tree head, int n, sa_tree_item *v);                    /* returns success */
extern int     sa_get_item_8    (const sa_tree head, int n, sa_tree_item *v1, sa_tree_item *v2); /* returns success */

extern void    sa_set_item_0    (const sa_tree head, int n, int v, int gl);
extern void    sa_set_item_1    (const sa_tree head, int n, int v, int gl);
extern void    sa_set_item_2    (const sa_tree head, int n, int v, int gl);
extern void    sa_set_item_4    (const sa_tree head, int n, const sa_tree_item v, int gl);
extern void    sa_set_item_8    (const sa_tree head, int n, const sa_tree_item v1, const sa_tree_item v2, int gl);
extern sa_tree sa_new_tree      (int identifier, int stacksize, int stackstep, int bytes, const sa_tree_item dflt);
extern sa_tree sa_copy_tree     (const sa_tree head);
extern void    sa_destroy_tree  (sa_tree head);
extern void    sa_dump_tree     (dumpstream f, sa_tree a);
extern sa_tree sa_undump_tree   (dumpstream f);
extern void    sa_restore_stack (const sa_tree a, int gl);
extern void    sa_reinit_stack  (const sa_tree a, int gl);
extern void    sa_show_stack    (const sa_tree a);
extern void    sa_clear_stack   (const sa_tree a);

extern void    sa_set_item_n    (const sa_tree head, int n, int v, int gl);
extern int     sa_get_item_n    (const sa_tree head, int n);

static inline halfword sa_return_item_0(const sa_tree head, halfword n)
{
    int hp = LMT_SA_H_PART(n);
    if (head->tree[hp]) {
        int mp = LMT_SA_M_PART(n);
        if (head->tree[hp][mp]) {
            return (halfword) get_nibble(head->tree[hp][mp][sa_index_8(LMT_SA_L_PART(n))].uint_value, n);
        }
    }
    return (halfword) get_nibble(head->dflt.uint_value, 0);
}

static inline halfword sa_return_item_1(const sa_tree head, halfword n)
{
    int hp = LMT_SA_H_PART(n);
    if (head->tree[hp]) {
        int mp = LMT_SA_M_PART(n);
        if (head->tree[hp][mp]) {
            return (halfword) head->tree[hp][mp][sa_index_4(LMT_SA_L_PART(n))].uchar_value[sa_value_4(n)];
        }
    }
    return (halfword) head->dflt.uchar_value[0];
}

static inline halfword sa_return_item_2(const sa_tree head, halfword n)
{
    int hp = LMT_SA_H_PART(n);
    if (head->tree[hp]) {
        int mp = LMT_SA_M_PART(n);
        if (head->tree[hp][mp]) {
            return (halfword) head->tree[hp][mp][sa_index_2(LMT_SA_L_PART(n))].ushort_value[sa_value_2(n)];
        }
    }
    return (halfword) head->dflt.ushort_value[0];
}

static inline halfword sa_return_item_4(const sa_tree head, halfword n)
{
    int hp = LMT_SA_H_PART(n);
    if (head->tree[hp]) {
        int mp = LMT_SA_M_PART(n);
        if (head->tree[hp][mp]) {
            return (halfword) head->tree[hp][mp][LMT_SA_L_PART(n)].int_value;
        }
    }
    return (halfword) head->dflt.int_value;
}

static inline void sa_rawset_item_0(const sa_tree head, halfword n, unsigned char v)
{
    head->tree[LMT_SA_H_PART(n)][LMT_SA_M_PART(n)][sa_index_8(LMT_SA_L_PART(n))].uint_value = set_nibble(head->tree[LMT_SA_H_PART(n)][LMT_SA_M_PART(n)][sa_index_8(LMT_SA_L_PART(n))].uint_value, n, v);
}

static inline void sa_rawset_item_1(const sa_tree head, halfword n, unsigned char v)
{
    head->tree[LMT_SA_H_PART(n)][LMT_SA_M_PART(n)][sa_index_4(LMT_SA_L_PART(n))].uchar_value[sa_value_4(n)] = v;
}

static inline void sa_rawset_item_2(const sa_tree head, halfword n, unsigned short v)
{
    head->tree[LMT_SA_H_PART(n)][LMT_SA_M_PART(n)][sa_index_2(LMT_SA_L_PART(n))].ushort_value[sa_value_2(n)] = v;
}

static inline void sa_rawset_item_4(const sa_tree head, halfword n, const sa_tree_item v)
{
    head->tree[LMT_SA_H_PART(n)][LMT_SA_M_PART(n)][sa_index_1(LMT_SA_L_PART(n))] = v;
}

static inline void sa_rawset_item_8(const sa_tree head, halfword n,  const sa_tree_item v1, const sa_tree_item v2)
{
    sa_tree_item *low = head->tree[LMT_SA_H_PART(n)][LMT_SA_M_PART(n)];
    int l = sa_index_0(LMT_SA_L_PART(n));
    low[l] = v1;
    low[l+1] = v2;
}

// inline them

extern void *sa_malloc_array  (int recordsize, int size);
extern void *sa_realloc_array (void *p, int recordsize, int size, int step);
extern void *sa_calloc_array  (int recordsize, int size);
extern void *sa_free_array    (void *p);
extern void  sa_wipe_array    (void *head, int recordsize, int size);

# endif