/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. 
 *
 *    Copyright 2018 (c) Julius Pfrommer
 */

#ifndef	ZIPTREE_H_
#define	ZIPTREE_H_

#ifdef __cplusplus
extern "C" {
#endif

/* Reusable zip tree implementation. The style is inspired by the BSD
 * sys/queue.h linked list definition.
 *
 * Zip trees were developed in: Tarjan, R. E., Levy, C. C., and Timmel, S. "Zip
 * Trees." arXiv preprint arXiv:1806.06726 (2018).
 *
 * The ZIP_ENTRY definitions are to be contained in the tree entries themselves.
 * Use ZIP_PROTTYPE to define the signature of the zip tree and ZIP_IMPL (in a
 * .c compilation unit) for the method implementations.
 *
 * Zip trees are a probabilistic data structure. Entries are assigned a
 * (nonzero) rank k with probability 1/2^{k+1}. This header file does not assume
 * a specific random number generator. So the rank must be given when an entry
 * is inserted. A fast way (with a single call to a pseudo random generator) to
 * compute the rank is with ZIP_FFS32(random()). The ZIP_FFS32 returns the least
 * significant nonzero bit of a 32bit number. */

#define ZIP_HEAD(name, type)                    \
struct name {                                   \
    struct type *zip_root;                      \
}

#define ZIP_INIT(head) do { (head)->zip_root = NULL; } while (0)
#define ZIP_ROOT(head) (head)->zip_root
#define ZIP_EMPTY(head) (ZIP_ROOT(head) == NULL)

#define ZIP_ENTRY(type)                         \
struct {                                        \
    struct type *zip_left;                      \
    struct type *zip_right;                     \
    unsigned char rank;                         \
}

#define ZIP_LEFT(elm, field) (elm)->field.zip_left
#define ZIP_RIGHT(elm, field) (elm)->field.zip_right
#define ZIP_RANK(elm, field) (elm)->field.rank

/* Shortcuts */
#define ZIP_INSERT(name, head, elm, rank) name##_ZIP_INSERT(head, elm, rank)
#define ZIP_REMOVE(name, head, elm) name##_ZIP_REMOVE(head, elm)
#define ZIP_FIND(name, head, key) name##_ZIP_FIND(head, key)
#define ZIP_MIN(name, head) name##_ZIP_MIN(head)
#define ZIP_MAX(name, head) name##_ZIP_MAX(head)
#define ZIP_ITER(name, head, cb, d) name##_ZIP_ITER(head, cb, d)

/* Zip tree method prototypes */
#define ZIP_PROTTYPE(name, type, keytype)                               \
void name##_ZIP_INSERT(struct name *head, struct type *elm, unsigned char rank); \
void name##_ZIP_REMOVE(struct name *head, struct type *elm);            \
struct type *name##_ZIP_FIND(struct name *head, const keytype *key);    \
struct type *name##_ZIP_MIN(struct name *head);                         \
struct type *name##_ZIP_MAX(struct name *head);                         \
typedef void (*name##_cb)(struct type *elm, void *data);                \
void name##_ZIP_ITER(struct name *head, name##_cb cb, void *data);      \

/* The comparison method "cmp" defined for every zip tree has the signature
 *
 *   enum ZIP_CMP cmpDateTime(const keytype *a, const keytype *b);
 *
 * The entries need an absolute ordering. So ZIP_CMP_EQ must only be returned if
 * a and b point to the same memory. (E.g. assured by unique identifiers.) */
enum ZIP_CMP {
    ZIP_CMP_LESS = -1,
    ZIP_CMP_EQ = 0,
    ZIP_CMP_MORE = 1
};

/* Find the position of the first bit in an unsigned 32bit integer */
#ifdef _MSC_VER
static __inline
#else
static inline
#endif
unsigned char
ZIP_FFS32(unsigned int v) {
    unsigned int t = 1;
    unsigned char r = 1;
    if(v == 0) return 0;
    while((v & t) == 0) {
        t = t << 1; r++;
    }
    return r;
}

/* Zip tree method implementations */
#define ZIP_IMPL(name, type, field, keytype, keyfield, cmp)             \
static struct type *                                                    \
__##name##_ZIP_INSERT(struct type *root, struct type *elm) {            \
    if(!root) {                                                         \
        ZIP_LEFT(elm, field) = NULL;                                    \
        ZIP_RIGHT(elm, field) = NULL;                                   \
        return elm;                                                     \
    }                                                                   \
    if((cmp)(&(elm)->keyfield, &(root)->keyfield) == ZIP_CMP_LESS) {    \
        if(__##name##_ZIP_INSERT(ZIP_LEFT(root, field), elm) == elm) {  \
            if(ZIP_RANK(elm, field) < ZIP_RANK(root, field)) {          \
                ZIP_LEFT(root, field) = elm;                            \
            } else {                                                    \
                ZIP_LEFT(root, field) = ZIP_RIGHT(elm, field);          \
                ZIP_RIGHT(elm, field) = root;                           \
                return elm;                                             \
            }                                                           \
        }                                                               \
    } else {                                                            \
        if(__##name##_ZIP_INSERT(ZIP_RIGHT(root, field), elm) == elm) { \
            if(ZIP_RANK(elm, field) <= ZIP_RANK(root, field)) {         \
                ZIP_RIGHT(root, field) = elm;                           \
            } else {                                                    \
                ZIP_RIGHT(root, field) = ZIP_LEFT(elm, field);          \
                ZIP_LEFT(elm, field) = root;                            \
                return elm;                                             \
            }                                                           \
        }                                                               \
    }                                                                   \
    return root;                                                        \
}                                                                       \
                                                                        \
void                                                                    \
name##_ZIP_INSERT(struct name *head, struct type *elm,                  \
                  unsigned char rank) {                                 \
    ZIP_RANK(elm, field) = rank;                                        \
    ZIP_ROOT(head) = __##name##_ZIP_INSERT(ZIP_ROOT(head), elm);        \
}                                                                       \
                                                                        \
static struct type *                                                    \
__##name##ZIP(struct type *x, struct type *y) {                         \
    if(!x) return y;                                                    \
    if(!y) return x;                                                    \
    if(ZIP_RANK(x, field) < ZIP_RANK(y, field)) {                       \
        ZIP_LEFT(y, field) = __##name##ZIP(x, ZIP_LEFT(y, field));      \
        return y;                                                       \
    }                                                                   \
    ZIP_RIGHT(x, field) = __##name##ZIP(ZIP_RIGHT(x, field), y);        \
    return x;                                                           \
}                                                                       \
                                                                        \
static struct type *                                                    \
__##name##_ZIP_REMOVE(struct type *root, struct type *elm) {            \
    if(root == elm)                                                     \
        return __##name##ZIP(ZIP_LEFT(root, field),                     \
                             ZIP_RIGHT(root, field));                   \
    enum ZIP_CMP eq = (cmp)(&(elm)->keyfield, &(root)->keyfield);       \
    if(eq == ZIP_CMP_LESS) {                                            \
        struct type *left = ZIP_LEFT(root, field);                      \
        if(elm == left)                                                 \
            ZIP_LEFT(root, field) =                                     \
                __##name##ZIP(ZIP_LEFT(left, field),                    \
                              ZIP_RIGHT(left, field));                  \
        else                                                            \
            __##name##_ZIP_REMOVE(left, elm);                           \
    } else {                                                            \
        struct type *right = ZIP_RIGHT(root, field);                    \
        if(elm == right)                                                \
            ZIP_RIGHT(root, field) =                                    \
                __##name##ZIP(ZIP_LEFT(right, field),                   \
                              ZIP_RIGHT(right, field));                 \
        else                                                            \
            __##name##_ZIP_REMOVE(right, elm);                          \
    }                                                                   \
    return root;                                                        \
}                                                                       \
                                                                        \
void                                                                    \
name##_ZIP_REMOVE(struct name *head, struct type *elm) {                \
    ZIP_ROOT(head) = __##name##_ZIP_REMOVE(ZIP_ROOT(head), elm);        \
}                                                                       \
                                                                        \
static struct type *                                                    \
__##name##_ZIP_FIND(struct type *root, const keytype *key) {            \
    if(!root)                                                           \
        return NULL;                                                    \
    enum ZIP_CMP eq = (cmp)(key, &(root)->keyfield);                    \
    if(eq == ZIP_CMP_EQ) {                                              \
        return root;                                                    \
    }                                                                   \
    if(eq == ZIP_CMP_LESS) {                                            \
        return __##name##_ZIP_FIND(ZIP_LEFT(root, field), key);         \
    }                                                                   \
    return __##name##_ZIP_FIND(ZIP_RIGHT(root, field), key);            \
}                                                                       \
                                                                        \
struct type *                                                           \
name##_ZIP_FIND(struct name *head, const keytype *key) {                \
    return __##name##_ZIP_FIND(ZIP_ROOT(head), key);                    \
}                                                                       \
                                                                        \
struct type *                                                           \
name##_ZIP_MIN(struct name *head) {                                     \
    struct type *cur = ZIP_ROOT(head);                                  \
    if(!cur) return NULL;                                               \
    while(ZIP_LEFT(cur, field)) {                                       \
        cur = ZIP_LEFT(cur, field);                                     \
    }                                                                   \
    return cur;                                                         \
}                                                                       \
                                                                        \
struct type *                                                           \
name##_ZIP_MAX(struct name *head) {                                     \
    struct type *cur = ZIP_ROOT(head);                                  \
    if(!cur) return NULL;                                               \
    while(ZIP_RIGHT(cur, field)) {                                      \
        cur = ZIP_RIGHT(cur, field);                                    \
    }                                                                   \
    return cur;                                                         \
}                                                                       \
                                                                        \
static void                                                             \
__##name##_ZIP_ITER(struct type *elm, name##_cb cb, void *data) {       \
    if(!elm)                                                            \
        return;                                                         \
    __##name##_ZIP_ITER(ZIP_LEFT(elm, field), cb, data);                \
    __##name##_ZIP_ITER(ZIP_RIGHT(elm, field), cb, data);               \
    cb(elm, data);                                                      \
}                                                                       \
                                                                        \
void                                                                    \
name##_ZIP_ITER(struct name *head, name##_cb cb, void *data) {          \
    __##name##_ZIP_ITER(ZIP_ROOT(head), cb, data);                      \
}

#ifdef __cplusplus
} /* extern "C" */
#endif

#endif /* ZIPTREE_H_ */