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