add simple sort to Linked_List implementation

cshorler · cshorler · commit 65d3937e7227 · 2014-06-08T20:44:50.000+01:00
diff --git a/include/express/linklist.h b/include/express/linklist.h
@@ -129,6 +129,8 @@ extern SC_EXPRESS_EXPORT void LISTinitialize PROTO( ( void ) );
 extern SC_EXPRESS_EXPORT void LISTcleanup PROTO( ( void ) );
 extern SC_EXPRESS_EXPORT Linked_List LISTcreate PROTO( ( void ) );
 extern SC_EXPRESS_EXPORT Linked_List LISTcopy PROTO( ( Linked_List ) );
+extern SC_EXPRESS_EXPORT void LISTsort PROTO( ( Linked_List, int (*comp)(void*, void*) ) );
+extern SC_EXPRESS_EXPORT void LISTswap PROTO( ( Link, Link ) );
 extern SC_EXPRESS_EXPORT Generic  LISTadd_first PROTO( ( Linked_List, Generic ) );
 extern SC_EXPRESS_EXPORT Generic  LISTadd_last PROTO( ( Linked_List, Generic ) );
 extern SC_EXPRESS_EXPORT Generic  LISTadd_after PROTO( ( Linked_List, Link, Generic ) );
diff --git a/src/express/linklist.c b/src/express/linklist.c
@@ -67,6 +67,38 @@ void LISTfree( Linked_List list ) {
     LIST_destroy( list );
 }
 
+void LISTsort( Linked_List list, int (*comp)(void*, void*)) {
+    unsigned int moved;
+    Link node, prev;
+
+    if (LISTempty(list))
+        return;
+
+    while (true) {
+        for ( node = list->mark->next, moved = 0; node != list->mark; node = node->next ) {
+            prev = node->prev;
+            if (prev != list->mark && comp(prev->data, node->data) < 0) {
+                LISTswap(prev, node);
+                moved++;
+            }
+        }
+        if (moved == 0)
+            break;
+    }
+}
+
+void LISTswap( Link p, Link q ) {
+    Generic     tmp;
+
+    if( p == LINK_NULL || q == LINK_NULL || p == q )
+        return;
+
+    tmp = p->data;
+    p->data = q->data;
+    q->data = tmp;
+}
+
+
 Generic LISTadd_first( Linked_List list, Generic item ) {
     Link        node;
 
