+ /* Allocate temporary storage for the items */
+ TmpItems = xmalloc (Bytes);
+
+ /* Copy the items we have to move to the temporary storage */
+ memcpy (TmpItems, C->Items + Start, Bytes);
+
+ /* Check if the range has to be moved upwards or downwards. Move the
+ * existing items to their final location, so that the space needed
+ * for the items now in temporary storage is unoccupied.
+ */
+ if (Target < Start) {
+
+ /* Move downwards */
+ unsigned BytesToMove = (Start - Target) * sizeof (void*);
+ memmove (C->Items+Target+Count, C->Items+Target, BytesToMove);
+
+ } else if (Target < Start + Count) {
+
+ /* Target is inside range */
+ FAIL ("Not supported");
+
+ } else {
+
+ /* Move upwards */
+ unsigned ItemsToMove = (Target - Start - Count);
+ unsigned BytesToMove = ItemsToMove * sizeof (void*);
+ memmove (C->Items+Start, C->Items+Target-ItemsToMove, BytesToMove);
+
+ /* Adjust the target index */
+ Target -= Count;
+ }
+
+ /* Move the old items to their final location */
+ memcpy (C->Items + Target, TmpItems, Bytes);
+
+ /* Delete the temporary item space */
+ xfree (TmpItems);
+}
+
+
+
+static void QuickSort (Collection* C, int Lo, int Hi,
+ int (*Compare) (void*, const void*, const void*),
+ void* Data)
+/* Internal recursive sort function. */
+{
+ /* Get a pointer to the items */
+ void** Items = C->Items;
+
+ /* Quicksort */
+ while (Hi > Lo) {
+ int I = Lo + 1;
+ int J = Hi;
+ while (I <= J) {
+ while (I <= J && Compare (Data, Items[Lo], Items[I]) >= 0) {
+ ++I;
+ }
+ while (I <= J && Compare (Data, Items[Lo], Items[J]) < 0) {
+ --J;
+ }
+ if (I <= J) {
+ /* Swap I and J */
+ void* Tmp = Items[I];
+ Items[I] = Items[J];
+ Items[J] = Tmp;
+ ++I;
+ --J;
+ }
+ }
+ if (J != Lo) {
+ /* Swap J and Lo */
+ void* Tmp = Items[J];
+ Items[J] = Items[Lo];
+ Items[Lo] = Tmp;
+ }
+ if (J > (Hi + Lo) / 2) {
+ QuickSort (C, J + 1, Hi, Compare, Data);
+ Hi = J - 1;
+ } else {
+ QuickSort (C, Lo, J - 1, Compare, Data);
+ Lo = J + 1;
+ }
+ }
+}
+
+
+
+void CollSort (Collection* C,
+ int (*Compare) (void*, const void*, const void*),
+ void* Data)
+/* Sort the collection using the given compare function. The data pointer is
+ * passed as *first* element to the compare function, it's not used by the
+ * sort function itself. The other two pointer passed to the Compare function
+ * are pointers to objects.
+ */
+{
+ if (C->Count > 1) {
+ QuickSort (C, 0, C->Count-1, Compare, Data);
+ }
+}