Deleted: trunk/reactos/lib/crtdll/direct/
Deleted: trunk/reactos/lib/crtdll/dirent/
Deleted: trunk/reactos/lib/crtdll/float/
Deleted: trunk/reactos/lib/crtdll/io/
Deleted: trunk/reactos/lib/crtdll/math/
Deleted: trunk/reactos/lib/crtdll/mbstring/
Deleted: trunk/reactos/lib/crtdll/misc/
Added: trunk/reactos/lib/crtdll/old cruft/direct/
Added: trunk/reactos/lib/crtdll/old cruft/dirent/
Added: trunk/reactos/lib/crtdll/old cruft/float/
Added: trunk/reactos/lib/crtdll/old cruft/io/
Added: trunk/reactos/lib/crtdll/old cruft/math/
Added: trunk/reactos/lib/crtdll/old cruft/mbstring/
Added: trunk/reactos/lib/crtdll/old cruft/misc/
Added: trunk/reactos/lib/crtdll/old cruft/process/
Added: trunk/reactos/lib/crtdll/old cruft/setjmp/
Added: trunk/reactos/lib/crtdll/old cruft/stdio/
Added: trunk/reactos/lib/crtdll/old cruft/stdlib/
Added: trunk/reactos/lib/crtdll/old cruft/stdlib/stdlib/
Deleted: trunk/reactos/lib/crtdll/old cruft/stdlib/stdlib/alloca.c
Deleted: trunk/reactos/lib/crtdll/old cruft/stdlib/stdlib/atexit.c
Deleted: trunk/reactos/lib/crtdll/old cruft/stdlib/stdlib/calloc.c
Deleted: trunk/reactos/lib/crtdll/old cruft/stdlib/stdlib/errno.c
Deleted: trunk/reactos/lib/crtdll/old cruft/stdlib/stdlib/fullpath.c
Deleted: trunk/reactos/lib/crtdll/old cruft/stdlib/stdlib/itoa.c
Deleted: trunk/reactos/lib/crtdll/old cruft/stdlib/stdlib/itow.c
Deleted: trunk/reactos/lib/crtdll/old cruft/stdlib/stdlib/llabs.c
Deleted: trunk/reactos/lib/crtdll/old cruft/stdlib/stdlib/lldiv.c
Deleted: trunk/reactos/lib/crtdll/old cruft/stdlib/stdlib/makepath.c
Deleted: trunk/reactos/lib/crtdll/old cruft/stdlib/stdlib/malloc.c
Deleted: trunk/reactos/lib/crtdll/old cruft/stdlib/stdlib/mbstowcs.c
Deleted: trunk/reactos/lib/crtdll/old cruft/stdlib/stdlib/putenv.c
Deleted: trunk/reactos/lib/crtdll/old cruft/stdlib/stdlib/qsort.c
Deleted: trunk/reactos/lib/crtdll/old cruft/stdlib/stdlib/rand.c
Deleted: trunk/reactos/lib/crtdll/old cruft/stdlib/stdlib/splitp.c
Deleted: trunk/reactos/lib/crtdll/old cruft/stdlib/stdlib/strtoull.c
Deleted: trunk/reactos/lib/crtdll/old cruft/stdlib/stdlib/swab.c
Deleted: trunk/reactos/lib/crtdll/old cruft/stdlib/stdlib/wcstom.c
Deleted: trunk/reactos/lib/crtdll/old cruft/stdlib/stdlib/wcstomb.c
Deleted: trunk/reactos/lib/crtdll/old cruft/stdlib/stdlib/wcstombs.c
Added: trunk/reactos/lib/crtdll/old cruft/sys_stat/
Added: trunk/reactos/lib/crtdll/old cruft/time/
Deleted: trunk/reactos/lib/crtdll/process/
Deleted: trunk/reactos/lib/crtdll/setjmp/
Deleted: trunk/reactos/lib/crtdll/stdio/
Deleted: trunk/reactos/lib/crtdll/stdlib/
Deleted: trunk/reactos/lib/crtdll/sys_stat/
Deleted: trunk/reactos/lib/crtdll/time/
Property changes on: trunk/reactos/lib/crtdll/old cruft/stdlib/stdlib
___________________________________________________________________
Name: svn:ignore
+ *.d
*.o
*.sym
--- trunk/reactos/lib/crtdll/stdlib/alloca.c 2005-08-22 14:26:37 UTC (rev 17475)
+++ trunk/reactos/lib/crtdll/old cruft/stdlib/stdlib/alloca.c 2005-08-22 14:39:10 UTC (rev 17476)
@@ -1,64 +0,0 @@
-#include <precomp.h>
-#include <msvcrt/stdlib.h>
-
-
-#undef alloca
-void *alloca(size_t s)
-{
- register unsigned int as = s;
-
-// alloca(0) should not return the stack pointer
- if ( s == 0 )
- return NULL;
-
- as = (as + 3) & (~3);
-
- __asm__ __volatile__(
- "mov %0, %%edx \n"
-// "popl %%ebp \n"
- "leave \n"
- "popl %%ecx \n"
- "subl %%edx, %%esp \n"
- "movl %%esp, %%eax \n"
- "addl $20, %%eax \n"//4 bytes + 16 bytes = arguments
- "push %%ecx \n"
- "ret \n"
- :
- :"g" ( as)
- );
-
-
- return NULL;
-}
-
-void *_alloca(size_t s)
-{
- register unsigned int as = s;
-
-// alloca(0) should not return the stack pointer
- if ( s == 0 )
- return NULL;
-
-
- if ( (s & 0xfffffffc) != 0 )
- as += 4;
-
- as &= 0xfffffffc;
-
- __asm__ __volatile__(
- "mov %0, %%edx \n"
-// "popl %%ebp \n"
- "leave \n"
- "popl %%ecx \n"
- "subl %%edx, %%esp \n"
- "movl %%esp, %%eax \n"
- "addl $20, %%eax \n"//4 bytes + 16 bytes = arguments
- "push %%ecx \n"
- "ret \n"
- :
- :"g" ( as)
- );
-
-
- return NULL;
-}
--- trunk/reactos/lib/crtdll/stdlib/atexit.c 2005-08-22 14:26:37 UTC (rev 17475)
+++ trunk/reactos/lib/crtdll/old cruft/stdlib/stdlib/atexit.c 2005-08-22 14:39:10 UTC (rev 17476)
@@ -1,21 +0,0 @@
-/* Copyright (C) 1994 DJ Delorie, see COPYING.DJ for details */
-#include <msvcrt/stdlib.h>
-#include <msvcrt/internal/atexit.h>
-
-/*
- * @implemented
- */
-int
-atexit(void (*a)(void))
-{
- struct __atexit *ap;
- if (a == 0)
- return -1;
- ap = (struct __atexit *)malloc(sizeof(struct __atexit));
- if (!ap)
- return -1;
- ap->__next = __atexit_ptr;
- ap->__function = a;
- __atexit_ptr = ap;
- return 0;
-}
--- trunk/reactos/lib/crtdll/stdlib/calloc.c 2005-08-22 14:26:37 UTC (rev 17475)
+++ trunk/reactos/lib/crtdll/old cruft/stdlib/stdlib/calloc.c 2005-08-22 14:39:10 UTC (rev 17476)
@@ -1,15 +0,0 @@
-/* Copyright (C) 1994 DJ Delorie, see COPYING.DJ for details */
-#include <msvcrt/stdlib.h>
-#include <msvcrt/string.h>
-
-/*
- * @implemented
- */
-void *
-calloc(size_t size, size_t nelem)
-{
- void *rv = malloc(size*nelem);
- if (rv)
- memset(rv, 0, size*nelem);
- return rv;
-}
--- trunk/reactos/lib/crtdll/stdlib/errno.c 2005-08-22 14:26:37 UTC (rev 17475)
+++ trunk/reactos/lib/crtdll/old cruft/stdlib/stdlib/errno.c 2005-08-22 14:39:10 UTC (rev 17476)
@@ -1,71 +0,0 @@
-#include <precomp.h>
-#include <msvcrt/errno.h>
-#include "../../msvcrt/stdlib/doserrmap.h"
-
-#undef errno
-int errno;
-
-#undef _doserrno
-int _doserrno;
-
-#undef _fpecode
-int fpecode;
-
-/*
- * @implemented
- */
-int *_errno(void)
-{
- return &errno;
-}
-
-int __set_errno (int error)
-{
- errno = error;
- return error;
-}
-
-/*
- * @implemented
- */
-int * __fpecode ( void )
-{
- return &fpecode;
-}
-
-/*
- * @implemented
- */
-int* __doserrno(void)
-{
- _doserrno = GetLastError();
- return &_doserrno;
-}
-
-/*
- * This function sets both doserrno to the passed in OS error code
- * and also maps this to an appropriate errno code. The mapping
- * has been deduced automagically by running this functions, which
- * exists in MSVCRT but is undocumented, on all the error codes in
- * winerror.h.
- */
-void _dosmaperr(unsigned long oserror)
-{
- int pos, base, lim;
-
- SetLastError(oserror);
-
- /* Use binary chop to find the corresponding errno code */
- for (base=0, lim=sizeof(doserrmap)/sizeof(doserrmap[0]); lim; lim >>= 1) {
- pos = base+(lim >> 1);
- if (doserrmap[pos].winerr == oserror) {
- __set_errno(doserrmap[pos].en);
- return;
- } else if (doserrmap[pos].winerr > oserror) {
- base = pos + 1;
- --lim;
- }
- }
- /* EINVAL appears to be the default */
- __set_errno(EINVAL);
-}
--- trunk/reactos/lib/crtdll/stdlib/fullpath.c 2005-08-22 14:26:37 UTC (rev 17475)
+++ trunk/reactos/lib/crtdll/old cruft/stdlib/stdlib/fullpath.c 2005-08-22 14:39:10 UTC (rev 17476)
@@ -1,31 +0,0 @@
-/*
- * COPYRIGHT: See COPYING in the top level directory
- * PROJECT: ReactOS system libraries
- * FILE: lib/crtdll/stdlib/fullpath.c
- * PURPOSE: Gets the fullpathname
- * PROGRAMER: Boudewijn Dekker
- * UPDATE HISTORY:
- * 28/12/98: Created
- */
-
-#include <precomp.h>
-#include <msvcrt/stdlib.h>
-
-#undef fullpath
-char *fullpath(char *absPath, const char *relPath, size_t maxLength)
-{
- return _fullpath(absPath,relPath,maxLength );
-}
-
-/*
- * @implemented
- */
-char* _fullpath(char* absPath, const char* relPath, size_t maxLength)
-{
- char* lpFilePart;
-
- if (GetFullPathNameA(relPath,maxLength,absPath,&lpFilePart) == 0)
- return NULL;
-
- return absPath;
-}
--- trunk/reactos/lib/crtdll/stdlib/itoa.c 2005-08-22 14:26:37 UTC (rev 17475)
+++ trunk/reactos/lib/crtdll/old cruft/stdlib/stdlib/itoa.c 2005-08-22 14:39:10 UTC (rev 17476)
@@ -1,155 +0,0 @@
-/*
- * COPYRIGHT: See COPYING in the top level directory
- * PROJECT: ReactOS system libraries
- * FILE: lib/crtdll/stdlib/itoa.c
- * PURPOSE: converts a integer to ascii
- * PROGRAMER:
- * UPDATE HISTORY:
- * 1995: Created
- * 1998: Added ltoa Boudewijn Dekker
- */
-/* Copyright (C) 1995 DJ Delorie, see COPYING.DJ for details */
-
-#include <msvcrt/errno.h>
-#include <msvcrt/stdlib.h>
-#include <msvcrt/internal/file.h>
-
-
-/*
- * @implemented
- *
- * this function is now forwarded to NTDLL._itoa to reduce code duplication
- */
-#if 0
-char* _itoa(int value, char* string, int radix)
-{
- char tmp[33];
- char *tp = tmp;
- int i;
- unsigned v;
- int sign;
- char *sp;
-
- if (radix > 36 || radix <= 1)
- {
- __set_errno(EDOM);
- return 0;
- }
-
- sign = (radix == 10 && value < 0);
- if (sign)
- v = -value;
- else
- v = (unsigned)value;
- while (v || tp == tmp)
- {
- i = v % radix;
- v = v / radix;
- if (i < 10)
- *tp++ = i+'0';
- else
- *tp++ = i + 'a' - 10;
- }
-
- if (string == 0)
- string = (char *)malloc((tp-tmp)+sign+1);
- sp = string;
-
- if (sign)
- *sp++ = '-';
- while (tp > tmp)
- *sp++ = *--tp;
- *sp = 0;
- return string;
-}
-#endif
-
-/*
- * @implemented
- *
- * this function is now forwarded to NTDLL._ltoa to reduce code duplication
- */
-#if 0
-char* _ltoa(long value, char* string, int radix)
-{
- char tmp[33];
- char *tp = tmp;
- long i;
- unsigned long v;
- int sign;
- char *sp;
-
- if (radix > 36 || radix <= 1)
- {
- __set_errno(EDOM);
- return 0;
- }
-
- sign = (radix == 10 && value < 0);
- if (sign)
- v = -value;
- else
- v = (unsigned long)value;
- while (v || tp == tmp)
- {
- i = v % radix;
- v = v / radix;
- if (i < 10)
- *tp++ = i+'0';
- else
- *tp++ = i + 'a' - 10;
- }
-
- if (string == 0)
- string = (char *)malloc((tp-tmp)+sign+1);
- sp = string;
-
- if (sign)
- *sp++ = '-';
- while (tp > tmp)
- *sp++ = *--tp;
- *sp = 0;
- return string;
-}
-#endif
-
-/*
- * @implemented
- *
- * this function is now forwarded to NTDLL._ultoa to reduce code duplication
- */
-#if 0
-char* _ultoa(unsigned long value, char* string, int radix)
-{
- char tmp[33];
- char *tp = tmp;
- long i;
- unsigned long v = value;
- char *sp;
-
- if (radix > 36 || radix <= 1)
- {
- __set_errno(EDOM);
- return 0;
- }
-
- while (v || tp == tmp)
- {
- i = v % radix;
- v = v / radix;
- if (i < 10)
- *tp++ = i+'0';
- else
- *tp++ = i + 'a' - 10;
- }
-
- if (string == 0)
- string = (char *)malloc((tp-tmp)+1);
- sp = string;
-
- while (tp > tmp)
- *sp++ = *--tp;
- *sp = 0;
- return string;
-}
-#endif
--- trunk/reactos/lib/crtdll/stdlib/itow.c 2005-08-22 14:26:37 UTC (rev 17475)
+++ trunk/reactos/lib/crtdll/old cruft/stdlib/stdlib/itow.c 2005-08-22 14:39:10 UTC (rev 17476)
@@ -1,168 +0,0 @@
-/* $Id$
- *
- * COPYRIGHT: See COPYING in the top level directory
- * PROJECT: ReactOS system libraries
- * FILE: lib/crtdll/stdlib/itow.c
- * PURPOSE: converts a integer to wchar_t
- * PROGRAMER:
- * UPDATE HISTORY:
- * 1995: Created
- * 1998: Added ltoa Boudewijn Dekker
- * 2000: derived from ./itoa.c by ea
- */
-/* Copyright (C) 1995 DJ Delorie, see COPYING.DJ for details */
-
-#include <msvcrt/errno.h>
-#include <msvcrt/stdlib.h>
-#include <msvcrt/internal/file.h>
-
-
-/*
- * @implemented
- *
- * this function is now forwarded to NTDLL._itow to reduce code duplication
- */
-#if 0
-wchar_t* _itow(int value, wchar_t* string, int radix)
-{
- wchar_t tmp [33];
- wchar_t * tp = tmp;
- int i;
- unsigned int v;
- int sign;
- wchar_t * sp;
-
- if (radix > 36 || radix <= 1)
- {
- __set_errno(EDOM);
- return 0;
- }
-
- sign = ((radix == 10) && (value < 0));
- if (sign) {
- v = -value;
- } else {
- v = (unsigned) value;
- }
- while (v || tp == tmp) {
- i = v % radix;
- v = v / radix;
- if (i < 10) {
- *tp++ = i+ (wchar_t) '0';
- } else {
- *tp++ = i + (wchar_t) 'a' - 10;
- }
- }
-
- if (string == 0) {
- string = (wchar_t *) malloc((tp-tmp) + (sign + 1) * sizeof(wchar_t));
- }
- sp = string;
-
- if (sign) {
- *sp++ = (wchar_t) '-';
- }
- while (tp > tmp) {
- *sp++ = *--tp;
- }
- *sp = (wchar_t) 0;
- return string;
-}
-#endif
-
-/*
- * @implemented
- *
- * this function is now forwarded to NTDLL._ltow to reduce code duplication
- */
-#if 0
-wchar_t* _ltow(long value, wchar_t* string, int radix)
-{
- wchar_t tmp [33];
- wchar_t * tp = tmp;
- long int i;
- unsigned long int v;
- int sign;
- wchar_t * sp;
-
- if (radix > 36 || radix <= 1) {
- __set_errno(EDOM);
- return 0;
- }
-
- sign = ((radix == 10) && (value < 0));
- if (sign) {
- v = -value;
- } else {
- v = (unsigned long) value;
- }
- while (v || tp == tmp) {
- i = v % radix;
- v = v / radix;
- if (i < 10) {
- *tp++ = i + (wchar_t) '0';
- } else {
- *tp++ = i + (wchar_t) 'a' - 10;
- }
- }
-
- if (string == 0) {
- string = (wchar_t *) malloc((tp - tmp) + (sign + 1) * sizeof(wchar_t));
- }
- sp = string;
-
- if (sign) {
- *sp++ = (wchar_t) '-';
- }
- while (tp > tmp) {
- *sp++ = *--tp;
- }
- *sp = (wchar_t) 0;
- return string;
-}
-#endif
-
-/*
- * @implemented
- *
- * this function is now forwarded to NTDLL._ultow to reduce code duplication
- */
-#if 0
-wchar_t* _ultow(unsigned long value, wchar_t* string, int radix)
-{
- wchar_t tmp [33];
- wchar_t * tp = tmp;
- long int i;
- unsigned long int v = value;
- wchar_t * sp;
-
- if (radix > 36 || radix <= 1) {
- __set_errno(EDOM);
- return 0;
- }
- while (v || tp == tmp) {
- i = v % radix;
- v = v / radix;
- if (i < 10) {
- *tp++ = i + (wchar_t) '0';
- } else {
- *tp++ = i + (wchar_t) 'a' - 10;
- }
- }
-
- if (string == 0) {
-#ifdef _MSVCRT_LIB_ // TODO: check on difference?
- string = (wchar_t *)malloc(((tp-tmp)+1)*sizeof(wchar_t));
-#else // TODO: FIXME: review which is correct
- string = (wchar_t *) malloc((tp - tmp) + sizeof(wchar_t));
-#endif /*_MSVCRT_LIB_*/
- }
- sp = string;
-
- while (tp > tmp) {
- *sp++ = *--tp;
- }
- *sp = (wchar_t) 0;
- return string;
-}
-#endif
--- trunk/reactos/lib/crtdll/stdlib/llabs.c 2005-08-22 14:26:37 UTC (rev 17475)
+++ trunk/reactos/lib/crtdll/old cruft/stdlib/stdlib/llabs.c 2005-08-22 14:39:10 UTC (rev 17476)
@@ -1,9 +0,0 @@
-/* Copyright (C) 1996 DJ Delorie, see COPYING.DJ for details */
-/* Copyright (C) 1994 DJ Delorie, see COPYING.DJ for details */
-#include <msvcrt/stdlib.h>
-
-long long
-llabs(long long j)
-{
- return j<0 ? -j : j;
-}
--- trunk/reactos/lib/crtdll/stdlib/lldiv.c 2005-08-22 14:26:37 UTC (rev 17475)
+++ trunk/reactos/lib/crtdll/old cruft/stdlib/stdlib/lldiv.c 2005-08-22 14:39:10 UTC (rev 17476)
@@ -1,26 +0,0 @@
-/* Copyright (C) 1996 DJ Delorie, see COPYING.DJ for details */
-/* Copyright (C) 1994 DJ Delorie, see COPYING.DJ for details */
-#include <msvcrt/stdlib.h>
-
-lldiv_t
-lldiv(long long num, long long denom)
-{
- lldiv_t r;
-
- if (num > 0 && denom < 0)
- {
- num = -num;
- denom = -denom;
- }
- r.quot = num / denom;
- r.rem = num % denom;
- if (num < 0 && denom > 0)
- {
- if (r.rem > 0)
- {
- r.quot++;
- r.rem -= denom;
- }
- }
- return r;
-}
--- trunk/reactos/lib/crtdll/stdlib/makepath.c 2005-08-22 14:26:37 UTC (rev 17475)
+++ trunk/reactos/lib/crtdll/old cruft/stdlib/stdlib/makepath.c 2005-08-22 14:39:10 UTC (rev 17476)
@@ -1,35 +0,0 @@
-/* $Id$
- */
-#include <msvcrt/stdlib.h>
-#include <msvcrt/string.h>
-
-/*
- * @implemented
- */
-void _makepath(char *path, const char *drive, const char *dir, const char *fname, const char *ext)
-{
- int dir_len;
-
- if ((drive != NULL) && (*drive)) {
- strcpy(path, drive);
- strcat(path, ":");
- } else {
- (*path)=0;
- }
-
- if (dir != NULL) {
- strcat(path, dir);
- dir_len = strlen(dir);
- if (dir_len && *(dir + dir_len - 1) != '\\')
- strcat(path, "\\");
- }
-
- if (fname != NULL) {
- strcat(path, fname);
- if (ext != NULL && *ext != 0) {
- if (*ext != '.')
- strcat(path, ".");
- strcat(path, ext);
- }
- }
-}
--- trunk/reactos/lib/crtdll/stdlib/malloc.c 2005-08-22 14:26:37 UTC (rev 17475)
+++ trunk/reactos/lib/crtdll/old cruft/stdlib/stdlib/malloc.c 2005-08-22 14:39:10 UTC (rev 17476)
@@ -1,37 +0,0 @@
-#include <precomp.h>
-#include <msvcrt/stdlib.h>
-
-
-/*
- * @implemented
- */
-void* malloc(size_t _size)
-{
- return(HeapAlloc(GetProcessHeap(),0,_size));
-}
-
-/*
- * @implemented
- */
-void free(void* _ptr)
-{
- HeapFree(GetProcessHeap(),0,_ptr);
-}
-
-/*
- * @implemented
- */
-void* calloc(size_t _nmemb, size_t _size)
-{
- return(HeapAlloc(GetProcessHeap(),HEAP_ZERO_MEMORY, _nmemb*_size));
-}
-
-/*
- * @implemented
- */
-void* realloc(void* _ptr, size_t _size)
-{
- if (!_ptr)
- return(HeapAlloc(GetProcessHeap(),0,_size));
- return(HeapReAlloc(GetProcessHeap(),0,_ptr,_size));
-}
--- trunk/reactos/lib/crtdll/stdlib/mbstowcs.c 2005-08-22 14:26:37 UTC (rev 17475)
+++ trunk/reactos/lib/crtdll/old cruft/stdlib/stdlib/mbstowcs.c 2005-08-22 14:39:10 UTC (rev 17476)
@@ -1,17 +0,0 @@
-#include <stdlib.h>
-
-/*
- * @unimplemented
- */
-size_t mbstowcs( wchar_t *wcstr, const char *mbstr, size_t count )
-{
- return 0;
-}
-
-/*
- * @unimplemented
- */
-int mbtowc( wchar_t *wchar, const char *mbchar, size_t count )
-{
- return 0;
-}
--- trunk/reactos/lib/crtdll/stdlib/putenv.c 2005-08-22 14:26:37 UTC (rev 17475)
+++ trunk/reactos/lib/crtdll/old cruft/stdlib/stdlib/putenv.c 2005-08-22 14:39:10 UTC (rev 17476)
@@ -1,23 +0,0 @@
-#include <precomp.h>
-#include <msvcrt/stdlib.h>
-#include <msvcrt/string.h>
-
-
-
-int putenv(const char *val)
-{
-
- char buffer[1024];
- char *epos;
-
- strcpy(buffer,val);
-
-
- epos = strchr(buffer, '=');
- if ( epos == NULL )
- return -1;
-
- *epos = 0;
-
- return SetEnvironmentVariableA(buffer,epos+1);
-}
--- trunk/reactos/lib/crtdll/stdlib/qsort.c 2005-08-22 14:26:37 UTC (rev 17475)
+++ trunk/reactos/lib/crtdll/old cruft/stdlib/stdlib/qsort.c 2005-08-22 14:39:10 UTC (rev 17476)
@@ -1,239 +0,0 @@
-/* Copyright (C) 1994 DJ Delorie, see COPYING.DJ for details */
-#include <msvcrt/stdlib.h>
-
-/*-
- * Copyright (c) 1980, 1983 The Regents of the University of California.
- * All rights reserved.
- *
- * Redistribution and use in source and binary forms are permitted
- * provided that: (1) source distributions retain this entire copyright
- * notice and comment, and (2) distributions including binaries display
- * the following acknowledgement: ``This product includes software
- * developed by the University of California, Berkeley and its contributors''
- * in the documentation or other materials provided with the distribution
- * and in all advertising materials mentioning features or use of this
- * software. 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 ``AS IS'' AND WITHOUT ANY EXPRESS OR
- * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
- * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
- */
-
-/*
- * qsort.c:
- * Our own version of the system qsort routine which is faster by an average
- * of 25%, with lows and highs of 10% and 50%.
- * The THRESHold below is the insertion sort threshold, and has been adjusted
- * for records of size 48 bytes.
- * The MTHREShold is where we stop finding a better median.
- */
-
-#define THRESH 4 /* threshold for insertion */
-#define MTHRESH 6 /* threshold for median */
-
-static int (*qcmp)(const void *, const void *); /* the comparison routine */
-static int qsz; /* size of each record */
-static int thresh; /* THRESHold in chars */
-static int mthresh; /* MTHRESHold in chars */
-
-/*
- * qst:
- * Do a quicksort
- * First, find the median element, and put that one in the first place as the
- * discriminator. (This "median" is just the median of the first, last and
- * middle elements). (Using this median instead of the first element is a big
- * win). Then, the usual partitioning/swapping, followed by moving the
- * discriminator into the right place. Then, figure out the sizes of the two
- * partions, do the smaller one recursively and the larger one via a repeat of
- * this code. Stopping when there are less than THRESH elements in a partition
- * and cleaning up with an insertion sort (in our caller) is a huge win.
- * All data swaps are done in-line, which is space-losing but time-saving.
- * (And there are only three places where this is done).
- */
-
-static void
-qst(char *base, char *max)
-{
- char c, *i, *j, *jj;
- int ii;
- char *mid, *tmp;
- int lo, hi;
-
- /*
- * At the top here, lo is the number of characters of elements in the
- * current partition. (Which should be max - base).
- * Find the median of the first, last, and middle element and make
- * that the middle element. Set j to largest of first and middle.
- * If max is larger than that guy, then it's that guy, else compare
- * max with loser of first and take larger. Things are set up to
- * prefer the middle, then the first in case of ties.
- */
- lo = max - base; /* number of elements as chars */
- do {
- mid = i = base + qsz * ((lo / qsz) >> 1);
- if (lo >= mthresh)
- {
- j = (qcmp((jj = base), i) > 0 ? jj : i);
- if (qcmp(j, (tmp = max - qsz)) > 0)
- {
- /* switch to first loser */
- j = (j == jj ? i : jj);
- if (qcmp(j, tmp) < 0)
- j = tmp;
- }
- if (j != i)
- {
- ii = qsz;
- do {
- c = *i;
- *i++ = *j;
- *j++ = c;
- } while (--ii);
- }
- }
- /*
- * Semi-standard quicksort partitioning/swapping
- */
- for (i = base, j = max - qsz; ; )
- {
- while (i < mid && qcmp(i, mid) <= 0)
- i += qsz;
- while (j > mid)
- {
- if (qcmp(mid, j) <= 0)
- {
- j -= qsz;
- continue;
- }
- tmp = i + qsz; /* value of i after swap */
- if (i == mid)
- {
- /* j <-> mid, new mid is j */
- mid = jj = j;
- }
- else
- {
- /* i <-> j */
- jj = j;
- j -= qsz;
- }
- goto swap;
- }
- if (i == mid)
- {
- break;
- }
- else
- {
- /* i <-> mid, new mid is i */
- jj = mid;
- tmp = mid = i; /* value of i after swap */
- j -= qsz;
- }
- swap:
- ii = qsz;
- do {
- c = *i;
- *i++ = *jj;
- *jj++ = c;
- } while (--ii);
- i = tmp;
- }
- /*
- * Look at sizes of the two partitions, do the smaller
- * one first by recursion, then do the larger one by
- * making sure lo is its size, base and max are update
- * correctly, and branching back. But only repeat
- * (recursively or by branching) if the partition is
- * of at least size THRESH.
- */
- i = (j = mid) + qsz;
- if ((lo = j - base) <= (hi = max - i))
- {
- if (lo >= thresh)
- qst(base, j);
- base = i;
- lo = hi;
- }
- else
- {
- if (hi >= thresh)
- qst(i, max);
- max = j;
- }
- } while (lo >= thresh);
-}
-
-/*
- * qsort:
- * First, set up some global parameters for qst to share. Then, quicksort
- * with qst(), and then a cleanup insertion sort ourselves. Sound simple?
- * It's not...
- *
- * @implemented
- */
-void
-qsort(const void *base0, size_t n, size_t size, _pfunccmp_t compar)
-{
- char *base = (char *)base0;
- char c, *i, *j, *lo, *hi;
- char *min, *max;
-
- if (n <= 1)
- return;
- qsz = size;
- qcmp = compar;
- thresh = qsz * THRESH;
- mthresh = qsz * MTHRESH;
- max = base + n * qsz;
- if (n >= THRESH)
- {
- qst(base, max);
- hi = base + thresh;
- }
- else
- {
- hi = max;
- }
- /*
- * First put smallest element, which must be in the first THRESH, in
- * the first position as a sentinel. This is done just by searching
- * the first THRESH elements (or the first n if n < THRESH), finding
- * the min, and swapping it into the first position.
- */
- for (j = lo = base; (lo += qsz) < hi; )
- if (qcmp(j, lo) > 0)
- j = lo;
- if (j != base)
- {
- /* swap j into place */
- for (i = base, hi = base + qsz; i < hi; )
- {
- c = *j;
- *j++ = *i;
- *i++ = c;
- }
- }
- /*
- * With our sentinel in place, we now run the following hyper-fast
- * insertion sort. For each remaining element, min, from [1] to [n-1],
- * set hi to the index of the element AFTER which this one goes.
- * Then, do the standard insertion sort shift on a character at a time
- * basis for each element in the frob.
- */
- for (min = base; (hi = min += qsz) < max; )
- {
- while (qcmp(hi -= qsz, min) > 0)
- /* void */;
- if ((hi += qsz) != min) {
- for (lo = min + qsz; --lo >= min; )
- {
- c = *lo;
- for (i = j = lo; (j -= qsz) >= hi; i = j)
- *i = *j;
- *i = c;
- }
- }
- }
-}
[truncated at 1000 lines; 498 more skipped]