array.c

android-w.song.android.widget

/*
 * array.c - functions to create, destroy, access, and manipulate arrays
 *	     of strings.
 *
 * Arrays are sparse doubly-linked lists.  An element's index is stored
 * with it.
 *
 * Chet Ramey
 * [e-mail]
 */

/* Copyright (C) 1997-2009 Free Software Foundation, Inc.

   This file is part of GNU Bash, the Bourne Again SHell.

   Bash 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 3 of the License, or
   (at your option) any later version.

   Bash 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 Bash.  If not, see <http://www.gnu.org/licenses/>.
*/

#include "config.h"

#if defined (ARRAY_VARS)

#if defined (HAVE_UNISTD_H)
#  ifdef _MINIX
#    include <sys/types.h>
#  endif
#  include <unistd.h>
#endif

#include <stdio.h>
#include "bashansi.h"

#include "shell.h"
#include "array.h"
#include "builtins/common.h"

#define ADD_BEFORE(ae, new) \
	do { \
		ae->prev->next = new; \
		new->prev = ae->prev; \
		ae->prev = new; \
		new->next = ae; \
	} while(0)

static char *array_to_string_internal __P((ARRAY_ELEMENT *, ARRAY_ELEMENT *, char *, int));

static ARRAY *lastarray = 0;
static ARRAY_ELEMENT *lastref = 0;

#define IS_LASTREF(a)	((a) == lastarray)

#define INVALIDATE_LASTREF(a) \
do { \
	if ((a) == lastarray) { \
		lastarray = 0; \
		lastref = 0; \
	} \
} while (0)

#define SET_LASTREF(a, e) \
do { \
	lastarray = (a); \
	lastref = (e); \
} while (0)

#define UNSET_LASTREF() \
do { \
	lastarray = 0; \
	lastref = 0; \
} while (0)

ARRAY *
array_create()
{
	ARRAY	*r;
	ARRAY_ELEMENT	*head;

	r =(ARRAY *)xmalloc(sizeof(ARRAY));
	r->type = array_indexed;
	r->max_index = -1;
	r->num_elements = 0;
	head = array_create_element(-1, (char *)NULL);	/* dummy head */
	head->prev = head->next = head;
	r->head = head;
	return(r);
}

void
array_flush (a)
ARRAY	*a;
{
	register ARRAY_ELEMENT *r, *r1;

	if (a == 0)
		return;
	for (r = element_forw(a->head); r != a->head; ) {
		r1 = element_forw(r);
		array_dispose_element(r);
		r = r1;
	}
	a->head->next = a->head->prev = a->head;
	a->max_index = -1;
	a->num_elements = 0;
	INVALIDATE_LASTREF(a);
}

void
array_dispose(a)
ARRAY	*a;
{
	if (a == 0)
		return;
	array_flush (a);
	array_dispose_element(a->head);
	free(a);
}

ARRAY *
array_copy(a)
ARRAY	*a;
{
	ARRAY	*a1;
	ARRAY_ELEMENT	*ae, *new;

	if (a == 0)
		return((ARRAY *) NULL);
	a1 = array_create();
	a1->type = a->type;
	a1->max_index = a->max_index;
	a1->num_elements = a->num_elements;
	for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae)) {
		new = array_create_element(element_index(ae), element_value(ae));
		ADD_BEFORE(a1->head, new);
	}
	return(a1);
}

/*
 * Make and return a new array composed of the elements in array A from
 * S to E, inclusive.
 */
ARRAY *
array_slice(array, s, e)
ARRAY		*array;
ARRAY_ELEMENT	*s, *e;
{
	ARRAY	*a;
	ARRAY_ELEMENT *p, *n;
	int	i;
	arrayind_t mi;

	a = array_create ();
	a->type = array->type;

	for (mi = 0, p = s, i = 0; p != e; p = element_forw(p), i++) {
		n = array_create_element (element_index(p), element_value(p));
		ADD_BEFORE(a->head, n);
		mi = element_index(n);
	}
	a->num_elements = i;
	a->max_index = mi;
	return a;
}

/*
 * Walk the array, calling FUNC once for each element, with the array
 * element as the argument.
 */
void
array_walk(a, func, udata)
ARRAY	*a;
sh_ae_map_func_t *func;
void	*udata;
{
	register ARRAY_ELEMENT *ae;

	if (a == 0 || array_empty(a))
		return;
	for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae))
		if ((*func)(ae, udata) < 0)
			return;
}

/*
 * Shift the array A N elements to the left.  Delete the first N elements
 * and subtract N from the indices of the remaining elements.  If FLAGS
 * does not include AS_DISPOSE, this returns a singly-linked null-terminated
 * list of elements so the caller can dispose of the chain.  If FLAGS
 * includes AS_DISPOSE, this function disposes of the shifted-out elements
 * and returns NULL.
 */
ARRAY_ELEMENT *
array_shift(a, n, flags)
ARRAY	*a;
int	n, flags;
{
	register ARRAY_ELEMENT *ae, *ret;
	register int i;

	if (a == 0 || array_empty(a) || n <= 0)
		return ((ARRAY_ELEMENT *)NULL);

	INVALIDATE_LASTREF(a);
	for (i = 0, ret = ae = element_forw(a->head); ae != a->head && i < n; ae = element_forw(ae), i++)
		;
	if (ae == a->head) {
		/* Easy case; shifting out all of the elements */
		if (flags & AS_DISPOSE) {
			array_flush (a);
			return ((ARRAY_ELEMENT *)NULL);
		}
		for (ae = ret; element_forw(ae) != a->head; ae = element_forw(ae))
			;
		element_forw(ae) = (ARRAY_ELEMENT *)NULL;
		a->head->next = a->head->prev = a->head;
		a->max_index = -1;
		a->num_elements = 0;
		return ret;
	}
	/*
	 * ae now points to the list of elements we want to retain.
	 * ret points to the list we want to either destroy or return.
	 */
	ae->prev->next = (ARRAY_ELEMENT *)NULL;		/* null-terminate RET */

	a->head->next = ae;		/* slice RET out of the array */
	ae->prev = a->head;

	for ( ; ae != a->head; ae = element_forw(ae))
		element_index(ae) -= n;	/* renumber retained indices */

	a->num_elements -= n;		/* modify bookkeeping information */
	a->max_index = element_index(a->head->prev);

	if (flags & AS_DISPOSE) {
		for (ae = ret; ae; ) {
			ret = element_forw(ae);
			array_dispose_element(ae);
			ae = ret;
		}
		return ((ARRAY_ELEMENT *)NULL);
	}

	return ret;
}

/*
 * Shift array A right N indices.  If S is non-null, it becomes the value of
 * the new element 0.  Returns the number of elements in the array after the
 * shift.
 */
int
array_rshift (a, n, s)
ARRAY	*a;
int	n;
char	*s;
{
	register ARRAY_ELEMENT	*ae, *new;

	if (a == 0 || (array_empty(a) && s == 0))
		return 0;
	else if (n <= 0)
		return (a->num_elements);

	ae = element_forw(a->head);
	if (s) {
		new = array_create_element(0, s);
		ADD_BEFORE(ae, new);
		a->num_elements++;
		if (array_num_elements(a) == 1)	{	/* array was empty */
			a->max_index = 0;
			return 1;
		}
	}

	/*
	 * Renumber all elements in the array except the one we just added.
	 */
	for ( ; ae != a->head; ae = element_forw(ae))
		element_index(ae) += n;

	a->max_index = element_index(a->head->prev);

	INVALIDATE_LASTREF(a);
	return (a->num_elements);
}

ARRAY_ELEMENT *
array_unshift_element(a)
ARRAY	*a;
{
	return (array_shift (a, 1, 0));
}

int
array_shift_element(a, v)
ARRAY	*a;
char	*v;
{
	return (array_rshift (a, 1, v));
}

ARRAY *
array_quote(array)
ARRAY	*array;
{
	ARRAY_ELEMENT	*a;
	char	*t;

	if (array == 0 || array_head(array) == 0 || array_empty(array))
		return (ARRAY *)NULL;
	for (a = element_forw(array->head); a != array->head; a = element_forw(a)) {
		t = quote_string (a->value);
		FREE(a->value);
		a->value = t;
	}
	return array;
}

ARRAY *
array_quote_escapes(array)
ARRAY	*array;
{
	ARRAY_ELEMENT	*a;
	char	*t;

	if (array == 0 || array_head(array) == 0 || array_empty(array))
		return (ARRAY *)NULL;
	for (a = element_forw(array->head); a != array->head; a = element_forw(a)) {
		t = quote_escapes (a->value);
		FREE(a->value);
		a->value = t;
	}
	return array;
}

ARRAY *
array_dequote(array)
ARRAY	*array;
{
	ARRAY_ELEMENT	*a;
	char	*t;

	if (array == 0 || array_head(array) == 0 || array_empty(array))
		return (ARRAY *)NULL;
	for (a = element_forw(array->head); a != array->head; a = element_forw(a)) {
		t = dequote_string (a->value);
		FREE(a->value);
		a->value = t;
	}
	return array;
}

ARRAY *
array_dequote_escapes(array)
ARRAY	*array;
{
	ARRAY_ELEMENT	*a;
	char	*t;

	if (array == 0 || array_head(array) == 0 || array_empty(array))
		return (ARRAY *)NULL;
	for (a = element_forw(array->head); a != array->head; a = element_forw(a)) {
		t = dequote_escapes (a->value);
		FREE(a->value);
		a->value = t;
	}
	return array;
}

ARRAY *
array_remove_quoted_nulls(array)
ARRAY	*array;
{
	ARRAY_ELEMENT	*a;
	char	*t;

	if (array == 0 || array_head(array) == 0 || array_empty(array))
		return (ARRAY *)NULL;
	for (a = element_forw(array->head); a != array->head; a = element_forw(a))
		a->value = remove_quoted_nulls (a->value);
	return array;
}

/*
 * Return a string whose elements are the members of array A beginning at
 * index START and spanning NELEM members.  Null elements are counted.
 * Since arrays are sparse, unset array elements are not counted.
 */
char *
array_subrange (a, start, nelem, starsub, quoted)
ARRAY	*a;
arrayind_t	start, nelem;
int	starsub, quoted;
{
	ARRAY		*a2;
	ARRAY_ELEMENT	*h, *p;
	arrayind_t	i;
	char		*ifs, *sifs, *t;
	int		slen;

	p = a ? array_head (a) : 0;
	if (p == 0 || array_empty (a) || start > array_max_index(a))
		return ((char *)NULL);

	/*
	 * Find element with index START.  If START corresponds to an unset
	 * element (arrays can be sparse), use the first element whose index
	 * is >= START.  If START is < 0, we count START indices back from
	 * the end of A (not elements, even with sparse arrays -- START is an
	 * index).
	 */
	for (p = element_forw(p); p != array_head(a) && start > element_index(p); p = element_forw(p))
		;

	if (p == a->head)
		return ((char *)NULL);

	/* Starting at P, take NELEM elements, inclusive. */
	for (i = 0, h = p; p != a->head && i < nelem; i++, p = element_forw(p))
		;

	a2 = array_slice(a, h, p);

	if (quoted & (Q_DOUBLE_QUOTES|Q_HERE_DOCUMENT))
		array_quote(a2);
	else
		array_quote_escapes(a2);

	if (starsub && (quoted & (Q_DOUBLE_QUOTES|Q_HERE_DOCUMENT))) {
		/* ${array[*]} */
		array_remove_quoted_nulls (a2);
		sifs = ifs_firstchar ((int *)NULL);
		t = array_to_string (a2, sifs, 0);
		free (sifs);
	} else if (quoted & (Q_DOUBLE_QUOTES|Q_HERE_DOCUMENT)) {
		/* ${array[@]} */
		sifs = ifs_firstchar (&slen);
		ifs = getifs ();
		if (ifs == 0 || *ifs == 0) {
			if (slen < 2)
				sifs = xrealloc(sifs, 2);
			sifs[0] = ' ';
			sifs[1] = '\0';
		}
		t = array_to_string (a2, sifs, 0);
		free (sifs);
	} else
		t = array_to_string (a2, " ", 0);
	array_dispose(a2);

	return t;
}

char *
array_patsub (a, pat, rep, mflags)
ARRAY	*a;
char	*pat, *rep;
int	mflags;
{
	ARRAY		*a2;
	ARRAY_ELEMENT	*e;
	char	*t, *sifs, *ifs;
	int	slen;

	if (a == 0 || array_head(a) == 0 || array_empty(a))
		return ((char *)NULL);

	a2 = array_copy(a);
	for (e = element_forw(a2->head); e != a2->head; e = element_forw(e)) {
		t = pat_subst(element_value(e), pat, rep, mflags);
		FREE(element_value(e));
		e->value = t;
	}

	if (mflags & MATCH_QUOTED)
		array_quote(a2);
	else
		array_quote_escapes(a2);

	if (mflags & MATCH_STARSUB) {
		array_remove_quoted_nulls (a2);
		sifs = ifs_firstchar((int *)NULL);
		t = array_to_string (a2, sifs, 0);
		free(sifs);
	} else if (mflags & MATCH_QUOTED) {
		/* ${array[@]} */
		sifs = ifs_firstchar (&slen);
		ifs = getifs ();
		if (ifs == 0 || *ifs == 0) {
			if (slen < 2)
				sifs = xrealloc (sifs, 2);
			sifs[0] = ' ';
			sifs[1] = '\0';
		}
		t = array_to_string (a2, sifs, 0);
		free(sifs);
	} else
		t = array_to_string (a2, " ", 0);
	array_dispose (a2);

	return t;
}

char *
array_modcase (a, pat, modop, mflags)
ARRAY	*a;
char	*pat;
int	modop;
int	mflags;
{
	ARRAY		*a2;
	ARRAY_ELEMENT	*e;
	char	*t, *sifs, *ifs;
	int	slen;

	if (a == 0 || array_head(a) == 0 || array_empty(a))
		return ((char *)NULL);

	a2 = array_copy(a);
	for (e = element_forw(a2->head); e != a2->head; e = element_forw(e)) {
		t = sh_modcase(element_value(e), pat, modop);
		FREE(element_value(e));
		e->value = t;
	}

	if (mflags & MATCH_QUOTED)
		array_quote(a2);
	else
		array_quote_escapes(a2);

	if (mflags & MATCH_STARSUB) {
		array_remove_quoted_nulls (a2);
		sifs = ifs_firstchar((int *)NULL);
		t = array_to_string (a2, sifs, 0);
		free(sifs);
	} else if (mflags & MATCH_QUOTED) {
		/* ${array[@]} */
		sifs = ifs_firstchar (&slen);
		ifs = getifs ();
		if (ifs == 0 || *ifs == 0) {
			if (slen < 2)
				sifs = xrealloc (sifs, 2);
			sifs[0] = ' ';
			sifs[1] = '\0';
		}
		t = array_to_string (a2, sifs, 0);
		free(sifs);
	} else
		t = array_to_string (a2, " ", 0);
	array_dispose (a2);

	return t;
}
/*