[Patches] Tkinter _flatten speedup

Fredrik Lundh Fredrik Lundh" <effbot@telia.com
Sun, 18 Jun 2000 17:00:18 +0200


This is a multi-part message in MIME format.

------=_NextPart_000_0079_01BFD946.AE0EB200
Content-Type: text/plain;
	charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable

[as discussed on python-dev]

this patch adds a fast _flatten function to the _tkinter
module, and imports it from Tkinter.py (if available).

this speeds up canvas operations like create_line and
create_polygon.  for example, a create_line with 5000
vertices runs about 50 times faster with this patch in
place.

</F>

I confirm that, to the best of my knowledge and belief, this
contribution is free of any claims of third parties under copyright,
patent or other rights or interests ("claims").  To the extent that I
have any such claims, I hereby grant to CNRI a nonexclusive,
irrevocable, royalty-free, worldwide license to reproduce, distribute,
perform and/or display publicly, prepare derivative versions, and
otherwise use this contribution as part of the Python software and its
related documentation, or any derivative versions thereof, at no cost to
CNRI or its licensed users, and to authorize others to do so.

I acknowledge that CNRI may, at its sole discretion, decide whether or
not to incorporate this contribution in the Python software and its
related documentation.  I further grant CNRI permission to use my name
and other identifying information provided to CNRI by me for use in
connection with the Python software and its related documentation.



------=_NextPart_000_0079_01BFD946.AE0EB200
Content-Type: text/plain;
	name="tkinter-patch.txt"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: attachment;
	filename="tkinter-patch.txt"

Index: Modules/_tkinter.c
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
RCS file: /cvsroot/python/python/dist/src/Modules/_tkinter.c,v
retrieving revision 1.99
diff -u -r1.99 _tkinter.c
--- Modules/_tkinter.c	2000/05/04 15:55:17	1.99
+++ Modules/_tkinter.c	2000/06/18 14:36:36
@@ -1978,6 +1982,105 @@
 =0C
 /**** Tkinter Module ****/
=20
+typedef struct {
+	PyObject* tuple;
+	int size; /* current size */
+	int maxsize; /* allocated size */
+} FlattenContext;
+
+static int
+_bump(FlattenContext* context, int size)
+{
+	/* expand tuple to hold (at least) size new items.	return true if
+	   successful, false if an exception was raised*/
+
+	int maxsize =3D context->maxsize * 2;
+
+	if (maxsize < context->size + size)
+		maxsize =3D context->size + size;
+
+	context->maxsize =3D maxsize;
+
+	return _PyTuple_Resize(&context->tuple, maxsize, 0) >=3D 0;
+}
+
+static int
+_flatten1(FlattenContext* context, PyObject* item)
+{
+	/* add tuple or list to argument tuple (recursively) */
+
+	int i, size;
+
+	if (PyList_Check(item)) {
+		size =3D PyList_GET_SIZE(item);
+		/* preallocate (assume no nesting) */
+		if (context->size + size > context->maxsize && !_bump(context, size))
+			return 0;
+		/* copy items to output tuple */
+		for (i =3D 0; i < size; i++) {
+			PyObject *o =3D PyList_GET_ITEM(item, i);
+			if (PyList_Check(o) || PyTuple_Check(o)) {
+				if (!_flatten1(context, o))
+					return 0;
+			} else if (o !=3D Py_None) {
+				if (context->size + 1 > context->maxsize && !_bump(context, 1))
+					return 0;
+				Py_INCREF(o);
+				PyTuple_SET_ITEM(context->tuple, context->size++, o);
+			}
+		}
+	} else if (PyTuple_Check(item)) {
+		/* same, for tuples */
+		size =3D PyTuple_GET_SIZE(item);
+		if (context->size + size > context->maxsize && !_bump(context, size))
+			return 0;
+		for (i =3D 0; i < size; i++) {
+			PyObject *o =3D PyTuple_GET_ITEM(item, i);
+			if (PyList_Check(o) || PyTuple_Check(o)) {
+				if (!_flatten1(context, o))
+					return 0;
+			} else if (o !=3D Py_None) {
+				if (context->size + 1 > context->maxsize && !_bump(context, 1))
+					return 0;
+				Py_INCREF(o);
+				PyTuple_SET_ITEM(context->tuple, context->size++, o);
+			}
+		}
+	} else {
+		PyErr_SetString(PyExc_TypeError, "argument must be sequence");
+		return 0;
+	}
+	return 1;
+}
+
+static PyObject *
+Tkinter_Flatten(PyObject* self, PyObject* args)
+{
+	FlattenContext context;
+	PyObject* item;
+
+	if (!PyArg_ParseTuple(args, "O:_flatten", &item))
+		return NULL;
+
+	context.maxsize =3D PySequence_Length(item);
+	if (context.maxsize <=3D 0)
+		return PyTuple_New(0);
+=09
+	context.tuple =3D PyTuple_New(context.maxsize);
+	if (!context.tuple)
+		return NULL;
+=09
+	context.size =3D 0;
+
+	if (!_flatten1(&context, item))
+		return NULL;
+
+	if (_PyTuple_Resize(&context.tuple, context.size, 0))
+		return NULL;
+
+	return context.tuple;
+}
+
 static PyObject *
 Tkinter_Create(self, args)
 	PyObject *self;
@@ -2006,6 +2109,7 @@
=20
 static PyMethodDef moduleMethods[] =3D
 {
+	{"_flatten",           Tkinter_Flatten, 1},
 	{"create",             Tkinter_Create, 1},
 #ifdef HAVE_CREATEFILEHANDLER
 	{"createfilehandler",  Tkapp_CreateFileHandler, 1},
Index: Lib/lib-tk/Tkinter.py
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
RCS file: /cvsroot/python/python/dist/src/Lib/lib-tk/Tkinter.py,v
retrieving revision 1.137
diff -u -r1.137 Tkinter.py
--- Lib/lib-tk/Tkinter.py	2000/03/30 23:19:44	1.137
+++ Lib/lib-tk/Tkinter.py	2000/06/18 14:36:43
@@ -39,6 +39,9 @@
 			res =3D res + (item,)
 	return res
=20
+try: _flatten =3D _tkinter._flatten
+except AttributeError: pass
+
 def _cnfmerge(cnfs):
 	if type(cnfs) is DictionaryType:
 		return cnfs
@@ -54,6 +57,9 @@
 				for k, v in c.items():
 					cnf[k] =3D v
 		return cnf
+
+try: _cnfmerge =3D _tkinter._cnfmerge
+except AttributeError: pass
=20
 class Event:
 	pass

------=_NextPart_000_0079_01BFD946.AE0EB200--