changeset 14297:85ec4f714596

Use libc qsort to sort ODML index. Based on patch by phillip at phdcam dot com

--- a/libmpdemux/aviheader.c	Sun Jan 02 14:10:13 2005 +0000
+++ b/libmpdemux/aviheader.c	Sun Jan 02 14:29:43 2005 +0000
@@ -44,45 +44,10 @@
     return 0;
 }
 
-/**
- * Simple quicksort for AVIINDEXENTRYs
- * To avoid too deep recursion, the bigger part is handled iteratively,
- * thus limiting recursion to log2(n) levels.
- * The pivot element is randomized to "even out" otherwise extreme cases.
- */
-static void avi_idx_quicksort(AVIINDEXENTRY *idx, int from, int to)
-{
-    AVIINDEXENTRY temp;
-    int lo;
-    int hi;
-    off_t pivot_ofs;
-    int pivot_idx;
-  while (from < to) {
-    pivot_idx = from;
-    pivot_idx += rand() % (to - from + 1);
-    pivot_ofs = AVI_IDX_OFFSET(&idx[pivot_idx]);
-    lo = to;
-    hi = from;
-    do {
-	while(pivot_ofs < AVI_IDX_OFFSET(&idx[lo])) lo--;
-	while(pivot_ofs > AVI_IDX_OFFSET(&idx[hi])) hi++;
-	if(hi <= lo) {
-	    if (hi != lo) {
-		memcpy(&temp, &idx[lo], sizeof(temp));
-		memcpy(&idx[lo], &idx[hi], sizeof(temp));
-		memcpy(&idx[hi], &temp, sizeof(temp));
-	    }
-	    lo--; hi++;
-	}
-    } while (lo >= hi);
-    if ((lo - from) < (to - hi)) {
-      avi_idx_quicksort(idx, from, lo);
-      from = hi;
-    } else {
-      avi_idx_quicksort(idx, hi, to);
-      to = lo;
-    }
-  }
+int avi_idx_cmp(const void *elem1,const void *elem2) {
+  register off_t a = AVI_IDX_OFFSET((AVIINDEXENTRY *)elem1);
+  register off_t b = AVI_IDX_OFFSET((AVIINDEXENTRY *)elem2);
+  return (a > b) - (b > a);
 }
 
 void read_avi_header(demuxer_t *demuxer,int index_mode){
@@ -535,7 +500,7 @@
 	    }
 	}
     }
-    avi_idx_quicksort(priv->idx, 0, priv->idx_size-1);
+    qsort(priv->idx, priv->idx_size, sizeof(AVIINDEXENTRY), avi_idx_cmp);
 
     /*
        Hack to work around a "wrong" index in some divx odml files