chiark / gitweb /
Release 1.0.5.
[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
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
42DA_DECL(obj_v, PyObject *);
43
44typedef 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
51typedef 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 60static 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
82static void range_inc(PyObject **v, PyObject **vl)
83 { while (v < vl) { Py_INCREF(*v); v++; } }
84static void range_dec(PyObject **v, PyObject **vl)
85 { if (v) { while (v < vl) { Py_DECREF(*v); v++; } } }
86static 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
98static 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
107static 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
115static void daiter_pydealloc(PyObject *me)
116 { Py_DECREF(DAITER_DA(me)); PyObject_DEL(me); }
117
579d0169 118PyTypeObject 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
168static 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
215static 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
230static 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
237static PyObject *da_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
238 { return (da_new(ty)); }
239static 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
250static 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
260static int da_pylength(PyObject *me)
261 { return (DA_LEN(DA_V(me))); }
262
263static 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
277static 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
284static 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
298static 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
313static 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
326static 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
339static 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
354static int da_pyputslice(PyObject *me, int i, int j, PyObject *x)
355 { return (da_insert(me, x, i, j)); }
356
357static 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
373static 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);
394done:
395 dstr_destroy(&d);
396 return (rc);
397}
398
399static 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
406static 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
432static 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
463static 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
501static 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
509static 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
519static 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
536static 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
546static 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
563static 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
570static 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
581static 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
594static PyMappingMethods da_pymapping = {
595 da_pylength, /* @mp_length@ */
596 da_pyget, /* @mp_subscript@ */
597 da_pyput /* @mp_ass_subscript@ */
598};
599
579d0169 600PyTypeObject 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 650void da_pysetup(void)
651 { PyType_Ready(&da_pytype); PyType_Ready(&daiter_pytype); }
20bce5e9 652
653/*----- That's all, folks -------------------------------------------------*/