[mLib-python] / array.c

/* -*-c-*-
 *
 * 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 "array.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 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); }

PyTypeObject daiter_pytype = {
  PyObject_HEAD_INIT(0) 0,		/* Header */
  "mLib.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@ */
};

PyTypeObject da_pytype = {
  PyObject_HEAD_INIT(0) 0,		/* Header */
  "mLib.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 ----------------------------------------------------*/

void da_pysetup(void)
  { PyType_Ready(&da_pytype); PyType_Ready(&daiter_pytype); }

/*----- That's all, folks -------------------------------------------------*/
Commit	Line	Data
20bce5e9	1	/* --c--
20bce5e9	2	*
	3	* Double-ended arrays
	4	*
	5	* (c) 2005 Straylight/Edgeware
	6	*/
	7
d8d81d1b	8	/----- Licensing notice --------------------------------------------------
20bce5e9	9	*
	10	* This file is part of the Python interface to mLib.
	11	*
	12	* mLib/Python is free software; you can redistribute it and/or modify
	13	* it under the terms of the GNU General Public License as published by
	14	* the Free Software Foundation; either version 2 of the License, or
	15	* (at your option) any later version.
d8d81d1b	16	*
20bce5e9	17	* mLib/Python is distributed in the hope that it will be useful,
	18	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	19	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	20	* GNU General Public License for more details.
d8d81d1b	21	*
20bce5e9	22	* You should have received a copy of the GNU General Public License
	23	* along with mLib/Python; if not, write to the Free Software Foundation,
	24	* Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
	25	*/
	26
	27	/----- Header files ------------------------------------------------------/
	28
	29	#include <Python.h>
	30
	31	#include <string.h>
	32
	33	#include <mLib/darray.h>
	34	#include <mLib/dstr.h>
	35	#include <mLib/exc.h>
	36
579d0169	37	#include "array.h"
20bce5e9	38	#include "grim.h"
	39
	40	/----- Data structures ---------------------------------------------------/
	41
	42	DA_DECL(obj_v, PyObject *);
	43
	44	typedef struct da_pyobj {
	45	PyObject_HEAD
	46	obj_v v;
	47	} da_pyobj;
	48	#define DA_PYCHECK(o) PyObject_TypeCheck((o), &da_pytype)
	49	#define DA_V(o) (&((da_pyobj *)(o))->v)
	50
	51	typedef struct daiter_pyobj {
	52	PyObject_HEAD
	53	PyObject *da;
	54	size_t i;
	55	} daiter_pyobj;
	56	#define DAITER_DA(obj) (((daiter_pyobj *)(obj))->da)
	57	#define DAITER_V(obj) DA_V(DAITER_DA(obj))
	58	#define DAITER_I(obj) (((daiter_pyobj *)(obj))->i)
	59
20bce5e9	60	static int getseq(PyObject pseq, PyObject v, size_t n)
	61	{
	62	PyObject seq = pseq;
	63
	64	if (!seq \|\| seq == Py_None) {
	65	*v = 0;
	66	*n = 0;
	67	*pseq = 0;
	68	} else if (DA_PYCHECK(seq)) {
	69	*v = DA(DA_V(seq));
	70	*n = DA_LEN(DA_V(seq));
	71	Py_INCREF(seq);
	72	} else if ((seq = PySequence_Fast(seq, "expected iterable")) == 0)
	73	return (-1);
	74	else {
	75	*pseq = seq;
	76	*v = PySequence_Fast_ITEMS(seq);
	77	*n = PySequence_Fast_GET_SIZE(seq);
	78	}
	79	return (0);
	80	}
	81
	82	static void range_inc(PyObject v, PyObject vl)
	83	{ while (v < vl) { Py_INCREF(*v); v++; } }
	84	static void range_dec(PyObject v, PyObject vl)
	85	{ if (v) { while (v < vl) { Py_DECREF(*v); v++; } } }
	86	static void range_copy(PyObject *gv, PyObject *gvl)
	87	{
	88	size_t n = gvl - gv;
	89	size_t sz = sizeof(PyObject ) n;
	90	PyObject **v;
	91	if (!n) { gv = gvl = 0; return; }
	92	v = xmalloc(sz);
	93	memcpy(v, *gv, sz);
	94	*gv = v;
	95	*gvl = v + n;
	96	}
	97
	98	static PyObject abstract_pynew(PyTypeObject ty,
	99	PyObject hunoz, PyObject hukairz)
	100	{
	101	PyErr_SetString(PyExc_TypeError, "can't instantiate this type");
	102	return (0);
	103	}
	104
	105	/----- Iterator ----------------------------------------------------------/
	106
	107	static PyObject daiter_pynext(PyObject me)
	108	{
	109	PyObject *x;
	110
	111	if (DAITER_I(me) >= DA_LEN(DAITER_V(me))) return (0);
	112	x = DA(DAITER_V(me))[DAITER_I(me)]; DAITER_I(me)++; RETURN_OBJ(x);
	113	}
	114
	115	static void daiter_pydealloc(PyObject *me)
	116	{ Py_DECREF(DAITER_DA(me)); PyObject_DEL(me); }
	117
579d0169	118	PyTypeObject daiter_pytype = {
20bce5e9	119	PyObject_HEAD_INIT(0) 0, /* Header */
3655f952	120	"mLib.ArrayIter", /* @tp_name@ */
20bce5e9	121	sizeof(daiter_pyobj), /* @tp_basicsize@ */
	122	0, /* @tp_itemsize@ */
	123
	124	daiter_pydealloc, /* @tp_dealloc@ */
	125	0, /* @tp_print@ */
	126	0, /* @tp_getattr@ */
	127	0, /* @tp_setattr@ */
	128	0, /* @tp_compare@ */
	129	0, /* @tp_repr@ */
	130	0, /* @tp_as_number@ */
	131	0, /* @tp_as_sequence@ */
	132	0, /* @tp_as_mapping@ */
	133	0, /* @tp_hash@ */
	134	0, /* @tp_call@ */
	135	0, /* @tp_str@ */
	136	0, /* @tp_getattro@ */
	137	0, /* @tp_setattro@ */
	138	0, /* @tp_as_buffer@ */
	139	Py_TPFLAGS_DEFAULT \| /* @tp_flags@ */
	140	Py_TPFLAGS_BASETYPE,
	141
	142	/* @tp_doc@ */
	143	"Array iterator.",
	144
	145	0, /* @tp_traverse@ */
	146	0, /* @tp_clear@ */
	147	0, /* @tp_richcompare@ */
	148	0, /* @tp_weaklistoffset@ */
	149	PyObject_SelfIter, /* @tp_iter@ */
	150	daiter_pynext, /* @tp_iternexr@ */
	151	0, /* @tp_methods@ */
	152	0, /* @tp_members@ */
	153	0, /* @tp_getset@ */
	154	0, /* @tp_base@ */
	155	0, /* @tp_dict@ */
	156	0, /* @tp_descr_get@ */
	157	0, /* @tp_descr_set@ */
	158	0, /* @tp_dictoffset@ */
	159	0, /* @tp_init@ */
	160	PyType_GenericAlloc, /* @tp_alloc@ */
	161	abstract_pynew, /* @tp_new@ */
	162	0, /* @tp_free@ */
	163	0 /* @tp_is_gc@ */
	164	};
	165
	166	/----- Main array code ---------------------------------------------------/
	167
	168	static void da_doinsert(PyObject me, PyObject *items, size_t n,
	169	size_t start, size_t end)
	170	{
	171	PyObject v, gv, **gvl;
	172	obj_v *da = DA_V(me);
	173	size_t off, ne;
	174
	175	ne = end - start;
	176	v = DA(da);
	177	gv = v + start; gvl = v + end; range_copy(&gv, &gvl);
	178	if (start < DA_LEN(da) - end) {
	179	if (n > ne) {
	180	off = n - ne;
	181	DA_SHUNT(da, off);
	182	DA_UNSAFE_SLIDE(da, off);
	183	memmove(v, v + off, sizeof(PyObject ) start);
	184	} else {
185	off = ne - n;
186	memmove(v + off, v, sizeof(PyObject ) start);
187	DA_UNSAFE_UNSLIDE(da, off);
188	}
189	} else {
190	if (n > ne) {
191	off = n - ne;
192	DA_ENSURE(da, off);
193	memmove(v + end + off, v + end,
194	sizeof(PyObject ) (DA_LEN(da) - end));
195	} else {
196	off = ne - n;
197	memmove(v + end - off, v + end,
198	sizeof(PyObject ) (DA_LEN(da) - end));
199	DA_UNSAFE_SHRINK(da, off);
200	}
201	DA_UNSAFE_EXTEND(da, off);
202	}
203
204	if (n) {
205	v = DA(da) + start;
206	memcpy(v, items, sizeof(PyObject ) n);
207	range_inc(v, v + n);
208	}
209	if (gv) {
210	range_dec(gv, gvl);
211	xfree(gv);
212	}
213	}
214
215	static int da_insert(PyObject me, PyObject seq, int start, int end)
216	{
217	PyObject **items;
218	size_t n;
d8d81d1b	219
20bce5e9	220	if (0 > start \|\| start > end \|\| end > DA_LEN(DA_V(me))) {
	221	PyErr_SetString(PyExc_IndexError, "bad slice");
	222	return (-1);
	223	}
	224	if (getseq(&seq, &items, &n)) return (-1);
	225	da_doinsert(me, items, n, start, end);
	226	Py_XDECREF(seq);
	227	return (0);
	228	}
	229
	230	static PyObject da_new(PyTypeObject ty)
	231	{
	232	da_pyobj me = (da_pyobj )ty->tp_alloc(ty, 0);
	233	DA_CREATE(&me->v);
	234	return ((PyObject *)me);
	235	}
	236
	237	static PyObject da_pynew(PyTypeObject ty, PyObject arg, PyObject kw)
	238	{ return (da_new(ty)); }
	239	static int da_pyinit(PyObject me, PyObject arg, PyObject *kw)
	240	{
	241	PyObject *init = 0;
	242	static char *kwlist[] = { "sequence", 0 };
	243
	244	if (!PyArg_ParseTupleAndKeywords(arg, kw, "\|O:new", kwlist, &init) \|\|
	245	(init && da_insert((PyObject *)me, init, 0, 0)))
	246	return (-1);
	247	return (0);
	248	}
	249
	250	static void da_pydealloc(PyObject *me)
	251	{
	252	size_t i;
	253	PyObject **v = DA(DA_V(me));
	254	size_t n = DA_LEN(DA_V(me));
	255
	256	for (i = 0; i < n; i++) Py_DECREF(v[i]);
	257	DA_DESTROY(DA_V(me));
	258	}
	259
	260	static int da_pylength(PyObject *me)
	261	{ return (DA_LEN(DA_V(me))); }
	262
	263	static int da_pytraverse(PyObject me, visitproc proc, void arg)
	264	{
	265	size_t i;
	266	PyObject **v = DA(DA_V(me));
	267	size_t n = DA_LEN(DA_V(me));
	268	int err;
	269
	270	for (i = 0; i < n; i++) {
	271	if ((err = proc(v[i], arg)) != 0)
	272	return (err);
	273	}
	274	return (0);
	275	}
	276
	277	static int da_pyclear(PyObject *me)
	278	{
	279	range_dec(DA(DA_V(me)), DA(DA_V(me)) + DA_LEN(DA_V(me)));
	280	DA_RESET(DA_V(me));
	281	return (0);
	282	}
	283
284	static PyObject da_pyconcat(PyObject me, PyObject *other)
285	{
286	PyObject *x = da_new(&da_pytype);
287	PyObject **items = DA(DA_V(me));
288	size_t n = DA_LEN(DA_V(me));
289
290	da_doinsert(x, items, n, 0, 0);
291	if (da_insert(x, other, n, n)) {
292	Py_DECREF(x);
293	return (0);
294	}
295	return (x);
296	}
297
298	static PyObject da_pyrepeat(PyObject me, int times)
299	{
300	PyObject *x = da_new(&da_pytype);
301	PyObject items = DA(DA_V(me)), dest;
302	size_t n = DA_LEN(DA_V(me));
303	int i;
304
305	DA_ENSURE(DA_V(x), n * times);
306	DA_UNSAFE_EXTEND(DA_V(x), n * times);
307	for (i = 0, dest = DA(DA_V(x)); i < times; i++, dest += n)
308	memcpy(dest, items, n * sizeof(PyObject *));
309	range_inc(DA(DA_V(x)), DA(DA_V(x)) + n * times);
310	return (x);
311	}
312
313	static PyObject da_pygetitem(PyObject me, int i)
314	{
315	PyObject *o;
316
317	if (i < 0 \|\| i >= DA_LEN(DA_V(me))) {
318	PyErr_SetString(PyExc_IndexError, "index out of range");
319	return (0);
320	}
321	o = DA(DA_V(me))[i];
322	Py_INCREF(o);
323	return (o);
324	}
325
326	static PyObject da_pygetslice(PyObject me, int i, int j)
327	{
328	PyObject *x;
329
330	if (i < 0 \|\| j < i \|\| DA_LEN(DA_V(me)) < j) {
331	PyErr_SetString(PyExc_IndexError, "bad slice");
332	return (0);
333	}
334	x = da_new(&da_pytype);
335	da_doinsert(x, DA(DA_V(me)) + i, j - i, 0, 0);
336	return (x);
337	}
338
339	static int da_pyputitem(PyObject me, int i, PyObject x)
340	{
341	PyObject **p;
d8d81d1b	342
20bce5e9	343	if (i < 0 \|\| i >= DA_LEN(DA_V(me))) {
	344	PyErr_SetString(PyExc_IndexError, "index out of range");
	345	return (-1);
	346	}
	347	p = DA(DA_V(me)) + i;
	348	Py_DECREF(*p);
	349	*p = x;
	350	Py_INCREF(*p);
	351	return (0);
	352	}
	353
	354	static int da_pyputslice(PyObject me, int i, int j, PyObject x)
	355	{ return (da_insert(me, x, i, j)); }
	356
	357	static int da_pycontainsp(PyObject me, PyObject x)
	358	{
	359	PyObject **items = DA(DA_V(me));
	360	size_t n = DA_LEN(DA_V(me));
	361	size_t i;
	362	int rc;
	363
	364	for (i = 0; i < n; i++) {
	365	if (PyObject_Cmp(items[i], x, &rc))
	366	return (-1);
	367	if (rc)
	368	return (1);
	369	}
	370	return (0);
	371	}
	372
	373	static PyObject da_pyrepr(PyObject me)
	374	{
	375	dstr d = DSTR_INIT;
	376	PyObject s, rc = 0;
	377	char *p;
	378	int n;
	379	size_t i;
	380
	381	dstr_puts(&d, "Array([");
	382	for (i = 0; i < DA_LEN(DA_V(me)); i++) {
	383	if ((s = PyObject_Repr(DA(DA_V(me))[i])) == 0 \|\|
d8d81d1b	384	PyString_AsStringAndSize(s, &p, &n)) {
20bce5e9	385	Py_XDECREF(s);
	386	goto done;
	387	}
	388	if (i) dstr_puts(&d, ", ");
	389	dstr_putm(&d, p, n);
	390	Py_DECREF(s);
	391	}
	392	dstr_puts(&d, "])");
	393	rc = PyString_FromStringAndSize(d.buf, d.len);
	394	done:
	395	dstr_destroy(&d);
	396	return (rc);
	397	}
	398
	399	static PyObject da_pyappend(PyObject me, PyObject *seq)
	400	{
	401	size_t n = DA_LEN(DA_V(me));
	402	if (da_insert(me, seq, n, n)) return (0);
	403	RETURN_ME;
	404	}
	405
	406	static PyObject da_pyiprepeat(PyObject me, int times)
	407	{
	408	PyObject items, dest;
	409	size_t n = DA_LEN(DA_V(me));
	410	int i;
	411
	412	if (times < 0) {
	413	PyErr_SetString(PyExc_ValueError, "multiplier must be nonnegative");
	414	return (0);
	415	}
	416	if (!times) {
	417	items = DA(DA_V(me));
	418	range_dec(items, items + n);
	419	DA_RESET(DA_V(me));
	420	RETURN_ME;
	421	}
	422	times--;
	423	DA_ENSURE(DA_V(me), n * times);
	424	items = DA(DA_V(me));
	425	for (i = 0, dest = items + n; i < times; i++, dest += n)
	426	memcpy(dest, items, n * sizeof(PyObject *));
	427	range_inc(items + n, dest);
	428	DA_UNSAFE_EXTEND(DA_V(me), n * times);
	429	RETURN_ME;
	430	}
	431
	432	static PyObject da_pyget(PyObject me, PyObject *index)
	433	{
	434	if (PySlice_Check(index)) {
	435	int start, stop, step, len;
	436	PyObject *v;
	437	PyObject **ww;
	438	PyObject **vv;
	439
	440	if (PySlice_GetIndicesEx((PySliceObject *)index, DA_LEN(DA_V(me)),
	441	&start, &stop, &step, &len))
	442	return (0);
	443	if (step == 1) return (da_pygetslice(me, start, stop));
	444	v = da_new(&da_pytype);
	445	DA_ENSURE(DA_V(v), len);
	446	vv = DA(DA_V(v));
	447	ww = DA(DA_V(me)) + start;
	448	DA_UNSAFE_EXTEND(DA_V(v), len);
449	while (len) {
450	vv = ww;
451	Py_INCREF(*vv);
452	vv++; ww += step; len--;
453	}
454	return ((PyObject *)v);
455	} else {
456	int i;
457
458	if ((i = PyInt_AsLong(index)) == -1 && PyErr_Occurred()) return (0);
459	return (da_pygetitem(me, i));
460	}
461	}
462
463	static int da_pyput(PyObject me, PyObject index, PyObject *x)
464	{
465	if (PySlice_Check(index)) {
466	int start, stop, step, len;
467	size_t n;
468	PyObject **ww;
469	PyObject **vv;
470	PyObject g, gg;
471
472	if (PySlice_GetIndicesEx((PySliceObject *)index, DA_LEN(DA_V(me)),
473	&start, &stop, &step, &len))
474	return (-1);
475	if (step == 1) return (da_insert(me, x, start, stop));
476	if (getseq(&x, &vv, &n)) return (-1);
477	if (n != len) {
478	PyErr_SetString(PyExc_ValueError, "wrong number of items");
479	Py_XDECREF(x);
480	return (-1);
481	}
482	g = gg = xmalloc(len * sizeof(PyObject *));
483	ww = DA(DA_V(me)) + start;
484	while (len) {
485	gg++ = ww; ww = vv++;
486	Py_INCREF(*ww);
487	ww += step; len--;
488	}
489	range_dec(g, gg);
490	xfree(g);
491	Py_XDECREF(x);
492	return (0);
493	} else {
494	int i;
495
496	if ((i = PyInt_AsLong(index)) == -1 && PyErr_Occurred()) return (-1);
497	return (da_pyputitem(me, i, x));
498	}
499	}
500
501	static PyObject da_pyiter(PyObject me)
502	{
503	daiter_pyobj *i = PyObject_NEW(daiter_pyobj, &daiter_pytype);
504	i->da = me; Py_INCREF(me);
505	i->i = 0;
506	return ((PyObject *)i);
507	}
508
509	static PyObject dameth_push(PyObject me, PyObject *arg)
510	{
511	PyObject *x;
512
513	if (!PyArg_ParseTuple(arg, "O:push", &x)) return (0);
514	Py_INCREF(x);
515	DA_PUSH(DA_V(me), x);
516	RETURN_ME;
517	}
518
519	static PyObject dameth_pop(PyObject me, PyObject *arg)
520	{
521	PyObject *x;
522
523	if (!PyArg_ParseTuple(arg, ":pop")) return (0);
524	TRY
525	x = DA_POP(DA_V(me));
526	CATCH switch (exc_type) {
527	case DAEXC_UFLOW:
528	PyErr_SetString(PyExc_ValueError, "stack underflow");
529	return (0);
530	default:
531	RETHROW;
532	} END_TRY;
533	RETURN_OBJ(x);
534	}
535
536	static PyObject dameth_unshift(PyObject me, PyObject *arg)
537	{
538	PyObject *x;
539
540	if (!PyArg_ParseTuple(arg, "O:unshift", &x)) return (0);
541	Py_INCREF(x);
542	DA_UNSHIFT(DA_V(me), x);
543	RETURN_ME;
544	}
545
546	static PyObject dameth_shift(PyObject me, PyObject *arg)
547	{
548	PyObject *x;
549
550	if (!PyArg_ParseTuple(arg, ":shift")) return (0);
551	TRY
552	x = DA_SHIFT(DA_V(me));
553	CATCH switch (exc_type) {
554	case DAEXC_UFLOW:
555	PyErr_SetString(PyExc_ValueError, "stack underflow");
556	return (0);
557	default:
558	RETHROW;
559	} END_TRY;
560	RETURN_OBJ(x);
561	}
562
563	static PyObject dameth_tidy(PyObject me, PyObject *arg)
564	{
565	if (!PyArg_ParseTuple(arg, ":tidy")) return (0);
566	DA_TIDY(DA_V(me));
567	RETURN_ME;
568	}
569
570	static PyMethodDef da_pymethods[] = {
571	#define METHNAME(func) dameth_##func
572	METH (push, "A.push(X): [A, B, ..., W], X -> [A, B, ..., W, X]")
573	METH (pop, "A.pop() -> X: [A, B, ..., W, X] -> [A, B, ..., W]")
574	METH (unshift, "A.unshift(X): [A, B, ..., W], X -> [X, A, ..., W]")
575	METH (shift, "A.shift() -> X: [X, A, ..., W] -> [A, ..., W], X")
576	METH (tidy, "A.tidy()")
577	#undef METHNAME
578	{ 0 }
579	};
580
581	static PySequenceMethods da_pysequence = {
582	da_pylength, /* @sq_length@ */
583	da_pyconcat, /* @sq_concat@ */
584	da_pyrepeat, /* @sq_repeat@ */
585	da_pygetitem, /* @sq_item@ */
586	da_pygetslice, /* @sq_slice@ */
587	da_pyputitem, /* @sq_ass_item@ */
588	da_pyputslice, /* @sq_ass_slice@ */
589	da_pycontainsp, /* @sq_contains@ */
590	da_pyappend, /* @sq_inplace_concat@ */
591	da_pyiprepeat /* @sq_inplace_repeat@ */
592	};
593
594	static PyMappingMethods da_pymapping = {
595	da_pylength, /* @mp_length@ */
596	da_pyget, /* @mp_subscript@ */
597	da_pyput /* @mp_ass_subscript@ */
598	};
599
579d0169	600	PyTypeObject da_pytype = {
20bce5e9	601	PyObject_HEAD_INIT(0) 0, /* Header */
3655f952	602	"mLib.Array", /* @tp_name@ */
20bce5e9	603	sizeof(da_pyobj), /* @tp_basicsize@ */
	604	0, /* @tp_itemsize@ */
	605
	606	da_pydealloc, /* @tp_dealloc@ */
	607	0, /* @tp_print@ */
	608	0, /* @tp_getattr@ */
	609	0, /* @tp_setattr@ */
	610	0, /* @tp_compare@ */
	611	da_pyrepr, /* @tp_repr@ */
	612	0, /* @tp_as_number@ */
	613	&da_pysequence, /* @tp_as_sequence@ */
	614	&da_pymapping, /* @tp_as_mapping@ */
	615	0, /* @tp_hash@ */
	616	0, /* @tp_call@ */
	617	&da_pyrepr, /* @tp_str@ */
	618	0, /* @tp_getattro@ */
	619	0, /* @tp_setattro@ */
	620	0, /* @tp_as_buffer@ */
	621	Py_TPFLAGS_DEFAULT \| /* @tp_flags@ */
	622	Py_TPFLAGS_HAVE_GC,
	623
	624	/* @tp_doc@ */
	625	"Double-ended array type.",
	626
	627	da_pytraverse, /* @tp_traverse@ */
	628	da_pyclear, /* @tp_clear@ */
	629	0, /* @tp_richcompare@ */
	630	0, /* @tp_weaklistoffset@ */
	631	da_pyiter, /* @tp_iter@ */
	632	0, /* @tp_iternext@ */
	633	da_pymethods, /* @tp_methods@ */
	634	0, /* @tp_members@ */
	635	0, /* @tp_getset@ */
	636	0, /* @tp_base@ */
	637	0, /* @tp_dict@ */
	638	0, /* @tp_descr_get@ */
	639	0, /* @tp_descr_set@ */
	640	0, /* @tp_dictoffset@ */
	641	da_pyinit, /* @tp_init@ */
	642	PyType_GenericAlloc, /* @tp_alloc@ */
	643	da_pynew, /* @tp_new@ */
	644	0, /* @tp_free@ */
	645	0 /* @tp_is_gc@ */
	646	};
	647
	648	/----- Initialization ----------------------------------------------------/
	649
579d0169	650	void da_pysetup(void)
579d0169	651	{ PyType_Ready(&da_pytype); PyType_Ready(&daiter_pytype); }
20bce5e9	652
20bce5e9	653	/----- That's all, folks -------------------------------------------------/