Commits

Eric Snow  committed 6bf1c9a

a little more meat on COrderedDict's bones

  • Participants
  • Parent commits eb406b0

Comments (0)

Files changed (3)

File .unstable/cordereddict/odictobject.c

-
 /*
  * A C implementation of collections.OrderedDict.
  */
 PyDoc_STRVAR(values__doc__,
 "D.values() -> an object providing a view on D's values");
 
+
+/*************
+ * odict keys
+ *************/
+
+static void
+_odict_get_key(ODictObject *od, PyObject *key)
+{
+    for (odictkey *node = od->keys; node != NULL; node = node->next)
+        if (PyObject_RichCompareBool(key, node->key) == Py_EQ)
+            return node;
+    return NULL;
+}
+
+static void
+_odict_add_key(ODictObject *od, PyObject *key)
+{
+    odictkey *node = (odictkey *)PyMem_Malloc(sizeof(odictkey));
+    /* XXX check for out-of-memory? */
+
+    node->key = key;
+    node->prev = od->last;
+    node->next = NULL;
+    if (od->keys == NULL)
+        od->keys = node;
+    else
+        od->last->next = node;
+    od->last = node;
+}
+
+static void
+_odict_remove_key(ODictObject *od, PyObject *key)
+{
+    odictkey *node = _odict_get_key(key);
+    if (node == NULL)
+        return;
+    if (node->prev != NULL)
+        node->prev->next = node->next;
+    if (node->next != NULL)
+        node->next->prev = node->prev;
+    Py_DECREF(node->key);
+    PyMem_Free((void *)node);
+}
+
+static void
+_odict_clear_keys(ODictObject *od)
+{
+    for (odictkey *node = od->keys; node != NULL; node = node->next) {
+        Py_DECREF(node->key);
+        if (node->prev != NULL)
+            PyMem_Free((void *)(node->prev));
+    }
+    if (od->last != NULL)
+        PyMem_Free((void *)(od->last));
+    od->last = NULL;
+    od->keys = NULL;
+}
+
+
 /***********************
  * odict implementation
  ***********************/
 
 /* tp_dealloc */
 static void
-odict_dealloc(PyObject *self)
+odict_dealloc(ODictObject *self)
 {
-    /* XXX not finished */
-    PyMem_DEL(self);
+    _odict_clear_keys(self);
+    /* XXX how to be more flexible? */
+    ODict_BASE(self)->tp_dealloc((PyDictObject *)self);
 };
 
 PyDoc_STRVAR(repr_doc, "od.__repr__() <==> repr(od)");
     return result;
 };
 
-/* mp_ass_subscript */
+/* mp_ass_subscript: __setitem__() and __delitem__() */
 static int
-odict_ass_sub(ODictObject *mp, PyObject *v, PyObject *w)
+odict_ass_sub(ODictObject *od, PyObject *v, PyObject *w)
 {
     if (w == NULL)
         return ODict_DelItem((PyObject *)mp, v);
         return ODict_SetItem((PyObject *)mp, v, w);
 }
 
+/* __sizeof__() */
 static PyObject *
-odict_sizeof(ODictObject *mp)
+odict_sizeof(ODictObject *od)
 {
-    /* XXX not finished */
     Py_ssize_t res;
 
-    res = sizeof(ODictObject);
-    if (mp->ma_table != mp->ma_smalltable)
-        res = res + (mp->ma_mask + 1) * sizeof(PyDictEntry);
+    /* XXX need to extract Py_ssize_t from PyLong... */
+    res = PyObject_CallFunctionObjArgs(ODict_BASE(od), "__sizeof__",
+                                     (PyObject*)od, NULL);
+    res += sizeof(odictkey*) * 2;  /* od->keys and od->last */
+    res += sizeof(odictkey) * (PyDictObject *)od->ma_keys;
     return PyLong_FromSsize_t(res);
 }
 
+/* setdefault() */
 static PyObject *
-odict_setdefault(register ODictObject *mp, PyObject *args)
+odict_setdefault(register ODictObject *od, PyObject *args)
 {
     /* XXX not finished */
+    PyTypeObject *base = Py_TYPE(od)->tp_base;
+    return PyObject_CallFunctionObjArgs((PyObject*)Py_TYPE(od), Py_None, od, NULL);
+
 }
 
+/* pop() */
 static PyObject *
-odict_pop(PyDictObject *mp, PyObject *args)
+odict_pop(PyDictObject *od, PyObject *args)
 {
-    /* XXX not finished */
+    _odict_remove_key(key);
+    /* XXX is this the right call? */
+    return PyObject_CallFunctionObjArgs(ODict_BASE(od), "pop", od, args, NULL);
 }
 
+/* popitem() */
 static PyObject *
-odict_popitem(ODictObject *mp)
+odict_popitem(ODictObject *od)
 {
+    PyObject *item = PyObject_CallFunctionObjArgs(ODict_BASE(od), "popitem",
+                                                  od, NULL);
     /* XXX not finished */
+    _odict_remove_key(key);
+    return item;
 }
 
+/* update() */
 static PyObject *
 odict_update(PyObject *self, PyObject *args, PyObject *kwds)
 {
     /* XXX not finished */
 }
 
+/* clear() */
 static PyObject *
-odict_fromkeys(PyObject *cls, PyObject *args)
+odict_clear(register ODictObject *od)
+{
+    if (PyObject_CallMethod(Py_TYPE(od)->tp_base, "clear", NULL) == NULL)
+        return -1;
+    _odict_clear_keys(od);
+    return 0;
+}
+
+/* copy() */
+static PyObject *
+odict_copy(register ODictObject *od)
+{
+    PyObject *od_copy = PyObject_Call((PyObject*)Py_TYPE(od), NULL);
+    if (od_copy == NULL)
+        return NULL;
+
+    for (odictkey *node = od->keys; node != NULL; node = node->next) {
+        PyObject *value = PyObject_GetItem(od, node->key);
+        if (value == NULL) {
+            Py_DECREF(od_copy);
+            return NULL;
+        }
+        Py_INCREF(key);
+        if (PyObject_SetItem((PyObject *)od, node->key, value) == -1) {
+            Py_DECREF(key);
+            Py_DECREF(value);
+            Py_DECREF(od_copy);
+            return NULL;
+        }
+    }
+    return od_copy;
+}
+
+/* __reversed__() */
+static PyObject *
+odict_reversed(register ODictObject *od)
+{
+    Py_ssize_t index = 0;
+    PyObject *reversed = PyList_New(((PyDictObject *)od)->ma_used);
+    if (reversed == NULL)
+        return NULL;
+    for (odictkey *node = od->last; node != NULL; node = node->prev) {
+        Py_INCREF(node->key);
+        if (PyList_SET_ITEM(reversed, index++, node->key) == -1) {
+            /* XXX do more? */
+            Py_DECREF(reversed);
+            return NULL;
+        }
+    }
+    return PyObject_GetIter(reversed);
+}
+
+/* __reduce__() */
+static PyObject *
+odict_reduce(register ODictObject *od)
 {
     /* XXX not finished */
 }
 
+/* move_to_end() */
 static PyObject *
-odict_clear(register ODictObject *mp)
+odict_move_to_end(ODictObject *od, PyObject *args)
 {
     /* XXX not finished */
 }
 
-static PyObject *
-odict_copy(register ODictObject *mp)
-{
-    /* XXX not finished */
-}
-
-static PyObject *
-odict_reversed(register ODictObject *mp)
-{
-    /* XXX not finished */
-}
-
-static PyObject *
-odict_reduce(register ODictObject *mp)
-{
-    /* XXX not finished */
-}
-
-static PyObject *
-odict_move_to_end(register ODictObject *mp, PyObject *args)
-{
-    /* XXX not finished */
-}
-
+/* keys() */
 odictkeys_new
 {
     /* XXX not finished */
 }
 
+/* items() */
 odictitems_new
 {
     /* XXX not finished */
 }
 
+/* values() */
 odictvalues_new
 {
     /* XXX not finished */
 }
 
-static int
-odict_tp_clear(PyObject *op)
-{
-    /* XXX not finished */
-};
-
+/* __eq__() */
 static int
 odict_equal(ODictObject *a, ODictObject *b)
 {
 static PyObject *
 odict_richcompare(PyObject *v, PyObject *w, int op)
 {
-    int cmp;
-    PyObject *res;
-
+    /* XXX allow for any mapping type... */
     if (!ODict_Check(v) || !PyDict_Check(w)) {
-        res = Py_NotImplemented;
+        Py_RETURN_NOTIMPLEMENTED;
     }
     else if (op == Py_EQ || op == Py_NE) {
-        if (ODict_Check(w)) {
-            cmp = odict_equal((ODictObject *)v, (ODictObject *)w);
-        }
-        else {
+        int cmp;
+        PyObject *res;
+
+        if (!ODict_Check(w))
             return PyDict_richcompare(v, w, op);
-            /* XXX if odict were in Objects/dictobject.c... */
-            /*
-            cmp = dict_equal((PyDictObject *)v, (PyDictObject *)w);
-            */
-        }
+
+        cmp = odict_equal((ODictObject *)v, (ODictObject *)w);
         if (cmp < 0)
             return NULL;
         res = (cmp == (op == Py_EQ)) ? Py_True : Py_False;
+        Py_INCREF(res);
+        return res;
     }
-    else
-        res = Py_NotImplemented;
-    Py_INCREF(res);
-    return res;
+    else {
+        Py_RETURN_NOTIMPLEMENTED;
+    }
 };
 
 /* tp_iter */
 static PyObject *
-dict_iter(ODictObject *dict)
+odict_iter(ODictObject *dict)
 {
     /* XXX not finished */
     return dictiter_new(dict, &PyDictIterKey_Type);
 };
 
-
-/* tp_new */
-static PyObject *
-odict_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
-{
-    /* XXX not finished */
-    PyObject *self;
-
-    assert(type != NULL && type->tp_alloc != NULL);
-    self = type->tp_alloc(type, 0);
-    if (self != NULL) {
-        PyDictObject *d = (PyDictObject *)self;
-        /* It's guaranteed that tp->alloc zeroed out the struct. */
-        assert(d->ma_table == NULL && d->ma_fill == 0 && d->ma_used == 0);
-        INIT_NONZERO_DICT_SLOTS(d);
-        d->ma_lookup = lookdict_unicode;
-        /* The object has been implicitly tracked by tp_alloc */
-        if (type == &PyDict_Type)
-            _PyObject_GC_UNTRACK(d);
-#ifdef SHOW_CONVERSION_COUNTS
-        ++created;
-#endif
-#ifdef SHOW_TRACK_COUNT
-        if (_PyObject_GC_IS_TRACKED(d))
-            count_tracked++;
-        else
-            count_untracked++;
-#endif
-    }
-    return self;
-};
-
 /* tp_init */
 static int
 odict_init(PyObject *self, PyObject *args, PyObject *kwds)
 {
-    /* XXX not finished */
-    return dict_update_common(self, args, kwds, "dict");
+    return odict_update(self, args, kwds);
 };
 
 /* Forward */
  * PyTypeObject extras
  ***********************/
 
-/* methods inherited from dict:
- *
- * __contains__()
- * __getitem__()
- * get()
- *
- */
-
 /* tp_methods */
 static PyMethodDef odict_methods[] = {
 
      values__doc__},
     {"update",          (PyCFunction)ODict_update,      METH_VARARGS | METH_KEYWORDS,
      update__doc__},
-    {"fromkeys",        (PyCFunction)ODict_fromkeys,    METH_VARARGS | METH_CLASS,
-     fromkeys__doc__},
     {"clear",           (PyCFunction)ODict_clear,       METH_NOARGS,
      clear__doc__},
     {"copy",            (PyCFunction)ODict_copy,        METH_NOARGS,
 
 /* tp_as_mapping */
 static PyMappingMethods ODict_as_mapping = {
-    /* XXX don't these need to be set? */
+    /* XXX don't these need to be set? inherited? */
     0, /*(lenfunc)dict_length,*/        /*mp_length*/
     0, /*(binaryfunc)dict_subscript,*/  /*mp_subscript*/
     (objobjargproc)odict_ass_sub,       /*mp_ass_subscript*/
  * public API
  ***********************/
 
-/* methods in collections.OrderedDict:
+/*
+
+methods inherited from dict:
  *
+ * fromkeys (classmethod)
+ * __contains__
+ * __getitem__
+ * __len__
+ * __new__
+ * get
+
+methods in collections.OrderedDict:
+ * __eq__           tp_richcompare
  * __init__         tp_init
+ * __iter__         tp_iter
+ * __repr__         tp_repr
+ * __delitem__      tp_as_mapping (mp_ass_subscript)
  * __setitem__      tp_as_mapping (mp_ass_subscript)
- * __delitem_       tp_as_mapping (mp_ass_subscript)
- * __iter__         tp_iter
+
+ * __sizeof__       tp_methods ("__sizeof__")
+ * __reduce__       #####
+ * clear            #####
+ * pop              #####
+ * popitem          #####
+ * setdefault       #####
+ * copy             #####
+ * fromkeys(cls)    #####
+
  * __reversed__     #####
- * clear            #####
- * popitem          #####
  * move_to_end      #####
- * __sizeof__       tp_methods ("__sizeof__")
- * pop              #####
- * setdefault       #####
- * __repr__         tp_repr
- * __reduce__       #####
- * copy             #####
- * fromkeys         #####
- * __eq__           tp_richcompare
- *
- * (from MutableMapping)
+
+(from MutableMapping)
+ * __ne__           tp_richcompare
+ * items            #####
+ * keys             #####
  * update           #####
- * keys             #####
  * values           #####
- * items            #####
- * __ne__           tp_richcompare
+
  */
 
 static PyTypeObject ODict_Type = {
-    PyObject_HEAD_INIT(&PyType_Type)
+    PyVarObject_HEAD_INIT(&PyType_Type, 0)
     0,
     "OrderedDict",                  /* tp_name */
     sizeof(ODictObject),            /* tp_basicsize */  /* XXX different? */
     0,                              /* tp_flags */
     odict_doc,                      /* tp_doc */
     0,                              /* tp_traverse */
-    odict_tp_clear,                 /* tp_clear */
+    0,                              /* tp_clear */
     odict_richcompare               /* tp_richcompare */
     0,                              /* tp_weaklistoffset */
     (getiterfunco)odict_iter,       /* tp_iter */
     0,                              /* tp_dictoffset */
     odict_init,                     /* tp_init */
     0,                              /* tp_alloc */
-    odict_new,                      /* tp_new */
+    0,                              /* tp_new */
     0,                              /* tp_free */
 };
 
     return odict_new(&ODict_Type, NULL, NULL);
 };
 
-PyAPI_FUNC(int) ODict_SetItem(PyObject *mp, PyObject *key, PyObject *item) {
+PyAPI_FUNC(int) ODict_SetItem(PyObject *od, PyObject *key, PyObject *item) {
     /* XXX not finished */
 };
 
-PyAPI_FUNC(int) ODict_DelItem(PyObject *mp, PyObject *key) {
+PyAPI_FUNC(int) ODict_DelItem(PyObject *od, PyObject *key) {
     /* XXX not finished */
 };
 
-PyAPI_FUNC(void) ODict_Clear(PyObject *mp) {
+PyAPI_FUNC(void) ODict_Clear(PyObject *od) {
     /* XXX not finished */
 };
 
 PyAPI_FUNC(int) ODict_Next(
-    PyObject *mp, Py_ssize_t *pos, PyObject **key, PyObject **value) {
+    PyObject *od, Py_ssize_t *pos, PyObject **key, PyObject **value) {
     /* XXX not finished */
 };
 
-PyAPI_FUNC(PyObject *) ODict_Keys(PyObject *mp) {
+PyAPI_FUNC(PyObject *) ODict_Keys(PyObject *od) {
     /* XXX not finished */
 };
 
-PyAPI_FUNC(PyObject *) ODict_Values(PyObject *mp) {
+PyAPI_FUNC(PyObject *) ODict_Values(PyObject *od) {
     /* XXX not finished */
 };
 
-PyAPI_FUNC(PyObject *) ODict_Items(PyObject *mp) {
+PyAPI_FUNC(PyObject *) ODict_Items(PyObject *od) {
     /* XXX not finished */
 };
 
-PyAPI_FUNC(Py_ssize_t) ODict_Size(PyObject *mp) {
+PyAPI_FUNC(Py_ssize_t) ODict_Size(PyObject *od) {
     /* XXX not finished */
 };
 
-PyAPI_FUNC(PyObject *) ODict_Copy(PyObject *mp) {
+PyAPI_FUNC(PyObject *) ODict_Copy(PyObject *od) {
     /* XXX not finished */
 };
 
-PyAPI_FUNC(int) ODict_Update(PyObject *mp, PyObject *other) {
+PyAPI_FUNC(int) ODict_Update(PyObject *od, PyObject *other) {
     /* XXX not finished */
 };
 
-PyAPI_FUNC(int) ODict_Merge(PyObject *mp,
+PyAPI_FUNC(int) ODict_Merge(PyObject *od,
                             PyObject *other,
                             int override) {
     /* XXX not finished */

File .unstable/cordereddict/odictobject.h

 
 #ifndef Py_LIMITED_API
 
+typedef struct {
+    PyObject *key;
+    odictkey *next;
+    odictkey *prev;
+} odictkey;
+
 typedef struct _odictobject ODictObject;
 struct _odictobject {
-    /* XXX not finished */
     PyDictObject dict;
-    long value;
+    odictkey *keys;
+    odictkey *last;
 };
 
 /* XXX Are these needed? */
 //PyAPI_FUNC(PyObject *) _PyDict_NewPresized(Py_ssize_t minused);
 //PyAPI_FUNC(int) PyDict_ClearFreeList(void);
 
+#define ODict_BASE(op) ((PyObject*)(Py_TYPE(op)->tp_base))
+
 #endif
 
 /***********************

File .unstable/cordereddict/ordereddict.c

-
 /*
  * A simple module providing a C implementation of OrderedDict.
  */
         Py_DECREF(&ODict_Type);
         goto fail;
     }
-    
+
     return module;
 fail:
     Py_DECREF(module);