Provide C implementation of tree item sorter.
[jelmer/dulwich-libgit2.git] / dulwich / _objects.c
index cf6aaaee40375a5d7d2349433fbb02fd6940f368..0273d743ac7fcff59ea32b55e3d28e2db28e8bc8 100644 (file)
@@ -18,6 +18,8 @@
  */
 
 #include <Python.h>
+#include <stdlib.h>
+#include <sys/stat.h>
 
 #define bytehex(x) (((x)<0xa)?('0'+(x)):('a'-0xa+(x)))
 
@@ -49,8 +51,8 @@ static PyObject *py_parse_tree(PyObject *self, PyObject *args)
 
        end = text + len;
 
-    while (text < end) {
-        long mode;
+       while (text < end) {
+               long mode;
                mode = strtol(text, &text, 8);
 
                if (*text != ' ') {
@@ -61,7 +63,7 @@ static PyObject *py_parse_tree(PyObject *self, PyObject *args)
 
                text++;
 
-        namelen = strlen(text);
+               namelen = strlen(text);
 
                name = PyString_FromStringAndSize(text, namelen);
                if (name == NULL) {
@@ -69,12 +71,13 @@ static PyObject *py_parse_tree(PyObject *self, PyObject *args)
                        return NULL;
                }
 
-        item = Py_BuildValue("(lN)", mode, sha_to_pyhex((unsigned char *)text+namelen+1));
-        if (item == NULL) {
-            Py_DECREF(ret);
+               item = Py_BuildValue("(lN)", mode,
+                                                        sha_to_pyhex((unsigned char *)text+namelen+1));
+               if (item == NULL) {
+                       Py_DECREF(ret);
                        Py_DECREF(name);
-            return NULL;
-        }
+                       return NULL;
+               }
                if (PyDict_SetItem(ret, name, item) == -1) {
                        Py_DECREF(ret);
                        Py_DECREF(item);
@@ -84,13 +87,110 @@ static PyObject *py_parse_tree(PyObject *self, PyObject *args)
                Py_DECREF(item);
 
                text += namelen+21;
-    }
+       }
+
+       return ret;
+}
+
+struct tree_item {
+       const char *name;
+       int mode;
+       PyObject *tuple;
+};
+
+int cmp_tree_item(const void *_a, const void *_b)
+{
+       const struct tree_item *a = _a, *b = _b;
+       const char *remain_a, *remain_b;
+       int ret, common;
+       if (strlen(a->name) > strlen(b->name)) {
+               common = strlen(b->name);
+               remain_a = a->name + common;
+               remain_b = (S_ISDIR(b->mode)?"/":"");
+       } else if (strlen(b->name) > strlen(a->name)) { 
+               common = strlen(a->name);
+               remain_a = (S_ISDIR(a->mode)?"/":"");
+               remain_b = b->name + common;
+       } else { /* strlen(a->name) == strlen(b->name) */
+               common = 0;
+               remain_a = a->name;
+               remain_b = b->name;
+       }
+       ret = strncmp(a->name, b->name, common);
+       if (ret != 0)
+               return ret;
+       return strcmp(remain_a, remain_b);
+}
+
+static PyObject *py_sorted_tree_items(PyObject *self, PyObject *entries)
+{
+       struct tree_item *qsort_entries;
+       int num, i;
+       PyObject *ret;
+       Py_ssize_t pos = 0; 
+       PyObject *key, *value;
+
+       if (!PyDict_Check(entries)) {
+               PyErr_SetString(PyExc_TypeError, "Argument not a dictionary");
+               return NULL;
+       }
+
+       num = PyDict_Size(entries);
+       qsort_entries = malloc(num * sizeof(struct tree_item));
+       if (qsort_entries == NULL) {
+               PyErr_NoMemory();
+               return NULL;
+       }
+
+       i = 0;
+       while (PyDict_Next(entries, &pos, &key, &value)) {
+               PyObject *py_mode, *py_sha;
+               
+               if (PyTuple_Size(value) != 2) {
+                       PyErr_SetString(PyExc_ValueError, "Tuple has invalid size");
+                       free(qsort_entries);
+                       return NULL;
+               }
+
+               py_mode = PyTuple_GET_ITEM(value, 0);
+               py_sha = PyTuple_GET_ITEM(value, 1);
+               qsort_entries[i].tuple = Py_BuildValue("(OOO)", key, py_mode, py_sha);
+               if (!PyString_CheckExact(key)) {
+                       PyErr_SetString(PyExc_TypeError, "Name is not a string");
+                       free(qsort_entries);
+                       return NULL;
+               }
+               qsort_entries[i].name = PyString_AS_STRING(key);
+               if (!PyInt_CheckExact(py_mode)) {
+                       PyErr_SetString(PyExc_TypeError, "Mode is not an int");
+                       free(qsort_entries);
+                       return NULL;
+               }
+               qsort_entries[i].mode = PyInt_AS_LONG(py_mode);
+               i++;
+       }
+
+       qsort(qsort_entries, num, sizeof(struct tree_item), cmp_tree_item);
+
+       ret = PyList_New(num);
+       if (ret == NULL) {
+               free(qsort_entries);
+               PyErr_NoMemory();
+               return NULL;
+       }
+
+       for (i = 0; i < num; i++) {
+               PyList_SET_ITEM(ret, i, qsort_entries[i].tuple);
+       }
+
+       free(qsort_entries);
 
-    return ret;
+       return ret;
 }
 
 static PyMethodDef py_objects_methods[] = {
        { "parse_tree", (PyCFunction)py_parse_tree, METH_VARARGS, NULL },
+       { "sorted_tree_items", (PyCFunction)py_sorted_tree_items, METH_O, NULL },
        { NULL, NULL, 0, NULL }
 };