[Python-checkins] CVS: python/dist/src/Objects listobject.c,2.90,2.91
Guido van Rossum
gvanrossum@users.sourceforge.net
Wed, 17 Jan 2001 14:12:02 -0800
Update of /cvsroot/python/python/dist/src/Objects
In directory usw-pr-cvs1:/tmp/cvs-serv20814
Modified Files:
listobject.c
Log Message:
Convert to rich comparisons:
- sort's docompare() calls RichCompare(Py_LT).
- list_contains(), list_index(), listcount(), listremove() call
RichCompare(Py_EQ).
- Get rid of list_compare(), in favor of new list_richcompare(). The
latter does some nice shortcuts, like when == or != is requested, it
first compares the lengths for trivial accept/reject. Then it goes
over the items until it finds an index where the items differe; then
it does more shortcut magic to minimize the number of additional
comparisons.
- Aligned the comments for large struct initializers.
Index: listobject.c
===================================================================
RCS file: /cvsroot/python/python/dist/src/Objects/listobject.c,v
retrieving revision 2.90
retrieving revision 2.91
diff -C2 -r2.90 -r2.91
*** listobject.c 2001/01/03 22:32:16 2.90
--- listobject.c 2001/01/17 22:11:59 2.91
***************
*** 247,263 ****
static int
- list_compare(PyListObject *v, PyListObject *w)
- {
- int i;
-
- for (i = 0; i < v->ob_size && i < w->ob_size; i++) {
- int cmp = PyObject_Compare(v->ob_item[i], w->ob_item[i]);
- if (cmp != 0)
- return cmp;
- }
- return v->ob_size - w->ob_size;
- }
-
- static int
list_length(PyListObject *a)
{
--- 247,250 ----
***************
*** 270,280 ****
list_contains(PyListObject *a, PyObject *el)
{
! int i, cmp;
for (i = 0; i < a->ob_size; ++i) {
! cmp = PyObject_Compare(el, PyList_GET_ITEM(a, i));
! if (cmp == 0)
return 1;
! if (PyErr_Occurred())
return -1;
}
--- 257,268 ----
list_contains(PyListObject *a, PyObject *el)
{
! int i;
for (i = 0; i < a->ob_size; ++i) {
! int cmp = PyObject_RichCompareBool(el, PyList_GET_ITEM(a, i),
! Py_EQ);
! if (cmp > 0)
return 1;
! else if (cmp < 0)
return -1;
}
***************
*** 726,733 ****
if (compare == NULL) {
! i = PyObject_Compare(x, y);
! if (i && PyErr_Occurred())
! i = CMPERROR;
! return i;
}
--- 714,727 ----
if (compare == NULL) {
! /* NOTE: we rely on the fact here that the sorting algorithm
! only ever checks whether k<0, i.e., whether x<y. So we
! invoke the rich comparison function with Py_LT ('<'), and
! return -1 when it returns true and 0 when it returns
! false. */
! i = PyObject_RichCompareBool(x, y, Py_LT);
! if (i < 0)
! return CMPERROR;
! else
! return -i;
}
***************
*** 1345,1351 ****
return NULL;
for (i = 0; i < self->ob_size; i++) {
! if (PyObject_Compare(self->ob_item[i], v) == 0)
return PyInt_FromLong((long)i);
! if (PyErr_Occurred())
return NULL;
}
--- 1339,1346 ----
return NULL;
for (i = 0; i < self->ob_size; i++) {
! int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
! if (cmp > 0)
return PyInt_FromLong((long)i);
! else if (cmp < 0)
return NULL;
}
***************
*** 1364,1370 ****
return NULL;
for (i = 0; i < self->ob_size; i++) {
! if (PyObject_Compare(self->ob_item[i], v) == 0)
count++;
! if (PyErr_Occurred())
return NULL;
}
--- 1359,1366 ----
return NULL;
for (i = 0; i < self->ob_size; i++) {
! int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
! if (cmp > 0)
count++;
! else if (cmp < 0)
return NULL;
}
***************
*** 1381,1385 ****
return NULL;
for (i = 0; i < self->ob_size; i++) {
! if (PyObject_Compare(self->ob_item[i], v) == 0) {
if (list_ass_slice(self, i, i+1,
(PyObject *)NULL) != 0)
--- 1377,1382 ----
return NULL;
for (i = 0; i < self->ob_size; i++) {
! int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
! if (cmp > 0) {
if (list_ass_slice(self, i, i+1,
(PyObject *)NULL) != 0)
***************
*** 1388,1392 ****
return Py_None;
}
! if (PyErr_Occurred())
return NULL;
}
--- 1385,1389 ----
return Py_None;
}
! else if (cmp < 0)
return NULL;
}
***************
*** 1419,1422 ****
--- 1416,1491 ----
}
+ static PyObject *
+ list_richcompare(PyObject *v, PyObject *w, int op)
+ {
+ PyListObject *vl, *wl;
+ int i;
+
+ if (!PyList_Check(v) || !PyList_Check(w)) {
+ Py_INCREF(Py_NotImplemented);
+ return Py_NotImplemented;
+ }
+
+ vl = (PyListObject *)v;
+ wl = (PyListObject *)w;
+
+ if (vl->ob_size != wl->ob_size && (op == Py_EQ || op == Py_NE)) {
+ /* Shortcut: if the lengths differ, the lists differ */
+ PyObject *res;
+ if (op == Py_EQ)
+ res = Py_False;
+ else
+ res = Py_True;
+ Py_INCREF(res);
+ return res;
+ }
+
+ /* Search for the first index where items are different */
+ for (i = 0; i < vl->ob_size && i < wl->ob_size; i++) {
+ int k = PyObject_RichCompareBool(vl->ob_item[i],
+ wl->ob_item[i], Py_EQ);
+ if (k < 0)
+ return NULL;
+ if (!k)
+ break;
+ }
+
+ if (i >= vl->ob_size || i >= wl->ob_size) {
+ /* No more items to compare -- compare sizes */
+ int vs = vl->ob_size;
+ int ws = wl->ob_size;
+ int cmp;
+ PyObject *res;
+ switch (op) {
+ case Py_LT: cmp = vs < ws; break;
+ case Py_LE: cmp = ws <= ws; break;
+ case Py_EQ: cmp = vs == ws; break;
+ case Py_NE: cmp = vs != ws; break;
+ case Py_GT: cmp = vs > ws; break;
+ case Py_GE: cmp = vs >= ws; break;
+ default: return NULL; /* cannot happen */
+ }
+ if (cmp)
+ res = Py_True;
+ else
+ res = Py_False;
+ Py_INCREF(res);
+ return res;
+ }
+
+ /* We have an item that differs -- shortcuts for EQ/NE */
+ if (op == Py_EQ) {
+ Py_INCREF(Py_False);
+ return Py_False;
+ }
+ if (op == Py_NE) {
+ Py_INCREF(Py_True);
+ return Py_True;
+ }
+
+ /* Compare the final item again using the proper operator */
+ return PyObject_RichCompare(vl->ob_item[i], wl->ob_item[i], op);
+ }
+
static char append_doc[] =
"L.append(object) -- append object to end";
***************
*** 1439,1451 ****
static PyMethodDef list_methods[] = {
! {"append", (PyCFunction)listappend, METH_VARARGS, append_doc},
! {"insert", (PyCFunction)listinsert, METH_VARARGS, insert_doc},
! {"extend", (PyCFunction)listextend, METH_VARARGS, extend_doc},
! {"pop", (PyCFunction)listpop, METH_VARARGS, pop_doc},
! {"remove", (PyCFunction)listremove, METH_VARARGS, remove_doc},
! {"index", (PyCFunction)listindex, METH_VARARGS, index_doc},
! {"count", (PyCFunction)listcount, METH_VARARGS, count_doc},
{"reverse", (PyCFunction)listreverse, METH_VARARGS, reverse_doc},
! {"sort", (PyCFunction)listsort, METH_VARARGS, sort_doc},
{NULL, NULL} /* sentinel */
};
--- 1508,1520 ----
static PyMethodDef list_methods[] = {
! {"append", (PyCFunction)listappend, METH_VARARGS, append_doc},
! {"insert", (PyCFunction)listinsert, METH_VARARGS, insert_doc},
! {"extend", (PyCFunction)listextend, METH_VARARGS, extend_doc},
! {"pop", (PyCFunction)listpop, METH_VARARGS, pop_doc},
! {"remove", (PyCFunction)listremove, METH_VARARGS, remove_doc},
! {"index", (PyCFunction)listindex, METH_VARARGS, index_doc},
! {"count", (PyCFunction)listcount, METH_VARARGS, count_doc},
{"reverse", (PyCFunction)listreverse, METH_VARARGS, reverse_doc},
! {"sort", (PyCFunction)listsort, METH_VARARGS, sort_doc},
{NULL, NULL} /* sentinel */
};
***************
*** 1458,1471 ****
static PySequenceMethods list_as_sequence = {
! (inquiry)list_length, /*sq_length*/
! (binaryfunc)list_concat, /*sq_concat*/
! (intargfunc)list_repeat, /*sq_repeat*/
! (intargfunc)list_item, /*sq_item*/
! (intintargfunc)list_slice, /*sq_slice*/
! (intobjargproc)list_ass_item, /*sq_ass_item*/
! (intintobjargproc)list_ass_slice, /*sq_ass_slice*/
! (objobjproc)list_contains, /*sq_contains*/
! (binaryfunc)list_inplace_concat, /*sq_inplace_concat*/
! (intargfunc)list_inplace_repeat, /*sq_inplace_repeat*/
};
--- 1527,1540 ----
static PySequenceMethods list_as_sequence = {
! (inquiry)list_length, /* sq_length */
! (binaryfunc)list_concat, /* sq_concat */
! (intargfunc)list_repeat, /* sq_repeat */
! (intargfunc)list_item, /* sq_item */
! (intintargfunc)list_slice, /* sq_slice */
! (intobjargproc)list_ass_item, /* sq_ass_item */
! (intintobjargproc)list_ass_slice, /* sq_ass_slice */
! (objobjproc)list_contains, /* sq_contains */
! (binaryfunc)list_inplace_concat, /* sq_inplace_concat */
! (intargfunc)list_inplace_repeat, /* sq_inplace_repeat */
};
***************
*** 1476,1498 ****
sizeof(PyListObject) + PyGC_HEAD_SIZE,
0,
! (destructor)list_dealloc, /*tp_dealloc*/
! (printfunc)list_print, /*tp_print*/
! (getattrfunc)list_getattr, /*tp_getattr*/
! 0, /*tp_setattr*/
! (cmpfunc)list_compare, /*tp_compare*/
! (reprfunc)list_repr, /*tp_repr*/
! 0, /*tp_as_number*/
! &list_as_sequence, /*tp_as_sequence*/
! 0, /*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_GC, /*tp_flags*/
! 0, /* tp_doc */
! (traverseproc)list_traverse, /* tp_traverse */
! (inquiry)list_clear, /* tp_clear */
};
--- 1545,1568 ----
sizeof(PyListObject) + PyGC_HEAD_SIZE,
0,
! (destructor)list_dealloc, /* tp_dealloc */
! (printfunc)list_print, /* tp_print */
! (getattrfunc)list_getattr, /* tp_getattr */
! 0, /* tp_setattr */
! 0, /* tp_compare */
! (reprfunc)list_repr, /* tp_repr */
! 0, /* tp_as_number */
! &list_as_sequence, /* tp_as_sequence */
! 0, /* 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_GC, /* tp_flags */
! 0, /* tp_doc */
! (traverseproc)list_traverse, /* tp_traverse */
! (inquiry)list_clear, /* tp_clear */
! list_richcompare, /* tp_richcompare */
};
***************
*** 1537,1548 ****
static PySequenceMethods immutable_list_as_sequence = {
! (inquiry)list_length, /*sq_length*/
! (binaryfunc)list_concat, /*sq_concat*/
! (intargfunc)list_repeat, /*sq_repeat*/
! (intargfunc)list_item, /*sq_item*/
! (intintargfunc)list_slice, /*sq_slice*/
! (intobjargproc)immutable_list_ass, /*sq_ass_item*/
! (intintobjargproc)immutable_list_ass, /*sq_ass_slice*/
! (objobjproc)list_contains, /*sq_contains*/
};
--- 1607,1618 ----
static PySequenceMethods immutable_list_as_sequence = {
! (inquiry)list_length, /* sq_length */
! (binaryfunc)list_concat, /* sq_concat */
! (intargfunc)list_repeat, /* sq_repeat */
! (intargfunc)list_item, /* sq_item */
! (intintargfunc)list_slice, /* sq_slice */
! (intobjargproc)immutable_list_ass, /* sq_ass_item */
! (intintobjargproc)immutable_list_ass, /* sq_ass_slice */
! (objobjproc)list_contains, /* sq_contains */
};
***************
*** 1553,1573 ****
sizeof(PyListObject) + PyGC_HEAD_SIZE,
0,
! 0, /*tp_dealloc*/ /* Cannot happen */
! (printfunc)list_print, /*tp_print*/
! (getattrfunc)immutable_list_getattr, /*tp_getattr*/
! 0, /*tp_setattr*/
! 0, /*tp_compare*/ /* Won't be called */
! (reprfunc)list_repr, /*tp_repr*/
! 0, /*tp_as_number*/
! &immutable_list_as_sequence, /*tp_as_sequence*/
! 0, /*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_GC, /*tp_flags*/
! 0, /* tp_doc */
! (traverseproc)list_traverse, /* tp_traverse */
};
--- 1623,1646 ----
sizeof(PyListObject) + PyGC_HEAD_SIZE,
0,
! 0, /* Cannot happen */ /* tp_dealloc */
! (printfunc)list_print, /* tp_print */
! (getattrfunc)immutable_list_getattr, /* tp_getattr */
! 0, /* tp_setattr */
! 0, /* Won't be called */ /* tp_compare */
! (reprfunc)list_repr, /* tp_repr */
! 0, /* tp_as_number */
! &immutable_list_as_sequence, /* tp_as_sequence */
! 0, /* 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_GC, /* tp_flags */
! 0, /* tp_doc */
! (traverseproc)list_traverse, /* tp_traverse */
! 0, /* tp_clear */
! list_richcompare, /* tp_richcompare */
! /* NOTE: This is *not* the standard list_type struct! */
};