#include "Python.h"

#include "pycore_call.h" // _PyObject_CallNoArgs()

#include "pycore_object.h" // _PyObject_GC_UNTRACK()

#include "pycore_dict.h" // _Py_dict_lookup()

#include <stddef.h> // offsetof()

#include "clinic/odictobject.c.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))

static Py_ssize_t

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

{

PyObject *value = NULL;

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

Py_ssize_t ix;

ix = _Py_dict_lookup((PyDictObject *)od, key, hash, &value);

if (ix == DKIX_EMPTY) {

return keys->dk_nentries; /* index of new entry */

}

if (ix < 0)

return -1;

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

return ix;

}

#define ONE ((Py_ssize_t)1)

static int

_odict_resize(PyODictObject *od)

{

Py_ssize_t size, i;

_ODictNode **fast_nodes, *node;

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

size = ONE << (((PyDictObject *)od)->ma_keys->dk_log2_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. */

PyMem_Free(od->od_fast_nodes);

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 != (ONE << (keys->dk_log2_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;

assert(od->od_fast_nodes != 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;

assert(od->od_fast_nodes != 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;

}

assert(od->od_fast_nodes != NULL);

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;

assert(od->od_fast_nodes != NULL);

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;

PyMem_Free(od->od_fast_nodes);

od->od_fast_nodes = NULL;

od->od_fast_nodes_size = 0;

od->od_resize_sentinel = 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*/

};

static int mutablemapping_update_arg(PyObject*, PyObject*);

static PyObject *

odict_or(PyObject *left, PyObject *right)

{

PyTypeObject *type;

PyObject *other;

if (PyODict_Check(left)) {

type = Py_TYPE(left);

other = right;

}

else {

type = Py_TYPE(right);

other = left;

}

if (!PyDict_Check(other)) {

Py_RETURN_NOTIMPLEMENTED;

}

PyObject *new = PyObject_CallOneArg((PyObject*)type, left);

if (!new) {

return NULL;

}

if (mutablemapping_update_arg(new, right) < 0) {

Py_DECREF(new);

return NULL;

}

return new;

}

static PyObject *

odict_inplace_or(PyObject *self, PyObject *other)

{

if (mutablemapping_update_arg(self, other) < 0) {

return NULL;

}

Py_INCREF(self);

return self;

}

static PyNumberMethods odict_as_number = {

.nb_or = odict_or,

.nb_inplace_or = odict_inplace_or,

};

static PyObject *

OrderedDict_fromkeys_impl(PyTypeObject *type, PyObject *seq, PyObject *value)

{

return _PyDict_FromKeys((PyObject *)type, seq, value);

}

PyDoc_STRVAR(odict_sizeof__doc__, "");

static PyObject *

odict_sizeof(PyODictObject *od, PyObject *Py_UNUSED(ignored))

{

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

res += sizeof(_ODictNode *) * od->od_fast_nodes_size; /* 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, PyObject *Py_UNUSED(ignored))

{

PyObject *state, *result = NULL;

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

/* capture any instance state */

state = _PyObject_GetState((PyObject *)od);

if (state == NULL)

goto Done;

/* build the result */

args = PyTuple_New(0);

if (args == NULL)

goto Done;

items = PyObject_CallMethodNoArgs((PyObject *)od, &_Py_ID(items));

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, state, Py_None, items_iter);

Py_DECREF(items_iter);

Done:

Py_XDECREF(state);

Py_XDECREF(args);

return result;

}

static PyObject *

OrderedDict_setdefault_impl(PyODictObject *self, PyObject *key,

PyObject *default_value)

{