BTreeTemplate.c 58.2 KB
Newer Older
1
/*****************************************************************************
matt@zope.com's avatar
matt@zope.com committed
2

3 4
  Copyright (c) 2001, 2002 Zope Corporation and Contributors.
  All Rights Reserved.
Tim Peters's avatar
Tim Peters committed
5

matt@zope.com's avatar
matt@zope.com committed
6
  This software is subject to the provisions of the Zope Public License,
Jim Fulton's avatar
Jim Fulton committed
7
  Version 2.1 (ZPL).  A copy of the ZPL should accompany this distribution.
matt@zope.com's avatar
matt@zope.com committed
8 9 10 11
  THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
  WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
  FOR A PARTICULAR PURPOSE
Tim Peters's avatar
Tim Peters committed
12

13 14
 ****************************************************************************/

15
#define BTREETEMPLATE_C "$Id$\n"
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53

/* Sanity-check a BTree.  This is a private helper for BTree_check.  Return:
 *      -1         Error.  If it's an internal inconsistency in the BTree,
 *                 AssertionError is set.
 *       0         No problem found.
 *
 * nextbucket is the bucket "one beyond the end" of the BTree; the last bucket
 * directly reachable from following right child pointers *should* be linked
 * to nextbucket (and this is checked).
 */
static int
BTree_check_inner(BTree *self, Bucket *nextbucket)
{
    int i;
    Bucket *bucketafter;
    Sized *child;
    char *errormsg = "internal error";  /* someone should have overriden */
    Sized *activated_child = NULL;
    int result = -1;    /* until proved innocent */

#define CHECK(CONDITION, ERRORMSG)          \
    if (!(CONDITION)) {                     \
        errormsg = (ERRORMSG);              \
        goto Error;                         \
    }

    PER_USE_OR_RETURN(self, -1);
    CHECK(self->len >= 0, "BTree len < 0");
    CHECK(self->len <= self->size, "BTree len > size");
    if (self->len == 0) {
        /* Empty BTree. */
        CHECK(self->firstbucket == NULL,
              "Empty BTree has non-NULL firstbucket");
        result = 0;
        goto Done;
    }
    /* Non-empty BTree. */
    CHECK(self->firstbucket != NULL, "Non-empty BTree has NULL firstbucket");
54 55 56 57 58 59 60 61 62 63 64

    /* Obscure:  The first bucket is pointed to at least by self->firstbucket
     * and data[0].child of whichever BTree node it's a child of.  However,
     * if persistence is enabled then the latter BTree node may be a ghost
     * at this point, and so its pointers "don't count":  we can only rely
     * on self's pointers being intact.
     */
#ifdef PERSISTENT
    CHECK(self->firstbucket->ob_refcnt >= 1,
          "Non-empty BTree firstbucket has refcount < 1");
#else
65 66
    CHECK(self->firstbucket->ob_refcnt >= 2,
          "Non-empty BTree firstbucket has refcount < 2");
67 68
#endif

69 70 71
    for (i = 0; i < self->len; ++i) {
        CHECK(self->data[i].child != NULL, "BTree has NULL child");
    }
72

73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109
    if (SameType_Check(self, self->data[0].child)) {
        /* Our children are also BTrees. */
        child = self->data[0].child;
        UNLESS (PER_USE(child)) goto Done;
        activated_child = child;
        CHECK(self->firstbucket == BTREE(child)->firstbucket,
               "BTree has firstbucket different than "
               "its first child's firstbucket");
        PER_ALLOW_DEACTIVATION(child);
        activated_child = NULL;
        for (i = 0; i < self->len; ++i) {
            child = self->data[i].child;
            CHECK(SameType_Check(self, child),
                  "BTree children have different types");
            if (i == self->len - 1)
                bucketafter = nextbucket;
            else {
                BTree *child2 = BTREE(self->data[i+1].child);
                UNLESS (PER_USE(child2)) goto Done;
                bucketafter = child2->firstbucket;
                PER_ALLOW_DEACTIVATION(child2);
            }
            if (BTree_check_inner(BTREE(child), bucketafter) < 0) goto Done;
        }
    }
    else {
        /* Our children are buckets. */
        CHECK(self->firstbucket == BUCKET(self->data[0].child),
              "Bottom-level BTree node has inconsistent firstbucket belief");
        for (i = 0; i < self->len; ++i) {
            child = self->data[i].child;
            UNLESS (PER_USE(child)) goto Done;
            activated_child = child;
            CHECK(!SameType_Check(self, child),
                  "BTree children have different types");
            CHECK(child->len >= 1, "Bucket length < 1"); /* no empty buckets! */
            CHECK(child->len <= child->size, "Bucket len > size");
110 111 112
#ifdef PERSISTENT
            CHECK(child->ob_refcnt >= 1, "Bucket has refcount < 1");
#else
113
            CHECK(child->ob_refcnt >= 2, "Bucket has refcount < 2");
114
#endif
115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147
            if (i == self->len - 1)
                bucketafter = nextbucket;
            else
                bucketafter = BUCKET(self->data[i+1].child);
            CHECK(BUCKET(child)->next == bucketafter,
                  "Bucket next pointer is damaged");
            PER_ALLOW_DEACTIVATION(child);
            activated_child = NULL;
        }
    }
    result = 0;
    goto Done;

Error:
    PyErr_SetString(PyExc_AssertionError, errormsg);
    result = -1;
Done:
    /* No point updating access time -- this isn't a "real" use. */
    PER_ALLOW_DEACTIVATION(self);
    if (activated_child) {
        PER_ALLOW_DEACTIVATION(activated_child);
    }
    return result;

#undef CHECK
}

/* Sanity-check a BTree.  This is the ._check() method.  Return:
 *      NULL       Error.  If it's an internal inconsistency in the BTree,
 *                 AssertionError is set.
 *      Py_None    No problem found.
 */
static PyObject*
148
BTree_check(BTree *self)
149 150 151 152 153 154 155 156 157 158
{
    PyObject *result = NULL;
    int i = BTree_check_inner(self, NULL);

    if (i >= 0) {
        result = Py_None;
        Py_INCREF(result);
    }
    return result;
}
159

160 161 162
/*
** _BTree_get
**
163 164 165 166 167 168 169 170 171 172 173 174 175 176 177
** Search a BTree.
**
** Arguments
**      self        a pointer to a BTree
**      keyarg      the key to search for, as a Python object
**      has_key     true/false; when false, try to return the associated
**                  value; when true, return a boolean
** Return
**      When has_key false:
**          If key exists, its associated value.
**          If key doesn't exist, NULL and KeyError is set.
**      When has_key true:
**          A Python int is returned in any case.
**          If key exists, the depth of the bucket in which it was found.
**          If key doesn't exist, 0.
178 179
*/
static PyObject *
180
_BTree_get(BTree *self, PyObject *keyarg, int has_key)
181
{
182 183 184 185 186 187 188 189 190 191 192 193 194 195
    KEY_TYPE key;
    PyObject *result = NULL;    /* guilty until proved innocent */
    int copied = 1;

    COPY_KEY_FROM_ARG(key, keyarg, copied);
    UNLESS (copied) return NULL;

    PER_USE_OR_RETURN(self, NULL);
    if (self->len == 0) {
        /* empty BTree */
        if (has_key)
            result = PyInt_FromLong(0);
        else
            PyErr_SetObject(PyExc_KeyError, keyarg);
196
    }
197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214
    else {
        for (;;) {
            int i;
            Sized *child;

            BTREE_SEARCH(i, self, key, goto Done);
            child = self->data[i].child;
            has_key += has_key != 0;    /* bump depth counter, maybe */
            if (SameType_Check(self, child)) {
                PER_UNUSE(self);
                self = BTREE(child);
                PER_USE_OR_RETURN(self, NULL);
            }
            else {
                result = _bucket_get(BUCKET(child), keyarg, has_key);
                break;
            }
        }
215
    }
216

217 218 219
Done:
    PER_UNUSE(self);
    return result;
Tim Peters's avatar
Tim Peters committed
220
}
221

222 223 224 225
static PyObject *
BTree_get(BTree *self, PyObject *key)
{
  return _BTree_get(self, key, 0);
226 227
}

228 229 230 231 232 233 234 235 236 237 238 239 240 241
/* Create a new bucket for the BTree or TreeSet using the class attribute
   _bucket_type, which is normally initialized to BucketType or SetType
   as appropriate.
*/
static Sized *
BTree_newBucket(BTree *self)
{
    PyObject *factory;
    Sized *result;

    /* _bucket_type_str defined in BTreeModuleTemplate.c */
    factory = PyObject_GetAttr((PyObject *)self->ob_type, _bucket_type_str);
    if (factory == NULL)
	return NULL;
242
    /* TODO: Should we check that the factory actually returns something
243 244 245 246 247 248 249 250 251
       of the appropriate type? How?  The C code here is going to
       depend on any custom bucket type having the same layout at the
       C level.
    */
    result = SIZED(PyObject_CallObject(factory, NULL));
    Py_DECREF(factory);
    return result;
}

252
/*
253 254 255 256 257 258 259 260 261 262 263
 * Move data from the current BTree, from index onward, to the newly created
 * BTree 'next'.  self and next must both be activated.  If index is OOB (< 0
 * or >= self->len), use self->len / 2 as the index (i.e., split at the
 * midpoint).  self must have at least 2 children on entry, and index must
 * be such that self and next each have at least one child at exit.  self's
 * accessed time is updated.
 *
 * Return:
 *    -1    error
 *     0    OK
 */
264 265 266
static int
BTree_split(BTree *self, int index, BTree *next)
{
267 268
    int next_size;
    Sized *child;
Tim Peters's avatar
Tim Peters committed
269

270 271
    if (index < 0 || index >= self->len)
	index = self->len / 2;
Tim Peters's avatar
Tim Peters committed
272

273 274 275
    next_size = self->len - index;
    ASSERT(index > 0, "split creates empty tree", -1);
    ASSERT(next_size > 0, "split creates empty tree", -1);
Tim Peters's avatar
Tim Peters committed
276

277
    next->data = BTree_Malloc(sizeof(BTreeItem) * next_size);
278 279 280 281
    if (!next->data)
	return -1;
    memcpy(next->data, self->data + index, sizeof(BTreeItem) * next_size);
    next->size = next_size;  /* but don't set len until we succeed */
282

283 284 285 286 287 288
    /* Set next's firstbucket.  self->firstbucket is still correct. */
    child = next->data[0].child;
    if (SameType_Check(self, child)) {
        PER_USE_OR_RETURN(child, -1);
	next->firstbucket = BTREE(child)->firstbucket;
	PER_UNUSE(child);
289
    }
290 291 292
    else
	next->firstbucket = BUCKET(child);
    Py_INCREF(next->firstbucket);
293

294 295
    next->len = next_size;
    self->len = index;
296
    return PER_CHANGED(self) >= 0 ? 0 : -1;
297 298
}

Tim Peters's avatar
Tim Peters committed
299

300 301
/* Fwd decl -- BTree_grow and BTree_split_root reference each other. */
static int BTree_grow(BTree *self, int index, int noval);
302

303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318
/* Split the root.  This is a little special because the root isn't a child
 * of anything else, and the root needs to retain its object identity.  So
 * this routine moves the root's data into a new child, and splits the
 * latter.  This leaves the root with two children.
 *
 * Return:
 *      0   OK
 *     -1   error
 *
 * CAUTION:  The caller must call PER_CHANGED on self.
 */
static int
BTree_split_root(BTree *self, int noval)
{
    BTree *child;
    BTreeItem *d;
319

320 321 322
    /* Create a child BTree, and a new data vector for self. */
    child = BTREE(PyObject_CallObject(OBJECT(self->ob_type), NULL));
    if (!child) return -1;
323

324
    d = BTree_Malloc(sizeof(BTreeItem) * 2);
325 326 327 328
    if (!d) {
        Py_DECREF(child);
        return -1;
    }
329

330 331 332 333 334 335 336 337 338 339 340 341 342
    /* Move our data to new BTree. */
    child->size = self->size;
    child->len = self->len;
    child->data = self->data;
    child->firstbucket = self->firstbucket;
    Py_INCREF(child->firstbucket);

    /* Point self to child and split the child. */
    self->data = d;
    self->len = 1;
    self->size = 2;
    self->data[0].child = SIZED(child); /* transfers reference ownership */
    return BTree_grow(self, 0, noval);
343 344 345 346 347
}

/*
** BTree_grow
**
Tim Peters's avatar
Tim Peters committed
348
** Grow a BTree
349 350
**
** Arguments:	self	The BTree
351 352 353 354
**		index	self->data[index].child needs to be split.  index
**                      must be 0 if self is empty (len == 0), and a new
**                      empty bucket is created then.
**              noval   Boolean; is this a set (true) or mapping (false)?
355 356 357
**
** Returns:	 0	on success
**		-1	on failure
358 359 360 361 362
**
** CAUTION:  If self is empty on entry, this routine adds an empty bucket.
** That isn't a legitimate BTree; if the caller doesn't put something in
** in the bucket (say, because of a later error), the BTree must be cleared
** to get rid of the empty bucket.
363
*/
Tim Peters's avatar
Tim Peters committed
364
static int
365
BTree_grow(BTree *self, int index, int noval)
366 367
{
  int i;
368
  Sized *v, *e = 0;
369 370
  BTreeItem *d;

371 372 373 374 375
  if (self->len == self->size) {
      if (self->size) {
          d = BTree_Realloc(self->data, sizeof(BTreeItem) * self->size * 2);
	  if (d == NULL)
	      return -1;
376
          self->data = d;
377
          self->size *= 2;
378 379 380 381 382
      }
      else {
          d = BTree_Malloc(sizeof(BTreeItem) * 2);
	  if (d == NULL)
	      return -1;
383
          self->data = d;
384
          self->size = 2;
385 386
      }
  }
Tim Peters's avatar
Tim Peters committed
387

388
  if (self->len) {
389
      d = self->data + index;
390
      v = d->child;
391
      /* Create a new object of the same type as the target value */
392 393 394
      e = (Sized *)PyObject_CallObject((PyObject *)v->ob_type, NULL);
      if (e == NULL)
	  return -1;
395

396
      UNLESS(PER_USE(v)) {
397 398
          Py_DECREF(e);
          return -1;
399
      }
400

401
      /* Now split between the original (v) and the new (e) at the midpoint*/
402
      if (SameType_Check(self, v))
403
          i = BTree_split((BTree *)v, -1, (BTree *)e);
404
      else
405
          i = bucket_split((Bucket *)v, -1, (Bucket *)e);
406
      PER_ALLOW_DEACTIVATION(v);
407

408
      if (i < 0) {
409
          Py_DECREF(e);
410
	  assert(PyErr_Occurred());
411
          return -1;
412
      }
413 414 415 416

      index++;
      d++;
      if (self->len > index)	/* Shift up the old values one array slot */
417
	  memmove(d+1, d, sizeof(BTreeItem)*(self->len-index));
418

419
      if (SameType_Check(self, v)) {
420
          COPY_KEY(d->key, BTREE(e)->data->key);
421 422

          /* We take the unused reference from e, so there's no
Tim Peters's avatar
Tim Peters committed
423
             reason to INCREF!
424 425
          */
          /* INCREF_KEY(self->data[1].key); */
426 427
      }
      else {
428
          COPY_KEY(d->key, BUCKET(e)->keys[0]);
429
          INCREF_KEY(d->key);
430
      }
431
      d->child = e;
432 433
      self->len++;

434
      if (self->len >= MAX_BTREE_SIZE(self) * 2)    /* the root is huge */
435 436 437
	  return BTree_split_root(self, noval);
  }
  else {
438 439 440 441 442
      /* The BTree is empty.  Create an empty bucket.  See CAUTION in
       * the comments preceding.
       */
      assert(index == 0);
      d = self->data;
443 444 445
      d->child = BTree_newBucket(self);
      if (d->child == NULL)
	  return -1;
446
      self->len = 1;
447
      Py_INCREF(d->child);
448 449
      self->firstbucket = (Bucket *)d->child;
  }
Tim Peters's avatar
Tim Peters committed
450

451 452
  return 0;
}
453

454 455 456 457 458 459 460 461 462 463 464
/* Return the rightmost bucket reachable from following child pointers
 * from self.  The caller gets a new reference to this bucket.  Note that
 * bucket 'next' pointers are not followed:  if self is an interior node
 * of a BTree, this returns the rightmost bucket in that node's subtree.
 * In case of error, returns NULL.
 *
 * self must not be a ghost; this isn't checked.  The result may be a ghost.
 *
 * Pragmatics:  Note that the rightmost bucket's last key is the largest
 * key in self's subtree.
 */
465
static Bucket *
Tim Peters's avatar
Tim Peters committed
466
BTree_lastBucket(BTree *self)
467
{
468 469
    Sized *pchild;
    Bucket *result;
470

471
    UNLESS (self->data && self->len) {
472
        IndexError(-1); /* is this the best action to take? */
473
        return NULL;
474
    }
475

476 477 478 479 480
    pchild = self->data[self->len - 1].child;
    if (SameType_Check(self, pchild)) {
        self = BTREE(pchild);
        PER_USE_OR_RETURN(self, NULL);
        result = BTree_lastBucket(self);
481
        PER_UNUSE(self);
482 483 484 485 486 487
    }
    else {
        Py_INCREF(pchild);
        result = BUCKET(pchild);
    }
    return result;
488 489 490 491 492
}

static int
BTree_deleteNextBucket(BTree *self)
{
493
    Bucket *b;
494

495
    UNLESS (PER_USE(self)) return -1;
496

497 498 499 500 501
    b = BTree_lastBucket(self);
    if (b == NULL)
	goto err;
    if (Bucket_deleteNextBucket(b) < 0)
	goto err;
502

503 504
    Py_DECREF(b);
    PER_UNUSE(self);
505

506
    return 0;
507 508

 err:
509 510 511
    Py_XDECREF(b);
    PER_ALLOW_DEACTIVATION(self);
    return -1;
512 513
}

514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541
/*
** _BTree_clear
**
** Clears out all of the values in the BTree (firstbucket, keys, and children);
** leaving self an empty BTree.
**
** Arguments:	self	The BTree
**
** Returns:	 0	on success
**		-1	on failure
**
** Internal:  Deallocation order is important.  The danger is that a long
** list of buckets may get freed "at once" via decref'ing the first bucket,
** in which case a chain of consequenct Py_DECREF calls may blow the stack.
** Luckily, every bucket has a refcount of at least two, one due to being a
** BTree node's child, and another either because it's not the first bucket in
** the chain (so the preceding bucket points to it), or because firstbucket
** points to it.  By clearing in the natural depth-first, left-to-right
** order, the BTree->bucket child pointers prevent Py_DECREF(bucket->next)
** calls from freeing bucket->next, and the maximum stack depth is equal
** to the height of the tree.
**/
static int
_BTree_clear(BTree *self)
{
    const int len = self->len;

    if (self->firstbucket) {
542 543 544 545 546 547 548 549 550 551
        /* Obscure:  The first bucket is pointed to at least by
         * self->firstbucket and data[0].child of whichever BTree node it's
         * a child of.  However, if persistence is enabled then the latter
         * BTree node may be a ghost at this point, and so its pointers "don't
         * count":  we can only rely on self's pointers being intact.
         */
#ifdef PERSISTENT
	ASSERT(self->firstbucket->ob_refcnt > 0,
	       "Invalid firstbucket pointer", -1);
#else
552 553
	ASSERT(self->firstbucket->ob_refcnt > 1,
	       "Invalid firstbucket pointer", -1);
554
#endif
555 556 557 558 559 560 561 562 563 564 565
	Py_DECREF(self->firstbucket);
	self->firstbucket = NULL;
    }

    if (self->data) {
        int i;
        if (len > 0) { /* 0 is special because key 0 is trash */
            Py_DECREF(self->data[0].child);
	}

        for (i = 1; i < len; i++) {
566
#ifdef KEY_TYPE_IS_PYOBJECT
567
	    DECREF_KEY(self->data[i].key);
568
#endif
569 570 571 572 573 574 575 576 577 578
            Py_DECREF(self->data[i].child);
        }
	free(self->data);
	self->data = NULL;
    }

    self->len = self->size = 0;
    return 0;
}

579
/*
Tim Peters's avatar
Tim Peters committed
580
  Set (value != 0) or delete (value=0) a tree item.
581 582 583 584 585 586 587

  If unique is non-zero, then only change if the key is
  new.

  If noval is non-zero, then don't set a value (the tree
  is a set).

588 589 590 591 592 593 594 595 596 597
  Return:
    -1  error
     0  successful, and number of entries didn't change
    >0  successful, and number of entries did change

  Internal
     There are two distinct return values > 0:

     1  Successful, number of entries changed, but firstbucket did not go away.

598
     2  Successful, number of entries changed, firstbucket did go away.
599 600 601 602 603
        This can only happen on a delete (value == NULL).  The caller may
        need to change its own firstbucket pointer, and in any case *someone*
        needs to adjust the 'next' pointer of the bucket immediately preceding
        the bucket that went away (it needs to point to the bucket immediately
        following the bucket that went away).
604 605
*/
static int
Tim Peters's avatar
Tim Peters committed
606
_BTree_set(BTree *self, PyObject *keyarg, PyObject *value,
607
           int unique, int noval)
608
{
609 610 611 612 613
    int changed = 0;    /* did I mutate? */
    int min;            /* index of child I searched */
    BTreeItem *d;       /* self->data[min] */
    int childlength;    /* len(self->data[min].child) */
    int status;         /* our return value; and return value from callee */
614
    int self_was_empty; /* was self empty at entry? */
615

616
    KEY_TYPE key;
617
    int copied = 1;
618

619
    COPY_KEY_FROM_ARG(key, keyarg, copied);
620
    if (!copied) return -1;
621

622
    PER_USE_OR_RETURN(self, -1);
623

624 625
    self_was_empty = self->len == 0;
    if (self_was_empty) {
626
        /* We're empty.  Make room. */
627 628
	if (value) {
	    if (BTree_grow(self, 0, noval) < 0)
629
		goto Error;
630 631
	}
	else {
632
	    /* Can't delete a key from an empty BTree. */
633
	    PyErr_SetObject(PyExc_KeyError, keyarg);
634
	    goto Error;
635
	}
636
    }
637

638 639
    /* Find the right child to search, and hand the work off to it. */
    BTREE_SEARCH(min, self, key, goto Error);
640
    d = self->data + min;
641

642
    if (SameType_Check(self, d->child))
643
	status = _BTree_set(BTREE(d->child), keyarg, value, unique, noval);
644 645
    else {
        int bucket_changed = 0;
646
	status = _bucket_set(BUCKET(d->child), keyarg,
647 648 649 650 651
	                     value, unique, noval, &bucket_changed);
#ifdef PERSISTENT
	/* If a BTree contains only a single bucket, BTree.__getstate__()
	 * includes the bucket's entire state, and the bucket doesn't get
	 * an oid of its own.  So if we have a single oid-less bucket that
652 653
	 * changed, it's *our* oid that should be marked as changed -- the
	 * bucket doesn't have one.
654 655 656 657 658 659 660 661 662
	 */
	if (bucket_changed
	    && self->len == 1
	    && self->data[0].child->oid == NULL)
	{
	    changed = 1;
	}
#endif
    }
663 664 665 666 667 668 669 670 671
    if (status == 0) goto Done;
    if (status < 0) goto Error;
    assert(status == 1 || status == 2);

    /* The child changed size.  Get its new size.  Note that since the tree
     * rooted at the child changed size, so did the tree rooted at self:
     * our status must be >= 1 too.
     */
    UNLESS(PER_USE(d->child)) goto Error;
672
    childlength = d->child->len;
673
    PER_UNUSE(d->child);
674

675
    if (value) {
676
        /* A bucket got bigger -- if it's "too big", split it. */
677 678
        int toobig;

679
        assert(status == 1);    /* can be 2 only on deletes */
680
        if (SameType_Check(self, d->child))
681
            toobig = childlength > MAX_BTREE_SIZE(d->child);
682
        else
683
            toobig = childlength > MAX_BUCKET_SIZE(d->child);
684 685

        if (toobig) {
686 687
            if (BTree_grow(self, min, noval) < 0) goto Error;
            changed = 1;        /* BTree_grow mutated self */
688
        }
689
        goto Done;      /* and status still == 1 */
690
    }
691

692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711
    /* A bucket got smaller.  This is much harder, and despite that we
     * don't try to rebalance the tree.
     */
    if (status == 2) {  /*  this is the last reference to child status */
        /* Two problems to solve:  May have to adjust our own firstbucket,
         * and the bucket that went away needs to get unlinked.
         */
        if (min) {
            /* This wasn't our firstbucket, so no need to adjust ours (note
             * that it can't be the firstbucket of any node above us either).
             * Tell "the tree to the left" to do the unlinking.
             */
            if (BTree_deleteNextBucket(BTREE(d[-1].child)) < 0) goto Error;
            status = 1;     /* we solved the child's firstbucket problem */
        }
        else {
            /* This was our firstbucket.  Update to new firstbucket value. */
            Bucket *nextbucket;
            UNLESS(PER_USE(d->child)) goto Error;
            nextbucket = BTREE(d->child)->firstbucket;
712
            PER_UNUSE(d->child);
713 714 715 716 717 718 719 720 721 722 723

            Py_XINCREF(nextbucket);
            Py_DECREF(self->firstbucket);
            self->firstbucket = nextbucket;
            changed = 1;

            /* The caller has to do the unlinking -- we can't.  Also, since
             * it was our firstbucket, it may also be theirs.
             */
            assert(status == 2);
        }
724 725
    }

726 727 728 729 730 731 732 733 734 735
    /* If the child isn't empty, we're done!  We did all that was possible for
     * us to do with the firstbucket problems the child gave us, and since the
     * child isn't empty don't create any new firstbucket problems of our own.
     */
    if (childlength) goto Done;

    /* The child became empty:  we need to remove it from self->data.
     * But first, if we're a bottom-level node, we've got more bucket-fiddling
     * to set up.
     */
736
    if (!SameType_Check(self, d->child)) {
737
        /* We're about to delete a bucket. */
738
        if (min) {
739 740 741 742 743 744 745 746 747
            /* It's not our first bucket, so we can tell the previous
             * bucket to adjust its reference to it.  It can't be anyone
             * else's first bucket either, so the caller needn't do anything.
             */
            if (Bucket_deleteNextBucket(BUCKET(d[-1].child)) < 0) goto Error;
            /* status should be 1, and already is:  if it were 2, the
             * block above would have set it to 1 in its min != 0 branch.
             */
            assert(status == 1);
748 749
        }
        else {
750 751 752 753 754
            Bucket *nextbucket;
            /* It's our first bucket.  We can't unlink it directly. */
            /* 'changed' will be set true by the deletion code following. */
            UNLESS(PER_USE(d->child)) goto Error;
            nextbucket = BUCKET(d->child)->next;
755
            PER_UNUSE(d->child);
756 757 758 759 760 761 762

            Py_XINCREF(nextbucket);
            Py_DECREF(self->firstbucket);
            self->firstbucket = nextbucket;

            status = 2; /* we're giving our caller a new firstbucket problem */
         }
763
    }
764 765

    /* Remove the child from self->data. */
766
    Py_DECREF(d->child);
767
#ifdef KEY_TYPE_IS_PYOBJECT
768 769 770
    if (min) {
        DECREF_KEY(d->key);
    }
771 772 773 774 775 776 777 778 779 780 781 782
    else if (self->len > 1) {
	/* We're deleting the first child of a BTree with more than one
	 * child.  The key at d+1 is about to be shifted into slot 0,
	 * and hence never to be referenced again (the key in slot 0 is
	 * trash).
	 */
	DECREF_KEY((d+1)->key);
    }
    /* Else min==0 and len==1:  we're emptying the BTree entirely, and
     * there is no key in need of decrefing.
     */
#endif
783
    --self->len;
784
    if (min < self->len)
785
        memmove(d, d+1, (self->len - min) * sizeof(BTreeItem));
786
    changed = 1;
787

788
Done:
789
#ifdef PERSISTENT
790
    if (changed) {
791 792
        if (PER_CHANGED(self) < 0) goto Error;
    }
793
#endif
794
    PER_UNUSE(self);
795
    return status;
Tim Peters's avatar
Tim Peters committed
796

797
Error:
798
    assert(PyErr_Occurred());
799 800 801 802 803 804
    if (self_was_empty) {
        /* BTree_grow may have left the BTree in an invalid state.  Make
         * sure the tree is a legitimate empty tree.
         */
        _BTree_clear(self);
    }
805 806
    PER_UNUSE(self);
    return -1;
807 808 809
}

/*
810
** BTree_setitem
811
**
812
** wrapper for _BTree_set
813
**
814 815 816
** Arguments:	self	The BTree
**		key	The key to insert
**		v	The value to insert
817
**
818 819
** Returns	-1	on failure
**		 0	on success
820
*/
821 822
static int
BTree_setitem(BTree *self, PyObject *key, PyObject *v)
823
{
824 825 826
    if (_BTree_set(self, key, v, 0, 0) < 0)
	return -1;
    return 0;
827 828
}

Jim Fulton's avatar
Jim Fulton committed
829
#ifdef PERSISTENT
830
static PyObject *
831
BTree__p_deactivate(BTree *self, PyObject *args, PyObject *keywords)
832
{
833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850
    int ghostify = 1;
    PyObject *force = NULL;

    if (args && PyTuple_GET_SIZE(args) > 0) {
	PyErr_SetString(PyExc_TypeError,
			"_p_deactivate takes not positional arguments");
	return NULL;
    }
    if (keywords) {
	int size = PyDict_Size(keywords);
	force = PyDict_GetItemString(keywords, "force");
	if (force)
	    size--;
	if (size) {
	    PyErr_SetString(PyExc_TypeError,
			    "_p_deactivate only accepts keyword arg force");
	    return NULL;
	}
851 852
    }

853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869
    if (self->jar && self->oid) {
	ghostify = self->state == cPersistent_UPTODATE_STATE;
	if (!ghostify && force) {
	    if (PyObject_IsTrue(force))
		ghostify = 1;
	    if (PyErr_Occurred())
		return NULL;
	}
	if (ghostify) {
	    if (_BTree_clear(self) < 0)
		return NULL;
	    PER_GHOSTIFY(self);
	}
    }

    Py_INCREF(Py_None);
    return Py_None;
870
}
Jim Fulton's avatar
Jim Fulton committed
871
#endif
872 873

static PyObject *
874
BTree_clear(BTree *self)
875
{
876
  UNLESS (PER_USE(self)) return NULL;
877

878 879
  if (self->len)
    {
880 881 882 883
      if (_BTree_clear(self) < 0)
	  goto err;
      if (PER_CHANGED(self) < 0)
	  goto err;
884
    }
885

886
  PER_UNUSE(self);
887

Tim Peters's avatar
Tim Peters committed
888
  Py_INCREF(Py_None);
889
  return Py_None;
890 891

err:
892
  PER_UNUSE(self);
893 894 895
  return NULL;
}

896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922
/*
 * Return:
 *
 * For an empty BTree (self->len == 0), None.
 *
 * For a BTree with one child (self->len == 1), and that child is a bucket,
 * and that bucket has a NULL oid, a one-tuple containing a one-tuple
 * containing the bucket's state:
 *
 *     (
 *         (
 *              child[0].__getstate__(),
 *         ),
 *     )
 *
 * Else a two-tuple.  The first element is a tuple interleaving the BTree's
 * keys and direct children, of size 2*self->len - 1 (key[0] is unused and
 * is not saved).  The second element is the firstbucket:
 *
 *     (
 *          (child[0], key[1], child[1], key[2], child[2], ...,
 *                                       key[len-1], child[len-1]),
 *          self->firstbucket
 *     )
 *
 * In the above, key[i] means self->data[i].key, and similarly for child[i].
 */
923
static PyObject *
924
BTree_getstate(BTree *self)
925
{
926 927 928
    PyObject *r = NULL;
    PyObject *o;
    int i, l;
929

930
    UNLESS (PER_USE(self)) return NULL;
931

932 933 934 935
    if (self->len) {
	r = PyTuple_New(self->len * 2 - 1);
	if (r == NULL)
	    goto err;
936

937 938
	if (self->len == 1
	    && self->data->child->ob_type != self->ob_type
939
#ifdef PERSISTENT
940
	    && BUCKET(self->data->child)->oid == NULL
941
#endif
942 943 944 945 946 947 948
	    ) {
	    /* We have just one bucket. Save its data directly. */
	    o = bucket_getstate((Bucket *)self->data->child);
	    if (o == NULL)
		goto err;
	    PyTuple_SET_ITEM(r, 0, o);
	    ASSIGN(r, Py_BuildValue("(O)", r));
949
        }
950 951 952 953 954 955
        else {
	    for (i=0, l=0; i < self->len; i++) {
		if (i) {
		    COPY_KEY_TO_OBJECT(o, self->data[i].key);
		    PyTuple_SET_ITEM(r, l, o);
		    l++;
956
                }
957 958 959 960
		o = (PyObject *)self->data[i].child;
		Py_INCREF(o);
		PyTuple_SET_ITEM(r,l,o);
		l++;
961
            }
962
	    ASSIGN(r, Py_BuildValue("OO", r, self->firstbucket));
963
        }
964

965
    }
966 967 968
    else {
	r = Py_None;
	Py_INCREF(r);
Tim Peters's avatar
Tim Peters committed
969
    }
970

971
    PER_UNUSE(self);
972

973
    return r;
974

975 976 977 978
 err:
    PER_UNUSE(self);
    Py_XDECREF(r);
    return NULL;
979 980
}

981 982
static int
_BTree_setstate(BTree *self, PyObject *state, int noval)
983
{
984
    PyObject *items, *firstbucket = NULL;
985 986
    BTreeItem *d;
    int len, l, i, copied=1;
987

988
    if (_BTree_clear(self) < 0)
989
	return -1;
990

991 992 993 994 995 996
    /* The state of a BTree can be one of the following:
       None -- an empty BTree
       A one-tuple -- a single bucket btree
       A two-tuple -- a BTree with more than one bucket
       See comments for BTree_getstate() for the details.
    */
997

998 999
    if (state == Py_None)
	return 0;
1000

1001
    if (!PyArg_ParseTuple(state, "O|O:__setstate__", &items, &firstbucket))
1002
	return -1;
1003

1004 1005 1006 1007 1008
    len = PyTuple_Size(items);
    if (len < 0)
	return -1;
    len = (len + 1) / 2;

1009 1010 1011 1012
    assert(len > 0); /* If the BTree is empty, it's state is None. */
    assert(self->size == 0); /* We called _BTree_clear(). */

    self->data = BTree_Malloc(sizeof(BTreeItem) * len);
1013 1014 1015 1016 1017 1018 1019
    if (self->data == NULL)
	return -1;
    self->size = len;

    for (i = 0, d = self->data, l = 0; i < len; i++, d++) {
	PyObject *v;
	if (i) { /* skip the first key slot */
1020
	    COPY_KEY_FROM_ARG(d->key, PyTuple_GET_ITEM(items, l), copied);
1021 1022 1023 1024 1025 1026 1027 1028 1029
	    l++;
	    if (!copied)
		return -1;
	    INCREF_KEY(d->key);
	}
	v = PyTuple_GET_ITEM(items, l);
	if (PyTuple_Check(v)) {
	    /* Handle the special case in __getstate__() for a BTree
	       with a single bucket. */
1030 1031 1032
	    d->child = BTree_newBucket(self);
	    if (!d->child)
		return -1;
1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047
	    if (noval) {
		if (_set_setstate(BUCKET(d->child), v) < 0)
		    return -1;
	    }
	    else {
		if (_bucket_setstate(BUCKET(d->child), v) < 0)
		    return -1;
	    }
	}
	else {
	    d->child = (Sized *)v;
	    Py_INCREF(v);
	}
	l++;
    }
1048

1049
    if (!firstbucket)
1050
	firstbucket = (PyObject *)self->data->child;
1051

1052 1053 1054 1055
    if (!PyObject_IsInstance(firstbucket, (PyObject *)
			     (noval ? &SetType : &BucketType))) {
	PyErr_SetString(PyExc_TypeError,
			"No firstbucket in non-empty BTree");
1056 1057 1058 1059
	return -1;
    }
    self->firstbucket = BUCKET(firstbucket);
    Py_INCREF(firstbucket);
1060 1061 1062 1063 1064 1065
#ifndef PERSISTENT
    /* firstbucket is also the child of some BTree node, but that node may
     * be a ghost if persistence is enabled.
     */
    assert(self->firstbucket->ob_refcnt > 1);
#endif
1066
    self->len = len;
1067

1068
    return 0;
1069 1070 1071
}

static PyObject *
1072
BTree_setstate(BTree *self, PyObject *arg)
1073
{
1074
    int r;
1075

1076 1077 1078
    PER_PREVENT_DEACTIVATION(self);
    r = _BTree_setstate(self, arg, 0);
    PER_UNUSE(self);
1079

1080 1081 1082 1083
    if (r < 0)
	return NULL;
    Py_INCREF(Py_None);
    return Py_None;
1084 1085
}

1086
#ifdef PERSISTENT
1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105

/* Recognize the special cases of a BTree that's empty or contains a single
 * bucket.  In the former case, return a borrowed reference to Py_None.
 * In this single-bucket case, the bucket state is embedded directly in the
 * BTree state, like so:
 *
 *     (
 *         (
 *              thebucket.__getstate__(),
 *         ),
 *     )
 *
 * When this obtains, return a borrowed reference to thebucket.__getstate__().
 * Else return NULL with an exception set.  The exception should always be
 * ConflictError then, but may be TypeError if the state makes no sense at all
 * for a BTree (corrupted or hostile state).
 */
PyObject *
get_bucket_state(PyObject *t)
1106
{
1107 1108 1109 1110 1111 1112 1113
	if (t == Py_None)
		return Py_None;		/* an empty BTree */
	if (! PyTuple_Check(t)) {
		PyErr_SetString(PyExc_TypeError,
			"_p_resolveConflict: expected tuple or None for state");
		return NULL;
	}
1114

1115 1116 1117 1118
	if (PyTuple_GET_SIZE(t) == 2) {
		/* A non-degenerate BTree. */
		return merge_error(-1, -1, -1, 11);
	}
1119

1120
	/* We're in the one-bucket case. */
1121

1122 1123 1124 1125 1126
	if (PyTuple_GET_SIZE(t) != 1) {
		PyErr_SetString(PyExc_TypeError,
			"_p_resolveConflict: expected 1- or 2-tuple for state");
		return NULL;
	}
1127

1128 1129 1130 1131 1132 1133 1134
	t = PyTuple_GET_ITEM(t, 0);
	if (! PyTuple_Check(t) || PyTuple_GET_SIZE(t) != 1) {
		PyErr_SetString(PyExc_TypeError,
			"_p_resolveConflict: expected 1-tuple containing "
			"bucket state");
		return NULL;
	}
1135

1136 1137 1138 1139 1140 1141
	t = PyTuple_GET_ITEM(t, 0);
	if (! PyTuple_Check(t)) {
		PyErr_SetString(PyExc_TypeError,
			"_p_resolveConflict: expected tuple for bucket state");
		return NULL;
	}
1142

1143 1144
	return t;
}
1145

1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173
/* Tricky.  The only kind of BTree conflict we can actually potentially
 * resolve is the special case of a BTree containing a single bucket,
 * in which case this becomes a fancy way of calling the bucket conflict
 * resolution code.
 */
static PyObject *
BTree__p_resolveConflict(BTree *self, PyObject *args)
{
    PyObject *s[3];
    PyObject *x, *y, *z;

    if (!PyArg_ParseTuple(args, "OOO", &x, &y, &z))
	return NULL;

    s[0] = get_bucket_state(x);
    if (s[0] == NULL)
	return NULL;
    s[1] = get_bucket_state(y);
    if (s[1] == NULL)
	return NULL;
    s[2] = get_bucket_state(z);
    if (s[2] == NULL)
	return NULL;

    if (PyObject_IsInstance((PyObject *)self, (PyObject *)&BTreeType))
	x = _bucket__p_resolveConflict(OBJECT(&BucketType), s);
    else
	x = _bucket__p_resolveConflict(OBJECT(&SetType), s);
1174

1175 1176 1177 1178
    if (x == NULL)
	return NULL;

    return Py_BuildValue("((N))", x);
1179 1180
}
#endif
1181 1182 1183

/*
 BTree_findRangeEnd -- Find one end, expressed as a bucket and
1184
 position, for a range search.
1185 1186 1187 1188

 If low, return bucket and index of the smallest item >= key,
 otherwise return bucket and index of the largest item <= key.

1189 1190 1191 1192
 If exclude_equal, exact matches aren't acceptable; if one is found,
 move right if low, or left if !low (this is for range searches exclusive
 of an endpoint).

1193 1194 1195 1196 1197
 Return:
    -1      Error; offset and bucket unchanged
     0      Not found; offset and bucket unchanged
     1      Correct bucket and offset stored; the caller owns a new reference
            to the bucket.
1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235

 Internal:
    We do binary searches in BTree nodes downward, at each step following
    C(i) where K(i) <= key < K(i+1).  As always, K(i) <= C(i) < K(i+1) too.
    (See Maintainer.txt for the meaning of that notation.)  That eventually
    leads to a bucket where we do Bucket_findRangeEnd.  That usually works,
    but there are two cases where it can fail to find the correct answer:

    1. On a low search, we find a bucket with keys >= K(i), but that doesn't
       imply there are keys in the bucket >= key.  For example, suppose
       a bucket has keys in 1..100, its successor's keys are in 200..300, and
       we're doing a low search on 150.  We'll end up in the first bucket,
       but there are no keys >= 150 in it.  K(i+1) > key, though, and all
       the keys in C(i+1) >= K(i+1) > key, so the first key in the next
       bucket (if any) is the correct result.  This is easy to find by
       following the bucket 'next' pointer.

    2. On a high search, again that the keys in the bucket are >= K(i)
       doesn't imply that any key in the bucket is <= key, but it's harder
       for this to fail (and an earlier version of this routine didn't
       catch it):  if K(i) itself is in the bucket, it works (then
       K(i) <= key is *a* key in the bucket that's in the desired range).
       But when keys get deleted from buckets, they aren't also deleted from
       BTree nodes, so there's no guarantee that K(i) is in the bucket.
       For example, delete the smallest key S from some bucket, and S
       remains in the interior BTree nodes.  Do a high search for S, and
       the BTree nodes direct the search to the bucket S used to be in,
       but all keys remaining in that bucket are > S.  The largest key in
       the *preceding* bucket (if any) is < K(i), though, and K(i) <= key,
       so the largest key in the preceding bucket is < key and so is the
       proper result.

       This is harder to get at efficiently, as buckets are linked only in
       the increasing direction.  While we're searching downward,
       deepest_smaller is set to the  node deepest in the tree where
       we *could* have gone to the left of C(i).  The rightmost bucket in
       deepest_smaller's subtree is the bucket preceding the bucket we find
       at first.  This is clumsy to get at, but efficient.
1236 1237
*/
static int
1238
BTree_findRangeEnd(BTree *self, PyObject *keyarg, int low, int exclude_equal,
1239
                   Bucket **bucket, int *offset) {
1240
    Sized *deepest_smaller = NULL;      /* last possibility to move left */
Jeremy Hylton's avatar
Jeremy Hylton committed
1241
    int deepest_smaller_is_btree = 0;   /* Boolean; if false, it's a bucket */
1242 1243 1244 1245 1246 1247
    Bucket *pbucket;
    int self_got_rebound = 0;   /* Boolean; when true, deactivate self */
    int result = -1;            /* Until proven innocent */
    int i;
    KEY_TYPE key;
    int copied = 1;
1248

1249 1250
    COPY_KEY_FROM_ARG(key, keyarg, copied);
    UNLESS (copied) return -1;
1251

1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267
    /* We don't need to: PER_USE_OR_RETURN(self, -1);
       because the caller does. */
    UNLESS (self->data && self->len) return 0;

    /* Search downward until hitting a bucket, stored in pbucket. */
    for (;;) {
        Sized *pchild;
        int pchild_is_btree;

        BTREE_SEARCH(i, self, key, goto Done);
        pchild = self->data[i].child;
        pchild_is_btree = SameType_Check(self, pchild);
        if (i) {
            deepest_smaller = self->data[i-1].child;
            deepest_smaller_is_btree = pchild_is_btree;
        }
1268

1269 1270
        if (pchild_is_btree) {
            if (self_got_rebound) {
1271
                PER_UNUSE(self);
1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283
            }
            self = BTREE(pchild);
            self_got_rebound = 1;
            PER_USE_OR_RETURN(self, -1);
        }
        else {
            pbucket = BUCKET(pchild);
            break;
        }
    }

    /* Search the bucket for a suitable key. */
1284
    i = Bucket_findRangeEnd(pbucket, keyarg, low, exclude_equal, offset);
1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306
    if (i < 0)
        goto Done;
    if (i > 0) {
        Py_INCREF(pbucket);
        *bucket = pbucket;
        result = 1;
        goto Done;
    }
    /* This may be one of the two difficult cases detailed in the comments. */
    if (low) {
        Bucket *next;

        UNLESS(PER_USE(pbucket)) goto Done;
        next = pbucket->next;
        if (next) {
                result = 1;
                Py_INCREF(next);
                *bucket = next;
                *offset = 0;
        }
        else
                result = 0;
1307
        PER_UNUSE(pbucket);
1308 1309 1310 1311
    }
    /* High-end search:  if it's possible to go left, do so. */
    else if (deepest_smaller) {
        if (deepest_smaller_is_btree) {
1312 1313 1314
            UNLESS(PER_USE(deepest_smaller)) goto Done;
            /* We own the reference this returns. */
            pbucket = BTree_lastBucket(BTREE(deepest_smaller));
1315
            PER_UNUSE(deepest_smaller);
1316
            if (pbucket == NULL) goto Done;   /* error */
1317 1318
        }
        else {
1319 1320
            pbucket = BUCKET(deepest_smaller);
            Py_INCREF(pbucket);
1321
        }
1322 1323 1324 1325
        UNLESS(PER_USE(pbucket)) goto Done;
        result = 1;
        *bucket = pbucket;  /* transfer ownership to caller */
        *offset = pbucket->len - 1;
1326
        PER_UNUSE(pbucket);
1327 1328 1329
    }
    else
        result = 0;     /* simply not found */
1330

1331 1332
Done:
    if (self_got_rebound) {
1333
        PER_UNUSE(self);
1334 1335
    }
    return result;
Tim Peters's avatar
Tim Peters committed
1336
}
1337

1338 1339 1340
static PyObject *
BTree_maxminKey(BTree *self, PyObject *args, int min)
{
1341
  PyObject *key=0;
1342 1343
  Bucket *bucket = NULL;
  int offset, rc;
Tim Peters's avatar
Tim Peters committed
1344

1345
  UNLESS (PyArg_ParseTuple(args, "|O", &key)) return NULL;
Tim Peters's avatar
Tim Peters committed
1346

1347
  UNLESS (PER_USE(self)) return NULL;
1348 1349

  UNLESS (self->data && self->len) goto empty;
Tim Peters's avatar
Tim Peters committed
1350

1351
  /* Find the  range */
Tim Peters's avatar
Tim Peters committed
1352 1353

  if (key)
1354
    {
1355
      if ((rc = BTree_findRangeEnd(self, key, min, 0, &bucket, &offset)) <= 0)
1356 1357 1358
        {
          if (rc < 0) goto err;
          goto empty;
Tim Peters's avatar
Tim Peters committed
1359
        }
1360
      PER_UNUSE(self);
1361 1362 1363 1364 1365
      UNLESS (PER_USE(bucket))
        {
          Py_DECREF(bucket);
          return NULL;
        }
1366 1367 1368 1369
    }
  else if (min)
    {
      bucket = self->firstbucket;
1370
      PER_UNUSE(self);
1371
      PER_USE_OR_RETURN(bucket, NULL);
1372
      Py_INCREF(bucket);
1373 1374 1375 1376 1377
      offset = 0;
    }
  else
    {
      bucket = BTree_lastBucket(self);
1378
      PER_UNUSE(self);
1379 1380 1381 1382 1383
      UNLESS (PER_USE(bucket))
        {
          Py_DECREF(bucket);
          return NULL;
        }
1384 1385
      assert(bucket->len);
      offset = bucket->len - 1;
1386
     }
Tim Peters's avatar
Tim Peters committed
1387

1388
  COPY_KEY_TO_OBJECT(key, bucket->keys[offset]);
1389
  PER_UNUSE(bucket);
1390 1391 1392
  Py_DECREF(bucket);

  return key;
Tim Peters's avatar
Tim Peters committed
1393

1394 1395 1396 1397
 empty:
  PyErr_SetString(PyExc_ValueError, "empty tree");

 err:
1398
  PER_UNUSE(self);
Tim Peters's avatar
Tim Peters committed
1399
  if (bucket)
1400
    {
1401
      PER_UNUSE(bucket);
1402 1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413 1414 1415 1416 1417
      Py_DECREF(bucket);
    }
  return NULL;
}

static PyObject *
BTree_minKey(BTree *self, PyObject *args)
{
  return BTree_maxminKey(self, args, 1);
}

static PyObject *
BTree_maxKey(BTree *self, PyObject *args)
{
  return BTree_maxminKey(self, args, 0);
}
1418 1419 1420 1421 1422 1423 1424 1425 1426

/*
** BTree_rangeSearch
**
** Generates a BTreeItems object based on the two indexes passed in,
** being the range between them.
**
*/
static PyObject *
1427
BTree_rangeSearch(BTree *self, PyObject *args, PyObject *kw, char type)
1428
{
1429 1430 1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 1446 1447
    PyObject *min = Py_None;
    PyObject *max = Py_None;
    int excludemin = 0;
    int excludemax = 0;
    int rc;
    Bucket *lowbucket = NULL;
    Bucket *highbucket = NULL;
    int lowoffset;
    int highoffset;
    PyObject *result;

    if (args) {
        if (! PyArg_ParseTupleAndKeywords(args, kw, "|OOii", search_keywords,
  					  &min,
  					  &max,
  					  &excludemin,
  					  &excludemax))
	    return NULL;
    }
1448

1449
    UNLESS (PER_USE(self)) return NULL;
1450

1451
    UNLESS (self->data && self->len) goto empty;
Tim Peters's avatar
Tim Peters committed
1452

1453 1454 1455 1456 1457 1458
    /* Find the low range */
    if (min != Py_None) {
        if ((rc = BTree_findRangeEnd(self, min, 1, excludemin,
        			      &lowbucket, &lowoffset)) <= 0) {
            if (rc < 0) goto err;
            goto empty;
1459
        }
Tim Peters's avatar
Tim Peters committed
1460
    }
1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484
    else {
        lowbucket = self->firstbucket;
        lowoffset = 0;
        if (excludemin) {
            int bucketlen;
            UNLESS (PER_USE(lowbucket)) goto err;
            bucketlen = lowbucket->len;
            PER_UNUSE(lowbucket);
            if (bucketlen > 1)
            	lowoffset = 1;
	    else if (self->len < 2)
	    	goto empty;
            else {	/* move to first item in next bucket */
                Bucket *next;
                UNLESS (PER_USE(lowbucket)) goto err;
                next = lowbucket->next;
                PER_UNUSE(lowbucket);
                assert(next != NULL);
                lowbucket = next;
                /* and lowoffset is still 0 */
                assert(lowoffset == 0);
            }
	}
        Py_INCREF(lowbucket);
1485
    }
Tim Peters's avatar
Tim Peters committed
1486

1487 1488 1489 1490 1491 1492 1493
    /* Find the high range */
    if (max != Py_None) {
        if ((rc = BTree_findRangeEnd(self, max, 0, excludemax,
        			      &highbucket, &highoffset)) <= 0) {
            Py_DECREF(lowbucket);
            if (rc < 0) goto err;
            goto empty;
Tim Peters's avatar
Tim Peters committed
1494
        }
1495
    }
1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519 1520 1521 1522 1523
    else {
    	int bucketlen;
        highbucket = BTree_lastBucket(self);
        assert(highbucket != NULL);  /* we know self isn't empty */
        UNLESS (PER_USE(highbucket)) goto err_and_decref_buckets;
        bucketlen = highbucket->len;
    	PER_UNUSE(highbucket);
        highoffset = bucketlen - 1;
        if (excludemax) {
	    if (highoffset > 0)
	    	--highoffset;
	    else if (self->len < 2)
	    	goto empty_and_decref_buckets;
	    else {	/* move to last item of preceding bucket */
	    	int status;
	    	assert(highbucket != self->firstbucket);
	    	Py_DECREF(highbucket);
	    	status = PreviousBucket(&highbucket, self->firstbucket);
	    	if (status < 0) {
	    	    Py_DECREF(lowbucket);
	    	    goto err;
	    	}
	    	assert(status > 0);
	    	Py_INCREF(highbucket);
	        UNLESS (PER_USE(highbucket)) goto err_and_decref_buckets;
	        highoffset = highbucket->len - 1;
    	    	PER_UNUSE(highbucket);
	    }
1524
        }
1525
    	assert(highoffset >= 0);
1526
    }
Tim Peters's avatar
Tim Peters committed
1527

1528 1529 1530 1531 1532 1533 1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557
    /* It's still possible that the range is empty, even if min < max.  For
     * example, if min=3 and max=4, and 3 and 4 aren't in the BTree, but 2 and
     * 5 are, then the low position points to the 5 now and the high position
     * points to the 2 now.  They're not necessarily even in the same bucket,
     * so there's no trick we can play with pointer compares to get out
     * cheap in general.
     */
    if (lowbucket == highbucket && lowoffset > highoffset)
	goto empty_and_decref_buckets;      /* definitely empty */

    /* The buckets differ, or they're the same and the offsets show a non-
     * empty range.
     */
    if (min != Py_None && max != Py_None && /* both args user-supplied */
        lowbucket != highbucket)   /* and different buckets */ {
        KEY_TYPE first;
        KEY_TYPE last;
        int cmp;

        /* Have to check the hard way:  see how the endpoints compare. */
        UNLESS (PER_USE(lowbucket)) goto err_and_decref_buckets;
        COPY_KEY(first, lowbucket->keys[lowoffset]);
        PER_UNUSE(lowbucket);

        UNLESS (PER_USE(highbucket)) goto err_and_decref_buckets;
        COPY_KEY(last, highbucket->keys[highoffset]);
        PER_UNUSE(highbucket);

        TEST_KEY_SET_OR(cmp, first, last) goto err_and_decref_buckets;
        if (cmp > 0) goto empty_and_decref_buckets;
1558 1559
    }

1560
    PER_UNUSE(self);
Tim Peters's avatar
Tim Peters committed
1561

1562 1563 1564 1565
    result = newBTreeItems(type, lowbucket, lowoffset, highbucket, highoffset);
    Py_DECREF(lowbucket);
    Py_DECREF(highbucket);
    return result;
Tim Peters's avatar
Tim Peters committed
1566

1567
 err_and_decref_buckets:
1568 1569
    Py_DECREF(lowbucket);
    Py_DECREF(highbucket);
1570

1571
 err:
1572 1573
    PER_UNUSE(self);
    return NULL;
1574

1575
 empty_and_decref_buckets:
1576 1577
    Py_DECREF(lowbucket);
    Py_DECREF(highbucket);
1578

1579
 empty:
1580 1581
    PER_UNUSE(self);
    return newBTreeItems(type, 0, 0, 0, 0);
1582 1583 1584 1585 1586 1587
}

/*
** BTree_keys
*/
static PyObject *
1588
BTree_keys(BTree *self, PyObject *args, PyObject *kw)
1589
{
1590
    return BTree_rangeSearch(self, args, kw, 'k');
1591 1592 1593 1594 1595 1596
}

/*
** BTree_values
*/
static PyObject *
1597
BTree_values(BTree *self, PyObject *args, PyObject *kw)
1598
{
1599
    return BTree_rangeSearch(self, args, kw, 'v');
1600 1601 1602 1603 1604 1605
}

/*
** BTree_items
*/
static PyObject *
1606
BTree_items(BTree *self, PyObject *args, PyObject *kw)
1607
{
1608
    return BTree_rangeSearch(self, args, kw, 'i');
1609 1610
}

1611
static PyObject *
1612
BTree_byValue(BTree *self, PyObject *omin)
1613
{
1614
  PyObject *r=0, *o=0, *item=0;
1615 1616
  VALUE_TYPE min;
  VALUE_TYPE v;
1617
  int copied=1;
1618
  SetIteration it = {0, 0, 1};
1619

1620
  UNLESS (PER_USE(self)) return NULL;
1621

1622
  COPY_VALUE_FROM_ARG(min, omin, copied);
1623
  UNLESS(copied) return NULL;
Tim Peters's avatar
Tim Peters committed
1624

1625 1626
  UNLESS (r=PyList_New(0)) goto err;

1627
  it.set=BTree_rangeSearch(self, NULL, NULL, 'i');
1628 1629 1630 1631 1632 1633 1634
  UNLESS(it.set) goto err;

  if (nextBTreeItems(&it) < 0) goto err;

  while (it.position >= 0)
    {
      if (TEST_VALUE(it.value, min) >= 0)
Tim Peters's avatar
Tim Peters committed
1635
        {
1636 1637 1638 1639 1640 1641 1642 1643 1644 1645 1646 1647
          UNLESS (item = PyTuple_New(2)) goto err;

          COPY_KEY_TO_OBJECT(o, it.key);
          UNLESS (o) goto err;
          PyTuple_SET_ITEM(item, 1, o);

          COPY_VALUE(v, it.value);
          NORMALIZE_VALUE(v, min);
          COPY_VALUE_TO_OBJECT(o, v);
          DECREF_VALUE(v);
          UNLESS (o) goto err;
          PyTuple_SET_ITEM(item, 0, o);
Tim Peters's avatar
Tim Peters committed
1648

1649 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665
          if (PyList_Append(r, item) < 0) goto err;
          Py_DECREF(item);
          item = 0;
        }
      if (nextBTreeItems(&it) < 0) goto err;
    }

  item=PyObject_GetAttr(r,sort_str);
  UNLESS (item) goto err;
  ASSIGN(item, PyObject_CallObject(item, NULL));
  UNLESS (item) goto err;
  ASSIGN(item, PyObject_GetAttr(r, reverse_str));
  UNLESS (item) goto err;
  ASSIGN(item, PyObject_CallObject(item, NULL));
  UNLESS (item) goto err;
  Py_DECREF(item);

1666
  finiSetIteration(&it);
1667
  PER_UNUSE(self);
1668 1669 1670
  return r;

 err:
1671
  PER_UNUSE(self);
1672
  Py_XDECREF(r);
1673
  finiSetIteration(&it);
1674 1675 1676 1677
  Py_XDECREF(item);
  return NULL;
}

1678 1679 1680 1681 1682 1683 1684 1685 1686 1687
/*
** BTree_getm
*/
static PyObject *
BTree_getm(BTree *self, PyObject *args)
{
  PyObject *key, *d=Py_None, *r;

  UNLESS (PyArg_ParseTuple(args, "O|O", &key, &d)) return NULL;
  if ((r=_BTree_get(self, key, 0))) return r;
1688
  UNLESS (PyErr_ExceptionMatches(PyExc_KeyError)) return NULL;
1689 1690 1691 1692 1693 1694
  PyErr_Clear();
  Py_INCREF(d);
  return d;
}

static PyObject *
1695
BTree_has_key(BTree *self, PyObject *key)
1696
{
1697 1698 1699 1700 1701 1702 1703 1704 1705 1706 1707 1708 1709 1710 1711 1712
    return _BTree_get(self, key, 1);
}

/* Search BTree self for key.  This is the sq_contains slot of the
 * PySequenceMethods.
 *
 * Return:
 *     -1     error
 *      0     not found
 *      1     found
 */
static int
BTree_contains(BTree *self, PyObject *key)
{
    PyObject *asobj = _BTree_get(self, key, 1);
    int result = -1;
1713

1714 1715 1716 1717 1718
    if (asobj != NULL) {
        result = PyInt_AsLong(asobj) ? 1 : 0;
        Py_DECREF(asobj);
    }
    return result;
1719 1720 1721
}

static PyObject *
1722
BTree_addUnique(BTree *self, PyObject *args)
1723 1724 1725 1726 1727 1728
{
  int grew;
  PyObject *key, *v;

  UNLESS (PyArg_ParseTuple(args, "OO", &key, &v)) return NULL;

1729
  if ((grew=_BTree_set(self, key, v, 1, 0)) < 0) return NULL;
1730 1731 1732
  return PyInt_FromLong(grew);
}

1733 1734 1735 1736 1737 1738 1739 1740 1741 1742 1743 1744 1745 1746 1747 1748 1749 1750 1751 1752 1753 1754 1755 1756 1757 1758 1759 1760 1761 1762 1763 1764 1765 1766 1767 1768 1769 1770 1771 1772 1773 1774 1775 1776 1777 1778 1779 1780 1781 1782 1783 1784 1785
/**************************************************************************/
/* Iterator support. */

/* A helper to build all the iterators for BTrees and TreeSets.
 * If args is NULL, the iterator spans the entire structure.  Else it's an
 * argument tuple, with optional low and high arguments.
 * kind is 'k', 'v' or 'i'.
 * Returns a BTreeIter object, or NULL if error.
 */
static PyObject *
buildBTreeIter(BTree *self, PyObject *args, PyObject *kw, char kind)
{
    BTreeIter *result = NULL;
    BTreeItems *items = (BTreeItems *)BTree_rangeSearch(self, args, kw, kind);

    if (items) {
        result = BTreeIter_new(items);
        Py_DECREF(items);
    }
    return (PyObject *)result;
}

/* The implementation of iter(BTree_or_TreeSet); the BTree tp_iter slot. */
static PyObject *
BTree_getiter(BTree *self)
{
    return buildBTreeIter(self, NULL, NULL, 'k');
}

/* The implementation of BTree.iterkeys(). */
static PyObject *
BTree_iterkeys(BTree *self, PyObject *args, PyObject *kw)
{
    return buildBTreeIter(self, args, kw, 'k');
}

/* The implementation of BTree.itervalues(). */
static PyObject *
BTree_itervalues(BTree *self, PyObject *args, PyObject *kw)
{
    return buildBTreeIter(self, args, kw, 'v');
}

/* The implementation of BTree.iteritems(). */
static PyObject *
BTree_iteritems(BTree *self, PyObject *args, PyObject *kw)
{
    return buildBTreeIter(self, args, kw, 'i');
}

/* End of iterator support. */


1786 1787 1788
/* Caution:  Even though the _firstbucket attribute is read-only, a program
   could do arbitrary damage to the btree internals.  For example, it could
   call clear() on a bucket inside a BTree.
1789 1790 1791 1792 1793 1794 1795 1796 1797

   We need to decide if the convenience for inspecting BTrees is worth
   the risk.
*/

static struct PyMemberDef BTree_members[] = {
    {"_firstbucket", T_OBJECT, offsetof(BTree, firstbucket), RO},
    {NULL}
};
1798 1799

static struct PyMethodDef BTree_methods[] = {
1800 1801 1802 1803 1804 1805 1806 1807 1808 1809 1810 1811 1812 1813 1814 1815 1816 1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831 1832 1833 1834 1835 1836 1837 1838 1839 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 1868 1869 1870
    {"__getstate__", (PyCFunction) BTree_getstate,	METH_NOARGS,
     "__getstate__() -> state\n\n"
     "Return the picklable state of the BTree."},

    {"__setstate__", (PyCFunction) BTree_setstate,	METH_O,
     "__setstate__(state)\n\n"
     "Set the state of the BTree."},

    {"has_key",	(PyCFunction) BTree_has_key,	METH_O,
     "has_key(key)\n\n"
     "Return true if the BTree contains the given key."},

    {"keys",	(PyCFunction) BTree_keys,	METH_KEYWORDS,
     "keys([min, max]) -> list of keys\n\n"
     "Returns the keys of the BTree.  If min and max are supplied, only\n"
     "keys greater than min and less than max are returned."},

    {"values",	(PyCFunction) BTree_values,	METH_KEYWORDS,
     "values([min, max]) -> list of values\n\n"
     "Returns the values of the BTree.  If min and max are supplied, only\n"
     "values corresponding to keys greater than min and less than max are\n"
     "returned."},

    {"items",	(PyCFunction) BTree_items,	METH_KEYWORDS,
     "items([min, max]) -> -- list of key, value pairs\n\n"
     "Returns the items of the BTree.  If min and max are supplied, only\n"
     "items with keys greater than min and less than max are returned."},

    {"byValue",	(PyCFunction) BTree_byValue,	METH_O,
     "byValue(min) ->  list of value, key pairs\n\n"
     "Returns list of value, key pairs where the value is >= min.  The\n"
     "list is sorted by value.  Note that items() returns keys in the\n"
     "opposite order."},

    {"get",	(PyCFunction) BTree_getm,	METH_VARARGS,
     "get(key[, default=None]) -> Value for key or default\n\n"
     "Return the value or the default if the key is not found."},

    {"maxKey", (PyCFunction) BTree_maxKey,	METH_VARARGS,
     "maxKey([max]) -> key\n\n"
     "Return the largest key in the BTree.  If max is specified, return\n"
     "the largest key <= max."},

    {"minKey", (PyCFunction) BTree_minKey,	METH_VARARGS,
     "minKey([mi]) -> key\n\n"
     "Return the smallest key in the BTree.  If min is specified, return\n"
     "the smallest key >= min."},

    {"clear",	(PyCFunction) BTree_clear,	METH_NOARGS,
     "clear()\n\nRemove all of the items from the BTree."},

    {"insert", (PyCFunction)BTree_addUnique, METH_VARARGS,
     "insert(key, value) -> 0 or 1\n\n"
     "Add an item if the key is not already used. Return 1 if the item was\n"
     "added, or 0 otherwise."},

    {"update",	(PyCFunction) Mapping_update,	METH_O,
     "update(collection)\n\n Add the items from the given collection."},

    {"iterkeys", (PyCFunction) BTree_iterkeys,  METH_KEYWORDS,
     "B.iterkeys([min[,max]]) -> an iterator over the keys of B"},

    {"itervalues", (PyCFunction) BTree_itervalues,  METH_KEYWORDS,
     "B.itervalues([min[,max]]) -> an iterator over the values of B"},

    {"iteritems", (PyCFunction) BTree_iteritems,    METH_KEYWORDS,
     "B.iteritems([min[,max]]) -> an iterator over the (key, value) items of B"},

    {"_check", (PyCFunction) BTree_check,       METH_NOARGS,
     "Perform sanity check on BTree, and raise exception if flawed."},

Jim Fulton's avatar
Jim Fulton committed
1871
#ifdef PERSISTENT
1872 1873 1874 1875 1876 1877
    {"_p_resolveConflict", (PyCFunction) BTree__p_resolveConflict,
     METH_VARARGS,
     "_p_resolveConflict() -- Reinitialize from a newly created copy"},

    {"_p_deactivate", (PyCFunction) BTree__p_deactivate,	METH_KEYWORDS,
     "_p_deactivate()\n\nReinitialize from a newly created copy."},
Jim Fulton's avatar
Jim Fulton committed
1878
#endif
1879
    {NULL, NULL}
1880 1881
};

1882 1883 1884 1885 1886 1887 1888 1889 1890 1891 1892 1893 1894 1895
static int
BTree_init(PyObject *self, PyObject *args, PyObject *kwds)
{
    PyObject *v = NULL;

    if (!PyArg_ParseTuple(args, "|O:" MOD_NAME_PREFIX "BTree", &v))
	return -1;

    if (v)
	return update_from_seq(self, v);
    else
	return 0;
}

1896
static void
1897
BTree_dealloc(BTree *self)
1898
{
1899 1900 1901 1902 1903 1904 1905 1906 1907 1908 1909 1910 1911 1912 1913 1914 1915 1916 1917 1918 1919 1920 1921 1922 1923 1924 1925 1926 1927 1928 1929 1930 1931 1932 1933 1934 1935 1936 1937 1938 1939 1940 1941 1942 1943 1944 1945
    if (self->state != cPersistent_GHOST_STATE)
	_BTree_clear(self);
    cPersistenceCAPI->pertype->tp_dealloc((PyObject *)self);
}

static int
BTree_traverse(BTree *self, visitproc visit, void *arg)
{
    int err = 0;
    int i, len;

#define VISIT(SLOT)                             \
    if (SLOT) {                                 \
        err = visit((PyObject *)(SLOT), arg);   \
        if (err)                                \
            goto Done;                          \
    }

    if (self->ob_type == &BTreeType)
	assert(self->ob_type->tp_dictoffset == 0);

    /* Call our base type's traverse function.  Because BTrees are
     * subclasses of Peristent, there must be one.
     */
    err = cPersistenceCAPI->pertype->tp_traverse((PyObject *)self, visit, arg);
    if (err)
	goto Done;

    /* If this is registered with the persistence system, cleaning up cycles
     * is the database's problem.  It would be horrid to unghostify BTree
     * nodes here just to chase pointers every time gc runs.
     */
    if (self->state == cPersistent_GHOST_STATE)
	goto Done;

    len = self->len;
#ifdef KEY_TYPE_IS_PYOBJECT
    /* Keys are Python objects so need to be traversed.  Note that the
     * key 0 slot is unused and should not be traversed.
     */
    for (i = 1; i < len; i++)
        VISIT(self->data[i].key);
#endif

    /* Children are always pointers, and child 0 is legit. */
    for (i = 0; i < len; i++)
        VISIT(self->data[i].child);
1946

1947
    VISIT(self->firstbucket);
1948

1949 1950 1951 1952 1953 1954 1955 1956 1957 1958 1959 1960
Done:
    return err;

#undef VISIT
}

static int
BTree_tp_clear(BTree *self)
{
    if (self->state != cPersistent_GHOST_STATE)
	_BTree_clear(self);
    return 0;
1961 1962
}

1963 1964 1965 1966 1967 1968 1969 1970 1971 1972 1973 1974 1975 1976 1977
/*
 * Return the number of elements in a BTree.  nonzero is a Boolean, and
 * when true requests just a non-empty/empty result.  Testing for emptiness
 * is efficient (constant-time).  Getting the true length takes time
 * proportional to the number of leaves (buckets).
 *
 * Return:
 *     When nonzero true:
 *          -1  error
 *           0  empty
 *           1  not empty
 *     When nonzero false (possibly expensive!):
 *          -1  error
 *        >= 0  number of elements.
 */
1978 1979 1980
static int
BTree_length_or_nonzero(BTree *self, int nonzero)
{
1981 1982 1983
    int result;
    Bucket *b;
    Bucket *next;
Tim Peters's avatar
Tim Peters committed
1984

1985 1986 1987 1988 1989
    PER_USE_OR_RETURN(self, -1);
    b = self->firstbucket;
    PER_UNUSE(self);
    if (nonzero)
        return b != NULL;
1990

1991 1992 1993 1994 1995 1996 1997
    result = 0;
    while (b) {
        PER_USE_OR_RETURN(b, -1);
        result += b->len;
        next = b->next;
        PER_UNUSE(b);
        b = next;
1998
    }
1999
    return result;
2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013
}

static int
BTree_length( BTree *self)
{
  return BTree_length_or_nonzero(self, 0);
}

static PyMappingMethods BTree_as_mapping = {
  (inquiry)BTree_length,		/*mp_length*/
  (binaryfunc)BTree_get,		/*mp_subscript*/
  (objobjargproc)BTree_setitem,	        /*mp_ass_subscript*/
};

2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 2024 2025 2026
static PySequenceMethods BTree_as_sequence = {
    (inquiry)0,                     /* sq_length */
    (binaryfunc)0,                  /* sq_concat */
    (intargfunc)0,                  /* sq_repeat */
    (intargfunc)0,                  /* sq_item */
    (intintargfunc)0,               /* sq_slice */
    (intobjargproc)0,               /* sq_ass_item */
    (intintobjargproc)0,            /* sq_ass_slice */
    (objobjproc)BTree_contains,     /* sq_contains */
    0,                              /* sq_inplace_concat */
    0,                              /* sq_inplace_repeat */
};

2027
static int
2028
BTree_nonzero(BTree *self)
2029 2030 2031 2032 2033 2034 2035 2036
{
  return BTree_length_or_nonzero(self, 1);
}

static PyNumberMethods BTree_as_number_for_nonzero = {
  0,0,0,0,0,0,0,0,0,0,
  (inquiry)BTree_nonzero};

2037 2038 2039 2040 2041 2042 2043 2044 2045 2046 2047 2048 2049 2050 2051 2052 2053 2054 2055 2056 2057 2058 2059 2060 2061 2062 2063 2064 2065 2066 2067 2068 2069 2070 2071 2072 2073 2074 2075 2076 2077
static PyTypeObject BTreeType = {
    PyObject_HEAD_INIT(NULL) /* PyPersist_Type */
    0,					/* ob_size */
    MODULE_NAME MOD_NAME_PREFIX "BTree",/* tp_name */
    sizeof(BTree),			/* tp_basicsize */
    0,					/* tp_itemsize */
    (destructor)BTree_dealloc,		/* tp_dealloc */
    0,					/* tp_print */
    0,					/* tp_getattr */
    0,					/* tp_setattr */
    0,					/* tp_compare */
    0,					/* tp_repr */
    &BTree_as_number_for_nonzero,	/* tp_as_number */
    &BTree_as_sequence,			/* tp_as_sequence */
    &BTree_as_mapping,			/* 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 | Py_TPFLAGS_HAVE_GC |
	    Py_TPFLAGS_BASETYPE, 	/* tp_flags */
    0,					/* tp_doc */
    (traverseproc)BTree_traverse,	/* tp_traverse */
    (inquiry)BTree_tp_clear,		/* tp_clear */
    0,					/* tp_richcompare */
    0,					/* tp_weaklistoffset */
    (getiterfunc)BTree_getiter,		/* tp_iter */
    0,					/* tp_iternext */
    BTree_methods,			/* tp_methods */
    BTree_members,			/* tp_members */
    0,					/* tp_getset */
    0,					/* tp_base */
    0,					/* tp_dict */
    0,					/* tp_descr_get */
    0,					/* tp_descr_set */
    0,					/* tp_dictoffset */
    BTree_init,				/* tp_init */
    0,					/* tp_alloc */
    0, /*PyType_GenericNew,*/		/* tp_new */
2078
};