summaryrefslogtreecommitdiffstats
path: root/Modules/collectionsmodule.c
diff options
context:
space:
mode:
authorRaymond Hettinger <python@rcn.com>2004-10-01 06:24:12 (GMT)
committerRaymond Hettinger <python@rcn.com>2004-10-01 06:24:12 (GMT)
commit61f05fb96d17e60272bea6557125d8dc10c48a3f (patch)
tree672bb5eca05e79797916001ccddf74ece301b954 /Modules/collectionsmodule.c
parentcf8997f6f8be3d5feae2bd66de12b975d63d9bf5 (diff)
downloadcpython-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.c42
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;