/* $Id: dstring.c,v 1.30 2003/05/23 15:28:14 aa5779 Exp $ */
/* dstring.c -- manipulating varying-length strings */
/*
	Copyright (C) 2001, 2002, 2003 Artem V. Andreev (artem@AA5779.spb.edu)

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

*/
#ifdef HAVE_CONFIG_H
#include <config.h>
#endif
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#ifdef ENABLE_FP
#include <float.h>
#include <stdio.h>
#endif
#include <limits.h>
#include "util.h"
#define DSTRING_IMP
#include "dstring.h"
/*** \file
This file contains routines to maninpulate dynamic strings (\em[dstrings])

\include[dstring.h.in]
*/

/*** \ifdef[maintainer] \group[Internal macros] */
/*** \macro[INITIAL_MAXLEN] Initial amount of memory allocated for a dstring */
#define INITIAL_MAXLEN 128
/**** \macro[MAXLEN_DELTA] The amount of memory used to expand a dstring */
#define MAXLEN_DELTA 16
/**** \endif */

/*** \group[Controlling variables] */
/*** \variable 
Contains the limit of memory occupied by free strings
*/
int ds_reserved_mem_limit = 1024 * 1024;

/*** \variable 
Contains the limit of memory occupied by unfixed strings
which triggers garbage collecting
*/
int ds_unfix_mem_limit = 256 * 1024;

/*** \variable
Contains the maximum number of unfixed strings which triggers
garbage collecting.
*/
int ds_unfix_max_cnt = 8192;

#define UNFIX_MAX_CNT (ds_unfix_max_cnt)
#define RESERVED_MEM_LIMIT (ds_reserved_mem_limit)
#define UNFIX_MEM_LIMIT (ds_unfix_mem_limit)
#define EMERGENCY_THRESHOLD 1024

/*** \ifdef[maintainer] \group[Internals] 
\variables[2]
All \em[unfixed] dynamic strings are chained in a double-linked list which starts at
\var[dstrings]. When a dstring is freed, it is moved into \var[free_strings] 
for later reuse.
\variables[3]
These variables contain the current amount of memory occupied by free strings,
of memory occupied by unfixed strings (\see[functions][ds_fix]) and
the number of unfixed strings. These values are used by a garbage collector
(\see[functions][ds_squeeze]).
*/
static dstring *dstrings;
static dstring *free_strings;
static int reserved_mem;
static int unfixed_mem;
static int unfixed_cnt;

/*** \function
Adds an item to a double-linked list.
*/
static dstring *dlink_add(dstring *base, dstring *item)
{
	if(base)
		base->prev = item;
	item->next = base;
	item->prev = NULL;
	base = item;
	return base;
}

/*** \function
Takes an item from \see[variables][free_strings]; if there is no
such item, a new item is allocated reserving \see[macros][INITIAL_MAXLEN] bytes
of memory.
*/
static dstring *alloc_dstring(void)
{
	dstring *newd;
	if(!free_strings)
	{
		newd = xmalloc(sizeof(dstring));
		newd->curlen = 0;
		newd->maxlen = INITIAL_MAXLEN;
		newd->fixcnt = 0;
		newd->str  = xmalloc(INITIAL_MAXLEN);
	}
	else
	{
		newd = free_strings;
		free_strings = free_strings->next;
		reserved_mem -= newd->maxlen;
	}
	unfixed_mem += newd->maxlen;
	unfixed_cnt++;
	dstrings = dlink_add(dstrings, newd);
	return newd;
}
/*** \endif */

/**** \group[Functions] ***/

/*** \function
If a dstring \var[ds]'s buffer is smaller than \var[len],
expands it adding yet \see[macros][MAXLEN_DELTA].
Sets the current length to \var[len]
*/
void ds_expand(dstring *ds, int len)
{
	if(ds->maxlen < len)
	{
		int old = ds->maxlen;
		ds->maxlen = len + MAXLEN_DELTA;
		ds->str = xrealloc(ds->str, ds->maxlen);
		if(!ds->fixcnt)
			unfixed_mem += ds->maxlen - old;
	}
	ds->curlen = len;
}

/**** \function
\returns an unfixed dstring containing a copy of \var[src] 
*/
dstring *ds_create(const char *src)
{
	dstring *newd = alloc_dstring();
	if(src)
	{	
		ds_expand(newd, strlen(src) + 1);
		strcpy(newd->str, src);
	}
	else
	{
		ds_expand(newd, 1);
		newd->str[0] = '\0';			
	}
	return newd;
}

/*** \function
\returns a dstring containing \var[src] itself (no copy)
\arg[len] is a length of a buffer. It is caller's responsibility
to ensure this is correct.
\note \var[src] should point to a malloc'ed memory.
*/
dstring *ds_icreate(char *src, int len)
{
	dstring *newd = ALLOC(dstring);
	newd->maxlen = newd->curlen = len;
	newd->fixcnt = 0;
	newd->str = src;
	dstrings = dlink_add(dstrings, newd);
	unfixed_mem += len;
	unfixed_cnt++;
	return newd;
}

/*** \function
\returns an unfixed dstring which contains a single \var[ch] 
*/
dstring *ds_createch(int ch)
{
	dstring *newd = alloc_dstring();
	ds_expand(newd, 2);
	newd->str[0] = ch;
	newd->str[1] = '\0';
	return newd;
}

static dstring *ds_num_pad(char *buf, int numlen, int len)
{
	dstring *newd = ds_create(NULL);
	if(len >= 0)
	{
		while(numlen < len)
		{
			numlen++;
			ds_appendch(newd, ' ');
		}
		ds_appendstr(newd, buf);
	}
	else
	{
		ds_appendstr(newd, buf);
		while(numlen < len)
		{
			numlen++;
			ds_appendch(newd, ' ');
		}
	}
	return newd;
}

/*** \function
\returns an unfixed dstring which contains a string representation of \var[val]
using \var[base] as a conversion base (\code[2 <= base <= 36]).
\arg[len] if \var[len] > 0, the string is right-padded by spaces to \var[len];
if \var[len] < 0, the string is left-padded to \code[|len|].
*/
dstring *ds_fromint(long val, int base, int len)
{
	return ds_fromuint(val > 0 ? val : -val, val > 0 ? base : -base, len);
}

/**** \function
like \see[functions][ds_fromint], but accepts an unsigned value
*/
dstring *ds_fromuint(unsigned long val, int base, int len)
{
	static char symbols[] = "0123456789abcdefghijklmnopqrstuvwxyz";
	static char intbuffer[sizeof(unsigned long) * CHAR_BIT + 4];
	int rem;
	int minus = 0;
	char *bufpos = intbuffer + sizeof(intbuffer) - 1;

	if(base < 0)
	{
		base = -base;
		minus = 1;
	}
	if(!val)
		*--bufpos = '0';
	else
	{
		while(val)
		{
			rem = val % base;
			val /= base;
			*--bufpos = symbols[rem];
		}
		if(base == 8)
			*--bufpos = '0';
		else if(base == 16)
		{
			*--bufpos = 'x';
			*--bufpos = '0';
		}
		if(minus)
			*--bufpos = '-';
	}
	return ds_num_pad(bufpos, (intbuffer + sizeof(intbuffer) - 1) - bufpos, len);
}

#if (SIZEOF_LONG_LONG > 0) && (defined(LLONG_MIN) || defined(LONG_LONG_MIN))
#ifndef LONG_LONG_MIN
#define LONG_LONG_MIN LLONG_MIN
#define LONG_LONG_MAX LLONG_MAX
#endif

/*** \function
Like \see[functions][ds_fromint], but \var[val] is of type \type[long long]
*/
dstring *ds_fromllint(long long val, int base, int len)
{
	return ds_fromullint(val > 0 ? val : -val, val > 0 ? base : -base, len);
}

/*** \function
Like \see[functions][ds_fromint], but \var[val] is of type \type[unsigned long long]
*/
dstring *ds_fromullint(unsigned long long val, int base, int len)
{
	static char symbols[] = "0123456789abcdefghijklmnopqrstuvwxyz";
	static char intbuffer[sizeof(unsigned long long) * CHAR_BIT + 4];
	int rem;
	int minus = 0;
	char *bufpos = intbuffer + sizeof(intbuffer) - 1;

	if(base < 0)
	{
		base = -base;
		minus = 1;
	}
	if(!val)
		*--bufpos = '0';
	else
	{
		while(val)
		{
			rem = val % base;
			val /= base;
			*--bufpos = symbols[rem];
		}
		if(base == 8)
			*--bufpos = '0';
		else if(base == 16)
		{
			*--bufpos = 'x';
			*--bufpos = '0';
		}
		if(minus)
			*--bufpos = '-';
	}
	return ds_num_pad(bufpos, (intbuffer + sizeof(intbuffer) - 1) - bufpos, len);
}
#endif

/*** \function
\returns a (opaque) string representation of a pointer
*/
dstring *ds_fromptr(void *ptr)
{
#if SIZEOF_VOID_P > SIZEOF_LONG
#if SIZEOF_LONG_LONG == 0
	fatal_error("cannot do reliable pointer-to-int conversion on this platform");
#else
	return ds_fromullint((unsigned long long)ptr, 16, 0);
#endif
#else
	return ds_fromuint((unsigned long)ptr, 16, 0);
#endif
}

#ifdef ENABLE_FP
static int ds_dbl_precision = DBL_DIG;

/**** \function
sets the precision for floating-point conversions; 
initial value is maximal possible precision.
If \var[precision] is negative, the precision does not change.
\returns the old precision
*/
int ds_dbl_set_precision(int precision)
{
	int old = ds_dbl_precision;
	if(precision >= 0)
		ds_dbl_precision = precision;
	return old;
}

/**** \function
\returns a string representation of a floating-point value
*/
dstring *ds_fromdouble(double d)
{
	char buf[256];
#ifdef HAVE_SNPRINTF
	if(ds_dbl_precision)
		snprintf(buf, sizeof(buf), "%.*g", ds_dbl_precision, d);
	else
		snprintf(buf, sizeof(buf), "%.0f", d);
#else	
	if(ds_dbl_precision)
		sprintf(buf, "%.*g", ds_dbl_precision, d);
	else
		sprintf(buf, "%.0f", d);
#endif	
	return ds_create(buf);
}
#endif

/*** \function
checks whether a dstring handler is valid; produces a fatal error if not
\returns its arg
*/
dstring *ds_checkvalid(dstring *src)
{
	if(!src || !src->str || src->maxlen < src->curlen || src->curlen <= 0)
		fatal_error("invalid dstring handle");
	return src;
}

static dstring *dlink_delete(dstring *base, dstring *item)
{
	if(!base)
		return NULL;
	if(item->next)
		item->next->prev = item->prev;
	if(item->prev)
		item->prev->next = item->next;
	else base = item->next;
	return base;
}

/*** \function
fixes a given dstring so it cannot be squeezed
\returns its arg
*/
dstring *ds_fix(dstring *src)
{
	if(!src)
		return NULL;
	if(src->fixcnt < 0)
		return src;
	if(!src->fixcnt)
	{
		unfixed_mem -= src->maxlen;
		unfixed_cnt--;
		dstrings = dlink_delete(dstrings, src);
	}
	src->fixcnt++;
	return src;
}

/**** \function
unfixes a given dstring. There may be many calls to \see[functions][ds_fix] for
the same dstring; a counter is maintained internally, so only the last ds_unfix
will actually do the job. If a dstring is not fixed, nothing happens
\returns its arg
*/
dstring *ds_unfix(dstring *src)
{
	if(!src)
		return NULL;
	if(src->fixcnt <= 0) 
		return src;
	if(!--src->fixcnt)
	{
		unfixed_mem += src->maxlen;
		unfixed_cnt++;
		dstrings = dlink_add(dstrings, src);
	}
	return src;
}

/**** \function
Unfixes a dstring and if it is really unfixed, schedules it for
further reuse.
*/
void ds_destroy(dstring *src)
{
	if(!src)
		return;
	ds_unfix(src);
	if(!src->fixcnt)
	{
		dstrings = dlink_delete(dstrings, src);
		src->next = free_strings;
		free_strings = src;
		unfixed_mem -= src->maxlen;
		unfixed_cnt--;
		if(reserved_mem > RESERVED_MEM_LIMIT)
		{
			free(src->str);
			src->str = NULL;
			reserved_mem -= src->maxlen;
			src->maxlen = 0;
		}
		else
			reserved_mem += src->maxlen;
	}
}

/**** \function
Compacts the space ocuupied by a dstring, removed any reserved bytes behind
the last character
\returns its arg
*/
dstring *ds_compact(dstring *src)
{
	if(!src)
		return NULL;
	else
	{
		int old = src->maxlen;
		src->str = xrealloc(src->str, src->maxlen = src->curlen);
		if(!src->fixcnt)
			unfixed_mem += src->maxlen - old;
		return src;
	}
}

static int squeeze_cnt;
static int last_squeezed_cnt;
static int last_squeezed_mem;
/*** \function
Performs squeezing by collecting all unfixed strings and scheduling them for reuse
\note Squeezing does not necessary take places, but only if some memory usage limits
are reached. So it is performance-safe to call ds_squeeze several times.
\note The function should be called at the topmost level possible, so that there might
not be unfixed, but really used dstrings
*/
void ds_squeeze(int unused)
{
	dstring *iter, *temp;

	if(unfixed_cnt > UNFIX_MAX_CNT || unfixed_mem > UNFIX_MEM_LIMIT)
	{
		squeeze_cnt++;
		last_squeezed_cnt = last_squeezed_mem = 0;
		for(iter = dstrings; iter; iter = temp)
		{
			temp = iter->next;
			dstrings = dlink_delete(dstrings, iter);
			iter->next = free_strings;
			free_strings = iter;
			unfixed_mem -= iter->maxlen;
			last_squeezed_mem += iter->maxlen;
			last_squeezed_cnt++;
			unfixed_cnt--;
			if(reserved_mem > RESERVED_MEM_LIMIT)
			{
				free(iter->str);
				iter->str = NULL;
				iter->maxlen = 0;
			}
			else
				reserved_mem += iter->maxlen;
		}
	}
}

/**** \function
\returns a given parameter for memory usage
*/
int ds_memory_usage(int param)
{
	switch(param)
	{	
		case dsmu_reserved:
			return reserved_mem;
		case dsmu_unfixed:
			return unfixed_mem;
		case dsmu_unfixed_cnt:
			return unfixed_cnt;
		case dsmu_squeeze:
			return squeeze_cnt;
		case dsmu_lastsqueeze_mem:
			return last_squeezed_mem;
		case dsmu_lastsqueeze_cnt:
			return last_squeezed_cnt;
		default:
			fatal_error("invalid param for ds_memory_usage: %d", param);
	}
}

/*** \function \returns the length of a dstring */
int ds_length(dstring *src) { return src ? src->curlen - 1 : 0; }

/**** \function \returns 1 if a dstring is empty, 0 otherwise */
int ds_isempty(dstring *src) { return !src || !*src->str; }

/**** \function \returns an unfixed copy of a given dstring */
dstring *ds_copy(dstring *src)
{
	if(!src)
		return NULL;
	else
	{
		dstring *newd = alloc_dstring();
		ds_expand(newd, src->curlen);
		strcpy(newd->str, src->str);
		return newd;
	}
}

/**** \function 
Replaces the content of \var[dest] with that of \var[src].
The latter is unaffected.
If \var[src] is NULL, it is treated as an empty dstring
\returns \var[dest]
*/
dstring *ds_assign(dstring *dest, dstring *src)
{
	if(src)
	{
		ds_expand(dest, src->curlen);
		strcpy(dest->str, src->str);
	}
	else
	{
		dest->curlen = 1;
		*dest->str = '\0';
	}
	return dest;
}

/**** \function
\returns an unfixed concatenation of \var[arg1] and \var[arg2]
*/
dstring *ds_concat(dstring *arg1, dstring *arg2)
{
	dstring *newd = alloc_dstring();
	ds_expand(newd, (arg1 ? arg1->curlen : 1) + (arg2 ? arg2->curlen : 1) - 1);
	if(arg1)
		strcpy(newd->str, arg1->str);
	if(arg2)
		strcpy(newd->str + (arg1 ? arg1->curlen - 1 : 0), arg2->str);
	return newd;
}

/**** \function
Appends \var[arg2] to \var[dest]
\returns \var[dest]
*/
dstring *ds_append(dstring *dest, dstring *arg2)
{
	if(!dest)
		return ds_copy(arg2);
	else
	{
		int l = dest->curlen - 1;
		if(arg2)
		{
			ds_expand(dest, dest->curlen + arg2->curlen - 1);
			strcpy(dest->str + l, arg2->str);
		}
		return dest;
	}
}

/**** \function
Appends \var[arg2] to \var[dest] in a way that allows binary zeros inside strings
\returns \var[dest]
*/
dstring *ds_appendbin(dstring *dest, dstring *arg2)
{
	if(!dest)
		return ds_copy(arg2);
	else
	{
		int l = dest->curlen;
		if(arg2)
		{
			ds_expand(dest, dest->curlen + arg2->curlen);
			memcpy(dest->str + l, arg2->str, arg2->curlen);
		}
		return dest;
	}
}


/*** \function
Same as \see[function][ds_append], but the last argument is a C string
*/
dstring *ds_appendstr(dstring *dest, const char *arg2)
{
	if(!dest)
		return ds_create(arg2);
	else
	{
		int l = dest->curlen - 1;
		if(arg2)
		{
			ds_expand(dest, dest->curlen + strlen(arg2));
			strcpy(dest->str + l, arg2);
		}
		return dest;
	}
}

/*** \function
Same as \see[function][ds_appendbin], but the last argument is a (not necessarily
null-terminated) C string
*/
dstring *ds_appendstr_bin(dstring *dest, const char *arg2, int len)
{
	if(!dest)
		return ds_create(arg2);
	else
	{
		int l = dest->curlen;
		if(arg2)
		{
			ds_expand(dest, dest->curlen + len);
			memcpy(dest->str + l, arg2, len);
		}
		return dest;
	}
}


/**** \function
Same as \see[function][ds_append], but the last argument is a single character
*/
dstring *ds_appendch(dstring *dest, int ch)
{
	if(!dest)
		return ds_createch(ch);
	if(ch)
	{
		ds_expand(dest, dest->curlen + 1);
		dest->str[dest->curlen - 2] = ch;
		dest->str[dest->curlen - 1] = '\0';
	}
	return dest;
}

/**** \function
Same as \see[function][ds_appendbin], but the last argument is a single character
*/
dstring *ds_appendch_bin(dstring *dest, int ch)
{
	if(!dest)
		return ds_createch(ch);
	if(ch)
	{
		ds_expand(dest, dest->curlen + 1);
		dest->str[dest->curlen - 1] = ch;
	}
	return dest;
}


/**** \function
\returns an unfixed substring of \var[src] starting with \var[start] of
the length \var[len]
\note The function returns a copy, so changing it will not affect \var[src];
use \see[functions][ds_setsubstr] for that purpose
\note If \var[start] and/or \var[len] are too high, they are adjusted
*/
dstring *ds_substr(dstring *src, int start, int len)
{
	if(!src)
		return NULL;
	else
	{
		dstring *newd = alloc_dstring();
		if(start > src->curlen)
			start = src->curlen;
		if(start + len - 1 > src->curlen)
			len = src->curlen - start + 1;
		if(len < 0)
			len = 0;
		ds_expand(newd, len + 1);
		memcpy(newd->str, src->str + start, len);
		newd->str[len] = '\0';
		return newd;
	}
}

/*** \function
Replace a substring within \var[dest] starting with \var[start] of the length \var[len]
with \var[arg]
\returns \var[dest]
\note If \var[start] and/or \var[len] are too high, they are adjusted
*/ 
dstring *ds_setsubstr(dstring *dest, int start, int len, dstring *arg)
{
	int temp;
	if(!dest)
		return ds_copy(arg);
	if(start >= dest->curlen)
		return ds_append(dest, arg);
	if(start + len >= dest->curlen)
		len = dest->curlen - start - 1;
	if(!arg)
		arg = ds_create(NULL);
	temp = dest->curlen;
	ds_expand(dest, dest->curlen - len + arg->curlen - 1);
	memmove(dest->str + start + arg->curlen - 1, dest->str + start + len, 
			temp - start - len);
	memcpy(dest->str + start, arg->str, arg->curlen - 1);
	return dest;
}

/**** \function
\returns 1 if \var[base] starts with \var[prefix]
*/
int ds_isprefix(dstring *base, dstring *prefix)
{
	if(!base)
		return !prefix;
	if(!prefix)
		return 1;
	else
	{
		char *iter = base->str, *iter1 = prefix->str;
		while(*iter1)
		{
			if(*iter1 != *iter)
				return 0;
			iter1++;
			iter++;
		}
		return 1;
	}
}

/**** \function
\returns 1 if \var[base] ends with \var[suffix]
*/
int ds_issuffix(dstring *base, dstring *suffix)
{
	if(!base)
		return !suffix;
	if(!suffix)
		return 1;
	else
	{
		char *iter = base->str + base->curlen - 1;
		char *iter1 = suffix->str + suffix->curlen - 1;
		while(iter1 != suffix->str)
		{
			if(*iter1 != *iter || iter == base->str)
				return 0;
			iter1--;
			iter--;
		}
		return *iter1 == *iter;
	}
}

/**** \function
\returns the longest common prefix of \var[str1] and \var[str2]
(may be empty)
*/
dstring *ds_commonprefix(dstring *str1, dstring *str2)
{
	if(!str1 || !str2)
		return NULL;
	else
	{
		char *iter1 = str1->str, *iter2 = str2->str;
		dstring *news = ds_create(NULL);
		while(*iter1 == *iter2 && *iter1)
		{
			ds_appendch(news, *iter1);
			iter1++;
			iter2++;
		}
		return news;
	}
}

/*** \function
A standard byte-to-byte comparison predicate
*/
int ds_std_predicate(int ch, int ch1, void *extra)
{
	return ch - ch1;
}

/*** \function
A case-folding comparison predicate
*/
int ds_p_casefold(int ch, int ch1, void *extra)
{
	return toupper(ch) - toupper(ch1);
}

/**** \function
\returns a position of the first occurrence of \var[substr] within \var[dest] starting
with \var[startpos] using \var[userp] for comparison. If \var[userp] is NULL,
\see[function][ds_std_predicate] is assumed. If \var[substr] is not found, 
a negative value is returned
*/
int ds_find(dstring *dest, int startpos, dstring *substr, ds_predicate_t userp, void *extra)
{
	if(!dest)
		return substr ? -1 : 0;
	if(!substr)
		return 0;
	else
	{
		char *iter, *iter1, *base;
		if(!userp)
			userp = ds_std_predicate;
		if(startpos >= ds_length(dest))
			return -1;
		for(base = dest->str + startpos; *base; base++)
		{
			for(iter1 = substr->str, iter = base; *iter1; iter1++, iter++)
			{
				if(userp(*iter, *iter1, extra))
				break;
			}
			if(!*iter1)
				return base - dest->str;
		}
		return -1;
	}
}

/*** \function
Like \see[functions][ds_find], but finds the \em[last] occurrence of \var[substr]
\note This function has no \var[startpos]
*/
int ds_rfind(dstring *dest, dstring *substr, ds_predicate_t userp, void *extra)
{
	if(!dest)
		return substr ? -1 : 0;
	if(!substr)
		return 0;
	else
	{
		int i;
		char *ptr, *ptr1;
		if(!userp)
			userp = ds_std_predicate;
		if(substr->curlen == 1)
			return -1;
		for(i = dest->curlen - substr->curlen; i >= 0; i -= substr->curlen - 1)
		{
			for(ptr = substr->str, ptr1 = dest->str + i; *ptr; ptr++, ptr1++)
			{
				if(userp(*ptr, *ptr1, extra))
					break;
			}
			if(!*ptr)
				return i;
		}
		return -1;
	}
}

/**** \function
Analogous to \ref[strcmp(3)] for dstrings. Uses \var[userp] for comparison;
if it is NULL, \see[functions][ds_std_predicate] is assumed.
*/
int ds_compare(dstring *arg1, dstring *arg2, ds_predicate_t userp, void *extra)
{
	char *iter1, *iter2;
	int diff;

	if(arg1 == arg2)
		return 0;
	if(!arg1)
		return -1;
	if(!arg2)
		return 1;
	if(!userp)
		userp = ds_std_predicate;
	for(iter1 = arg1->str, iter2 = arg2->str; *iter1 || *iter2; iter1++, iter2++)
	{
		diff = userp(*iter1, *iter2, extra);
		if(diff)
			return diff;
	}
	return 0;
}

/**** \function
Like the previous, but \var[arg2] is a C string
*/
int ds_comparestr(dstring *arg1, const char *arg2, ds_predicate_t userp, void *extra)
{
	char *iter1;
	int diff;

	if(!arg1)
		return arg2 ? -1 : 0;
	if(!arg2)
		return 1;
	if(!userp)
		userp = ds_std_predicate;
	for(iter1 = arg1->str; *iter1 || *arg2; iter1++, arg2++)
	{
		diff = userp(*iter1, *arg2, extra);
		if(diff)
			return diff;
	}
	return 0;
}

/*** \function
Compares two dstrings according to the current locale.
See \ref[strcoll(3)]
*/
int ds_collate(dstring *arg1, dstring *arg2)
{
#ifdef HAVE_STRCOLL
	return strcoll(DS_BODY(arg1), DS_BODY(arg2));
#else
	return strcmp(DS_BODY(arg1), DS_BODY(arg2));
#endif
}

/**** \function
\returns the result of \ref[strxfrm(3)] on a dstring
*/
dstring *ds_tocollate(dstring *arg1)
{
#ifdef HAVE_STRXFRM	
	dstring *arg = ds_create(NULL);
	char tmp[2];
	int count = strxfrm(tmp, DS_BODY(arg1), 1);
	ds_expand(arg, count + 1);
	strxfrm(DS_BODY(arg), DS_BODY(arg1), count);
	return arg;
#else
	return ds_copy(arg1);
#endif	
}

/**** \function
Reverses its argument in-place
*/
dstring *ds_reversip(dstring *src)
{
	if(!src)
		return NULL;
	else
	{
		char *iter, *iter1;
		int temp;
		
		for(iter = src->str, iter1 = src->str + src->curlen - 2; iter < iter1; iter++, iter1--)
		{
			temp = *iter;
			*iter = *iter1;
			*iter1 = temp;
		}
		return src;
	}
}

/*** \function
Like the previous, but operates on a copy of the argument
*/
dstring *ds_reverse(dstring *src)
{
	dstring *newd = ds_copy(src);
	return ds_reversip(newd);
}

/*** \functions[2]
Standard transform functions to convert cases
*/
int ds_t_toupper(int ch, void *extra)
{
	return toupper(ch);
}

int ds_t_tolower(int ch, void *extra)
{
	return tolower(ch);
}

/**** \function
Applies a \var[func] to each character in \var[src].
The result is stored in \var[src] or in its copy depending of \var[inplace]
*/
dstring *ds_transform(dstring *src, ds_iterator_t func, int inplace, void *extra)
{
	if(!src)
		return NULL;
	else
	{
		char *iter;	
		if(!inplace)
			src = ds_copy(src);
		for(iter = src->str; *iter; iter++)
			*iter = func(*iter, extra);
		return src;
	}
}

/**** \function
Like the previous but can handle binary strings
*/
dstring *ds_transform_bin(dstring *src, ds_iterator_t func, int inplace, void *extra)
{
	if(!src)
		return NULL;
	else
	{
		char *iter;	
		int i = src->curlen;
		if(!inplace)
			src = ds_copy(src);
		for(iter = src->str; i; iter++, i--)
			*iter = func(*iter, extra);
		return src;
	}
}

/**** \function
Applies a \var[func] to each character in \var[src] creating a new string.
The way the string is created is completely determined by \var[func]
(unlike \see[function][ds_transform])
*/
dstring *ds_xtransform(dstring *src, ds_xtransform_t func, void *extra)
{
	if(!src)
		return NULL;
	else
	{
		char *iter;	
		dstring *ns = ds_create(NULL);

		for(iter = src->str; *iter; iter++)
		{
			if(func(*iter, ns, extra))
				break;
		}
		return ns;
	}
}

/**** \function
Like the previous, but can handle binary strings
*/
dstring *ds_xtransform_bin(dstring *src, ds_xtransform_t func, void *extra)
{
	if(!src)
		return NULL;
	else
	{
		char *iter;	
		int i = src->curlen;
		dstring *ns = ds_create(NULL);

		for(iter = src->str; i; iter++, i--)
		{
			if(func(*iter, ns, extra))
				break;
		}
		return ns;
	}
}

/**** \function
Applies a \var[func] to each character of \var[src].
Unlike the previous, \var[src] is never affected
*/
void ds_foreach(dstring *src, ds_iterator_t func, void *extra)
{
	char *iter;	
	if(!src)
		return;
	for(iter = src->str; *iter; iter++)
	{
		if(func(*iter, extra))
			break;
	}
}

/**** \function
Like the previous, but can handle binary strings
*/
void ds_foreach_bin(dstring *src, ds_iterator_t func, void *extra)
{
	char *iter;	
	int i;
	
	if(!src)
		return;
	i = src->curlen;
	for(iter = src->str; i; iter++, i--)
	{
		if(func(*iter, extra))
			break;
	}
}