On Thu, 7 Jun 2012 16:18:03 +0200
Campbell Barton <[email protected]> wrote:
> code review, patch neesd some more work.
> http://www.pasteall.org/pic/show.php?id=32822
OK, the code looks a lot better now, thanks!
Patch attached, along with the test script I am using.
These are the changes since the v1:
- Move some variables in an internal scope
- Allow sorting by the existing index order
- Decrement 'index' and 'py_elem' to avoid memory leaks
- Don't check the return value of BPy_BMElem_CreatePyObject()
- Use PyNumber_Check to verify that keyfunc actually returns a number
- Use the helper function range_vn_i() to intialize elem_idx
- Check that the key function is actually a callable object
- Check the return value of PyObject_CallFunctionObjArgs
- Move allocations right before where the memory is used
- Use qsort_r to sort the indices by the values in the 'keys' array
- Use PyMem_MALLOC and PyMem_FREE instead of malloc and free
- Return NULL on error and Py_RETURN_NONE on success, cleanup in
either case
- Call PyErr_NoMemory when allocations fail
- Set python exceptions appropriately on error paths
- Remove ultra-verbose debug printouts
- Avoid sorting if the sequence has 0 or 1 elements
- Reorder declarations, and remove initializers when not strictly
needed
- Cleanup docs and comments
There is still a problem with the current code, I think it will only
work on GNU systems: qsort_r does not seem to be that portable, on some
other Unix systems the compare function has a different order of
parameters[1] and on windows qsort_s[2] should be used, again with a
different order of parameters in the compare function.
I can think to 3 solutions:
- just use 'qsort' with 'keys' as a global variable, I don't know what
are the assumptions in blender about multi-threading, and if that is
going to cause problems.
- add some wrapping of qsort_r to handle system differences: boring and
error prone?
- build up a PyList and use that for sorting: overhead?
Thanks,
Antonio
[1] http://sourceware.org/ml/libc-alpha/2008-12/msg00003.html
[2] http://msdn.microsoft.com/en-us/library/4xc60xas%28VS.80%29.aspx
--
Antonio Ospite
http://ao2.it
A: Because it messes up the order in which people normally read text.
See http://en.wikipedia.org/wiki/Posting_style
Q: Why is top-posting such a bad thing?
>From d8424fcc2500873218969b9a414b6d06bc680a8e Mon Sep 17 00:00:00 2001
From: Antonio Ospite <[email protected]>
Date: Thu, 7 Jun 2012 10:54:45 +0200
Subject: [PATCH v2] Add a BMElemSeq.sort() method
X-Face: z*RaLf`X<@C75u6Ig9}{oW$H;1_\2t5)({*|jhM<pyWR#k60!#=#>/Vb;]yA5<GWI5`6u&+
;6b'@y|8w"wB;4/e!7wYYrcqdJFY,~%Gk_4]cq$Ei/7<j&N3ah(m`ku?pX.&+~:_/wC~dwn^)MizBG
!pE^+iDQQ1yC6^,)YDKkxDd!T>\I~93>J<_`<4)A{':UrE
Add a method to sort BMElemSeq sequences, like python sequences.
---
source/blender/python/bmesh/bmesh_py_types.c | 196 ++++++++++++++++++++++++++
1 file changed, 196 insertions(+)
diff --git a/source/blender/python/bmesh/bmesh_py_types.c b/source/blender/python/bmesh/bmesh_py_types.c
index 053dac7..8a1f9fa 100644
--- a/source/blender/python/bmesh/bmesh_py_types.c
+++ b/source/blender/python/bmesh/bmesh_py_types.c
@@ -2083,6 +2083,197 @@ static PyObject *bpy_bmelemseq_index_update(BPy_BMElemSeq *self)
Py_RETURN_NONE;
}
+PyDoc_STRVAR(bpy_bmelemseq_sort_doc,
+".. method:: sort(key=None, reverse=False)\n"
+"\n"
+" Sort the elements of this sequence, with an optional custom sort key.\n"
+"\n"
+" :arg key: The key that sets the ordering of the elements.\n"
+" :type key: :function: returning a number\n"
+" :arg reverse: Reverse the order of the elements\n"
+" :type reverse: :boolean:\n"
+"\n"
+" .. code-block:: python\n"
+"\n"
+" mesh.faces.sort(key=lambda f: f.calc_area())\n"
+"\n"
+" .. note::\n"
+"\n"
+" When the 'key' argument is not provided, the elements are reordered following their current index value.\n"
+" In particular this can be used by setting indices manually before calling this method.\n"
+"\n"
+);
+
+static int bpy_bmelemseq_sort_cmp_by_keys_ascending(const int *index1, const int *index2, double *keys)
+{
+ if (keys[*index1] < keys[*index2])
+ return -1;
+ else if (keys[*index1] > keys[*index2])
+ return 1;
+ else
+ return 0;
+}
+
+static int bpy_bmelemseq_sort_cmp_by_keys_descending(const int *index1, const int *index2, double *keys)
+{
+ return -bpy_bmelemseq_sort_cmp_by_keys_ascending(index1, index2, keys);
+}
+
+static PyObject *bpy_bmelemseq_sort(BPy_BMElemSeq *self, PyObject *args, PyObject *kw)
+{
+ static const char *kwlist[] = {"key", "reverse", NULL};
+ PyObject *keyfunc = NULL; /* optional */
+ int reverse = FALSE; /* optional */
+
+ const char htype = bm_iter_itype_htype_map[self->itype];
+ int n_elem;
+
+ BMIter iter;
+ BMElem *ele;
+
+ double *keys;
+ int *elem_idx;
+ int *elem_map_idx;
+ int (*elem_idx_compare_by_keys)(const void *, const void *, void *);
+
+ int *vert_idx = NULL;
+ int *edge_idx = NULL;
+ int *face_idx = NULL;
+ int i;
+
+ int ok = FALSE;
+
+ BMesh *bm = self->bm;
+
+ BPY_BM_CHECK_OBJ(self);
+
+ if (args != NULL) {
+ if(!PyArg_ParseTupleAndKeywords(args, kw,
+ "|Oi:BMElemSeq.sort",
+ (char **)kwlist,
+ &keyfunc, &reverse))
+ goto out;
+ }
+
+ if (keyfunc != NULL && !PyCallable_Check(keyfunc)) {
+ PyErr_SetString(PyExc_TypeError,
+ "the 'key' argument is not a callable object");
+ goto out;
+ }
+
+ n_elem = BM_mesh_elem_count(bm, htype);
+ if (n_elem <= 1) {
+ /* 0 or 1 elements: sorted already */
+ ok = TRUE;
+ goto out;
+ }
+
+ keys = PyMem_MALLOC(sizeof(*keys) * n_elem);
+ if (keys == NULL) {
+ PyErr_NoMemory();
+ goto out;
+ }
+
+ i = 0;
+ BM_ITER_BPY_BM_SEQ (ele, &iter, self) {
+ if (keyfunc != NULL) {
+ PyObject *py_elem;
+ PyObject *index;
+
+ py_elem = BPy_BMElem_CreatePyObject(self->bm, (BMHeader *)ele);
+ index = PyObject_CallFunctionObjArgs(keyfunc, py_elem, NULL);
+ Py_DECREF(py_elem);
+ if (index == NULL) {
+ /* No need to set the exception here,
+ * PyObject_CallFunctionObjArgs() does that */
+ goto out_free_keys;
+ }
+
+ if (!PyNumber_Check(index)) {
+ PyErr_SetString(PyExc_ValueError,
+ "the value returned by the 'key' function is not a number");
+ Py_DECREF(index);
+ goto out_free_keys;
+ }
+
+ keys[i] = PyFloat_AsDouble(index);
+ Py_DECREF(index);
+ } else {
+ /* If the 'key' function is not provided we sort
+ * according to the current index values */
+ keys[i] = ele->head.index;
+ }
+
+ i++;
+ }
+
+ elem_idx = PyMem_MALLOC(sizeof(*elem_idx) * n_elem);
+ if (elem_idx == NULL) {
+ PyErr_NoMemory();
+ goto out_free_keys;
+ }
+
+ /* Initialize the element index array */
+ range_vn_i(elem_idx, n_elem, 0);
+
+ /* Sort the index array according to the order of the 'keys' array */
+ if (reverse)
+ elem_idx_compare_by_keys = bpy_bmelemseq_sort_cmp_by_keys_descending;
+ else
+ elem_idx_compare_by_keys = bpy_bmelemseq_sort_cmp_by_keys_ascending;
+
+ qsort_r(elem_idx, n_elem, sizeof(*elem_idx), elem_idx_compare_by_keys, keys);
+
+ elem_map_idx = PyMem_MALLOC(sizeof(*elem_map_idx) * n_elem);
+ if (elem_map_idx == NULL) {
+ PyErr_NoMemory();
+ goto out_free_elem_idx;
+ }
+
+ /* Initialize the map array
+ *
+ * We need to know the index such that if used as the new_index in
+ * BM_mesh_remap() will give the order of the sorted keys like in
+ * elem_idx */
+ for (i = 0; i < n_elem; i++) {
+ elem_map_idx[elem_idx[i]] = i;
+ }
+
+ switch ((BMIterType)self->itype) {
+ case BM_VERTS_OF_MESH:
+ vert_idx = elem_map_idx;
+ break;
+ case BM_EDGES_OF_MESH:
+ edge_idx = elem_map_idx;
+ break;
+ case BM_FACES_OF_MESH:
+ face_idx = elem_map_idx;
+ break;
+ default:
+ PyErr_Format(PyExc_TypeError, "element type %d not supported", self->itype);
+ goto cleanup;
+ }
+
+ BM_mesh_remap(bm, vert_idx, edge_idx, face_idx);
+ BM_mesh_elem_index_ensure(bm, htype);
+
+ ok = TRUE;
+
+cleanup:
+ PyMem_FREE(elem_map_idx);
+
+out_free_elem_idx:
+ PyMem_FREE(elem_idx);
+
+out_free_keys:
+ PyMem_FREE(keys);
+
+out:
+ if (ok)
+ Py_RETURN_NONE;
+ else
+ return NULL;
+}
static struct PyMethodDef bpy_bmesh_methods[] = {
/* utility */
@@ -2166,6 +2357,7 @@ static struct PyMethodDef bpy_bmloop_methods[] = {
static struct PyMethodDef bpy_bmelemseq_methods[] = {
/* odd function, initializes index values */
{"index_update", (PyCFunction)bpy_bmelemseq_index_update, METH_NOARGS, bpy_bmelemseq_index_update_doc},
+ {"sort", (PyCFunction)bpy_bmelemseq_sort, METH_VARARGS | METH_KEYWORDS, bpy_bmelemseq_sort_doc},
{NULL, NULL, 0, NULL}
};
@@ -2175,6 +2367,7 @@ static struct PyMethodDef bpy_bmvertseq_methods[] = {
/* odd function, initializes index values */
{"index_update", (PyCFunction)bpy_bmelemseq_index_update, METH_NOARGS, bpy_bmelemseq_index_update_doc},
+ {"sort", (PyCFunction)bpy_bmelemseq_sort, METH_VARARGS | METH_KEYWORDS, bpy_bmelemseq_sort_doc},
{NULL, NULL, 0, NULL}
};
@@ -2186,6 +2379,7 @@ static struct PyMethodDef bpy_bmedgeseq_methods[] = {
/* odd function, initializes index values */
{"index_update", (PyCFunction)bpy_bmelemseq_index_update, METH_NOARGS, bpy_bmelemseq_index_update_doc},
+ {"sort", (PyCFunction)bpy_bmelemseq_sort, METH_VARARGS | METH_KEYWORDS, bpy_bmelemseq_sort_doc},
{NULL, NULL, 0, NULL}
};
@@ -2197,12 +2391,14 @@ static struct PyMethodDef bpy_bmfaceseq_methods[] = {
/* odd function, initializes index values */
{"index_update", (PyCFunction)bpy_bmelemseq_index_update, METH_NOARGS, bpy_bmelemseq_index_update_doc},
+ {"sort", (PyCFunction)bpy_bmelemseq_sort, METH_VARARGS | METH_KEYWORDS, bpy_bmelemseq_sort_doc},
{NULL, NULL, 0, NULL}
};
static struct PyMethodDef bpy_bmloopseq_methods[] = {
/* odd function, initializes index values */
/* no: index_update() function since we cant iterate over loops */
+ /* no: sort() function since we cant iterate over loops */
{NULL, NULL, 0, NULL}
};
--
1.7.10
#!/usr/bin/env python
import traceback
import bpy
import bmesh
def print_elems(elems, key=None):
print()
for e in elems:
print(e.index, key(e) if key else "")
print()
def print_elems_by_index(elems, key=None, reverse=False):
print()
sorted_elems = sorted(elems, key=lambda e: e.index, reverse=reverse)
for e in sorted_elems:
print(e.index, key(e) if key else "")
print()
cube = bpy.data .objects['Cube']
mesh = bmesh.new()
mesh.from_mesh(cube.data)
print(mesh)
print("\n\n")
print("A test for an invalid 'key' value, this is gonna fail")
try:
mesh.faces.sort(key=13)
except:
traceback.print_exc()
pass
print("\n\n")
print("A test for an invalid 'reverse' value, this is gonna fail")
try:
mesh.faces.sort(reverse='Ciao')
except:
traceback.print_exc()
pass
print("\n\n")
print("A test for an malformed function, this is gonna fail")
try:
mesh.verts.sort(key=lambda x: f.index)
except:
traceback.print_exc()
pass
print("\n\n")
print("A test for an invalid function, this is gonna fail")
def f(x, y):
return x.index
try:
mesh.verts.sort(key=f)
except:
traceback.print_exc()
pass
print("\n\n")
print("A test on using a key function which does not return a number, this is gonna fail")
try:
mesh.verts.sort(key=lambda f: "Ciao")
except:
traceback.print_exc()
pass
print("\n\n")
print("A test on sorting by the index values in reverse")
print_elems(mesh.faces, key=lambda f: f.calc_area())
mesh.faces.sort(key=lambda f: f.index, reverse=True)
print_elems(mesh.faces, key=lambda f: f.calc_area())
print("\n\n")
print("A test on sorting by setting the index values manually")
print_elems(mesh.verts, key=lambda v: v.co[0])
mesh.verts[0].index = 4
mesh.verts[4].index = 0
mesh.verts[1].index = 7
mesh.verts[7].index = 1
print_elems(mesh.verts, key=lambda v: v.co[0])
mesh.verts.sort()
print_elems(mesh.verts, key=lambda v: v.co[0])
print("\n\n")
print("A test on faces, sort according to face area")
print_elems(mesh.faces, key=lambda f: f.calc_area())
mesh.faces.sort(key=lambda f: f.calc_area())
#print("When iterating over the sorted elements we don't get the new natural order")
print_elems(mesh.faces, key=lambda f: f.calc_area())
#print("But if we sort by index then the order is right...")
#print_elems_by_index(mesh.faces, key=lambda f: f.calc_area())
print("\n\n")
print("A test on vertices, sort according to x coordinate")
print_elems(mesh.verts, key=lambda v: v.co[0])
mesh.verts.sort(key=lambda v: v.co[0])
#print("When iterating over the sorted elements we don't get the new natural order")
print_elems(mesh.verts, key=lambda v: v.co[0])
#print("But if we sort by index then the order is right...")
#print_elems_by_index(mesh.verts, key=lambda v: v.co[0])
mesh.to_mesh(cube.data)
mesh.free()
print("After exporting to mesh again the elements are properly sorted too")
print_elems(cube.data.vertices, key=lambda v: v.co[0])
_______________________________________________
Bf-python mailing list
[email protected]
http://lists.blender.org/mailman/listinfo/bf-python
