qsort_s.c

Lido PXA270平台开发板的最新BSP,包括源代码

/* -*- c-file-style: "img" -*-
<module>
 * Name         : qsort_s.c
 * Title        : Quick Sort
 * Author       : Marcus Shawcroft
 * Created      : 4 Nov 2003
 *
 * Copyright    : 2003 by Imagination Technologies Limited.
 *                All rights reserved.  No part of this software, either
 *                material or conceptual may be copied or distributed,
 *                transmitted, transcribed, stored in a retrieval system
 *                or translated into any human or computer language in any
 *                form by any means, electronic, mechanical, manual or
 *                other-wise, or disclosed to third parties without the
 *                express written permission of Imagination Technologies
 *                Limited, Unit 8, HomePark Industrial Estate,
 *                King's Langley, Hertfordshire, WD4 8LZ, U.K.
 *
 * Description  : Naive implementation of libc qsort with an arbitrary
 *                threaded state.
 * 
 * Platform     : ALL
 *
</module>
 */

#include "qsort.h"

/*
   <function>
   FUNCTION   : _swap
   PURPOSE    : Exchange to arbitrary elements within an array of element.
   PARAMETERS : In:  pva - pointer to first element
                In:  pvb - pointer to second element
                In:  size - size of each element in bytes.
   RETURNS    :
   </function>
 */
static void
_swap (void *pva, void *pvb, int size)
{
  unsigned char *a = pva;
  unsigned char *b = pvb;
  if (a!=b)
    {
      int i;
      for (i=0; i<size; i++)
	{
	  unsigned char t;
      
	  t = a[i];
	  a[i] = b[i];
	  b[i] = t;
	}
    }
}

/*
   <function>
   FUNCTION   : _partition
   PURPOSE    : Partition a sub-section of an array of elements such that
                all elements to the left of an arbitrary pivot point compare
                less than all of the elements to the right of the pivot point.
   PARAMETERS : In:  l - pointer to left most element in partition.
                In:  r - pointer to right most element in partition.
                In:  size - size of each element in bytes.
                In:  compare - element comparison function.
                In:  state
   RETURNS    : Pointer to the pivot.
   </function>
 */
static int *
_partition (void *l, void *r, int size,
	    int (*compare) (void *a, void *b, void *s),
	    void *state)
{
  void *p = l;
  
  while (l<r)
    {
      while (compare (l, p, state) <= 0 && l < r)
	l = (unsigned char *)l + size;
      while (compare (r, p, state) > 0)
	r = (unsigned char *)r - size;
      if (l<r)
	_swap (l, r, size);
    }
  _swap (p, r, size);
  return r;
}

/*
   <function>
   FUNCTION   : _sort
   PURPOSE    : Quick sort work horse. Sort the elements within a
                sub parition of an array of elements.
   PARAMETERS : In:  l - pointer to left most element in partition.
                In:  r - pointer to right most element in partition.
                In:  size - size of each element in bytes.
                In:  compare - element comparison function.
                In:  state -
   RETURNS    : None
   </function>
 */
static void
_sort (void *l, void *r, int size,
       int (*compare) (void *a, void *b, void *s),
       void *state)
{
  if (l<r)
    {
      int *m;
      m = _partition (l, r, size, compare, state);
      _sort (l, (unsigned char *)m - size, size, compare, state);
      _sort ((unsigned char *)m + size, r, size, compare, state);
    }
}

/*
   <function>
   FUNCTION   : PVR_qsort_s
   PURPOSE    : Quick sort in place.
   PARAMETERS : In:  base - array of elements to sort
                In:  n - number of elements in the array
                In:  size - size in bytes of each element
                In:  compare - function to compare two elements should
                     return 0 => a == b
                           <0 => a <  b
                           >0 => a >  b
                In:  state -
   RETURNS    : None
   </function>
 */
void
PVR_qsort_s (void *base, int n, int size,
	     int (*compare) (void *a, void *b, void *state),
	     void *state)
{
  _sort (base, (unsigned char *)base + size * (n-1), size, compare, state);
}