chiark / gitweb /
debian: Fix package sections.
[mLib-python] / array.c
1 /* -*-c-*-
2  *
3  * $Id$
4  *
5  * Double-ended arrays
6  *
7  * (c) 2005 Straylight/Edgeware
8  */
9
10 /*----- Licensing notice --------------------------------------------------* 
11  *
12  * This file is part of the Python interface to mLib.
13  *
14  * mLib/Python is free software; you can redistribute it and/or modify
15  * it under the terms of the GNU General Public License as published by
16  * the Free Software Foundation; either version 2 of the License, or
17  * (at your option) any later version.
18  * 
19  * mLib/Python is distributed in the hope that it will be useful,
20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
22  * GNU General Public License for more details.
23  * 
24  * You should have received a copy of the GNU General Public License
25  * along with mLib/Python; if not, write to the Free Software Foundation,
26  * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
27  */
28
29 /*----- Header files ------------------------------------------------------*/
30
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
39 #include "array.h"
40 #include "grim.h"
41
42 /*----- Data structures ---------------------------------------------------*/
43
44 DA_DECL(obj_v, PyObject *);
45
46 typedef 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
53 typedef 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
62 static 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
84 static void range_inc(PyObject **v, PyObject **vl)
85   { while (v < vl) { Py_INCREF(*v);  v++; } }
86 static void range_dec(PyObject **v, PyObject **vl)
87   { if (v) { while (v < vl) { Py_DECREF(*v);  v++; } } }
88 static 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
100 static 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
109 static 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
117 static void daiter_pydealloc(PyObject *me)
118   { Py_DECREF(DAITER_DA(me)); PyObject_DEL(me); }
119
120 PyTypeObject daiter_pytype = {
121   PyObject_HEAD_INIT(0) 0,              /* Header */
122   "array.ArrayIter",                    /* @tp_name@ */
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
170 static 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
217 static int da_insert(PyObject *me, PyObject *seq, int start, int end)
218 {
219   PyObject **items;
220   size_t n;
221   
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
232 static 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
239 static PyObject *da_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
240   { return (da_new(ty)); }
241 static 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
252 static 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
262 static int da_pylength(PyObject *me)
263   { return (DA_LEN(DA_V(me))); }
264
265 static 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
279 static 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
286 static 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
300 static PyObject *da_pyrepeat(PyObject *me, int times)
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));
305   int i;
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
315 static PyObject *da_pygetitem(PyObject *me, int i)
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
328 static PyObject *da_pygetslice(PyObject *me, int i, int j)
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
341 static int da_pyputitem(PyObject *me, int i, PyObject *x)
342 {
343   PyObject **p;
344   
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
356 static int da_pyputslice(PyObject *me, int i, int j, PyObject *x)
357   { return (da_insert(me, x, i, j)); }
358
359 static int da_pycontainsp(PyObject *me, PyObject *x)
360 {
361   PyObject **items = DA(DA_V(me));
362   size_t n = DA_LEN(DA_V(me));
363   size_t i;
364   int rc;
365
366   for (i = 0; i < n; i++) {
367     if (PyObject_Cmp(items[i], x, &rc))
368       return (-1);
369     if (rc)
370       return (1);
371   }
372   return (0);
373 }
374
375 static PyObject *da_pyrepr(PyObject *me)
376 {
377   dstr d = DSTR_INIT;
378   PyObject *s, *rc = 0;
379   char *p;
380   int n;
381   size_t i;
382
383   dstr_puts(&d, "Array([");
384   for (i = 0; i < DA_LEN(DA_V(me)); i++) {
385     if ((s = PyObject_Repr(DA(DA_V(me))[i])) == 0 ||
386         PyString_AsStringAndSize(s, &p, &n)) {
387       Py_XDECREF(s);
388       goto done;
389     }
390     if (i) dstr_puts(&d, ", ");
391     dstr_putm(&d, p, n);
392     Py_DECREF(s);
393   }
394   dstr_puts(&d, "])");
395   rc = PyString_FromStringAndSize(d.buf, d.len);
396 done:
397   dstr_destroy(&d);
398   return (rc);
399 }
400
401 static PyObject *da_pyappend(PyObject *me, PyObject *seq)
402 {
403   size_t n = DA_LEN(DA_V(me));
404   if (da_insert(me, seq, n, n)) return (0);
405   RETURN_ME;
406 }
407
408 static PyObject *da_pyiprepeat(PyObject *me, int times)
409 {
410   PyObject **items, **dest;
411   size_t n = DA_LEN(DA_V(me));
412   int i;
413
414   if (times < 0) {
415     PyErr_SetString(PyExc_ValueError, "multiplier must be nonnegative");
416     return (0);
417   }
418   if (!times) {
419     items = DA(DA_V(me));
420     range_dec(items, items + n);
421     DA_RESET(DA_V(me));
422     RETURN_ME;
423   }
424   times--;
425   DA_ENSURE(DA_V(me), n * times);
426   items = DA(DA_V(me));
427   for (i = 0, dest = items + n; i < times; i++, dest += n)
428     memcpy(dest, items, n * sizeof(PyObject *));
429   range_inc(items + n, dest);
430   DA_UNSAFE_EXTEND(DA_V(me), n * times);
431   RETURN_ME;
432 }
433
434 static PyObject *da_pyget(PyObject *me, PyObject *index)
435 {
436   if (PySlice_Check(index)) {
437     int start, stop, step, len;
438     PyObject *v;
439     PyObject **ww;
440     PyObject **vv;
441
442     if (PySlice_GetIndicesEx((PySliceObject *)index, DA_LEN(DA_V(me)),
443                              &start, &stop, &step, &len))
444       return (0);
445     if (step == 1) return (da_pygetslice(me, start, stop));
446     v = da_new(&da_pytype);
447     DA_ENSURE(DA_V(v), len);
448     vv = DA(DA_V(v));
449     ww = DA(DA_V(me)) + start;
450     DA_UNSAFE_EXTEND(DA_V(v), len);
451     while (len) {
452       *vv = *ww;
453       Py_INCREF(*vv);
454       vv++; ww += step; len--;
455     }
456     return ((PyObject *)v);
457   } else {
458     int i;
459
460     if ((i = PyInt_AsLong(index)) == -1 && PyErr_Occurred()) return (0);
461     return (da_pygetitem(me, i));
462   }
463 }
464
465 static int da_pyput(PyObject *me, PyObject *index, PyObject *x)
466 {
467   if (PySlice_Check(index)) {
468     int start, stop, step, len;
469     size_t n;
470     PyObject **ww;
471     PyObject **vv;
472     PyObject **g, **gg;
473
474     if (PySlice_GetIndicesEx((PySliceObject *)index, DA_LEN(DA_V(me)),
475                              &start, &stop, &step, &len))
476       return (-1);
477     if (step == 1) return (da_insert(me, x, start, stop));
478     if (getseq(&x, &vv, &n)) return (-1);
479     if (n != len) {
480       PyErr_SetString(PyExc_ValueError, "wrong number of items");
481       Py_XDECREF(x);
482       return (-1);
483     }
484     g = gg = xmalloc(len * sizeof(PyObject *));
485     ww = DA(DA_V(me)) + start;
486     while (len) {
487       *gg++ = *ww; *ww = *vv++;
488       Py_INCREF(*ww);
489       ww += step; len--;
490     }
491     range_dec(g, gg);
492     xfree(g);
493     Py_XDECREF(x);
494     return (0);
495   } else {
496     int i;
497
498     if ((i = PyInt_AsLong(index)) == -1 && PyErr_Occurred()) return (-1);
499     return (da_pyputitem(me, i, x));
500   }
501 }
502
503 static PyObject *da_pyiter(PyObject *me)
504 {
505   daiter_pyobj *i = PyObject_NEW(daiter_pyobj, &daiter_pytype);
506   i->da = me; Py_INCREF(me);
507   i->i = 0;
508   return ((PyObject *)i);
509 }
510
511 static PyObject *dameth_push(PyObject *me, PyObject *arg)
512 {
513   PyObject *x;
514
515   if (!PyArg_ParseTuple(arg, "O:push", &x)) return (0);
516   Py_INCREF(x);
517   DA_PUSH(DA_V(me), x);
518   RETURN_ME;
519 }
520
521 static PyObject *dameth_pop(PyObject *me, PyObject *arg)
522 {
523   PyObject *x;
524
525   if (!PyArg_ParseTuple(arg, ":pop")) return (0);
526   TRY
527     x = DA_POP(DA_V(me));
528   CATCH switch (exc_type) {
529     case DAEXC_UFLOW:
530       PyErr_SetString(PyExc_ValueError, "stack underflow");
531       return (0);
532     default:
533       RETHROW;
534   } END_TRY;
535   RETURN_OBJ(x);
536 }
537
538 static PyObject *dameth_unshift(PyObject *me, PyObject *arg)
539 {
540   PyObject *x;
541
542   if (!PyArg_ParseTuple(arg, "O:unshift", &x)) return (0);
543   Py_INCREF(x);
544   DA_UNSHIFT(DA_V(me), x);
545   RETURN_ME;
546 }
547
548 static PyObject *dameth_shift(PyObject *me, PyObject *arg)
549 {
550   PyObject *x;
551
552   if (!PyArg_ParseTuple(arg, ":shift")) return (0);
553   TRY
554     x = DA_SHIFT(DA_V(me));
555   CATCH switch (exc_type) {
556     case DAEXC_UFLOW:
557       PyErr_SetString(PyExc_ValueError, "stack underflow");
558       return (0);
559     default:
560       RETHROW;
561   } END_TRY;
562   RETURN_OBJ(x);
563 }
564
565 static PyObject *dameth_tidy(PyObject *me, PyObject *arg)
566 {
567   if (!PyArg_ParseTuple(arg, ":tidy")) return (0);
568   DA_TIDY(DA_V(me));
569   RETURN_ME;
570 }
571
572 static PyMethodDef da_pymethods[] = {
573 #define METHNAME(func) dameth_##func
574   METH  (push,          "A.push(X): [A, B, ..., W], X -> [A, B, ..., W, X]")
575   METH  (pop,           "A.pop() -> X: [A, B, ..., W, X] -> [A, B, ..., W]")
576   METH  (unshift,       "A.unshift(X): [A, B, ..., W], X -> [X, A, ..., W]")
577   METH  (shift,         "A.shift() -> X: [X, A, ..., W] -> [A, ..., W], X")
578   METH  (tidy,          "A.tidy()")
579 #undef METHNAME
580   { 0 }
581 };
582
583 static PySequenceMethods da_pysequence = {
584   da_pylength,                          /* @sq_length@ */
585   da_pyconcat,                          /* @sq_concat@ */
586   da_pyrepeat,                          /* @sq_repeat@ */
587   da_pygetitem,                         /* @sq_item@ */
588   da_pygetslice,                        /* @sq_slice@ */
589   da_pyputitem,                         /* @sq_ass_item@ */
590   da_pyputslice,                        /* @sq_ass_slice@ */
591   da_pycontainsp,                       /* @sq_contains@ */
592   da_pyappend,                          /* @sq_inplace_concat@ */
593   da_pyiprepeat                         /* @sq_inplace_repeat@ */
594 };
595
596 static PyMappingMethods da_pymapping = {
597   da_pylength,                          /* @mp_length@ */
598   da_pyget,                             /* @mp_subscript@ */
599   da_pyput                              /* @mp_ass_subscript@ */
600 };
601
602 PyTypeObject da_pytype = {
603   PyObject_HEAD_INIT(0) 0,              /* Header */
604   "array.Array",                        /* @tp_name@ */
605   sizeof(da_pyobj),                     /* @tp_basicsize@ */
606   0,                                    /* @tp_itemsize@ */
607
608   da_pydealloc,                         /* @tp_dealloc@ */
609   0,                                    /* @tp_print@ */
610   0,                                    /* @tp_getattr@ */
611   0,                                    /* @tp_setattr@ */
612   0,                                    /* @tp_compare@ */
613   da_pyrepr,                            /* @tp_repr@ */
614   0,                                    /* @tp_as_number@ */
615   &da_pysequence,                       /* @tp_as_sequence@ */
616   &da_pymapping,                        /* @tp_as_mapping@ */
617   0,                                    /* @tp_hash@ */
618   0,                                    /* @tp_call@ */
619   &da_pyrepr,                           /* @tp_str@ */
620   0,                                    /* @tp_getattro@ */
621   0,                                    /* @tp_setattro@ */
622   0,                                    /* @tp_as_buffer@ */
623   Py_TPFLAGS_DEFAULT |                  /* @tp_flags@ */
624     Py_TPFLAGS_HAVE_GC,
625
626   /* @tp_doc@ */
627 "Double-ended array type.",
628
629   da_pytraverse,                        /* @tp_traverse@ */
630   da_pyclear,                           /* @tp_clear@ */
631   0,                                    /* @tp_richcompare@ */
632   0,                                    /* @tp_weaklistoffset@ */
633   da_pyiter,                            /* @tp_iter@ */
634   0,                                    /* @tp_iternext@ */
635   da_pymethods,                         /* @tp_methods@ */
636   0,                                    /* @tp_members@ */
637   0,                                    /* @tp_getset@ */
638   0,                                    /* @tp_base@ */
639   0,                                    /* @tp_dict@ */
640   0,                                    /* @tp_descr_get@ */
641   0,                                    /* @tp_descr_set@ */
642   0,                                    /* @tp_dictoffset@ */
643   da_pyinit,                            /* @tp_init@ */
644   PyType_GenericAlloc,                  /* @tp_alloc@ */
645   da_pynew,                             /* @tp_new@ */
646   0,                                    /* @tp_free@ */
647   0                                     /* @tp_is_gc@ */
648 };
649
650 /*----- Initialization ----------------------------------------------------*/
651
652 void da_pysetup(void)
653   { PyType_Ready(&da_pytype); PyType_Ready(&daiter_pytype); }
654
655 /*----- That's all, folks -------------------------------------------------*/