chiark - git - mdw - mLib-python/blob - mapping.c

   1 /* -*-c-*-
   2  *
   3  * Generic mapping support
   4  *
   5  * (c) 2019 Straylight/Edgeware
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of Pyke: the Python Kit for Extensions.
  11  *
  12  * Pyke is free software: you can redistribute it and/or modify it under
  13  * the terms of the GNU General Public License as published by the Free
  14  * Software Foundation; either version 2 of the License, or (at your
  15  * option) any later version.
  16  *
  17  * Pyke is distributed in the hope that it will be useful, but WITHOUT
  18  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  19  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  20  * for more details.
  21  *
  22  * You should have received a copy of the GNU General Public License
  23  * along with Pyke.  If not, write to the Free Software Foundation, Inc.,
  24  * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  25  */
  26
  27 /*----- Header files ------------------------------------------------------*/
  28
  29 #include "pyke.h"
  30
  31 /*----- Iteration ---------------------------------------------------------*/
  32
  33 static PyTypeObject *keyiter_pytype, *itemiter_pytype, *valiter_pytype;
  34
  35 union iterstate {
  36   void *external;
  37   void *internal[4];
  38 };
  39
  40 typedef struct iter_pyobj {
  41   PyObject_HEAD
  42   PyObject *map;
  43   union iterstate iter;
  44 } iter_pyobj;
  45 #define ITER_MAP(o) (((iter_pyobj *)(o))->map)
  46 #define ITER_ITER(o) (&((iter_pyobj *)(o))->iter)
  47 #define ITER_EXTERNALP(o)                                               \
  48   (GMAP_OPS(ITER_MAP(o))->isz > sizeof(union iterstate))
  49 #define ITER_I(o) (ITER_EXTERNALP(o) ? ITER_ITER(o)->external           \
  50                                      : &ITER_ITER(o)->internal)
  51
  52 static void *iter_init(PyObject *me, union iterstate *iter)
  53 {
  54   const gmap_ops *gmops = GMAP_OPS(me);
  55   void *i;
  56
  57   if (gmops->isz <= sizeof(*iter)) i = &iter->internal;
  58   else { i = iter->external = PyObject_Malloc(gmops->isz); assert(i); }
  59   gmops->iter_init(me, i);
  60   return (i);
  61 }
  62
  63 static void iter_free(PyObject *me, union iterstate *iter)
  64   { if (GMAP_OPS(me)->isz > sizeof(*iter)) PyObject_Free(iter->external); }
  65
  66 static void iter_pydealloc(PyObject *me)
  67 {
  68   PyObject *map = ITER_MAP(me);
  69   iter_free(map, ITER_ITER(me));
  70   Py_DECREF(map); FREEOBJ(me);
  71 }
  72
  73 static PyObject *gmap_mkiter(PyObject *me, PyTypeObject *ty)
  74 {
  75   iter_pyobj *iter = PyObject_NEW(iter_pyobj, ty);
  76
  77   iter->map = me; Py_INCREF(me);
  78   iter_init(me, &iter->iter);
  79   return ((PyObject *)iter);
  80 }
  81
  82 static PyObject *keyiter_pynext(PyObject *me)
  83 {
  84   PyObject *map = ITER_MAP(me);
  85   const struct gmap_ops *gmops = GMAP_OPS(map);
  86   void *e = gmops->iter_next(map, ITER_I(me));
  87
  88   if (!e) return (0);
  89   else return (gmops->entry_key(map, e));
  90 }
  91
  92 static const PyTypeObject keyiter_pytype_skel = {
  93   PyVarObject_HEAD_INIT(0, 0)           /* Header */
  94   "_KeyIter",                           /* @tp_name@ */
  95   sizeof(iter_pyobj),                   /* @tp_basicsize@ */
  96   0,                                    /* @tp_itemsize@ */
  97
  98   iter_pydealloc,                       /* @tp_dealloc@ */
  99   0,                                    /* @tp_print@ */
 100   0,                                    /* @tp_getattr@ */
 101   0,                                    /* @tp_setattr@ */
 102   0,                                    /* @tp_compare@ */
 103   0,                                    /* @tp_repr@ */
 104   0,                                    /* @tp_as_number@ */
 105   0,                                    /* @tp_as_sequence@ */
 106   0,                                    /* @tp_as_mapping@ */
 107   0,                                    /* @tp_hash@ */
 108   0,                                    /* @tp_call@ */
 109   0,                                    /* @tp_str@ */
 110   0,                                    /* @tp_getattro@ */
 111   0,                                    /* @tp_setattro@ */
 112   0,                                    /* @tp_as_buffer@ */
 113   Py_TPFLAGS_DEFAULT |                  /* @tp_flags@ */
 114     Py_TPFLAGS_BASETYPE,
 115
 116   /* @tp_doc@ */
 117   "Iterates over the keys of a mapping.",
 118
 119   0,                                    /* @tp_traverse@ */
 120   0,                                    /* @tp_clear@ */
 121   0,                                    /* @tp_richcompare@ */
 122   0,                                    /* @tp_weaklistoffset@ */
 123   PyObject_SelfIter,                    /* @tp_iter@ */
 124   keyiter_pynext,                       /* @tp_iternext@ */
 125   0,                                    /* @tp_methods@ */
 126   0,                                    /* @tp_members@ */
 127   0,                                    /* @tp_getset@ */
 128   0,                                    /* @tp_base@ */
 129   0,                                    /* @tp_dict@ */
 130   0,                                    /* @tp_descr_get@ */
 131   0,                                    /* @tp_descr_set@ */
 132   0,                                    /* @tp_dictoffset@ */
 133   0,                                    /* @tp_init@ */
 134   PyType_GenericAlloc,                  /* @tp_alloc@ */
 135   abstract_pynew,                       /* @tp_new@ */
 136   0,                                    /* @tp_free@ */
 137   0                                     /* @tp_is_gc@ */
 138 };
 139
 140 static PyObject *valiter_pynext(PyObject *me)
 141 {
 142   PyObject *map = ITER_MAP(me);
 143   const struct gmap_ops *gmops = GMAP_OPS(map);
 144   void *e = gmops->iter_next(map, ITER_I(me));
 145
 146   if (!e) return (0);
 147   else return (gmops->entry_value(map, e));
 148 }
 149
 150 static const PyTypeObject valiter_pytype_skel = {
 151   PyVarObject_HEAD_INIT(0, 0)           /* Header */
 152   "_ValueIter",                         /* @tp_name@ */
 153   sizeof(iter_pyobj),                   /* @tp_basicsize@ */
 154   0,                                    /* @tp_itemsize@ */
 155
 156   iter_pydealloc,                       /* @tp_dealloc@ */
 157   0,                                    /* @tp_print@ */
 158   0,                                    /* @tp_getattr@ */
 159   0,                                    /* @tp_setattr@ */
 160   0,                                    /* @tp_compare@ */
 161   0,                                    /* @tp_repr@ */
 162   0,                                    /* @tp_as_number@ */
 163   0,                                    /* @tp_as_sequence@ */
 164   0,                                    /* @tp_as_mapping@ */
 165   0,                                    /* @tp_hash@ */
 166   0,                                    /* @tp_call@ */
 167   0,                                    /* @tp_str@ */
 168   0,                                    /* @tp_getattro@ */
 169   0,                                    /* @tp_setattro@ */
 170   0,                                    /* @tp_as_buffer@ */
 171   Py_TPFLAGS_DEFAULT |                  /* @tp_flags@ */
 172     Py_TPFLAGS_BASETYPE,
 173
 174   /* @tp_doc@ */
 175   "Iterates over the values of a mapping.",
 176
 177   0,                                    /* @tp_traverse@ */
 178   0,                                    /* @tp_clear@ */
 179   0,                                    /* @tp_richcompare@ */
 180   0,                                    /* @tp_weaklistoffset@ */
 181   PyObject_SelfIter,                    /* @tp_iter@ */
 182   valiter_pynext,                       /* @tp_iternext@ */
 183   0,                                    /* @tp_methods@ */
 184   0,                                    /* @tp_members@ */
 185   0,                                    /* @tp_getset@ */
 186   0,                                    /* @tp_base@ */
 187   0,                                    /* @tp_dict@ */
 188   0,                                    /* @tp_descr_get@ */
 189   0,                                    /* @tp_descr_set@ */
 190   0,                                    /* @tp_dictoffset@ */
 191   0,                                    /* @tp_init@ */
 192   PyType_GenericAlloc,                  /* @tp_alloc@ */
 193   abstract_pynew,                       /* @tp_new@ */
 194   0,                                    /* @tp_free@ */
 195   0                                     /* @tp_is_gc@ */
 196 };
 197
 198 static PyObject *itemiter_pynext(PyObject *me)
 199 {
 200   PyObject *map = ITER_MAP(me);
 201   const struct gmap_ops *gmops = GMAP_OPS(map);
 202   void *e = gmops->iter_next(map, ITER_I(me));
 203   PyObject *rc = 0;
 204
 205   if (e)
 206     rc = Py_BuildValue("(NN)",
 207                        gmops->entry_key(map, e),
 208                        gmops->entry_value(map, e));
 209   return (rc);
 210 }
 211
 212 static const PyTypeObject itemiter_pytype_skel = {
 213   PyVarObject_HEAD_INIT(0, 0)           /* Header */
 214   "_ItemIter",                          /* @tp_name@ */
 215   sizeof(iter_pyobj),                   /* @tp_basicsize@ */
 216   0,                                    /* @tp_itemsize@ */
 217
 218   iter_pydealloc,                       /* @tp_dealloc@ */
 219   0,                                    /* @tp_print@ */
 220   0,                                    /* @tp_getattr@ */
 221   0,                                    /* @tp_setattr@ */
 222   0,                                    /* @tp_compare@ */
 223   0,                                    /* @tp_repr@ */
 224   0,                                    /* @tp_as_number@ */
 225   0,                                    /* @tp_as_sequence@ */
 226   0,                                    /* @tp_as_mapping@ */
 227   0,                                    /* @tp_hash@ */
 228   0,                                    /* @tp_call@ */
 229   0,                                    /* @tp_str@ */
 230   0,                                    /* @tp_getattro@ */
 231   0,                                    /* @tp_setattro@ */
 232   0,                                    /* @tp_as_buffer@ */
 233   Py_TPFLAGS_DEFAULT |                  /* @tp_flags@ */
 234     Py_TPFLAGS_BASETYPE,
 235
 236   /* @tp_doc@ */
 237   "Iterates over the items of a mapping.",
 238
 239   0,                                    /* @tp_traverse@ */
 240   0,                                    /* @tp_clear@ */
 241   0,                                    /* @tp_richcompare@ */
 242   0,                                    /* @tp_weaklistoffset@ */
 243   PyObject_SelfIter,                    /* @tp_iter@ */
 244   itemiter_pynext,                      /* @tp_iternext@ */
 245   0,                                    /* @tp_methods@ */
 246   0,                                    /* @tp_members@ */
 247   0,                                    /* @tp_getset@ */
 248   0,                                    /* @tp_base@ */
 249   0,                                    /* @tp_dict@ */
 250   0,                                    /* @tp_descr_get@ */
 251   0,                                    /* @tp_descr_set@ */
 252   0,                                    /* @tp_dictoffset@ */
 253   0,                                    /* @tp_init@ */
 254   PyType_GenericAlloc,                  /* @tp_alloc@ */
 255   abstract_pynew,                       /* @tp_new@ */
 256   0,                                    /* @tp_free@ */
 257   0                                     /* @tp_is_gc@ */
 258 };
 259
 260 /*----- Other mapping protocol support ------------------------------------*/
 261
 262 Py_ssize_t gmap_pysize(PyObject *me)
 263 {
 264   const gmap_ops *gmops = GMAP_OPS(me);
 265   union iterstate iter;
 266   void *i;
 267   Py_ssize_t n = 0;
 268
 269   i = iter_init(me, &iter);
 270   while (gmops->iter_next(me, i)) n++;
 271   iter_free(me, &iter);
 272   return (n);
 273 }
 274
 275 PyObject *gmap_pylookup(PyObject *me, PyObject *key)
 276 {
 277   const gmap_ops *gmops = GMAP_OPS(me);
 278   void *e = gmops->lookup(me, key, 0);
 279   PyObject *rc = 0;
 280
 281   if (!e) { if (!PyErr_Occurred()) MAPERR(key); else goto end; }
 282   rc = gmops->entry_value(me, e);
 283 end:
 284   return (rc);
 285 }
 286
 287 int gmap_pystore(PyObject *me, PyObject *key, PyObject *value)
 288 {
 289   const gmap_ops *gmops = GMAP_OPS(me);
 290   unsigned f;
 291   void *e = gmops->lookup(me, key, &f);
 292   int rc = -1;
 293
 294   if (!e) goto end;
 295   if (!value)
 296     rc = gmops->del_entry(me, e);
 297   else {
 298     rc = gmops->set_entry(me, e, value);
 299     if (rc && !f) gmops->del_entry(me, e);
 300   }
 301   rc = 0;
 302 end:
 303   return (rc);
 304 }
 305
 306 int gmap_pyhaskey(PyObject *me, PyObject *key)
 307   { return (GMAP_OPS(me)->lookup(me, key, 0) ? 1 : PyErr_Occurred() ? -1 : 0); }
 308
 309 const PySequenceMethods gmap_pysequence = {
 310   0,                                    /* @sq_length@ */
 311   0,                                    /* @sq_concat@ */
 312   0,                                    /* @sq_repeat@ */
 313   0,                                    /* @sq_item@ */
 314   0,                                    /* @sq_slice@ */
 315   0,                                    /* @sq_ass_item@ */
 316   0,                                    /* @sq_ass_slice@ */
 317   gmap_pyhaskey,                        /* @sq_contains@ */
 318   0,                                    /* @sq_inplace_concat@ */
 319   0                                     /* @sq_inplace_repeat@ */
 320 };
 321
 322 PyObject *gmapmeth_has_key(PyObject *me, PyObject *arg)
 323 {
 324   PyObject *k;
 325   void *e;
 326   if (!PyArg_ParseTuple(arg, "O:has_key", &k)) return (0);
 327   e = GMAP_OPS(me)->lookup(me, k, 0);
 328   if (e) RETURN_TRUE;
 329   else if (!PyErr_Occurred()) RETURN_FALSE;
 330   else return (0);
 331 }
 332
 333 PyObject *gmapmeth_keys(PyObject *me)
 334 {
 335   const gmap_ops *gmops = GMAP_OPS(me);
 336   union iterstate iter; void *i = 0, *e;
 337   PyObject *l = 0, *k, *rc = 0;
 338   int err;
 339
 340   if ((l = PyList_New(0)) == 0) goto done;
 341   i = iter_init(me, &iter);
 342   while ((e = gmops->iter_next(me, i)) != 0) {
 343     k = gmops->entry_key(me, e);
 344     err = PyList_Append(l, k);
 345     Py_DECREF(k);
 346     if (err) goto done;
 347   }
 348   rc = l; l = 0;
 349 done:
 350   Py_XDECREF(l);
 351   if (i) iter_free(me, &iter);
 352   return (rc);
 353 }
 354
 355 PyObject *gmapmeth_values(PyObject *me)
 356 {
 357   const gmap_ops *gmops = GMAP_OPS(me);
 358   union iterstate iter; void *i = 0, *e;
 359   PyObject *l = 0, *v, *rc = 0;
 360   int err;
 361
 362   if ((l = PyList_New(0)) == 0) goto done;
 363   i = iter_init(me, &iter);
 364   while ((e = gmops->iter_next(me, i)) != 0) {
 365     v = gmops->entry_value(me, e);
 366     err = PyList_Append(l, v);
 367     Py_DECREF(v);
 368     if (err) goto done;
 369   }
 370   rc = l; l = 0;
 371 done:
 372   Py_XDECREF(l);
 373   if (i) iter_free(me, &iter);
 374   return (rc);
 375 }
 376
 377 PyObject *gmapmeth_items(PyObject *me)
 378 {
 379   const gmap_ops *gmops = GMAP_OPS(me);
 380   union iterstate iter; void *i = 0, *e;
 381   PyObject *l = 0, *z, *rc = 0;
 382   int err;
 383
 384   if ((l = PyList_New(0)) == 0) goto done;
 385   i = iter_init(me, &iter);
 386   while ((e = gmops->iter_next(me, i)) != 0) {
 387     if ((z = Py_BuildValue("(NN)",
 388                            gmops->entry_key(me, e),
 389                            gmops->entry_value(me, e))) == 0)
 390       goto done;
 391     err = PyList_Append(l, z);
 392     Py_XDECREF(z);
 393     if (err) goto done;
 394   }
 395   rc = l; l = 0;
 396 done:
 397   Py_XDECREF(l);
 398   if (i) iter_free(me, &iter);
 399   return (rc);
 400 }
 401
 402 PyObject *gmapmeth_iterkeys(PyObject *me)
 403   { return (gmap_mkiter(me, keyiter_pytype)); }
 404
 405 PyObject *gmapmeth_itervalues(PyObject *me)
 406   { return (gmap_mkiter(me, valiter_pytype)); }
 407
 408 PyObject *gmapmeth_iteritems(PyObject *me)
 409   { return (gmap_mkiter(me, itemiter_pytype)); }
 410
 411 PyObject *gmap_pyiter(PyObject *me)
 412   { return gmap_mkiter(me, keyiter_pytype); }
 413
 414 PyObject *gmapmeth_clear(PyObject *me)
 415 {
 416   const gmap_ops *gmops = GMAP_OPS(me);
 417   union iterstate iter;
 418   void *i, *e;
 419   PyObject *rc = 0;
 420
 421   i = iter_init(me, &iter);
 422   for (;;) {
 423     e = gmops->iter_next(me, i); if (!e) break;
 424     if (gmops->del_entry(me, e)) goto end;
 425   }
 426   iter_free(me, &iter);
 427   rc = me; Py_INCREF(me);
 428 end:
 429   return (rc);
 430 }
 431
 432 static const char *const def_kwlist[] = { "key", "default", 0 };
 433 #define DEF_KWLIST ((/*unconst*/ char **)def_kwlist)
 434
 435 PyObject *gmapmeth_get(PyObject *me, PyObject *arg, PyObject *kw)
 436 {
 437   const gmap_ops *gmops = GMAP_OPS(me);
 438   PyObject *k, *def = Py_None;
 439   void *e;
 440
 441   if (!PyArg_ParseTupleAndKeywords(arg, kw, "O|O:get", DEF_KWLIST, &k, &def))
 442     return (0);
 443   e = gmops->lookup(me, k, 0);
 444   if (e) return (gmops->entry_value(me, e));
 445   else if (!PyErr_Occurred()) RETURN_OBJ(def);
 446   else return (0);
 447 }
 448
 449 PyObject *gmapmeth_setdefault(PyObject *me, PyObject *arg, PyObject *kw)
 450 {
 451   const gmap_ops *gmops = GMAP_OPS(me);
 452   PyObject *k, *def = Py_None;
 453   void *e;
 454   unsigned f;
 455
 456   if (!PyArg_ParseTupleAndKeywords(arg, kw, "O|O:setdefault", DEF_KWLIST,
 457                                    &k, &def))
 458     return (0);
 459   e = gmops->lookup(me, k, &f);
 460   if (!e) return (0);
 461   else if (f) return (gmops->entry_value(me, e));
 462   else if (gmops->set_entry(me, e, def)) return (0);
 463   else RETURN_OBJ(def);
 464 }
 465
 466 PyObject *gmapmeth_pop(PyObject *me, PyObject *arg, PyObject *kw)
 467 {
 468   const gmap_ops *gmops = GMAP_OPS(me);
 469   PyObject *k, *def = 0;
 470   PyObject *rc = 0;
 471   void *e;
 472
 473   if (!PyArg_ParseTupleAndKeywords(arg, kw, "O|O:pop", DEF_KWLIST, &k, &def))
 474     goto end;
 475   e = gmops->lookup(me, k, 0);
 476   if (!e) {
 477     if (PyErr_Occurred()) goto end;
 478     else if (def) { rc = def; Py_INCREF(rc); }
 479     else MAPERR(k);
 480   } else {
 481     rc = gmops->entry_value(me, e);
 482     if (gmops->del_entry(me, e)) { Py_DECREF(rc); rc = 0; }
 483   }
 484 end:
 485   return (rc);
 486 }
 487
 488 static int update_core(PyObject *me, PyObject *map)
 489 {
 490   const gmap_ops *gmops = GMAP_OPS(me);
 491   PyObject *i = 0, *item = 0, *k = 0, *v = 0;
 492   void *e;
 493   unsigned foundp;
 494   int rc = -1;
 495
 496   i = PyObject_CallMethod(map, "iteritems", 0);
 497
 498   if (i) {
 499     for (;;) {
 500       item = PyIter_Next(i); if (!item) break;
 501       if (!PyTuple_Check(item) || PyTuple_GET_SIZE(item) != 2)
 502         TYERR("wanted a pair");
 503       k = PyTuple_GET_ITEM(item, 0); Py_INCREF(k);
 504       v = PyTuple_GET_ITEM(item, 1); Py_INCREF(v);
 505       e = gmops->lookup(me, k, &foundp); if (!e) goto end;
 506       if (gmops->set_entry(me, e, v)) goto end;
 507       Py_DECREF(item); Py_DECREF(k); Py_DECREF(v); item = k = v = 0;
 508     }
 509     if (PyErr_Occurred()) goto end;
 510   } else {
 511     PyErr_Clear();
 512     i = PyObject_GetIter(map); if (!i) goto end;
 513     for (;;) {
 514       k = PyIter_Next(i); if (!k) goto end;
 515       v = PyObject_GetItem(map, k); if (!v) goto end;
 516       e = gmops->lookup(me, k, &foundp); if (!e) goto end;
 517       if (gmops->set_entry(me, e, v)) goto end;
 518       Py_DECREF(k); Py_DECREF(v); k = v = 0;
 519     }
 520     if (PyErr_Occurred()) goto end;
 521   }
 522   rc = 0;
 523 end:
 524   Py_XDECREF(i); Py_XDECREF(item);
 525   Py_XDECREF(k); Py_XDECREF(v);
 526   return (rc);
 527 }
 528
 529 PyObject *gmapmeth_update(PyObject *me, PyObject *arg, PyObject *kw)
 530 {
 531   PyObject *map = 0;
 532
 533   if (!PyArg_ParseTuple(arg, "|O:update", &map)) return (0);
 534   if (map && update_core(me, map)) return (0);
 535   if (kw && update_core(me, kw)) return (0);
 536   RETURN_ME;
 537 }
 538
 539 PyObject *gmapmeth_popitem(PyObject *me)
 540 {
 541   const gmap_ops *gmops = GMAP_OPS(me);
 542   union iterstate iter;
 543   void *i;
 544   PyObject *rc = 0;
 545   void *e;
 546
 547   i = iter_init(me, &iter);
 548   e = gmops->iter_next(me, i);
 549   iter_free(me, &iter);
 550   if (!e)
 551     MAPERR(Py_None);
 552   else {
 553     rc = Py_BuildValue("(NN)",
 554                        gmops->entry_key(me, e), gmops->entry_value(me, e));
 555     if (gmops->del_entry(me, e)) { Py_DECREF(rc); rc = 0; }
 556   }
 557 end:
 558   return (rc);
 559 }
 560
 561 const PyMethodDef gmapro_pymethods[] = {
 562   GMAP_ROMETHODS
 563   { 0 }
 564 };
 565
 566 const PyMethodDef gmap_pymethods[] = {
 567   GMAP_METHODS
 568   { 0 }
 569 };
 570
 571 /*----- Submodule initialization ------------------------------------------*/
 572
 573 void pyke_gmap_pyinit(void)
 574 {
 575   INITTYPE(keyiter, root);
 576   INITTYPE(itemiter, root);
 577   INITTYPE(valiter, root);
 578 }
 579
 580 void pyke_gmap_pyinsert(PyObject *mod)
 581 {
 582   INSERT("_KeyIter", keyiter_pytype);
 583   INSERT("_ValueIter", valiter_pytype);
 584   INSERT("_ItemIter", itemiter_pytype);
 585 }
 586
 587 /*----- That's all, folks -------------------------------------------------*/