#include <string.h>
#include "_pair_list.h"

#include <Python.h>

// fix for VisualC complier used by Python 3.4
#ifdef __GNUC__
#define INLINE inline
#else
#define INLINE
#endif


#define MIN_LIST_CAPACITY 32

static PyTypeObject pair_list_type;
static PyObject * _istr_type;


_Py_IDENTIFIER(lower);


typedef PyObject * (*calc_identity_func)(PyObject *key);


/* Global counter used to set ma_version_tag field of dictionary.
 * It is incremented each time that a dictionary is created and each
 * time that a dictionary is modified. */
static uint64_t pair_list_global_version = 0;

#define NEXT_VERSION() (++pair_list_global_version)


typedef struct pair {
    PyObject  *identity;  // 8
    PyObject  *key;       // 8
    PyObject  *value;     // 8
    Py_hash_t  hash;      // 8
} pair_t;


typedef struct pair_list {  // 24 for GC prefix, 82 in total
    PyObject_HEAD           // 16
    Py_ssize_t  capacity;   // 8
    Py_ssize_t  size;       // 8
    uint64_t  version;      // 8
    calc_identity_func calc_identity;  // 8
    pair_t *pairs;          // 8
} pair_list_t;


static INLINE int
str_cmp(PyObject *s1, PyObject *s2)
{
    PyObject *ret = PyUnicode_RichCompare(s1, s2, Py_EQ);
    if (ret == Py_True) {
        Py_DECREF(ret);
        return 1;
    }
    else if (ret == NULL) {
        return -1;
    }
    else {
        Py_DECREF(ret);
        return 0;
    }
}


static INLINE PyObject *
key_to_str(PyObject *key)
{
    PyTypeObject *type = Py_TYPE(key);
    if (PyUnicode_CheckExact(key)) {
        Py_INCREF(key);
        return key;
    }
    if ((PyObject *)type == _istr_type) {
        return PyObject_Str(key);
    }
    if (PyUnicode_Check(key)) {
        return PyObject_Str(key);
    }
    PyErr_SetString(PyExc_TypeError,
                    "MultiDict keys should be either str "
                    "or subclasses of str");
    return NULL;
}


static PyObject *
ci_key_to_str(PyObject *key)
{
    PyTypeObject *type = Py_TYPE(key);
    if ((PyObject *)type == _istr_type) {
        return _PyObject_CallMethodId(key, &PyId_lower, NULL);
    }
    if (PyUnicode_Check(key)) {
        return _PyObject_CallMethodId(key, &PyId_lower, NULL);
    }
    PyErr_SetString(PyExc_TypeError,
                    "CIMultiDict keys should be either str "
                    "or subclasses of str");
    return NULL;
}

static INLINE pair_t *
pair_list_get(pair_list_t *list, Py_ssize_t i)
{
    pair_t *item = list->pairs + i;
    return item;
}

static int
pair_list_resize(pair_list_t *list, Py_ssize_t new_capacity)
{
    pair_t *new_pairs;
    // TODO: use more smart algo for capacity grow
    if (new_capacity < MIN_LIST_CAPACITY) {
        new_capacity = MIN_LIST_CAPACITY;
    }
    if (list->capacity == new_capacity) {
        // No need to resize
        return 0;
    }

    new_pairs = PyMem_Resize(list->pairs, pair_t, (size_t)new_capacity);

    if (NULL == new_pairs) {
        // if not enought mem for realloc we do nothing, just return false
        return -1;
    }

    list->pairs = new_pairs;
    list->capacity = new_capacity;

    return 0;
}


static PyObject *
_pair_list_new(calc_identity_func calc_identity)
{
    pair_list_t *list = PyObject_GC_New(pair_list_t, &pair_list_type);
    if (list == NULL) {
        return NULL;
    }

    // TODO: align size of pair to the nearest power of 2
    list->pairs = PyMem_New(pair_t, MIN_LIST_CAPACITY);
    if (list->pairs == NULL) {
        return NULL;
    }

    list->capacity = MIN_LIST_CAPACITY;
    list->size = 0;
    list->version = NEXT_VERSION();
    list->calc_identity = calc_identity;

    return (PyObject *)list;
}

PyObject *
pair_list_new(void)
{
    return _pair_list_new(key_to_str);
}


PyObject *
ci_pair_list_new(void)
{
    return _pair_list_new(ci_key_to_str);
}


void
pair_list_dealloc(pair_list_t *list)
{
    pair_t *pair;
    Py_ssize_t pos;

    PyObject_GC_UnTrack(list);
    Py_TRASHCAN_SAFE_BEGIN(list);

    for (pos = 0; pos < list->size; pos++) {
        pair = pair_list_get(list, pos);

        Py_XDECREF(pair->identity);
        Py_XDECREF(pair->key);
        Py_XDECREF(pair->value);
    }

    list->size = 0;
    if (list->pairs != NULL) {
        PyMem_Del(list->pairs);
        list->pairs = NULL;
    }

    Py_TYPE(list)->tp_free((PyObject *)list);
    Py_TRASHCAN_SAFE_END(list);
}


Py_ssize_t
pair_list_len(PyObject *op)
{
    pair_list_t *list = (pair_list_t *)op;
    return list->size;
}


static INLINE int
_pair_list_add_with_hash(PyObject *op,
                         PyObject *identity,
                         PyObject *key,
                         PyObject *value,
                         Py_hash_t hash)
{
    pair_list_t *list = (pair_list_t *)op;
    pair_t *pair;

    if (list->capacity < list->size + 1) {
        if (pair_list_resize(list, list->capacity + MIN_LIST_CAPACITY) < 0) {
            return -1;
        }
    }

    pair = pair_list_get(list, list->size);
    list->size += 1;

    Py_INCREF(identity);
    pair->identity = identity;

    Py_INCREF(key);
    pair->key = key;

    Py_INCREF(value);
    pair->value = value;

    pair->hash = hash;

    list->version = NEXT_VERSION();

    return 0;
}


int
pair_list_add(PyObject *op,
              PyObject *key,
              PyObject *value)
{
    Py_hash_t hash;
    PyObject *identity = NULL;
    pair_list_t *list = (pair_list_t *)op;
    int ret;

    identity = list->calc_identity(key);
    if (identity == NULL) {
        goto fail;
    }
    hash = PyObject_Hash(identity);
    if (hash == -1) {
        goto fail;
    }
    ret = _pair_list_add_with_hash(op, identity, key, value, hash);
    Py_DECREF(identity);
    return ret;
fail:
    Py_XDECREF(identity);
    return -1;
}


static int
pair_list_del_at(pair_list_t *list, Py_ssize_t pos)
{
    // return 1 on success, -1 on failure
    Py_ssize_t tail;
    pair_t *pair;

    pair = pair_list_get(list, pos);
    Py_DECREF(pair->identity);
    Py_DECREF(pair->key);
    Py_DECREF(pair->value);

    list->size -= 1;
    list->version = NEXT_VERSION();

    if (list->size == pos) {
        // remove from tail, no need to shift body
        return 0;
    }

    tail = list->size - pos;
    // TODO: raise an error if tail < 0
    memmove((void *)pair_list_get(list, pos),
            (void *)pair_list_get(list, pos + 1),
            sizeof(pair_t) * (size_t)tail);

    if (list->capacity - list->size > MIN_LIST_CAPACITY) {
        return pair_list_resize(list, list->capacity - MIN_LIST_CAPACITY);
    }

    return 0;
}


int
_pair_list_drop_tail(PyObject *op, PyObject *identity, Py_hash_t hash,
                     Py_ssize_t pos)
{
    // return 1 if deleted, 0 if not found
    pair_t *pair;
    int ret;
    pair_list_t *list = (pair_list_t *)op;
    int found = 0;

    if (pos >= list->size) {
        return 0;
    }

    for (; pos < list->size; pos++) {
        pair = pair_list_get(list, pos);
        if (pair->hash != hash) {
            continue;
        }
        ret = str_cmp(pair->identity, identity);
        if (ret > 0) {
            if (pair_list_del_at(list, pos) < 0) {
               return -1;
            }
            found = 1;
            pos--;
        }
        else if (ret == -1) {
            return -1;
        }
    }

    return found;
}

static int