#include "Python.h"

#include "structmember.h"

#include "dict-common.h"

#include <stddef.h>

typedef struct _odictnode _ODictNode;

struct _odictobject {

};

struct _odictnode {

};

#define _odictnode_KEY(node) \

(node->key)

#define _odictnode_HASH(node) \

(node->hash)

#define _odictnode_VALUE(node, od) \

PyODict_GetItemWithError((PyObject *)od, _odictnode_KEY(node))

#define _odictnode_PREV(node) (node->prev)

#define _odictnode_NEXT(node) (node->next)

#define _odict_FIRST(od) (((PyODictObject *)od)->od_first)

#define _odict_LAST(od) (((PyODictObject *)od)->od_last)

#define _odict_EMPTY(od) (_odict_FIRST(od) == NULL)

#define _odict_FOREACH(od, node) \

for (node = _odict_FIRST(od); node != NULL; node = _odictnode_NEXT(node))

#define _odict_FAST_SIZE(od) ((PyDictObject *)od)->ma_keys->dk_size

static void

_odict_free_fast_nodes(PyODictObject *od) {

if (od->od_fast_nodes) {

PyMem_FREE(od->od_fast_nodes);

}

}

static Py_ssize_t

_odict_get_index_raw(PyODictObject *od, PyObject *key, Py_hash_t hash)

{

PyObject **value_addr = NULL;

PyDictKeyEntry *ep;

PyDictKeysObject *keys = ((PyDictObject *)od)->ma_keys;

ep = (keys->dk_lookup)((PyDictObject *)od, key, hash, &value_addr);

if (ep == NULL)

return -1;

/* We use pointer arithmetic to get the entry's index into the table. */

return ep - keys->dk_entries;

}

static int

_odict_resize(PyODictObject *od) {

Py_ssize_t size, i;

_ODictNode **fast_nodes, *node;

/* Initialize a new "fast nodes" table. */

size = ((PyDictObject *)od)->ma_keys->dk_size;

fast_nodes = PyMem_NEW(_ODictNode *, size);

if (fast_nodes == NULL) {

PyErr_NoMemory();

return -1;

}

for (i = 0; i < size; i++)

fast_nodes[i] = NULL;

/* Copy the current nodes into the table. */

_odict_FOREACH(od, node) {

i = _odict_get_index_raw(od, _odictnode_KEY(node),

_odictnode_HASH(node));

if (i < 0) {

PyMem_FREE(fast_nodes);

return -1;

}

fast_nodes[i] = node;

}

/* Replace the old fast nodes table. */

_odict_free_fast_nodes(od);

od->od_fast_nodes = fast_nodes;

od->od_fast_nodes_size = size;

od->od_resize_sentinel = ((PyDictObject *)od)->ma_keys;

return 0;

}

static Py_ssize_t

_odict_get_index(PyODictObject *od, PyObject *key, Py_hash_t hash)

{

PyDictKeysObject *keys;

assert(key != NULL);

keys = ((PyDictObject *)od)->ma_keys;

/* Ensure od_fast_nodes and dk_entries are in sync. */

if (od->od_resize_sentinel != keys ||

od->od_fast_nodes_size != keys->dk_size) {

int resize_res = _odict_resize(od);

if (resize_res < 0)

return -1;

}

return _odict_get_index_raw(od, key, hash);

}

static _ODictNode *

_odict_find_node_hash(PyODictObject *od, PyObject *key, Py_hash_t hash)

{

Py_ssize_t index;

if (_odict_EMPTY(od))

return NULL;

index = _odict_get_index(od, key, hash);

if (index < 0)

return NULL;

return od->od_fast_nodes[index];

}

static _ODictNode *

_odict_find_node(PyODictObject *od, PyObject *key)

{

Py_ssize_t index;

Py_hash_t hash;

if (_odict_EMPTY(od))

return NULL;

hash = PyObject_Hash(key);

if (hash == -1)

return NULL;

index = _odict_get_index(od, key, hash);

if (index < 0)

return NULL;

return od->od_fast_nodes[index];

}

static void

_odict_add_head(PyODictObject *od, _ODictNode *node)

{

_odictnode_PREV(node) = NULL;

_odictnode_NEXT(node) = _odict_FIRST(od);

if (_odict_FIRST(od) == NULL)

_odict_LAST(od) = node;

else

_odictnode_PREV(_odict_FIRST(od)) = node;

_odict_FIRST(od) = node;

od->od_state++;

}

static void

_odict_add_tail(PyODictObject *od, _ODictNode *node)

{

_odictnode_PREV(node) = _odict_LAST(od);

_odictnode_NEXT(node) = NULL;

if (_odict_LAST(od) == NULL)

_odict_FIRST(od) = node;

else

_odictnode_NEXT(_odict_LAST(od)) = node;

_odict_LAST(od) = node;

od->od_state++;

}

static int

_odict_add_new_node(PyODictObject *od, PyObject *key, Py_hash_t hash)

{

Py_ssize_t i;

_ODictNode *node;

Py_INCREF(key);

i = _odict_get_index(od, key, hash);

if (i < 0) {

if (!PyErr_Occurred())

PyErr_SetObject(PyExc_KeyError, key);

Py_DECREF(key);

return -1;

}

else if (od->od_fast_nodes[i] != NULL) {

/* We already have a node for the key so there's no need to add one. */

Py_DECREF(key);

return 0;

}

/* must not be added yet */

node = (_ODictNode *)PyMem_MALLOC(sizeof(_ODictNode));

if (node == NULL) {

Py_DECREF(key);

PyErr_NoMemory();

return -1;

}

_odictnode_KEY(node) = key;

_odictnode_HASH(node) = hash;

_odict_add_tail(od, node);

od->od_fast_nodes[i] = node;

return 0;

}

#define _odictnode_DEALLOC(node) \

do { \

Py_DECREF(_odictnode_KEY(node)); \

PyMem_FREE((void *)node); \

} while (0)

static void

_odict_remove_node(PyODictObject *od, _ODictNode *node)

{

if (_odict_FIRST(od) == node)

_odict_FIRST(od) = _odictnode_NEXT(node);

else if (_odictnode_PREV(node) != NULL)

_odictnode_NEXT(_odictnode_PREV(node)) = _odictnode_NEXT(node);

if (_odict_LAST(od) == node)

_odict_LAST(od) = _odictnode_PREV(node);

else if (_odictnode_NEXT(node) != NULL)

_odictnode_PREV(_odictnode_NEXT(node)) = _odictnode_PREV(node);

_odictnode_PREV(node) = NULL;

_odictnode_NEXT(node) = NULL;

od->od_state++;

}

static int

_odict_clear_node(PyODictObject *od, _ODictNode *node, PyObject *key,

Py_hash_t hash)

{

Py_ssize_t i;

assert(key != NULL);

if (_odict_EMPTY(od)) {

/* Let later code decide if this is a KeyError. */

return 0;

}

i = _odict_get_index(od, key, hash);

if (i < 0)

return PyErr_Occurred() ? -1 : 0;

if (node == NULL)

node = od->od_fast_nodes[i];

assert(node == od->od_fast_nodes[i]);

if (node == NULL) {

/* Let later code decide if this is a KeyError. */

return 0;

}

// Now clear the node.

od->od_fast_nodes[i] = NULL;

_odict_remove_node(od, node);

_odictnode_DEALLOC(node);

return 0;

}

static void

_odict_clear_nodes(PyODictObject *od)

{

_ODictNode *node, *next;

_odict_free_fast_nodes(od);

od->od_fast_nodes = NULL;

node = _odict_FIRST(od);

_odict_FIRST(od) = NULL;

_odict_LAST(od) = NULL;

while (node != NULL) {

next = _odictnode_NEXT(node);

_odictnode_DEALLOC(node);

node = next;

}

}

#undef _odictnode_DEALLOC

static int

_odict_keys_equal(PyODictObject *a, PyODictObject *b)

{

_ODictNode *node_a, *node_b;

node_a = _odict_FIRST(a);

node_b = _odict_FIRST(b);

while (1) {

if (node_a == NULL && node_b == NULL)

/* success: hit the end of each at the same time */

return 1;

else if (node_a == NULL || node_b == NULL)

/* unequal length */

return 0;

else {

int res = PyObject_RichCompareBool(

(PyObject *)_odictnode_KEY(node_a),

(PyObject *)_odictnode_KEY(node_b),

Py_EQ);

if (res < 0)

return res;

else if (res == 0)

return 0;

/* otherwise it must match, so move on to the next one */

node_a = _odictnode_NEXT(node_a);

node_b = _odictnode_NEXT(node_b);

}

}

}

static int

odict_mp_ass_sub(PyODictObject *od, PyObject *v, PyObject *w)

{

if (w == NULL)

return PyODict_DelItem((PyObject *)od, v);

else

return PyODict_SetItem((PyObject *)od, v, w);

}

static PyMappingMethods odict_as_mapping = {

0, /*mp_length*/

0, /*mp_subscript*/

(objobjargproc)odict_mp_ass_sub, /*mp_ass_subscript*/

};

PyDoc_STRVAR(odict_delitem__doc__, "od.__delitem__(y) <==> del od[y]");

PyDoc_STRVAR(odict_eq__doc__,

");

static PyObject * odict_richcompare(PyObject *v, PyObject *w, int op);

static PyObject *

odict_eq(PyObject *a, PyObject *b)

{

return odict_richcompare(a, b, Py_EQ);

}

PyDoc_STRVAR(odict_init__doc__,

");

static int odict_init(PyObject *self, PyObject *args, PyObject *kwds);

PyDoc_STRVAR(odict_iter__doc__, "od.__iter__() <==> iter(od)");

static PyObject * odict_iter(PyODictObject *self); /* forward */

PyDoc_STRVAR(odict_ne__doc__, "");

static PyObject *

odict_ne(PyObject *a, PyObject *b)

{

return odict_richcompare(a, b, Py_NE);

}

PyDoc_STRVAR(odict_repr__doc__, "od.__repr__() <==> repr(od)");

static PyObject * odict_repr(PyODictObject *self); /* forward */

PyDoc_STRVAR(odict_setitem__doc__, "od.__setitem__(i, y) <==> od[i]=y");

PyDoc_STRVAR(odict_fromkeys__doc__,

");

static PyObject *

odict_fromkeys(PyObject *cls, PyObject *args, PyObject *kwargs)

{

static char *kwlist[] = {"iterable", "value", 0};

PyObject *seq;

PyObject *value = Py_None;

/* both borrowed */

if (!PyArg_ParseTupleAndKeywords(args, kwargs, "O|O:fromkeys", kwlist,

&seq, &value)) {

return NULL;

}

return _PyDict_FromKeys(cls, seq, value);

}

PyDoc_STRVAR(odict_sizeof__doc__, "");

static PyObject *

odict_sizeof(PyODictObject *od)

{

Py_ssize_t res = _PyDict_SizeOf((PyDictObject *)od);

res += sizeof(_ODictNode *) * _odict_FAST_SIZE(od); /* od_fast_nodes */

if (!_odict_EMPTY(od)) {

res += sizeof(_ODictNode) * PyODict_SIZE(od); /* linked-list */

}

return PyLong_FromSsize_t(res);

}

PyDoc_STRVAR(odict_reduce__doc__, "Return state information for pickling");

static PyObject *

odict_reduce(register PyODictObject *od)

{

_Py_IDENTIFIER(__dict__);

_Py_IDENTIFIER(items);

PyObject *dict = NULL, *result = NULL;

PyObject *items_iter, *items, *args = NULL;

/* capture any instance state */

dict = _PyObject_GetAttrId((PyObject *)od, &PyId___dict__);

if (dict == NULL)

goto Done;

else {

/* od.__dict__ isn't necessarily a dict... */

Py_ssize_t dict_len = PyObject_Length(dict);

if (dict_len == -1)

goto Done;

if (!dict_len) {

/* nothing to pickle in od.__dict__ */

Py_CLEAR(dict);

}

}

/* build the result */

args = PyTuple_New(0);

if (args == NULL)

goto Done;

items = _PyObject_CallMethodIdObjArgs((PyObject *)od, &PyId_items, NULL);

if (items == NULL)

goto Done;

items_iter = PyObject_GetIter(items);

Py_DECREF(items);

if (items_iter == NULL)

goto Done;

result = PyTuple_Pack(5, Py_TYPE(od), args, dict ? dict : Py_None, Py_None, items_iter);

Py_DECREF(items_iter);

Done:

Py_XDECREF(dict);

Py_XDECREF(args);

return result;

}