key S in a bucket in a BTree is deleted, doing a range search on the
BTree with S on the high end may claim that the range is empty even when
it's not.  It proved difficult to fix this correctly and efficiently in
all cases (our BTrees don't like "searching backwards").  The
implementation here is a new and non-recursive one (in effect, to do
this efficiently you have to remember the deepest point in the tree where
it was *possible* to "go one left" of where binary search tells you to go;
an iterative algorithm makes that part all but obvious).  Alas, the
number of uses of persistence macros is amazing, unfortunately making
this still-hairy algorithm hard to follow.

testPathologicalRangeSearch():  uncommented the lines that failed
before this patch.  They pass now.

Insecurity:  The test case only exercises the simplest possible form
of the failure.  Any failing case is hard to provoke, even the simplest.
The hairier failing cases require generating degenerate trees, deep
and with some interior nodes near the top having just one or two children
(since the tree needs to be deep too, that isn't easy to provoke).  I'll
think about how to provoke this without needing to build up multi-million
element trees first; maybe using __setstate__ directly is the answer.

references, what must not be and what may be a ghost, and exactly what
"last" means, it was surprisingly unclear).  Also simplified the
implementation (to my eyes -- it's arguable, but I'm the one working
on it, so my eyes count <wink>).  I believe this routine is key to
fixing the range-search bug efficiently.

commented out for now, because it fails.  I'm working on a fix.  The
problem was found by eyeballing the range-test implementation.  If you
delete a key from a BTree that just happens to be the first key in a
bucket, then a later high-end range search giving that specific key as
the endpoint claims that no keys are in the range, and whether or not
that's actually true.

so makes the full suite brittle.  Cleaned out all the places where unit
tests change sys.path.  (Use the PYTHONPATH environment variable instead.)

Also brought SearchIndex tests up to date, which I didn't really need to do
since SearchIndex is deprecated, but I did it as part of figuring out the
failed Interface tests, so I might as well check in my work. ;-)  One of the
test modules in SearchIndex forgets to define a global named "Dummy",
actually, so all the tests were failing before this checkin anyway.

Reindent MUCH_RING_CHECKING test.

Ignore invalidations on objects where _p_oid is None.
In other places, assert the _p_oid is not None.

Also, add whitespace in a bunch of places.

on Mac OS Roman Numeral <wink>.  The prototypes sorters.c needs here
should be supplied by <stdlib.h> anyway, which is also being included.

caller was compensating for this, others weren't, easier to fix the
routine than its callers (it's unexpected that an error return may
require the caller to decref an output argument).  Noted but did not
yet fix what looks to be a subtle algorithmic problem that can result
in a bad answer in an unlikely (but possible) case.

Do not encode the file position in the transaction id used for undo.
An attacker could construct a pickle with a bogus transaction record
in its binary data, deduce the position of the pickle in the file from
the undo log, then submit an undo with a bogus file position that
caused the pickle to get written as a regular data record.  Bad stuff.

The new implementation uses a straight linear search backwards from
the most recent transaction header.

directly without doing the unghostification dance.  Repaired to cache
the child length once in a local vrbl, bracketed by the right
persistence stuff.

an error return.

error return let a newly allocated object leak; curiously, there was
one more of these in the Zope3 version of the code than on the trunk.

If MUCH_RING_CHECKING is not defined (the default), then:
  - use a macro for OBJECT_FROM_RING() instead of a function call, and
  - define IS_RING_CORRUPT() to be constant 0.

XXX Sometime before Zope 2.6 final we should probably remove the
MUCH_RING_CHECKING and ENGINE_NOISE code entirely.

finish the persistence dance.

code and slashed nesting depth, but no semantic changes yet.

In the TRACE_REFS version of the code, call _Py_NewReference() instead
of INCREF to bump the refcount from zero to one.

When exiting the function, don't DECREF the object back to zero
refcount, as that will reinvoke the object's deallocation function.
XXX Why did this ever work?

and Zope3 branch versions of this function.  No semantic change.

to figure out to fix the off-by-1 bug in BTreeItems_slice().

"next" functions, these can return a PER_USE() error *after* decrefing
the keys and values left over from the last call.  But they don't mark
the iteration as terminated, so finiSetIteration() will also try to
decref the leftovers.  The fix is to mark the iteration as terminated
when these functions fail.

"BTreeItems slice contains 1 too many elements"
This also fixes many related glitches, such as that giving an
out-of-bound slice index raised IndexError instead of clipping.

BTreeItems_slice():  Emulate Python slicing semantics in all cases.

testBTrees.py:  new testSlicing() tests in MappingBase and NormalSetTests
to ensure that slicing of .keys()/.items()/.values() works exactly the
same way as slicing of Python lists, in all one-sided, two-sided and
whole-structure ([:]) cases, with both negative and positive slice indices,
and mixtures of + and -, and whether in bounds or out of bounds.

+ Documented the arguments.
+ Used BUCKET_SEARCH.
+ Vastly reduced nesting.
+ Changed the "*changed" argument to get set true whenever PER_CHANGED
  is called, i.e. whenever the bucket mutates.  The purpose of *changed
  wasn't documented, and its only use was in the BTree set routine, which
  is known to have at least one bug.  So it wasn't clear what the purpose
  of *changed was.  What it did do is get set true if and only if the
  key was found in the bucket and its value was replaced, and I couldn't
  imagine a plausible reason for why the BTree set routine could care
  about that alone (all other calls to _bucket_set pass NULL, so there
  were no other clues).
+ Fixed all places where error returns didn't finish the persistence
  dance.

micro-optimized BUCKET_SEARCH macro.  Change _bucket_get() to use
it (more later).

way out of date (prints stuff and asserts instead of raising unittest
failures).

does.