kc3-lang/libbsd/src/radixsort.c

• Show log

  Commit

• Hash : 8e8834d8
  Author :
  Date : 2017-06-14T02:53:35
  

  Remove RCSID tags These are obsolete markers, and in some cases they repeat the information already present in the comment header.

Download

• src/radixsort.c

• /*     $NetBSD: radixsort.c,v 1.18 2009/08/21 20:49:50 dsl Exp $       */
  /*-
   * Copyright (c) 1990, 1993
   *	The Regents of the University of California.  All rights reserved.
   *
   * This code is derived from software contributed to Berkeley by
   * Peter McIlroy and by Dan Bernstein at New York University,
   *
   * Redistribution and use in source and binary forms, with or without
   * modification, are permitted provided that the following conditions
   * are met:
   * 1. Redistributions of source code must retain the above copyright
   *    notice, this list of conditions and the following disclaimer.
   * 2. Redistributions in binary form must reproduce the above copyright
   *    notice, this list of conditions and the following disclaimer in the
   *    documentation and/or other materials provided with the distribution.
   * 3. Neither the name of the University nor the names of its contributors
   *    may be used to endorse or promote products derived from this software
   *    without specific prior written permission.
   *
   * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
   * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
   * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
   * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   * SUCH DAMAGE.
   */
  
  #include <sys/cdefs.h>
  
  /*
   * Radixsort routines.
   *
   * Program r_sort_a() is unstable but uses O(logN) extra memory for a stack.
   * Use radixsort(a, n, trace, endchar) for this case.
   *
   * For stable sorting (using N extra pointers) use sradixsort(), which calls
   * r_sort_b().
   *
   * For a description of this code, see D. McIlroy, P. McIlroy, K. Bostic,
   * "Engineering Radix Sort".
   */
  
  #include <sys/types.h>
  #include <stdlib.h>
  #include <stddef.h>
  #include <errno.h>
  
  typedef struct {
  	const unsigned char **sa;
  	int sn, si;
  } stack;
  
  static inline void simplesort(const unsigned char **, int, int, const unsigned char *, unsigned int);
  static void r_sort_a(const unsigned char **, int, int, const unsigned char *, unsigned int);
  static void r_sort_b(const unsigned char **,
  	    const unsigned char **, int, int, const unsigned char *, unsigned int);
  
  #define	THRESHOLD	20		/* Divert to simplesort(). */
  #define	SIZE		512		/* Default stack size. */
  
  #define SETUP {								\
  	if (tab == NULL) {						\
  		tr = tr0;						\
  		for (c = 0; c < endch; c++)				\
  			tr0[c] = c + 1;					\
  		tr0[c] = 0;						\
  		for (c++; c < 256; c++)					\
  			tr0[c] = c;					\
  		endch = 0;						\
  	} else {							\
  		endch = tab[endch];					\
  		tr = tab;						\
  		if (endch != 0 && endch != 255) {			\
  			errno = EINVAL;					\
  			return (-1);					\
  		}							\
  	}								\
  }
  
  int
  radixsort(const unsigned char **a, int n, const unsigned char *tab,
            unsigned int endch)
  {
  	const unsigned char *tr;
  	unsigned int c;
  	unsigned char tr0[256];
  
  	SETUP;
  	r_sort_a(a, n, 0, tr, endch);
  	return (0);
  }
  
  int
  sradixsort(const unsigned char **a, int n, const unsigned char *tab,
             unsigned int endch)
  {
  	const unsigned char *tr, **ta;
  	unsigned int c;
  	unsigned char tr0[256];
  
  	if (a == NULL) {
  		errno = EFAULT;
  		return (-1);
  	}
  
  	SETUP;
  	if (n < THRESHOLD)
  		simplesort(a, n, 0, tr, endch);
  	else {
  		ta = reallocarray(NULL, n, sizeof(*a));
  		if (ta == NULL)
  			return (-1);
  		r_sort_b(a, ta, n, 0, tr, endch);
  		free(ta);
  	}
  	return (0);
  }
  
  #define empty(s)	(s >= sp)
  #define pop(a, n, i)	a = (--sp)->sa, n = sp->sn, i = sp->si
  #define push(a, n, i)	sp->sa = a, sp->sn = n, (sp++)->si = i
  #define swap(a, b, t)	t = a, a = b, b = t
  
  /* Unstable, in-place sort. */
  static void
  r_sort_a(const unsigned char **a, int n, int i, const unsigned char *tr,
           unsigned int endch)
  {
  	static unsigned int count[256], nc, bmin;
  	unsigned int c;
  	const unsigned char **ak, *r;
  	stack s[SIZE], *sp, *sp0, *sp1, temp;
  	unsigned int *cp, bigc;
  	const unsigned char **an, *t, **aj, **top[256];
  
  	/* Set up stack. */
  	sp = s;
  	push(a, n, i);
  	while (!empty(s)) {
  		pop(a, n, i);
  		if (n < THRESHOLD) {
  			simplesort(a, n, i, tr, endch);
  			continue;
  		}
  		an = a + n;
  
  		/* Make character histogram. */
  		if (nc == 0) {
  			bmin = 255;	/* First occupied bin, excluding eos. */
  			for (ak = a; ak < an;) {
  				c = tr[(*ak++)[i]];
  				if (++count[c] == 1 && c != endch) {
  					if (c < bmin)
  						bmin = c;
  					nc++;
  				}
  			}
  			if (sp + nc > s + SIZE) {	/* Get more stack. */
  				r_sort_a(a, n, i, tr, endch);
  				continue;
  			}
  		}
  
  		/*
  		 * Special case: if all strings have the same
  		 * character at position i, move on to the next
  		 * character.
  		 */
  		if (nc == 1 && count[bmin] == (unsigned int)n) {
  			push(a, n, i+1);
  			nc = count[bmin] = 0;
  			continue;
  		}
  
  		/*
  		 * Set top[]; push incompletely sorted bins onto stack.
  		 * top[] = pointers to last out-of-place element in bins.
  		 * count[] = counts of elements in bins.
  		 * Before permuting: top[c-1] + count[c] = top[c];
  		 * during deal: top[c] counts down to top[c-1].
  		 */
  		sp0 = sp1 = sp;		/* Stack position of biggest bin. */
  		bigc = 2;		/* Size of biggest bin. */
  		if (endch == 0)		/* Special case: set top[eos]. */
  			top[0] = ak = a + count[0];
  		else {
  			ak = a;
  			top[255] = an;
  		}
  		for (cp = count + bmin; nc > 0; cp++) {
  			while (*cp == 0)	/* Find next non-empty pile. */
  				cp++;
  			if (*cp > 1) {
  				if (*cp > bigc) {
  					bigc = *cp;
  					sp1 = sp;
  				}
  				push(ak, *cp, i+1);
  			}
  			top[cp-count] = ak += *cp;
  			nc--;
  		}
  		swap(*sp0, *sp1, temp);	/* Play it safe -- biggest bin last. */
  
  		/*
  		 * Permute misplacements home.  Already home: everything
  		 * before aj, and in bin[c], items from top[c] on.
  		 * Inner loop:
  		 *	r = next element to put in place;
  		 *	ak = top[r[i]] = location to put the next element.
  		 *	aj = bottom of 1st disordered bin.
  		 * Outer loop:
  		 *	Once the 1st disordered bin is done, ie. aj >= ak,
  		 *	aj<-aj + count[c] connects the bins in a linked list;
  		 *	reset count[c].
  		 */
  		for (aj = a; aj < an;  *aj = r, aj += count[c], count[c] = 0)
  			for (r = *aj;  aj < (ak = --top[c = tr[r[i]]]);)
  				swap(*ak, r, t);
  	}
  }
  
  /* Stable sort, requiring additional memory. */
  static void
  r_sort_b(const unsigned char **a, const unsigned char **ta, int n, int i,
           const unsigned char *tr, unsigned int endch)
  {
  	static unsigned int count[256], nc, bmin;
  	unsigned int c;
  	const unsigned char **ak, **ai;
  	stack s[512], *sp, *sp0, *sp1, temp;
  	const unsigned char **top[256];
  	unsigned int *cp, bigc;
  
  	sp = s;
  	push(a, n, i);
  	while (!empty(s)) {
  		pop(a, n, i);
  		if (n < THRESHOLD) {
  			simplesort(a, n, i, tr, endch);
  			continue;
  		}
  
  		if (nc == 0) {
  			bmin = 255;
  			for (ak = a + n; --ak >= a;) {
  				c = tr[(*ak)[i]];
  				if (++count[c] == 1 && c != endch) {
  					if (c < bmin)
  						bmin = c;
  					nc++;
  				}
  			}
  			if (sp + nc > s + SIZE) {
  				r_sort_b(a, ta, n, i, tr, endch);
  				continue;
  			}
  		}
  
  		sp0 = sp1 = sp;
  		bigc = 2;
  		if (endch == 0) {
  			top[0] = ak = a + count[0];
  			count[0] = 0;
  		} else {
  			ak = a;
  			top[255] = a + n;
  			count[255] = 0;
  		}
  		for (cp = count + bmin; nc > 0; cp++) {
  			while (*cp == 0)
  				cp++;
  			if ((c = *cp) > 1) {
  				if (c > bigc) {
  					bigc = c;
  					sp1 = sp;
  				}
  				push(ak, c, i+1);
  			}
  			top[cp-count] = ak += c;
  			*cp = 0;			/* Reset count[]. */
  			nc--;
  		}
  		swap(*sp0, *sp1, temp);
  
  		for (ak = ta + n, ai = a+n; ak > ta;)	/* Copy to temp. */
  			*--ak = *--ai;
  		for (ak = ta+n; --ak >= ta;)		/* Deal to piles. */
  			*--top[tr[(*ak)[i]]] = *ak;
  	}
  }
  
  /* insertion sort */
  static inline void
  simplesort(const unsigned char **a, int n, int b, const unsigned char *tr,
             unsigned int endch)
  {
  	unsigned char ch;
  	const unsigned char  **ak, **ai, *s, *t;
  
  	for (ak = a+1; --n >= 1; ak++)
  		for (ai = ak; ai > a; ai--) {
  			for (s = ai[0] + b, t = ai[-1] + b;
  			    (ch = tr[*s]) != endch; s++, t++)
  				if (ch != tr[*t])
  					break;
  			if (ch >= tr[*t])
  				break;
  			swap(ai[0], ai[-1], s);
  		}
  }
  

Download