#include "i.h"

// per process allocation bucket list
// a pointer to this can be found at procdata()
typedef struct Pbucket Pbucket;
struct Pbucket
{
	Pbucket	*next;
	uchar*	free;
	uchar*	end;
	int		pad;
	uchar	data[1];
};

#define datoff		((int)((Pbucket*)0)->data)

enum {
	PBCHUNKBIG = 1*1024*1024 - datoff,
	PBCHUNKSMALL = 8*1024 - datoff,
	PBALIGN = 4,	// align returned results on multiples of this
};


Rune* whitespace = L" \t\n\r";
Rune* notwhitespace = L"^ \t\n\r";

static Pbucket* newpbucket(int dsize, Pbucket* link);


// All lists start out like List structure.
// List itself can be used as list of int.
int
listlen(List* l)
{
	int n = 0;

	while(l != nil) {
		l = l->next;
		n++;
	}
	return n;
}

// Cons
List*
newlist(int val, List* rest)
{
	List* ans;

	ans = (List*)emalloc(sizeof(List));
	ans->val = val;
	ans->next = rest;
	return ans;
}

Strlist*
newstrlist(Rune* val, Strlist* rest)
{
	Strlist* ans;

	ans = (Strlist*)newlist(0, (List*)rest);
	ans->val = val;
	return ans;
}

// Reverse a list in place
List*
revlist(List* l)
{
	List* newl;
	List* nextl;

	newl = nil;
	while(l != nil) {
		nextl = l->next;
		l->next = newl;
		newl = l;
		l = nextl;
	}
	return newl;
}

// The next few routines take a "character class" as argument.
//    e.g., "a-zA-Z", or "^ \t\n"
// (ranges indicated by - except in first position;
//  ^ is first position means "not in" the following class)

// Splitl splits s[0:n] just before first character of class cl.
// Answers go in (p1, n1) and (p2, n2).
// If no split, the whole thing goes in the first component.
// Note: answers contain pointers into original string.
void
splitl(Rune* s, int n, Rune* cl, Rune** p1, int* n1, Rune** p2, int* n2)
{
	Rune* p;

	p = Strnclass(s, cl, n);
	*p1 = s;
	if(p == nil) {
		*n1 = n;
		*p2 = nil;
		*n2 = 0;
	}
	else {
		*p2 = p;
		*n1 = p-s;
		*n2 = n-*n1;
	}
}

// Splitr splits s[0:n] just after last character of class cl.
// Answers go in (p1, n1) and (p2, n2).
// If no split, the whole thing goes in the last component.
// Note: answers contain pointers into original string.
void
splitr(Rune* s, int n, Rune* cl, Rune** p1, int* n1, Rune** p2, int* n2)
{
	Rune* p;

	p = Strnrclass(s, cl, n);
	if(p == nil) {
		*p1 = nil;
		*n1 = 0;
		*p2 = s;
		*n2 = n;
	}
	else {
		*p1 = s;
		*p2 = p+1;
		*n1 = *p2-s;
		*n2 = n-*n1;
	}
}

// Splitall splits s[0:n] into parts that are separated by characters from class cl.
// Each part will have nonzero length.
// At most alen parts are found, and pointers to their starts go into
// the strarr array, while their lengths go into the lenarr array.
// The return value is the number of parts found.
int
splitall(Rune* s, int n, Rune* cl, Rune** strarr, int* lenarr, int alen)
{
	int i;
	Rune* p;
	Rune* q;
	Rune* slast;

	if(s == nil || n == 0)
		return 0;
	i = 0;
	p = s;
	slast = s+n;
	while(p < slast && i < alen) {
		while(p < slast && inclass(*p, cl))
			p++;
		if(p == slast)
			break;
		q = Strnclass(p, cl, slast-p);
		if(q == nil)
			q = slast;
		assert(q > p && q <= slast);
		strarr[i] = p;
		lenarr[i] = q-p;
		i++;
		p = q;
	}
	return i;
}

// Find part of s that excludes leading and trailing whitespace,
// and return that part in *pans (and its length in *panslen).
void
trimwhite(Rune* s, int n, Rune** pans, int* panslen)
{
	Rune* p;
	Rune* q;

	p = nil;
	if(n > 0) {
		p = Strnclass(s, notwhitespace, n);
		if(p != nil) {
			q = Strnrclass(s, notwhitespace, n);
			assert(q != nil);
			n = q+1-p;
		}
	}
	*pans = p;
	*panslen = n;
}

// Strclass returns a pointer to the first element of s that is
// a member of class cl, nil if none.
Rune*
Strclass(Rune* s, Rune* cl)
{
	Rune* p;

	for(p = s; *p != 0; p++)
		if(inclass(*p, cl))
			return p;
	return nil;
}

// Strclass returns a pointer to the first element of s that is
// a member of class cl, nil if none.
Rune*
Strnclass(Rune* s, Rune* cl, int n)
{
	Rune* p;

	for(p = s; n-- && *p != 0; p++)
		if(inclass(*p, cl))
			return p;
	return nil;
}

// Strrclass returns a pointer to the last element of s that is
// a member of class cl, nil if none
Rune*
Strrclass(Rune* s, Rune* cl)
{
	Rune* p;

	if(s == nil || *s == 0)
		return nil;
	p = s + Strlen(s) - 1;
	while(p >= s) {
		if(inclass(*p, cl))
			return p;
		p--;
	};
	return nil;
}

// Strrclass returns a pointer to the last element of s that is
// a member of class cl, nil if none
Rune*
Strnrclass(Rune* s, Rune* cl, int n)
{
	Rune* p;

	if(s == nil || *s == 0 || n == 0)
		return nil;
	p = s + n - 1;
	while(p >= s) {
		if(inclass(*p, cl))
			return p;
		p--;
	};
	return nil;
}

// Is c in the class cl?
int
inclass(Rune c, Rune* cl)
{
	int	n;
	int	ans;
	int	negate;
	int	i;

	n = Strlen(cl);
	if(n == 0)
		return 0;
	ans = 0;
	negate = 0;
	if(cl[0] == '^') {
		negate = 1;
		cl++;
		n--;
	}
	for(i = 0; i < n; i++) {
		if(cl[i] == '-' && i > 0 && i < n - 1) {
			if(c >= cl[i - 1] && c <= cl[i + 1]) {
				ans = 1;
				break;
			}
			i++;
		}
		else if(c == cl[i]) {
			ans = 1;
			break;
		}
	}
	if(negate)
		ans = !ans;
	return ans;
}

// Is pre a prefix of s?
int
prefix(Rune* pre, Rune* s)
{
	int	ns;
	int	n;
	int	k;

	ns = Strlen(s);
	n = Strlen(pre);
	if(ns < n)
		return 0;
	for(k = 0; k < n; k++) {
		if(pre[k] != s[k])
			return 0;
	}
	return 1;
}

// Number of runes in (null-terminated) s
int
Strlen(Rune* s)
{
	int n = 0;

	if(s != nil) {
		while(*s++)
			n++;
	}
	return n;
}

// -1, 0, 1 as s1 is lexicographically less, equal greater than s2
int
Strcmp(Rune *s1, Rune *s2)
{
	Rune c1, c2;

	if(s1 == nil)
		return (s2 == nil || *s2 == 0) ? 0 : -1;
	if(s2 == nil)
		return (*s1 == 0) ? 0 : 1;
	for(;;) {
		c1 = *s1++;
		c2 = *s2++;
		if(c1 != c2) {
			if(c1 > c2)
				return 1;
			return -1;
		}
		if(c1 == 0)
			return 0;
	}
}

// Like Strcmp, but use exactly n chars of s1 (assume s1 has at least n chars).
// Also, do a case-insensitive match, assuming s2
// has no chars in [A-Z], only their lowercase versions.
// (This routine is used for in-place keyword lookup, where s2 is in a keyword
// list and s1 is some substring, possibly mixed-case, in a buffer.)
int
Strncmpci(Rune *s1, int n1, Rune *s2)
{
	Rune c1, c2;

	for(;;) {
		if(n1-- == 0) {
			if(*s2 == 0)
				return 0;
			return -1;
		}
		c1 = *s1++;
		c2 = *s2++;
		if(c1 >= 'A' && c1 <= 'Z')
			c1 = c1 - 'A' + 'a';
		if(c1 != c2) {
			if(c1 > c2)
				return 1;
			return -1;
		}
	}
}

// Like Strcmp, but use exactly n chars of s1 (assume s1 has at least n chars).
int
Strncmp(Rune *s1, int n1, Rune *s2)
{
	Rune c1, c2;

	for(;;) {
		if(n1-- == 0) {
			if(*s2 == 0)
				return 0;
			return -1;
		}
		c1 = *s1++;
		c2 = *s2++;
		if(c1 != c2) {
			if(c1 > c2)
				return 1;
			return -1;
		}
	}
}

// Return true if first n1 chars of s1 (assumed to have at least n1 chars)
// match n1 chars of s2.
int
Streqn(Rune *s1, int n1, Rune *s2)
{
	for(;;) {
		if(n1-- == 0)
			return 1;
		if(*s1++ != *s2++)
			return 0;
	}
}

// Pointer within s to first occurence of c, or nil
Rune*
Strrune(Rune* s, Rune c)
{
	Rune c1;

	if(s != nil) {
		while(c1 = *s++)
			if(c1 == c)
				return s-1;
	}
	return 0;
}

// Pointer within s[0..n] to first occurence of c, or nil
Rune*
Strnrune(Rune* s, Rune c, int n)
{
	Rune c1;

	if(s != nil) {
		while(c1 = *s++ && n--)
			if(c1 == c)
				return s-1;
	}
	return 0;
}

// emalloc and copy
Rune*
Strdup(Rune* s)
{
	return Strndup(s, Strlen(s));
}

// emalloc and copy n chars of s (assume s is at least that long),
// and add 0 terminator.
// Return nil if n==0.
Rune*
Strndup(Rune* s, int n)
{
	Rune* ans;

	if(n <= 0)
		return nil;
	ans = newstr(n);
	memmove(ans, s, n*sizeof(Rune));
	ans[n] = 0;
	return ans;
}
// emalloc enough room for n Runes, plus 1 null terminator.
// (Not initialized to anything.)
Rune*
newstr(int n)
{
	return (Rune*)emalloc((n+1)*sizeof(Rune));
}

// emalloc and copy s+t
Rune*
Strdup2(Rune* s, Rune* t)
{
	int ns, nt;
	Rune* ans;
	Rune* p;

	ns = Strlen(s);
	nt = Strlen(t);
	if(ns+nt == 0)
		return nil;
	ans = newstr(ns+nt);
	p = Stradd(ans, s, ns);
	p = Stradd(p, t, nt);
	*p = 0;
	return ans;
}

// emalloc and copy s+t+u
Rune*
Strdup3(Rune* s, Rune* t, Rune* u)
{
	int ns, nt, nu;
	Rune* ans;
	Rune* p;

	ns = Strlen(s);
	nt = Strlen(t);
	nu = Strlen(u);
	if(ns+nt+nu == 0)
		return nil;
	ans = newstr(ns+nt+nu);
	p = Stradd(ans, s, ns);
	p = Stradd(p, t, nt);
	p = Stradd(p, u, nu);
	*p = 0;
	return ans;
}

// Return emalloc'd substring s[start:stop],
Rune*
Strsubstr(Rune* s, int start, int stop)
{
	Rune* t;

	if(start == stop)
		return nil;
	t = Strndup(s+start, stop-start);
	return t;
}

// Copy n chars to s1 from s2, filling with 0's if s2 is too short
void
Strncpy(Rune* s1, Rune* s2, int n)
{
	int i;

	for(i = 0; i < n; i++)
		if((*s1++ = *s2++) == 0) {
			while(++i < n)
				*s1++ = 0;
		}
}

// Like Strncpy, but don't check for s2 ending early,
// and return s1+n
Rune*
Stradd(Rune* s1, Rune* s2, int n)
{
	if(n == 0)
		return s1;
	memmove(s1, s2, n*sizeof(Rune));
	return s1+n;
}

// Like strtol, but converting from Rune* string

#define LONG_MAX	2147483647L
#define LONG_MIN	-2147483648L

long
Strtol(Rune* nptr, Rune** endptr, int base)
{
	Rune* p;
	long n, nn;
	int c, ovfl, v, neg, ndig;

	p = nptr;
	neg = 0;
	n = 0;
	ndig = 0;
	ovfl = 0;

	/*
	 * White space
	 */
	for(;;p++){
		switch(*p){
		case ' ':
		case '\t':
		case '\n':
		case '\f':
		case '\r':
		case '\v':
			continue;
		}
		break;
	}

	/*
	 * Sign
	 */
	if(*p=='-' || *p=='+')
		if(*p++ == '-')
			neg = 1;

	/*
	 * Base
	 */
	if(base==0){
		if(*p != '0')
			base = 10;
		else{
			base = 8;
			if(p[1]=='x' || p[1]=='X'){
				p += 2;
				base = 16;
			}
		}
	}else if(base==16 && *p=='0'){
		if(p[1]=='x' || p[1]=='X')
			p += 2;
	}else if(base<0 || 36<base)
		goto Return;

	/*
	 * Non-empty sequence of digits
	 */
	for(;; p++,ndig++){
		c = *p;
		v = base;
		if('0'<=c && c<='9')
			v = c - '0';
		else if('a'<=c && c<='z')
			v = c - 'a' + 10;
		else if('A'<=c && c<='Z')
			v = c - 'A' + 10;
		if(v >= base)
			break;
		nn = n*base + v;
		if(nn < n)
			ovfl = 1;
		n = nn;
	}

    Return:
	if(ndig == 0)
		p = nptr;
	if(endptr)
		*endptr = p;
	if(ovfl){
		if(neg)
			return LONG_MIN;
		return LONG_MAX;
	}
	if(neg)
		return -n;
	return n;
}

// Convert buf[0:n], bytes whose character set is chset,
// into a emalloc'd null-terminated Unicode string.
Rune*
toStr(uchar* buf, int n, int chset)
{
	int i;
	int m;
	Rune ch;
	Rune* ans;

	switch(chset) {
	case US_Ascii:
	case ISO_8859_1:
		ans = (Rune*)emalloc((n+1)*sizeof(Rune));
		for(i = 0; i < n; i++)
			ans[i] = buf[i];
		ans[n] = 0;
		break;

	case UTF_8:
		m = 0;
		for(i = 0; i < n; ) {
			i += chartorune(&ch, (char*)(buf+i));
			m++;
		}
		ans = (Rune*)emalloc((m+1)*sizeof(Rune));
		m = 0;
		for(i = 0; i < n; ) {
			i += chartorune(&ch, (char*)(buf+i));
			ans[m++] = ch;
		}
		ans[m] = 0;
		break;

	default:
		ans = nil;
		assert(0);
	}
	return ans;
}

// Convert buf[0:n], Unicode characters,
// into an emalloc'd null-terminated string in character set chset.
// Use 0x80 for unconvertable characters.
uchar*
fromStr(Rune* buf, int n, int chset)
{
	uchar* ans;
	int i, lim, m;
	Rune ch;
	uchar* p;
	uchar s[UTFmax];

	ans = nil;
	switch(chset) {
	case US_Ascii:
	case ISO_8859_1:
		ans = (uchar*)emalloc(n+1);
		lim = (chset==US_Ascii)? 127 : 255;
		for(i = 0; i < n; i++) {
			ch = buf[i];
			if(ch > lim)
				ch = 0x80;
			ans[i] = ch;
		}
		ans[n] = 0;
		break;

	case UTF_8:
		m = 0;
		for(i = 0; i < n; i++) {
			m += runetochar((char*)s, &buf[i]);
		}
		ans = (uchar*)emalloc(m+1);
		p = ans;
		for(i = 0; i < n; i++)
			p += runetochar((char*)p, &buf[i]);
		*p = 0;
		break;

	default:
		assert(0);
	}
	return ans;

}

// Convert n to emalloc'd String.
Rune*
ltoStr(int n)
{
	int m;
	uchar buf[20];

	m = snprint((char*)buf, sizeof(buf), "%d", n);
	return toStr(buf, m, US_Ascii);
}

int
max(int a, int b)
{
	if(a > b)
		return a;
	return b;
}

int
min(int a, int b)
{
	if(a < b)
		return a;
	return b;
}

// Alloc from per-process bulk memory list.
// (bulk free only)
// Panic if no room.
void*
emalloc(int size)
{
	uchar* ans;
	uchar* nextfree;
	Pbucket* b;
	int n, m;

	b = *(Pbucket**)procdata();
	assert(b != nil);
	ans = b->free;
	n = (size + PBALIGN-1) & ~(PBALIGN-1);
	nextfree = ans+n;
	if(nextfree > b->end) {
		m = b->end - b->data;
		b = newpbucket(max(m, n), b);
		if(b != nil) {
			*((Pbucket**)procdata()) = b;
			ans = b->free;
			b->free = ans+n;
		}
		else {
			trace("pmalloc malloc failed\n");
			fatalerror("no mem");
		}
	}
	else
		b->free = nextfree;
	return ans;
}

// emalloc with zeroing of result before returning.
void*
emallocz(int size)
{
	void* ans;

	ans = emalloc(size);
	memset(ans, 0, size);
	return ans;
}

void*
erealloc(void* p, int size)
{
	void* ans;

	ans =emalloc(size);
	if(p != nil)
		memmove(ans, p, size);
	return ans;
}

static Pbucket*
newpbucket(int dsize, Pbucket* link)
{
	uchar*	p;
	Pbucket* ans;

	p = (uchar*)malloc(datoff + dsize);
	if(p == nil)
		return nil;
	ans = (Pbucket*)p;
	ans->next = link;
	ans->free = p+datoff;
	ans->end = p+datoff+dsize;
	return ans;
}

// Reinitialize the allocation data structures for current proc,
// freeing everything that was there before.
void
freeshortlived(void)
{
	Pbucket* p;
	Pbucket* pnext;

	for(p = *((Pbucket**)procdata()); p != nil; p = pnext) {
		pnext = p->next;
		free(p);
	}
}

// Initialize per-process memory allocation structure.
// The grp flag tells the kind of arena to be made.
void
meminit(int grp)
{
	Pbucket* p;
	int n;

	if(grp == GRnone)
		p = nil;
	else  {
		n = grp == GRmain? PBCHUNKBIG : PBCHUNKSMALL;
		p = newpbucket(n, nil);
	}
	threadsetgrp(grp);
	*((Pbucket**)procdata()) = p;
}

// Debugging
int
validptr(void* p)
{
	// TODO: a better job of this.
	// For now, just dereference, which cause a bomb
	// if not valid
	static char c;

	c = *((char*)p);
	return 1;
}

int
validStr(Rune* s)
{
	return s != nil && validptr(s);
}