+/* -*-c-*-
+ *
+ * $Id$
+ *
+ * Double-ended arrays
+ *
+ * (c) 2005 Straylight/Edgeware
+ */
+
+/*----- Licensing notice --------------------------------------------------*
+ *
+ * This file is part of the Python interface to mLib.
+ *
+ * mLib/Python is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * mLib/Python is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with mLib/Python; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include <Python.h>
+
+#include <string.h>
+
+#include <mLib/darray.h>
+#include <mLib/dstr.h>
+#include <mLib/exc.h>
+
+#include "grim.h"
+
+/*----- Data structures ---------------------------------------------------*/
+
+DA_DECL(obj_v, PyObject *);
+
+typedef struct da_pyobj {
+ PyObject_HEAD
+ obj_v v;
+} da_pyobj;
+#define DA_PYCHECK(o) PyObject_TypeCheck((o), &da_pytype)
+#define DA_V(o) (&((da_pyobj *)(o))->v)
+
+typedef struct daiter_pyobj {
+ PyObject_HEAD
+ PyObject *da;
+ size_t i;
+} daiter_pyobj;
+#define DAITER_DA(obj) (((daiter_pyobj *)(obj))->da)
+#define DAITER_V(obj) DA_V(DAITER_DA(obj))
+#define DAITER_I(obj) (((daiter_pyobj *)(obj))->i)
+
+static PyTypeObject da_pytype, daiter_pytype;
+
+static int getseq(PyObject **pseq, PyObject ***v, size_t *n)
+{
+ PyObject *seq = *pseq;
+
+ if (!seq || seq == Py_None) {
+ *v = 0;
+ *n = 0;
+ *pseq = 0;
+ } else if (DA_PYCHECK(seq)) {
+ *v = DA(DA_V(seq));
+ *n = DA_LEN(DA_V(seq));
+ Py_INCREF(seq);
+ } else if ((seq = PySequence_Fast(seq, "expected iterable")) == 0)
+ return (-1);
+ else {
+ *pseq = seq;
+ *v = PySequence_Fast_ITEMS(seq);
+ *n = PySequence_Fast_GET_SIZE(seq);
+ }
+ return (0);
+}
+
+static void range_inc(PyObject **v, PyObject **vl)
+ { while (v < vl) { Py_INCREF(*v); v++; } }
+static void range_dec(PyObject **v, PyObject **vl)
+ { if (v) { while (v < vl) { Py_DECREF(*v); v++; } } }
+static void range_copy(PyObject ***gv, PyObject ***gvl)
+{
+ size_t n = *gvl - *gv;
+ size_t sz = sizeof(PyObject *) * n;
+ PyObject **v;
+ if (!n) { *gv = *gvl = 0; return; }
+ v = xmalloc(sz);
+ memcpy(v, *gv, sz);
+ *gv = v;
+ *gvl = v + n;
+}
+
+static PyObject *abstract_pynew(PyTypeObject *ty,
+ PyObject *hunoz, PyObject *hukairz)
+{
+ PyErr_SetString(PyExc_TypeError, "can't instantiate this type");
+ return (0);
+}
+
+/*----- Iterator ----------------------------------------------------------*/
+
+static PyObject *daiter_pynext(PyObject *me)
+{
+ PyObject *x;
+
+ if (DAITER_I(me) >= DA_LEN(DAITER_V(me))) return (0);
+ x = DA(DAITER_V(me))[DAITER_I(me)]; DAITER_I(me)++; RETURN_OBJ(x);
+}
+
+static void daiter_pydealloc(PyObject *me)
+ { Py_DECREF(DAITER_DA(me)); PyObject_DEL(me); }
+
+static PyTypeObject daiter_pytype = {
+ PyObject_HEAD_INIT(0) 0, /* Header */
+ "array.ArrayIter", /* @tp_name@ */
+ sizeof(daiter_pyobj), /* @tp_basicsize@ */
+ 0, /* @tp_itemsize@ */
+
+ daiter_pydealloc, /* @tp_dealloc@ */
+ 0, /* @tp_print@ */
+ 0, /* @tp_getattr@ */
+ 0, /* @tp_setattr@ */
+ 0, /* @tp_compare@ */
+ 0, /* @tp_repr@ */
+ 0, /* @tp_as_number@ */
+ 0, /* @tp_as_sequence@ */
+ 0, /* @tp_as_mapping@ */
+ 0, /* @tp_hash@ */
+ 0, /* @tp_call@ */
+ 0, /* @tp_str@ */
+ 0, /* @tp_getattro@ */
+ 0, /* @tp_setattro@ */
+ 0, /* @tp_as_buffer@ */
+ Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
+ Py_TPFLAGS_BASETYPE,
+
+ /* @tp_doc@ */
+"Array iterator.",
+
+ 0, /* @tp_traverse@ */
+ 0, /* @tp_clear@ */
+ 0, /* @tp_richcompare@ */
+ 0, /* @tp_weaklistoffset@ */
+ PyObject_SelfIter, /* @tp_iter@ */
+ daiter_pynext, /* @tp_iternexr@ */
+ 0, /* @tp_methods@ */
+ 0, /* @tp_members@ */
+ 0, /* @tp_getset@ */
+ 0, /* @tp_base@ */
+ 0, /* @tp_dict@ */
+ 0, /* @tp_descr_get@ */
+ 0, /* @tp_descr_set@ */
+ 0, /* @tp_dictoffset@ */
+ 0, /* @tp_init@ */
+ PyType_GenericAlloc, /* @tp_alloc@ */
+ abstract_pynew, /* @tp_new@ */
+ 0, /* @tp_free@ */
+ 0 /* @tp_is_gc@ */
+};
+
+/*----- Main array code ---------------------------------------------------*/
+
+static void da_doinsert(PyObject *me, PyObject **items, size_t n,
+ size_t start, size_t end)
+{
+ PyObject **v, **gv, **gvl;
+ obj_v *da = DA_V(me);
+ size_t off, ne;
+
+ ne = end - start;
+ v = DA(da);
+ gv = v + start; gvl = v + end; range_copy(&gv, &gvl);
+ if (start < DA_LEN(da) - end) {
+ if (n > ne) {
+ off = n - ne;
+ DA_SHUNT(da, off);
+ DA_UNSAFE_SLIDE(da, off);
+ memmove(v, v + off, sizeof(PyObject *) * start);
+ } else {
+ off = ne - n;
+ memmove(v + off, v, sizeof(PyObject *) * start);
+ DA_UNSAFE_UNSLIDE(da, off);
+ }
+ } else {
+ if (n > ne) {
+ off = n - ne;
+ DA_ENSURE(da, off);
+ memmove(v + end + off, v + end,
+ sizeof(PyObject *) * (DA_LEN(da) - end));
+ } else {
+ off = ne - n;
+ memmove(v + end - off, v + end,
+ sizeof(PyObject *) * (DA_LEN(da) - end));
+ DA_UNSAFE_SHRINK(da, off);
+ }
+ DA_UNSAFE_EXTEND(da, off);
+ }
+
+ if (n) {
+ v = DA(da) + start;
+ memcpy(v, items, sizeof(PyObject *) * n);
+ range_inc(v, v + n);
+ }
+ if (gv) {
+ range_dec(gv, gvl);
+ xfree(gv);
+ }
+}
+
+static int da_insert(PyObject *me, PyObject *seq, int start, int end)
+{
+ PyObject **items;
+ size_t n;
+
+ if (0 > start || start > end || end > DA_LEN(DA_V(me))) {
+ PyErr_SetString(PyExc_IndexError, "bad slice");
+ return (-1);
+ }
+ if (getseq(&seq, &items, &n)) return (-1);
+ da_doinsert(me, items, n, start, end);
+ Py_XDECREF(seq);
+ return (0);
+}
+
+static PyObject *da_new(PyTypeObject *ty)
+{
+ da_pyobj *me = (da_pyobj *)ty->tp_alloc(ty, 0);
+ DA_CREATE(&me->v);
+ return ((PyObject *)me);
+}
+
+static PyObject *da_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
+ { return (da_new(ty)); }
+static int da_pyinit(PyObject *me, PyObject *arg, PyObject *kw)
+{
+ PyObject *init = 0;
+ static char *kwlist[] = { "sequence", 0 };
+
+ if (!PyArg_ParseTupleAndKeywords(arg, kw, "|O:new", kwlist, &init) ||
+ (init && da_insert((PyObject *)me, init, 0, 0)))
+ return (-1);
+ return (0);
+}
+
+static void da_pydealloc(PyObject *me)
+{
+ size_t i;
+ PyObject **v = DA(DA_V(me));
+ size_t n = DA_LEN(DA_V(me));
+
+ for (i = 0; i < n; i++) Py_DECREF(v[i]);
+ DA_DESTROY(DA_V(me));
+}
+
+static int da_pylength(PyObject *me)
+ { return (DA_LEN(DA_V(me))); }
+
+static int da_pytraverse(PyObject *me, visitproc proc, void *arg)
+{
+ size_t i;
+ PyObject **v = DA(DA_V(me));
+ size_t n = DA_LEN(DA_V(me));
+ int err;
+
+ for (i = 0; i < n; i++) {
+ if ((err = proc(v[i], arg)) != 0)
+ return (err);
+ }
+ return (0);
+}
+
+static int da_pyclear(PyObject *me)
+{
+ range_dec(DA(DA_V(me)), DA(DA_V(me)) + DA_LEN(DA_V(me)));
+ DA_RESET(DA_V(me));
+ return (0);
+}
+
+static PyObject *da_pyconcat(PyObject *me, PyObject *other)
+{
+ PyObject *x = da_new(&da_pytype);
+ PyObject **items = DA(DA_V(me));
+ size_t n = DA_LEN(DA_V(me));
+
+ da_doinsert(x, items, n, 0, 0);
+ if (da_insert(x, other, n, n)) {
+ Py_DECREF(x);
+ return (0);
+ }
+ return (x);
+}
+
+static PyObject *da_pyrepeat(PyObject *me, int times)
+{
+ PyObject *x = da_new(&da_pytype);
+ PyObject **items = DA(DA_V(me)), **dest;
+ size_t n = DA_LEN(DA_V(me));
+ int i;
+
+ DA_ENSURE(DA_V(x), n * times);
+ DA_UNSAFE_EXTEND(DA_V(x), n * times);
+ for (i = 0, dest = DA(DA_V(x)); i < times; i++, dest += n)
+ memcpy(dest, items, n * sizeof(PyObject *));
+ range_inc(DA(DA_V(x)), DA(DA_V(x)) + n * times);
+ return (x);
+}
+
+static PyObject *da_pygetitem(PyObject *me, int i)
+{
+ PyObject *o;
+
+ if (i < 0 || i >= DA_LEN(DA_V(me))) {
+ PyErr_SetString(PyExc_IndexError, "index out of range");
+ return (0);
+ }
+ o = DA(DA_V(me))[i];
+ Py_INCREF(o);
+ return (o);
+}
+
+static PyObject *da_pygetslice(PyObject *me, int i, int j)
+{
+ PyObject *x;
+
+ if (i < 0 || j < i || DA_LEN(DA_V(me)) < j) {
+ PyErr_SetString(PyExc_IndexError, "bad slice");
+ return (0);
+ }
+ x = da_new(&da_pytype);
+ da_doinsert(x, DA(DA_V(me)) + i, j - i, 0, 0);
+ return (x);
+}
+
+static int da_pyputitem(PyObject *me, int i, PyObject *x)
+{
+ PyObject **p;
+
+ if (i < 0 || i >= DA_LEN(DA_V(me))) {
+ PyErr_SetString(PyExc_IndexError, "index out of range");
+ return (-1);
+ }
+ p = DA(DA_V(me)) + i;
+ Py_DECREF(*p);
+ *p = x;
+ Py_INCREF(*p);
+ return (0);
+}
+
+static int da_pyputslice(PyObject *me, int i, int j, PyObject *x)
+ { return (da_insert(me, x, i, j)); }
+
+static int da_pycontainsp(PyObject *me, PyObject *x)
+{
+ PyObject **items = DA(DA_V(me));
+ size_t n = DA_LEN(DA_V(me));
+ size_t i;
+ int rc;
+
+ for (i = 0; i < n; i++) {
+ if (PyObject_Cmp(items[i], x, &rc))
+ return (-1);
+ if (rc)
+ return (1);
+ }
+ return (0);
+}
+
+static PyObject *da_pyrepr(PyObject *me)
+{
+ dstr d = DSTR_INIT;
+ PyObject *s, *rc = 0;
+ char *p;
+ int n;
+ size_t i;
+
+ dstr_puts(&d, "Array([");
+ for (i = 0; i < DA_LEN(DA_V(me)); i++) {
+ if ((s = PyObject_Repr(DA(DA_V(me))[i])) == 0 ||
+ PyString_AsStringAndSize(s, &p, &n)) {
+ Py_XDECREF(s);
+ goto done;
+ }
+ if (i) dstr_puts(&d, ", ");
+ dstr_putm(&d, p, n);
+ Py_DECREF(s);
+ }
+ dstr_puts(&d, "])");
+ rc = PyString_FromStringAndSize(d.buf, d.len);
+done:
+ dstr_destroy(&d);
+ return (rc);
+}
+
+static PyObject *da_pyappend(PyObject *me, PyObject *seq)
+{
+ size_t n = DA_LEN(DA_V(me));
+ if (da_insert(me, seq, n, n)) return (0);
+ RETURN_ME;
+}
+
+static PyObject *da_pyiprepeat(PyObject *me, int times)
+{
+ PyObject **items, **dest;
+ size_t n = DA_LEN(DA_V(me));
+ int i;
+
+ if (times < 0) {
+ PyErr_SetString(PyExc_ValueError, "multiplier must be nonnegative");
+ return (0);
+ }
+ if (!times) {
+ items = DA(DA_V(me));
+ range_dec(items, items + n);
+ DA_RESET(DA_V(me));
+ RETURN_ME;
+ }
+ times--;
+ DA_ENSURE(DA_V(me), n * times);
+ items = DA(DA_V(me));
+ for (i = 0, dest = items + n; i < times; i++, dest += n)
+ memcpy(dest, items, n * sizeof(PyObject *));
+ range_inc(items + n, dest);
+ DA_UNSAFE_EXTEND(DA_V(me), n * times);
+ RETURN_ME;
+}
+
+static PyObject *da_pyget(PyObject *me, PyObject *index)
+{
+ if (PySlice_Check(index)) {
+ int start, stop, step, len;
+ PyObject *v;
+ PyObject **ww;
+ PyObject **vv;
+
+ if (PySlice_GetIndicesEx((PySliceObject *)index, DA_LEN(DA_V(me)),
+ &start, &stop, &step, &len))
+ return (0);
+ if (step == 1) return (da_pygetslice(me, start, stop));
+ v = da_new(&da_pytype);
+ DA_ENSURE(DA_V(v), len);
+ vv = DA(DA_V(v));
+ ww = DA(DA_V(me)) + start;
+ DA_UNSAFE_EXTEND(DA_V(v), len);
+ while (len) {
+ *vv = *ww;
+ Py_INCREF(*vv);
+ vv++; ww += step; len--;
+ }
+ return ((PyObject *)v);
+ } else {
+ int i;
+
+ if ((i = PyInt_AsLong(index)) == -1 && PyErr_Occurred()) return (0);
+ return (da_pygetitem(me, i));
+ }
+}
+
+static int da_pyput(PyObject *me, PyObject *index, PyObject *x)
+{
+ if (PySlice_Check(index)) {
+ int start, stop, step, len;
+ size_t n;
+ PyObject **ww;
+ PyObject **vv;
+ PyObject **g, **gg;
+
+ if (PySlice_GetIndicesEx((PySliceObject *)index, DA_LEN(DA_V(me)),
+ &start, &stop, &step, &len))
+ return (-1);
+ if (step == 1) return (da_insert(me, x, start, stop));
+ if (getseq(&x, &vv, &n)) return (-1);
+ if (n != len) {
+ PyErr_SetString(PyExc_ValueError, "wrong number of items");
+ Py_XDECREF(x);
+ return (-1);
+ }
+ g = gg = xmalloc(len * sizeof(PyObject *));
+ ww = DA(DA_V(me)) + start;
+ while (len) {
+ *gg++ = *ww; *ww = *vv++;
+ Py_INCREF(*ww);
+ ww += step; len--;
+ }
+ range_dec(g, gg);
+ xfree(g);
+ Py_XDECREF(x);
+ return (0);
+ } else {
+ int i;
+
+ if ((i = PyInt_AsLong(index)) == -1 && PyErr_Occurred()) return (-1);
+ return (da_pyputitem(me, i, x));
+ }
+}
+
+static PyObject *da_pyiter(PyObject *me)
+{
+ daiter_pyobj *i = PyObject_NEW(daiter_pyobj, &daiter_pytype);
+ i->da = me; Py_INCREF(me);
+ i->i = 0;
+ return ((PyObject *)i);
+}
+
+static PyObject *dameth_push(PyObject *me, PyObject *arg)
+{
+ PyObject *x;
+
+ if (!PyArg_ParseTuple(arg, "O:push", &x)) return (0);
+ Py_INCREF(x);
+ DA_PUSH(DA_V(me), x);
+ RETURN_ME;
+}
+
+static PyObject *dameth_pop(PyObject *me, PyObject *arg)
+{
+ PyObject *x;
+
+ if (!PyArg_ParseTuple(arg, ":pop")) return (0);
+ TRY
+ x = DA_POP(DA_V(me));
+ CATCH switch (exc_type) {
+ case DAEXC_UFLOW:
+ PyErr_SetString(PyExc_ValueError, "stack underflow");
+ return (0);
+ default:
+ RETHROW;
+ } END_TRY;
+ RETURN_OBJ(x);
+}
+
+static PyObject *dameth_unshift(PyObject *me, PyObject *arg)
+{
+ PyObject *x;
+
+ if (!PyArg_ParseTuple(arg, "O:unshift", &x)) return (0);
+ Py_INCREF(x);
+ DA_UNSHIFT(DA_V(me), x);
+ RETURN_ME;
+}
+
+static PyObject *dameth_shift(PyObject *me, PyObject *arg)
+{
+ PyObject *x;
+
+ if (!PyArg_ParseTuple(arg, ":shift")) return (0);
+ TRY
+ x = DA_SHIFT(DA_V(me));
+ CATCH switch (exc_type) {
+ case DAEXC_UFLOW:
+ PyErr_SetString(PyExc_ValueError, "stack underflow");
+ return (0);
+ default:
+ RETHROW;
+ } END_TRY;
+ RETURN_OBJ(x);
+}
+
+static PyObject *dameth_tidy(PyObject *me, PyObject *arg)
+{
+ if (!PyArg_ParseTuple(arg, ":tidy")) return (0);
+ DA_TIDY(DA_V(me));
+ RETURN_ME;
+}
+
+static PyMethodDef da_pymethods[] = {
+#define METHNAME(func) dameth_##func
+ METH (push, "A.push(X): [A, B, ..., W], X -> [A, B, ..., W, X]")
+ METH (pop, "A.pop() -> X: [A, B, ..., W, X] -> [A, B, ..., W]")
+ METH (unshift, "A.unshift(X): [A, B, ..., W], X -> [X, A, ..., W]")
+ METH (shift, "A.shift() -> X: [X, A, ..., W] -> [A, ..., W], X")
+ METH (tidy, "A.tidy()")
+#undef METHNAME
+ { 0 }
+};
+
+static PySequenceMethods da_pysequence = {
+ da_pylength, /* @sq_length@ */
+ da_pyconcat, /* @sq_concat@ */
+ da_pyrepeat, /* @sq_repeat@ */
+ da_pygetitem, /* @sq_item@ */
+ da_pygetslice, /* @sq_slice@ */
+ da_pyputitem, /* @sq_ass_item@ */
+ da_pyputslice, /* @sq_ass_slice@ */
+ da_pycontainsp, /* @sq_contains@ */
+ da_pyappend, /* @sq_inplace_concat@ */
+ da_pyiprepeat /* @sq_inplace_repeat@ */
+};
+
+static PyMappingMethods da_pymapping = {
+ da_pylength, /* @mp_length@ */
+ da_pyget, /* @mp_subscript@ */
+ da_pyput /* @mp_ass_subscript@ */
+};
+
+static PyTypeObject da_pytype = {
+ PyObject_HEAD_INIT(0) 0, /* Header */
+ "array.Array", /* @tp_name@ */
+ sizeof(da_pyobj), /* @tp_basicsize@ */
+ 0, /* @tp_itemsize@ */
+
+ da_pydealloc, /* @tp_dealloc@ */
+ 0, /* @tp_print@ */
+ 0, /* @tp_getattr@ */
+ 0, /* @tp_setattr@ */
+ 0, /* @tp_compare@ */
+ da_pyrepr, /* @tp_repr@ */
+ 0, /* @tp_as_number@ */
+ &da_pysequence, /* @tp_as_sequence@ */
+ &da_pymapping, /* @tp_as_mapping@ */
+ 0, /* @tp_hash@ */
+ 0, /* @tp_call@ */
+ &da_pyrepr, /* @tp_str@ */
+ 0, /* @tp_getattro@ */
+ 0, /* @tp_setattro@ */
+ 0, /* @tp_as_buffer@ */
+ Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
+ Py_TPFLAGS_HAVE_GC,
+
+ /* @tp_doc@ */
+"Double-ended array type.",
+
+ da_pytraverse, /* @tp_traverse@ */
+ da_pyclear, /* @tp_clear@ */
+ 0, /* @tp_richcompare@ */
+ 0, /* @tp_weaklistoffset@ */
+ da_pyiter, /* @tp_iter@ */
+ 0, /* @tp_iternext@ */
+ da_pymethods, /* @tp_methods@ */
+ 0, /* @tp_members@ */
+ 0, /* @tp_getset@ */
+ 0, /* @tp_base@ */
+ 0, /* @tp_dict@ */
+ 0, /* @tp_descr_get@ */
+ 0, /* @tp_descr_set@ */
+ 0, /* @tp_dictoffset@ */
+ da_pyinit, /* @tp_init@ */
+ PyType_GenericAlloc, /* @tp_alloc@ */
+ da_pynew, /* @tp_new@ */
+ 0, /* @tp_free@ */
+ 0 /* @tp_is_gc@ */
+};
+
+/*----- Initialization ----------------------------------------------------*/
+
+static PyMethodDef emptymethods[] = { { 0 } };
+
+void initarray(void)
+{
+ PyObject *mod = Py_InitModule("array", emptymethods);
+ PyType_Ready(&da_pytype); PyType_Ready(&daiter_pytype);
+ PyModule_AddObject(mod, "Array", (PyObject *)&da_pytype);
+ PyModule_AddObject(mod, "ArrayIter", (PyObject *)&daiter_pytype);
+}
+
+/*----- That's all, folks -------------------------------------------------*/
~mdw / mLib-python / commitdiff