sgs/include/alist.h

/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (the "License").
 * You may not use this file except in compliance with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */

/*
 * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 *
 * Define an Alist, a list maintained as a reallocable array, and a for() loop
 * macro to generalize its traversal.  Note that the array can be reallocated
 * as it is being traversed, thus the offset of each element is recomputed from
 * the start of the structure.
 */

#ifndef	_ALIST_H
#define	_ALIST_H

#ifdef	__cplusplus
extern "C" {
#endif

#include <sys/types.h>
#include <sys/machelf.h>

/*
 * An Alist implements array lists. The functionality is similar to
 * that of a linked list. However, an Alist is represented by a single
 * contigious allocation of memory. The head of the memory is a header
 * that contains control information for the list. Following the header
 * is an array used to hold the user data. In the type definitions that
 * follow, we define these as an array with a single element, but when
 * we allocate the memory, we actually allocate the amount of memory needed.
 *
 * There are two "flavors" of array list:
 *
 *	Alist - Contain arbitrary data, usually structs.
 *	APlist - Contain pointers to data allocated elsewhere.
 *
 * This differentiation is useful, because pointer lists are heavily
 * used, and support a slightly different set of operations that are
 * unique to their purpose.
 *
 * Array lists are initially represented by a NULL pointer. The memory
 * for the list is only allocated if an item is inserted. This is very
 * efficient for data structures that may or may not be needed for a
 * given linker operation --- you only pay for what you use. In addition:
 *
 *	- Array lists grow as needed (memory is reallocated as necessary)
 *	- Data is kept contiguously (no unused holes in between elements)
 *		at the beginning of the data area. This locality has
 *		good cache behavior, as access to adjacent items are
 *		highly likely to be in the same page of memory.
 *	- Insert/Delete operations at the end of the list are very
 *		efficient. However, insert/delete operations elsewhere
 *		will cause a relatively expensive overlapped memory
 *		copy of the data following the insert/delete location.
 *	- As with any generic memory alloctor (i.e. malloc()/free()),
 *		array lists are not type safe for the data they contain.
 *		Data is managed as (void *) pointers to data of a given
 *		length, so the Alist module cannot prevent the caller from
 *		inserting/extracting the wrong type of data. The caller
 *		must guard against this.
 *	- To free an array list, simply call the standard free() function
 *		on the list pointer.
 */


/*
 * Aliste is used to represent list indexes, offsets, and sizes.
 */
typedef	size_t	Aliste;


/*
 * Alist is used to hold non-pointer items --- usually structs:
 *	- There must be an even number of Aliste fields before the
 *		al_data field. This ensures that al_data will have
 *		an alignment of 8, no matter whether sizeof(Aliste)
 *		is 4 or 8. That means that al_data will have sufficient
 *		alignment for any use, just like memory allocated via
 *		malloc().
 *	- al_nitems and al_next are redundant, in that they are
 *		directly related:
 *			al_next = al_nitems * al_size
 *		We do this to make ALIST_TRAVERSE_BYOFFSET maximally
 *		efficient. This doesn't waste space, because of the
 *		requirement to have an even # of Alist fields (above).
 *
 * Note that Alists allow the data to be referenced by 0 based array
 * index, or by their byte offset from the start of the Alist memory
 * allocation. The index form is preferred for most use, as it is simpler.
 * However, by-offset access is used by rtld link maps, and this ability
 * is convenient in that case.
 */
typedef struct {
	Aliste 		al_arritems;	/* # of items in al_data allocation */
	Aliste 		al_nitems;	/* # items (index of next avail item) */
	Aliste 		al_next;	/* offset of next available al_data[] */
	Aliste		al_size;	/* size of each al_data[] item */
	void 		*al_data[1];	/* data (can grow) */
} Alist;

/*
 * APlist is a variant of Alist that contains pointers. There are several
 * benefits to this special type:
 *	- API is simpler
 *	- Pointers are used directly, instead of requiring a
 *		pointer-to-pointer double indirection.
 *	- The implementation is slightly more efficient.
 *	- Operations that make particular sense for pointers
 *		can be supported without confusing the API for the
 *		regular Alists.
 */
typedef struct {
	Aliste		apl_arritems;	/* # of items in apl_data allocation */
	Aliste 		apl_nitems;	/* # items (index of next avail item) */
	void		*apl_data[1];	/* data area: (arrcnt * size) bytes */
} APlist;

#ifdef	_SYSCALL32			/* required by librtld_db */
typedef	struct {
	Elf32_Word	apl_arritems;
	Elf32_Word	apl_nitems;
	Elf32_Addr	apl_data[1];
} APlist32;
#endif	/* _SYSCALL32 */

/*
 * The ALIST_OFF_DATA and APLIST_OFF_DATA macros give the byte offset
 * from the start of an array list to the first byte of the data area
 * used to hold user data. The same trick used by the standard offsetof()
 * macro is used.
 */
#define	ALIST_OFF_DATA	((size_t)(((Alist *)0)->al_data))
#define	APLIST_OFF_DATA	((size_t)(((APlist *)0)->apl_data))


/*
 * The TRAVERSE macros are intended to be used within a for(), and
 * cause the resulting loop to iterate over each item in the loop,
 * in order.
 *	ALIST_TRAVERSE: Traverse over the items in an Alist,
 *		using the zero based item array index to refer to
 *		each item.
 *	ALIST_TRAVERSE_BY_OFFSET: Traverse over the items in an
 *		Alist using the byte offset from the head of the
 *		Alist pointer to refer to each item. It should be noted
 *		that the first such offset is given by ALIST_OFF_DATA,
 *		and as such, there will never be a 0 offset. Some code
 *		uses this fact to treat 0 as a reserved value with
 *		special meaning.
 *
 *		By-offset access is convenient for some parts of
 *		rtld, where a value of 0 is used to indicate an
 *		uninitialized link map control.
 *
 *	APLIST_TRAVERSE: Traverse over the pointers in an APlist, using
 *		the zero based item array index to refer to each pointer.
 */

/*
 * Within the loop:
 *
 *	LIST - Pointer to Alist structure for list
 *	IDX - The current item index
 *	OFF - The current item offset
 *	DATA - Pointer to item
 */
#define	ALIST_TRAVERSE(LIST, IDX, DATA) \
	(IDX) = 0, \
	((LIST) != NULL) && ((DATA) = (void *)(LIST)->al_data); \
	\
	((LIST) != NULL) && ((IDX) < (LIST)->al_nitems); \
	\
	(IDX)++, \
	(DATA) = (void *) (((LIST)->al_size * (IDX)) + (char *)(LIST)->al_data)

#define	ALIST_TRAVERSE_BY_OFFSET(LIST, OFF, DATA) \
	(((LIST) != NULL) && ((OFF) = ALIST_OFF_DATA) && \
	(((DATA) = (void *)((char *)(LIST) + (OFF))))); \
	\
	(((LIST) != NULL) && ((OFF) < (LIST)->al_next)); \
	\
	(((OFF) += ((LIST)->al_size)), \
	((DATA) = (void *)((char *)(LIST) + (OFF))))

/*
 * Within the loop:
 *
 *	LIST - Pointer to APlist structure for list
 *	IDX - The current item index
 *	PTR - item value
 *
 * Note that this macro is designed to ensure that PTR retains the
 * value of the final pointer in the list after exiting the for loop,
 * and to avoid dereferencing an out of range address. This is done by
 * doing the dereference in the middle expression, using the comma
 * operator to ensure that a NULL pointer won't stop the loop.
 */
#define	APLIST_TRAVERSE(LIST, IDX, PTR) \
	(IDX) = 0; \
	\
	((LIST) != NULL) && ((IDX) < (LIST)->apl_nitems) && \
	(((PTR) = ((LIST)->apl_data)[IDX]), 1); \
	\
	(IDX)++


/*
 * Possible values returned by aplist_test()
 */
typedef enum {
	ALE_ALLOCFAIL = 0,	/* memory allocation error */
	ALE_EXISTS =	1,	/* alist entry already exists */
	ALE_NOTFND =	2,	/* item not found and insert not required */
	ALE_CREATE =	3	/* alist entry created */
} aplist_test_t;


/*
 * Access to an Alist item by index or offset. This is needed because the
 * size of an item in an Alist is not known by the C compiler, and we
 * have to do the indexing arithmetic explicitly.
 *
 * For an APlist, index the apl_data field directly --- No macro is needed.
 */
#define	alist_item(_lp, _idx) \
	((void *)(ALIST_OFF_DATA + ((_idx) * (_lp)->al_size) + (char *)(_lp)))
#define	alist_item_by_offset(_lp, _off) \
	((void *)((_off) + (char *)(_lp)))

/*
 * The number of items currently found in a list (nitems), and the total number
 * of slots in the current data allocation (arritems).  These macros handle the
 * case where the list has not been allocated yet.
 */
#define	alist_nitems(_lp)	(((_lp) == NULL) ? 0 : (_lp)->al_nitems)
#define	aplist_nitems(_lp)	(((_lp) == NULL) ? 0 : (_lp)->apl_nitems)
#define	alist_arritems(_lp)	(((_lp) == NULL) ? 0 : (_lp)->al_arritems)
#define	aplist_arritems(_lp)	(((_lp) == NULL) ? 0 : (_lp)->apl_arritems)


extern void		*alist_append(Alist **, const void *, size_t, Aliste);
extern void		alist_delete(Alist *, Aliste *);
extern void		alist_delete_by_offset(Alist *, Aliste *);
extern void		*alist_insert(Alist **, const void *, size_t,
			    Aliste, Aliste);
extern void		*alist_insert_by_offset(Alist **, const void *, size_t,
			    Aliste, Aliste);
extern void		alist_reset(Alist *);


extern void		*aplist_append(APlist **, const void *, Aliste);
extern void		aplist_delete(APlist *, Aliste *);
extern int		aplist_delete_value(APlist *, const void *);
extern void		*aplist_insert(APlist **, const void *,
			    Aliste, Aliste idx);
extern void		aplist_reset(APlist *);
extern aplist_test_t	aplist_test(APlist **, const void *, Aliste);

#ifdef	__cplusplus
}
#endif

#endif /* _ALIST_H */