/**********************************************************************
util.c -
$Author$
created at: Fri Mar 10 17:22:34 JST 1995
Copyright (C) 1993-2008 Yukihiro Matsumoto
**********************************************************************/
#include "ruby/ruby.h"
#include <ctype.h>
#include <stdio.h>
#include <errno.h>
#include <math.h>
#include <float.h>
#ifdef _WIN32
#include "missing/file.h"
#endif
#if defined(__CYGWIN32__)
#define _open open
#define _close close
#define _unlink unlink
#define _access access
#elif defined(_WIN32)
#include <io.h>
#endif
#include "ruby/util.h"
unsigned long
ruby_scan_oct(const char *start, int len, int *retlen)
{
register const char *s = start;
register unsigned long retval = 0;
while (len-- && *s >= '0' && *s <= '7') {
retval <<= 3;
retval |= *s++ - '0';
}
*retlen = s - start;
return retval;
}
unsigned long
ruby_scan_hex(const char *start, int len, int *retlen)
{
static const char hexdigit[] = "0123456789abcdef0123456789ABCDEF";
register const char *s = start;
register unsigned long retval = 0;
char *tmp;
while (len-- && *s && (tmp = strchr(hexdigit, *s))) {
retval <<= 4;
retval |= (tmp - hexdigit) & 15;
s++;
}
*retlen = s - start;
return retval;
}
static unsigned long
scan_digits(const char *str, int base, size_t *retlen, int *overflow)
{
static signed char table[] = {
/* 0 1 2 3 4 5 6 7 8 9 a b c d e f */
/*0*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
/*1*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
/*2*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
/*3*/ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,-1,-1,-1,-1,-1,-1,
/*4*/ -1,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,
/*5*/ 25,26,27,28,29,30,31,32,33,34,35,-1,-1,-1,-1,-1,
/*6*/ -1,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,
/*7*/ 25,26,27,28,29,30,31,32,33,34,35,-1,-1,-1,-1,-1,
/*8*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
/*9*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
/*a*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
/*b*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
/*c*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
/*d*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
/*e*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
/*f*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
};
const char *start = str;
unsigned long ret = 0, x;
unsigned long mul_overflow = (~(unsigned long)0) / base;
int c;
*overflow = 0;
while ((c = (unsigned char)*str++) != '\0') {
int d = table[c];
if (d == -1 || base <= d) {
*retlen = (str-1) - start;
return ret;
}
if (mul_overflow < ret)
*overflow = 1;
ret *= base;
x = ret;
ret += d;
if (ret < x)
*overflow = 1;
}
*retlen = (str-1) - start;
return ret;
}
unsigned long
ruby_strtoul(const char *str, char **endptr, int base)
{
int c, b, overflow;
int sign = 0;
size_t len;
unsigned long ret;
const char *subject_found = str;
if (base == 1 || 36 < base) {
errno = EINVAL;
return 0;
}
while ((c = *str) && ISSPACE(c))
str++;
if (c == '+') {
sign = 1;
str++;
}
else if (c == '-') {
sign = -1;
str++;
}
if (str[0] == '0') {
subject_found = str+1;
if (base == 0 || base == 16) {
if (str[1] == 'x' || str[1] == 'X') {
b = 16;
str += 2;
}
else {
b = base == 0 ? 8 : 16;
str++;
}
}
else {
b = base;
str++;
}
}
else {
b = base == 0 ? 10 : base;
}
ret = scan_digits(str, b, &len, &overflow);
if (0 < len)
subject_found = str+len;
if (endptr)
*endptr = (char*)subject_found;
if (overflow) {
errno = ERANGE;
return ULONG_MAX;
}
if (sign < 0) {
ret = -ret;
return ret;
}
else {
return ret;
}
}
#include <sys/types.h>
#include <sys/stat.h>
#ifdef HAVE_UNISTD_H
#include <unistd.h>
#endif
#if defined(HAVE_FCNTL_H)
#include <fcntl.h>
#endif
#ifndef S_ISDIR
# define S_ISDIR(m) ((m & S_IFMT) == S_IFDIR)
#endif
#if defined(__CYGWIN32__) || defined(_WIN32)
/*
* Copyright (c) 1993, Intergraph Corporation
*
* You may distribute under the terms of either the GNU General Public
* License or the Artistic License, as specified in the perl README file.
*
* Various Unix compatibility functions and NT specific functions.
*
* Some of this code was derived from the MSDOS port(s) and the OS/2 port.
*
*/
/*
* Suffix appending for in-place editing under MS-DOS and OS/2 (and now NT!).
*
* Here are the rules:
*
* Style 0: Append the suffix exactly as standard perl would do it.
* If the filesystem groks it, use it. (HPFS will always
* grok it. So will NTFS. FAT will rarely accept it.)
*
* Style 1: The suffix begins with a '.'. The extension is replaced.
* If the name matches the original name, use the fallback method.
*
* Style 2: The suffix is a single character, not a '.'. Try to add the
* suffix to the following places, using the first one that works.
* [1] Append to extension.
* [2] Append to filename,
* [3] Replace end of extension,
* [4] Replace end of filename.
* If the name matches the original name, use the fallback method.
*
* Style 3: Any other case: Ignore the suffix completely and use the
* fallback method.
*
* Fallback method: Change the extension to ".$$$". If that matches the
* original name, then change the extension to ".~~~".
*
* If filename is more than 1000 characters long, we die a horrible
* death. Sorry.
*
* The filename restriction is a cheat so that we can use buf[] to store
* assorted temporary goo.
*
* Examples, assuming style 0 failed.
*
* suffix = ".bak" (style 1)
* foo.bar => foo.bak
* foo.bak => foo.$$$ (fallback)
* foo.$$$ => foo.~~~ (fallback)
* makefile => makefile.bak
*
* suffix = "~" (style 2)
* foo.c => foo.c~
* foo.c~ => foo.c~~
* foo.c~~ => foo~.c~~
* foo~.c~~ => foo~~.c~~
* foo~~~~~.c~~ => foo~~~~~.$$$ (fallback)
*
* foo.pas => foo~.pas
* makefile => makefile.~
* longname.fil => longname.fi~
* longname.fi~ => longnam~.fi~
* longnam~.fi~ => longnam~.$$$
*
*/
static int valid_filename(const char *s);
static const char suffix1[] = ".$$$";
static const char suffix2[] = ".~~~";
#define ext (&buf[1000])
#define strEQ(s1,s2) (strcmp(s1,s2) == 0)
void
ruby_add_suffix(VALUE str, const char *suffix)
{
int baselen;
int extlen = strlen(suffix);
char *s, *t, *p;
long slen;
char buf[1024];
if (RSTRING_LEN(str) > 1000)
rb_fatal("Cannot do inplace edit on long filename (%ld characters)",
RSTRING_LEN(str));
#if defined(__CYGWIN32__) || defined(_WIN32)
/* Style 0 */
slen = RSTRING_LEN(str);
rb_str_cat(str, suffix, extlen);
if (valid_filename(RSTRING_PTR(str))) return;
/* Fooey, style 0 failed. Fix str before continuing. */
rb_str_resize(str, slen);
#endif
slen = extlen;
t = buf; baselen = 0; s = RSTRING_PTR(str);
while ((*t = *s) && *s != '.') {
baselen++;
if (*s == '\\' || *s == '/') baselen = 0;
s++; t++;
}
p = t;
t = ext; extlen = 0;
while ((*t++ = *s++) != 0) extlen++;
if (extlen == 0) { ext[0] = '.'; ext[1] = 0; extlen++; }
if (*suffix == '.') { /* Style 1 */
if (strEQ(ext, suffix)) goto fallback;
strcpy(p, suffix);
}
else if (suffix[1] == '\0') { /* Style 2 */
if (extlen < 4) {
ext[extlen] = *suffix;
ext[++extlen] = '\0';
}
else if (baselen < 8) {
*p++ = *suffix;
}
else if (ext[3] != *suffix) {
ext[3] = *suffix;
}
else if (buf[7] != *suffix) {
buf[7] = *suffix;
}
else goto fallback;
strcpy(p, ext);
}
else { /* Style 3: Panic */
fallback:
(void)memcpy(p, strEQ(ext, suffix1) ? suffix2 : suffix1, 5);
}
rb_str_resize(str, strlen(buf));
memcpy(RSTRING_PTR(str), buf, RSTRING_LEN(str));
}
#if defined(__CYGWIN32__) || defined(_WIN32)
static int
valid_filename(const char *s)
{
int fd;
/*
// It doesn't exist, so see if we can open it.
*/
if ((fd = _open(s, O_CREAT|O_EXCL, 0666)) >= 0) {
_close(fd);
_unlink(s); /* don't leave it laying around */
return 1;
}
else if (errno == EEXIST) {
/* if the file exists, then it's a valid filename! */
return 1;
}
return 0;
}
#endif
#endif
/* mm.c */
#define A ((int*)a)
#define B ((int*)b)
#define C ((int*)c)
#define D ((int*)d)
#define mmprepare(base, size) do {\
if (((long)base & (0x3)) == 0)\
if (size >= 16) mmkind = 1;\
else mmkind = 0;\
else mmkind = -1;\
high = (size & (~0xf));\
low = (size & 0x0c);\
} while (0)\
#define mmarg mmkind, size, high, low
static void mmswap_(register char *a, register char *b, int mmkind, int size, int high, int low)
{
register int s;
if (a == b) return;
if (mmkind >= 0) {
if (mmkind > 0) {
register char *t = a + high;
do {
s = A[0]; A[0] = B[0]; B[0] = s;
s = A[1]; A[1] = B[1]; B[1] = s;
s = A[2]; A[2] = B[2]; B[2] = s;
s = A[3]; A[3] = B[3]; B[3] = s; a += 16; b += 16;
} while (a < t);
}
if (low != 0) { s = A[0]; A[0] = B[0]; B[0] = s;
if (low >= 8) { s = A[1]; A[1] = B[1]; B[1] = s;
if (low == 12) {s = A[2]; A[2] = B[2]; B[2] = s;}}}
}
else {
register char *t = a + size;
do {s = *a; *a++ = *b; *b++ = s;} while (a < t);
}
}
#define mmswap(a,b) mmswap_((a),(b),mmarg)
static void mmrot3_(register char *a, register char *b, register char *c, int mmkind, int size, int high, int low)
{
register int s;
if (mmkind >= 0) {
if (mmkind > 0) {
register char *t = a + high;
do {
s = A[0]; A[0] = B[0]; B[0] = C[0]; C[0] = s;
s = A[1]; A[1] = B[1]; B[1] = C[1]; C[1] = s;
s = A[2]; A[2] = B[2]; B[2] = C[2]; C[2] = s;
s = A[3]; A[3] = B[3]; B[3] = C[3]; C[3] = s; a += 16; b += 16; c += 16;
} while (a < t);
}
if (low != 0) { s = A[0]; A[0] = B[0]; B[0] = C[0]; C[0] = s;
if (low >= 8) { s = A[1]; A[1] = B[1]; B[1] = C[1]; C[1] = s;
if (low == 12) {s = A[2]; A[2] = B[2]; B[2] = C[2]; C[2] = s;}}}
}
else {
register char *t = a + size;
do {s = *a; *a++ = *b; *b++ = *c; *c++ = s;} while (a < t);
}
}
#define mmrot3(a,b,c) mmrot3_((a),(b),(c),mmarg)
/* qs6.c */
/*****************************************************/
/* */
/* qs6 (Quick sort function) */
/* */
/* by Tomoyuki Kawamura 1995.4.21 */
/* kawamura@tokuyama.ac.jp */
/*****************************************************/
typedef struct { char *LL, *RR; } stack_node; /* Stack structure for L,l,R,r */
#define PUSH(ll,rr) do { top->LL = (ll); top->RR = (rr); ++top; } while (0) /* Push L,l,R,r */
#define POP(ll,rr) do { --top; ll = top->LL; rr = top->RR; } while (0) /* Pop L,l,R,r */
#define med3(a,b,c) ((*cmp)(a,b,d)<0 ? \
((*cmp)(b,c,d)<0 ? b : ((*cmp)(a,c,d)<0 ? c : a)) : \
((*cmp)(b,c,d)>0 ? b : ((*cmp)(a,c,d)<0 ? a : c)))
void
ruby_qsort(void* base, const int nel, const int size,
int (*cmp)(const void*, const void*, void*), void *d)
{
register char *l, *r, *m; /* l,r:left,right group m:median point */
register int t, eq_l, eq_r; /* eq_l: all items in left group are equal to S */
char *L = base; /* left end of curren region */
char *R = (char*)base + size*(nel-1); /* right end of current region */
int chklim = 63; /* threshold of ordering element check */
stack_node stack[32], *top = stack; /* 32 is enough for 32bit CPU */
int mmkind, high, low;
if (nel <= 1) return; /* need not to sort */
mmprepare(base, size);
goto start;
nxt:
if (stack == top) return; /* return if stack is empty */
POP(L,R);
for (;;) {
start:
if (L + size == R) { /* 2 elements */
if ((*cmp)(L,R,d) > 0) mmswap(L,R); goto nxt;
}
l = L; r = R;
t = (r - l + size) / size; /* number of elements */
m = l + size * (t >> 1); /* calculate median value */
if (t >= 60) {
register char *m1;
register char *m3;
if (t >= 200) {
t = size*(t>>3); /* number of bytes in splitting 8 */
{
register char *p1 = l + t;
register char *p2 = p1 + t;
register char *p3 = p2 + t;
m1 = med3(p1, p2, p3);
p1 = m + t;
p2 = p1 + t;
p3 = p2 + t;
m3 = med3(p1, p2, p3);
}
}
else {
t = size*(t>>2); /* number of bytes in splitting 4 */
m1 = l + t;
m3 = m + t;
}
m = med3(m1, m, m3);
}
if ((t = (*cmp)(l,m,d)) < 0) { /*3-5-?*/
if ((t = (*cmp)(m,r,d)) < 0) { /*3-5-7*/
if (chklim && nel >= chklim) { /* check if already ascending order */
char *p;
chklim = 0;
for (p=l; p<r; p+=size) if ((*cmp)(p,p+size,d) > 0) goto fail;
goto nxt;
}
fail: goto loopA; /*3-5-7*/
}
if (t > 0) {
if ((*cmp)(l,r,d) <= 0) {mmswap(m,r); goto loopA;} /*3-5-4*/
mmrot3(r,m,l); goto loopA; /*3-5-2*/
}
goto loopB; /*3-5-5*/
}
if (t > 0) { /*7-5-?*/
if ((t = (*cmp)(m,r,d)) > 0) { /*7-5-3*/
if (chklim && nel >= chklim) { /* check if already ascending order */
char *p;
chklim = 0;
for (p=l; p<r; p+=size) if ((*cmp)(p,p+size,d) < 0) goto fail2;
while (l<r) {mmswap(l,r); l+=size; r-=size;} /* reverse region */
goto nxt;
}
fail2: mmswap(l,r); goto loopA; /*7-5-3*/
}
if (t < 0) {
if ((*cmp)(l,r,d) <= 0) {mmswap(l,m); goto loopB;} /*7-5-8*/
mmrot3(l,m,r); goto loopA; /*7-5-6*/
}
mmswap(l,r); goto loopA; /*7-5-5*/
}
if ((t = (*cmp)(m,r,d)) < 0) {goto loopA;} /*5-5-7*/
if (t > 0) {mmswap(l,r); goto loopB;} /*5-5-3*/
/* determining splitting type in case 5-5-5 */ /*5-5-5*/
for (;;) {
if ((l += size) == r) goto nxt; /*5-5-5*/
if (l == m) continue;
if ((t = (*cmp)(l,m,d)) > 0) {mmswap(l,r); l = L; goto loopA;}/*575-5*/
if (t < 0) {mmswap(L,l); l = L; goto loopB;} /*535-5*/
}
loopA: eq_l = 1; eq_r = 1; /* splitting type A */ /* left <= median < right */
for (;;) {
for (;;) {
if ((l += size) == r)
{l -= size; if (l != m) mmswap(m,l); l -= size; goto fin;}
if (l == m) continue;
if ((t = (*cmp)(l,m,d)) > 0) {eq_r = 0; break;}
if (t < 0) eq_l = 0;
}
for (;;) {
if (l == (r -= size))
{l -= size; if (l != m) mmswap(m,l); l -= size; goto fin;}
if (r == m) {m = l; break;}
if ((t = (*cmp)(r,m,d)) < 0) {eq_l = 0; break;}
if (t == 0) break;
}
mmswap(l,r); /* swap left and right */
}
loopB: eq_l = 1; eq_r = 1; /* splitting type B */ /* left < median <= right */
for (;;) {
for (;;) {
if (l == (r -= size))
|