diff options
author | Raymond Hettinger <python@rcn.com> | 2004-10-01 06:24:12 (GMT) |
---|---|---|
committer | Raymond Hettinger <python@rcn.com> | 2004-10-01 06:24:12 (GMT) |
commit | 61f05fb96d17e60272bea6557125d8dc10c48a3f (patch) | |
tree | 672bb5eca05e79797916001ccddf74ece301b954 /Modules/collectionsmodule.c | |
parent | cf8997f6f8be3d5feae2bd66de12b975d63d9bf5 (diff) | |
download | cpython-61f05fb96d17e60272bea6557125d8dc10c48a3f.zip cpython-61f05fb96d17e60272bea6557125d8dc10c48a3f.tar.gz cpython-61f05fb96d17e60272bea6557125d8dc10c48a3f.tar.bz2 |
* Elaborate on the invariant comments and make them more precise.
* Change the centering by one to make it possible to test the module
with BLOCKLEN's as low as two. Testing small blocks makes end-point
errors surface more readily.
Diffstat (limited to 'Modules/collectionsmodule.c')
-rw-r--r-- | Modules/collectionsmodule.c | 42 |
1 files changed, 28 insertions, 14 deletions
diff --git a/Modules/collectionsmodule.c b/Modules/collectionsmodule.c index 196cbe2..188b239 100644 --- a/Modules/collectionsmodule.c +++ b/Modules/collectionsmodule.c @@ -8,20 +8,33 @@ */ #define BLOCKLEN 46 +#define CENTER ((BLOCKLEN - 1) / 2) /* A `dequeobject` is composed of a doubly-linked list of `block` nodes. * This list is not circular (the leftmost block has leftlink==NULL, * and the rightmost block has rightlink==NULL). A deque d's first * element is at d.leftblock[leftindex] and its last element is at * d.rightblock[rightindex]; note that, unlike as for Python slice - * indices, these indices are inclusive on both ends. - * The list of blocks is never empty. An empty deque d has - * d.leftblock == d.rightblock != NULL; d.len == 0; and - * d.leftindex > d.rightindex; checking for d.len == 0 is the intended - * way to see whether d is empty. - * Note that since d.leftindex and d.rightindex may be indices into - * distinct blocks (and certainly are, for any d with len(d) > BLOCKLEN), - * it's not generally true that d.leftindex <= d.rightindex. + * indices, these indices are inclusive on both ends. By being inclusive + * on both ends, algorithms for left and right operations become + * symmetrical which simplifies the design. + * + * The list of blocks is never empty, so d.leftblock and d.rightblock + * are never equal to NULL. + * + * The indices, d.leftindex and d.rightindex are always in the range + * 0 <= index < BLOCKLEN. + * + * Empty deques have d.len == 0; d.leftblock==d.rightblock; + * d.leftindex == CENTER+1; and d.rightindex == CENTER. + * Checking for d.len == 0 is the intended way to see whether d is empty. + * + * Whenever d.leftblock == d.rightblock, + * d.leftindex + d.len == d.rightindex + 1. + * + * However, when d.leftblock != rightblock, d.leftindex and d.rightindex + * are indices into distinct blocks and have no relationship to one + * another (for example, sometimes d.leftindex > d.rightindex). */ typedef struct BLOCK { @@ -71,10 +84,11 @@ deque_new(PyTypeObject *type, PyObject *args, PyObject *kwds) return NULL; } + assert(BLOCKLEN >= 2); deque->leftblock = b; deque->rightblock = b; - deque->leftindex = BLOCKLEN / 2 + 1; - deque->rightindex = BLOCKLEN / 2; + deque->leftindex = CENTER + 1; + deque->rightindex = CENTER; deque->len = 0; deque->weakreflist = NULL; @@ -142,8 +156,8 @@ deque_pop(dequeobject *deque, PyObject *unused) assert(deque->leftblock == deque->rightblock); assert(deque->leftindex == deque->rightindex+1); /* re-center instead of freeing a block */ - deque->leftindex = BLOCKLEN / 2 + 1; - deque->rightindex = BLOCKLEN / 2; + deque->leftindex = CENTER + 1; + deque->rightindex = CENTER; } else { prevblock = deque->rightblock->leftlink; assert(deque->leftblock != deque->rightblock); @@ -177,8 +191,8 @@ deque_popleft(dequeobject *deque, PyObject *unused) assert(deque->leftblock == deque->rightblock); assert(deque->leftindex == deque->rightindex+1); /* re-center instead of freeing a block */ - deque->leftindex = BLOCKLEN / 2 + 1; - deque->rightindex = BLOCKLEN / 2; + deque->leftindex = CENTER + 1; + deque->rightindex = CENTER; } else { assert(deque->leftblock != deque->rightblock); prevblock = deque->leftblock->rightlink; |