string.c

Calc Software Package for Number Calc

/*
 * string - string list routines
 *
 * Copyright (C) 1999-2006  David I. Bell and Ernest Bowen
 *
 * Primary author:  David I. Bell
 *
 * Calc is open software; you can redistribute it and/or modify it under
 * the terms of the version 2.1 of the GNU Lesser General Public License
 * as published by the Free Software Foundation.
 *
 * Calc 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 Lesser General
 * Public License for more details.
 *
 * A copy of version 2.1 of the GNU Lesser General Public License is
 * distributed with calc under the filename COPYING-LGPL.  You should have
 * received a copy with calc; if not, write to Free Software Foundation, Inc.
 * 59 Temple Place, Suite 330, Boston, MA  02111-1307, USA.
 *
 * @(#) $Revision: 29.10 $
 * @(#) $Id: string.c,v 29.10 2006/08/20 15:01:30 chongo Exp $
 * @(#) $Source: /usr/local/src/cmd/calc/RCS/string.c,v $
 *
 * Under source code control:	1990/02/15 01:48:10
 * File existed as early as:	before 1990
 *
 * Share and enjoy!  :-)	http://www.isthe.com/chongo/tech/comp/calc/
 */


#include <stdio.h>
#include "calc.h"
#include "string.h"

#define STR_TABLECHUNK	100	/* how often to reallocate string table */
#define STR_CHUNK	2000	/* size of string storage allocation */
#define STR_UNIQUE	100	/* size of string to allocate separately */

STRING _nullstring_ = {"", 0, 1, NULL};

static char *chartable;		/* single character string table */

static struct {
	long l_count;		/* count of strings in table */
	long l_maxcount;	/* maximum strings storable in table */
	size_t l_avail;		/* characters available in current string */
	char *l_alloc;		/* next available string storage */
	char **l_table;		/* current string table */
} literals;


/*
 * Initialize or reinitialize a string header for use.
 *
 * given:
 *	hp		structure to be inited
 */
void
initstr(STRINGHEAD *hp)
{
	if (hp->h_list == NULL) {
		hp->h_list = (char *)malloc(2000);
		hp->h_avail = 2000;
		hp->h_used = 0;
	}
	hp->h_avail += hp->h_used;
	hp->h_used = 0;
	hp->h_count = 0;
	hp->h_list[0] = '\0';
	hp->h_list[1] = '\0';
}


/*
 * Copy a string to the end of a list of strings, and return the address
 * of the copied string.  Returns NULL if the string could not be copied.
 * No checks are made to see if the string is already in the list.
 * The string cannot be null or have imbedded nulls.
 *
 * given:
 *	hp		header of string storage
 *	str		string to be added
 */
char *
addstr(STRINGHEAD *hp, char *str)
{
	char *retstr;		/* returned string pointer */
	char *list;		/* string list */
	long newsize;		/* new size of string list */
	size_t len;		/* length of current string */

	if ((str == NULL) || (*str == '\0'))
		return NULL;
	len = strlen(str) + 1;
	if (hp->h_avail <= len) {
		newsize = len + 2000 + hp->h_used + hp->h_avail;
		list = (char *)realloc(hp->h_list, newsize);
		if (list == NULL)
			return NULL;
		hp->h_list = list;
		hp->h_avail = newsize - hp->h_used;
	}
	retstr = hp->h_list + hp->h_used;
	hp->h_used += len;
	hp->h_avail -= len;
	hp->h_count++;
	strcpy(retstr, str);
	retstr[len] = '\0';
	return retstr;
}


/*
 * Return a null-terminated string which consists of a single character.
 * The table is initialized on the first call.
 */
char *
charstr(int ch)
{
	char *cp;
	int i;

	if (chartable == NULL) {
		cp = (char *)malloc(512);
		if (cp == NULL) {
			math_error("Cannot allocate character table");
			/*NOTREACHED*/
		}
		for (i = 0; i < 256; i++) {
			*cp++ = (char)i;
			*cp++ = '\0';
		}
		chartable = cp - 512;
	}
	return &chartable[(ch & 0xff) * 2];
}


/*
 * Find a string with the specified name and return its number in the
 * string list.	 The first string is numbered zero.  Minus one is returned
 * if the string is not found.
 *
 * given:
 *	hp		header of string storage
 *	str		string to be added
 */
int
findstr(STRINGHEAD *hp, char *str)
{
	register char *test;	/* string being tested */
	size_t len;		/* length of string being found */
	size_t testlen;		/* length of test string */
	int index;		/* index of string */

	if ((hp->h_count <= 0) || (str == NULL))
		return -1;
	len = strlen(str);
	test = hp->h_list;
	index = 0;
	while (*test) {
		testlen = strlen(test);
		if ((testlen == len) && (*test == *str) && (strcmp(test, str) == 0))
			return index;
		test += (testlen + 1);
		index++;
	}
	return -1;
}


/*
 * Return the name of a string with the given index.
 * If the index is illegal, a pointer to an empty string is returned.
 *
 * given:
 *	hp		header of string storage
 *	n		string index
 */
char *
namestr(STRINGHEAD *hp, long n)
{
	register char *str;	/* current string */

	if (n >= hp->h_count)
		return "";
	str = hp->h_list;
	while (*str) {
		if (--n < 0)
			return str;
		str += (strlen(str) + 1);
	}
	return "";
}


/*
 * Useful routine to return the index of one string within another one
 * which has the format:  "str1\000str2\000str3\000...strn\0\0".  Index starts
 * at one for the first string.	 Returns zero if the string being checked
 * is not contained in the formatted string.
 *
 * Be sure to use \000 instead of \0.  ANSI-C compilers interpret "foo\0foo..."
 * as "foo\017oo...".
 *
 * given:
 *	format		string formatted into substrings
 *	test		string to be found in formatted string
 */
long
stringindex(char *format, char *test)
{
	long index;		/* found index */
	size_t len;		/* length of current piece of string */
	size_t testlen;		/* length of test string */

	testlen = strlen(test);
	index = 1;
	while (*format) {
		len = strlen(format);
		if ((len == testlen) && (*format == *test) &&
			(strcmp(format, test) == 0))
				return index;
		format += (len + 1);
		index++;
	}
	return 0;
}


/*
 * Add a possibly new literal string to the literal string pool.
 * Returns the new string address which is guaranteed to be always valid.
 * Duplicate strings will repeatedly return the same address.
 */
char *
addliteral(char *str)
{
	register char **table;	/* table of strings */
	char *newstr;		/* newly allocated string */
	long count;		/* number of strings */
	size_t len;		/* length of string to allocate */

	len = strlen(str);
	if (len <= 1)
		return charstr(*str);
	/*
	 * See if the string is already in the table.
	 */
	table = literals.l_table;
	count = literals.l_count;
	while (count-- > 0) {
		if ((str[0] == table[0][0]) && (str[1] == table[0][1]) &&
			(strcmp(str, table[0]) == 0))
				return table[0];
		table++;
	}
	/*
	 * Make the table of string pointers larger if necessary.
	 */
	if (literals.l_count >= literals.l_maxcount) {
		count = literals.l_maxcount + STR_TABLECHUNK;
		if (literals.l_maxcount)
			table = (char **) realloc(literals.l_table, count * sizeof(char *));
		else
			table = (char **) malloc(count * sizeof(char *));
		if (table == NULL) {
			math_error("Cannot allocate string literal table");
			/*NOTREACHED*/
		}
		literals.l_table = table;
		literals.l_maxcount = count;
	}
	table = literals.l_table;
	/*
	 * If the new string is very long, allocate it manually.
	 */
	len = (len + 2) & ~1;	/* add room for null and round up to word */
	if (len >= STR_UNIQUE) {
		newstr = (char *)malloc(len);
		if (newstr == NULL) {
			math_error("Cannot allocate large literal string");
			/*NOTREACHED*/
		}
		strcpy(newstr, str);
		table[literals.l_count++] = newstr;
		return newstr;
	}
	/*
	 * If the remaining space in the allocate string is too small,
	 * then allocate a new one.
	 */
	if (literals.l_avail < len) {
		newstr = (char *)malloc(STR_CHUNK);
		if (newstr == NULL) {
			math_error("Cannot allocate new literal string");
			/*NOTREACHED*/
		}
		literals.l_alloc = newstr;
		literals.l_avail = STR_CHUNK;
	}
	/*
	 * Allocate the new string from the allocate string.
	 */
	newstr = literals.l_alloc;
	literals.l_avail -= len;
	literals.l_alloc += len;
	table[literals.l_count++] = newstr;
	strcpy(newstr, str);
	return newstr;
}


STRING *
stringadd(STRING *s1, STRING *s2)
{
	STRING *s;
	char *cfrom, *c;
	long len;

	len = s1->s_len + s2->s_len;
	s = stralloc();
	s->s_len = len;
	s->s_str = (char *) malloc(len + 1);
	if (s->s_str == NULL)
		return NULL;
	len = s1->s_len;
	cfrom = s1->s_str;
	c = s->s_str;
	while (len-- > 0)
		*c++ = *cfrom++;
	len = s2->s_len;
	cfrom = s2->s_str;
	while (len-- > 0)
		*c++ = *cfrom++;
	*c = '\0';
	return s;
}

/*
 * stringneg reverses the characters in a string, returns null if malloc fails
 */
STRING *
stringneg(STRING *str)
{
	long len;
	STRING *s;
	char *c, *cfrom;

	len = str->s_len;
	if (len <= 1)
		return slink(str);
	c = (char *) malloc(len + 1);
	if (c == NULL)
		return NULL;
	s = stralloc();
	s->s_len = len;
	s->s_str = c;
	cfrom = str->s_str + len;
	while (len-- > 0)
		*c++ = *--cfrom;
	*c = '\0';
	return s;
}

STRING *
stringsub(STRING *s1, STRING *s2)
{
	STRING *tmp, *s;

	tmp = stringneg(s2);
	if (tmp == NULL)
		return NULL;
	s = stringadd(s1, tmp);
	if (s != NULL)
		sfree(tmp);
	return s;
}

/*
 * stringmul: repeated concatenation, reverse if negative multiplier
 * returns null if malloc fails
 */
STRING *
stringmul(NUMBER *q, STRING *str)
{
	long len;
	size_t j;
	NUMBER *tmp1, *tmp2;
	char *c, *c1;
	STRING *s;
	BOOL neg;

	if (str->s_len == 0)
		return slink(str);
	neg = qisneg(q);
	q = neg ? qneg(q): qlink(q);
	tmp1 = itoq(str->s_len);
	tmp2 = qmul(q, tmp1);
	qfree(tmp1);
	tmp1 = qint(tmp2);
	qfree(tmp2);
	if (zge31b(tmp1->num)) {
		qfree(q);
		qfree(tmp1);
		return NULL;
	}
	len = qtoi(tmp1);
	qfree(tmp1);
	qfree(q);
	if (len == 0)
		return slink(&_nullstring_);
	c = (char *) malloc(len + 1);
	if (c == NULL)
		return NULL;
	str = neg ? stringneg(str) : slink(str);
	s = stralloc();
	s->s_str = c;
	s->s_len = len;
	j = 0;
	c1 = str->s_str;
	while (len-- > 0) {
		*c++ = *c1++;
		if (++j == str->s_len) {
			j = 0;
			c1 = str->s_str;
		}
	}
	*c = '\0';
	sfree(str);
	return s;
}

STRING *
stringand(STRING *s1, STRING *s2)
{
	STRING *s;
	size_t len;
	char *c1, *c2, *c;

	if (s1->s_len == 0  || s2->s_len == 0)
		return slink(&_nullstring_);
	len = s1->s_len;
	if (s2->s_len < len)
		len = s2->s_len;
	s = stralloc();
	s->s_len = len;
	c = malloc(len + 1);
	if (c == NULL)
		return NULL;
	s->s_str = c;
	c1 = s1->s_str;
	c2 = s2->s_str;
	while (len-- > 0)
		*c++ = *c1++ & *c2++;
	return s;
}


STRING *
stringor(STRING *s1, STRING *s2)
{
	STRING *s;
	long len, i, j;
	char *c1, *c2, *c;

	if (s1->s_len < s2->s_len) {
		s = s1;
		s1 = s2;
		s2 = s;
	}		/* Now len(s1) >= len(s2) */
	if (s2->s_len == 0)
		return slink(s1);
	i = s1->s_len;
	if (i == 0)
		return slink(&_nullstring_);
	len = s1->s_len;
	s = stralloc();
	s->s_len = len;
	c = malloc(len + 1);
	if (c == NULL)
		return NULL;
	s->s_str = c;
	c1 = s1->s_str;
	c2 = s2->s_str;
	i = s2->s_len;
	j = s1->s_len - i;
	while (i-- > 0)
		*c++ = *c1++ | *c2++;
	while (j-- > 0)
		*c++ = *c1++;
	return s;
}


STRING *
stringxor(STRING *s1, STRING *s2)
{
	STRING *s;
	long len, i, j;
	char *c1, *c2, *c;

	if (s1->s_len < s2->s_len) {
		s = s1;
		s1 = s2;
		s2 = s;
	}		/* Now len(s1) >= len(s2) */
	if (s2->s_len == 0)
		return slink(s1);
	i = s1->s_len;
	if (i == 0)
		return slink(&_nullstring_);
	len = s1->s_len;
	s = stralloc();
	s->s_len = len;
	c = malloc(len + 1);
	if (c == NULL)
		return NULL;
	s->s_str = c;
	c1 = s1->s_str;
	c2 = s2->s_str;
	i = s2->s_len;
	j = s1->s_len - i;
	while (i-- > 0)
		*c++ = *c1++ ^ *c2++;
	while (j-- > 0)
		*c++ = *c1++;
	return s;
}


STRING *
stringdiff(STRING *s1, STRING *s2)
{
	STRING *s;
	size_t i;
	char *c2, *c;

	i = s1->s_len;
	if (i == 0)
		return slink(s1);
	s = stringcopy(s1);
	if (i > s2->s_len)
		i = s2->s_len;
	c = s->s_str;
	c2 = s2->s_str;
	while (i-- > 0)
		*c++ &= ~*c2++;
	return s;
}

STRING *
stringcomp(STRING *s1)
{
	long len;
	STRING *s;
	char *c1, *c;

	len = s1->s_len;
	if (len == 0)
		return slink(&_nullstring_);
	c = malloc(len + 1);
	if (c == NULL)
		return NULL;
	s = stralloc();
	s->s_len = len;
	s->s_str = c;
	c1 = s1->s_str;
	while (len-- > 0)
		*c++ = ~*c1++;
	*c = '\0';
	return s;
}

STRING *
stringsegment(STRING *s1, long n1, long n2)
{
	STRING *s;
	char *c, *c1;
	long len;

	if ((n1 < 0 && n2 < 0) ||
	    ((size_t)n1 >= s1->s_len && (size_t)n2 >= s1->s_len))
		return slink(&_nullstring_);
	if (n1 < 0)
		n1 = 0;
	if (n2 < 0)
		n2 = 0;
	if ((size_t)n1 >= s1->s_len)
		n1 = s1->s_len - 1;
	if ((size_t)n2 >= s1->s_len)
		n2 = s1->s_len - 1;
	len = (n1 >= n2) ? n1 - n2 + 1 : n2 - n1 + 1;
	s = stralloc();
	c = malloc(len + 1);
	if (c == NULL)
		return NULL;
	s->s_len = len;
	s->s_str = c;
	c1 = s1->s_str + n1;
	if (n1 >= n2) {
		/*
		 * We prevent the c1 pointer from walking behind s1_s_str
		 * by stopping one short of the end and running the loop one
		 * more time.
		 *
		 * We could stop the loop with just len-- > 0, but stopping
		 * short and running the loop one last time manually helps make
		 * code checkers such as insure happy.
		 */
		while (len-- > 1) {
			*c++ = *c1--;
		}
		/* run the loop manually one last time */
		*c++ = *c1;
	} else {
		while (len-- > 0)
			*c++ = *c1++;
	}
	*c = '\0';
	return s;
}

/*
 * stringshift shifts s1 n bits to left if n > 0, -n to the right if n < 0;
 * octets in string considered to be in decreasing order of index, as in
 * ... a_3 a_2 a_1 a_0.	 Returned string has same length as s1.
 * Vacated bits are filled with '\0'; bits shifted off end are lost
 */
STRING *
stringshift(STRING *s1, long n)
{
	char *c1, *c;
	STRING *s;
	long len, i, j, k;
	BOOL right;
	char ch;

	len = s1->s_len;
	if (len == 0 || n == 0)
		return slink(s1);
	right = (n < 0);
	if (right) n = -n;
	j = n & 7;
	k = 8 - j;
	n >>= 3;
	c = malloc(len + 1);
	if (c == NULL)
		return NULL;
	s = stralloc();
	s->s_len = len;
	s->s_str = c;
	c[len] = '\0';
	if (n > len)
		n = len;
	ch = '\0';
	c1 = s1->s_str;
	i = n;
	if (right) {
		c += len;
		c1 += len;
		while (i-- > 0)
			*--c = '\0';
		i = len - n;
		while (i-- > 0) {
			*--c = ((unsigned char) *--c1 >> j) | ch;
			ch = (unsigned char) *c1 << k;
		}
	} else {
		while (i-- > 0)
			*c++ = '\0';
		i = len - n;
		while (i-- > 0) {
			*c++ = ((unsigned char) *c1 << j) | ch;
			ch = (unsigned char) *c1++ >> k;
		}
	}
	return s;
}

/*
 * stringcpy copies as many characters as possible
 * from s2 to s1 and returns s1
 */
STRING *
stringcpy(STRING *s1, STRING *s2)
{
	char *c1, *c2;
	size_t num;

	if (s1->s_len > 0) {
		c1 = s1->s_str;
		c2 = s2->s_str;
		num = s1->s_len;
		if (num > s2->s_len)
			num = s2->s_len;
		while (num-- > 0)
			*c1++ = *c2++;
		*c1 = '\0';
	}
	return slink(s1);
}

/*
 * stringncpy copies up to num characters from s2 to s1 and returns s1
 * If num > size(s2) null characters are copied until s1 is full or
 * a total of num characters have been copied
 */
STRING *
stringncpy(STRING *s1, STRING *s2, size_t num)
{
	char *c1, *c2;
	size_t i;

	if (num > s1->s_len)
		num = s1->s_len;
	i = num;
	if (i > s2->s_len)
		i = s2->s_len;
	c1 = s1->s_str;