Pointer Tables

Support for generalized "pointer tables", kept compactly in a dynamic array. More...

Collaboration diagram for Pointer Tables:

Files
file	ptbl.h

Data Structures
struct	bu_ptbl

Macros
#define	BU_PTBL_NULL   ((struct bu_ptbl *)0)
#define	BU_CK_PTBL(_p)   BU_CKMAG(_p, BU_PTBL_MAGIC, "bu_ptbl")
#define	BU_PTBL_INIT(_p)
#define	BU_PTBL_INIT_ZERO   { {BU_PTBL_MAGIC, BU_LIST_NULL, BU_LIST_NULL}, 0, 0, NULL }
#define	BU_PTBL_IS_INITIALIZED(_p)   (((struct bu_ptbl *)(_p) != BU_PTBL_NULL) && LIKELY((_p)->l.magic == BU_PTBL_MAGIC))
#define	BU_PTBL_LEN(ptbl)   (((uintptr_t)(ptbl) != (uintptr_t)NULL)?(ptbl)->end:0)
#define	BU_PTBL_TEST(ptbl)   (((uintptr_t)(ptbl) != (uintptr_t)NULL)?(ptbl)->l.magic == BU_PTBL_MAGIC:0)
#define	BU_PTBL_GET(ptbl, i)   ((ptbl)->buffer[(i)])
#define	BU_PTBL_SET(ptbl, i, val)   ((ptbl)->buffer[(i)] = (long*)(val))
#define	BU_PTBL_END(ptbl)   ((ptbl)->end)
#define	BU_PTBL_BASEADDR(ptbl)   (((uintptr_t)(ptbl) != (uintptr_t)NULL)?(ptbl)->buffer:NULL)
#define	BU_PTBL_LASTADDR(ptbl)   (((uintptr_t)(ptbl) != (uintptr_t)NULL)?(ptbl)->buffer + (ptbl)->end - 1:NULL)
#define	BU_PTBL_FOR(ip, cast, ptbl)    ip = cast BU_PTBL_LASTADDR(ptbl); ip >= cast BU_PTBL_BASEADDR(ptbl); ip--

Typedefs
typedef struct bu_ptbl	bu_ptbl_t

Functions
void	bu_ptbl_init (struct bu_ptbl *b, size_t len, const char *str)
void	bu_ptbl_reset (struct bu_ptbl *b)
size_t	bu_ptbl_ins (struct bu_ptbl *b, long *p)
intmax_t	bu_ptbl_locate (const struct bu_ptbl *b, const long *p)
void	bu_ptbl_zero (struct bu_ptbl *b, const long *p)
intmax_t	bu_ptbl_ins_unique (struct bu_ptbl *b, long *p)
size_t	bu_ptbl_rm (struct bu_ptbl *b, const long *p)
void	bu_ptbl_cat (struct bu_ptbl *dest, const struct bu_ptbl *src)
void	bu_ptbl_cat_uniq (struct bu_ptbl *dest, const struct bu_ptbl *src)
void	bu_ptbl_free (struct bu_ptbl *b)
void	bu_pr_ptbl (const char *title, const struct bu_ptbl *tbl, int verbose)
void	bu_ptbl_trunc (struct bu_ptbl *tbl, size_t end)

Detailed Description

Support for generalized "pointer tables", kept compactly in a dynamic array.

The table is currently un-ordered, and is merely an array of pointers. The support routines BU_*PTBL* and bu_ptbl* manipulate the array for you. Pointers to be operated on (inserted, deleted, searched for) are passed as a "pointer to long".

Macro Definition Documentation

BU_PTBL_NULL

#define BU_PTBL_NULL   ((struct bu_ptbl *)0)

Definition at line 60 of file ptbl.h.

BU_CK_PTBL

#define BU_CK_PTBL

(

_p

)

BU_CKMAG(_p, BU_PTBL_MAGIC, "bu_ptbl")

assert the integrity of a bu_ptbl struct pointer.

Definition at line 65 of file ptbl.h.

BU_PTBL_INIT

#define BU_PTBL_INIT

(

_p

)

Value:

        { \
        BU_LIST_INIT_MAGIC(&(_p)->l, BU_PTBL_MAGIC); \
        (_p)->end = 0; \
        (_p)->blen = 0; \
        (_p)->buffer = NULL; \
    }

initialize a bu_ptbl struct without allocating any memory. this macro is not suitable for initializing a list head node.

Definition at line 71 of file ptbl.h.

BU_PTBL_INIT_ZERO

#define BU_PTBL_INIT_ZERO   { {BU_PTBL_MAGIC, BU_LIST_NULL, BU_LIST_NULL}, 0, 0, NULL }

macro suitable for declaration statement initialization of a bu_ptbl struct. does not allocate memory. not suitable for initializing a list head node.

Definition at line 83 of file ptbl.h.

BU_PTBL_IS_INITIALIZED

#define BU_PTBL_IS_INITIALIZED

(

_p

)

(((struct bu_ptbl *)(_p) != BU_PTBL_NULL) && LIKELY((_p)->l.magic == BU_PTBL_MAGIC))

returns truthfully whether a bu_ptbl has been initialized via BU_PTBL_INIT() or BU_PTBL_INIT_ZERO.

Definition at line 89 of file ptbl.h.

BU_PTBL_LEN

#define BU_PTBL_LEN

(

ptbl

)

(((uintptr_t)(ptbl) != (uintptr_t)NULL)?(ptbl)->end:0)

Definition at line 95 of file ptbl.h.

BU_PTBL_TEST

#define BU_PTBL_TEST

(

ptbl

)

(((uintptr_t)(ptbl) != (uintptr_t)NULL)?(ptbl)->l.magic == BU_PTBL_MAGIC:0)

Definition at line 96 of file ptbl.h.

BU_PTBL_GET

#define BU_PTBL_GET	(		ptbl,
			i
	)		((ptbl)->buffer[(i)])

Definition at line 97 of file ptbl.h.

BU_PTBL_SET

#define BU_PTBL_SET	(		ptbl,
			i,
			val
	)		((ptbl)->buffer[(i)] = (long*)(val))

Definition at line 98 of file ptbl.h.

BU_PTBL_END

#define BU_PTBL_END

(

ptbl

)

((ptbl)->end)

DEPRECATED

Definition at line 101 of file ptbl.h.

BU_PTBL_BASEADDR

#define BU_PTBL_BASEADDR

(

ptbl

)

(((uintptr_t)(ptbl) != (uintptr_t)NULL)?(ptbl)->buffer:NULL)

DEPRECATED

Definition at line 103 of file ptbl.h.

BU_PTBL_LASTADDR

#define BU_PTBL_LASTADDR

(

ptbl

)

(((uintptr_t)(ptbl) != (uintptr_t)NULL)?(ptbl)->buffer + (ptbl)->end - 1:NULL)

DEPRECATED

Definition at line 105 of file ptbl.h.

BU_PTBL_FOR

#define BU_PTBL_FOR	(		ip,
			cast,
			ptbl
	)		ip = cast BU_PTBL_LASTADDR(ptbl); ip >= cast BU_PTBL_BASEADDR(ptbl); ip--

A handy way to visit all the elements of the table is:

struct edgeuse **eup; for (eup = (struct edgeuse **)BU_PTBL_LASTADDR(&eutab); eup >= (struct edgeuse **)BU_PTBL_BASEADDR(&eutab); eup–) { NMG_CK_EDGEUSE(*eup); } — OR — for (BU_PTBL_FOR(eup, (struct edgeuse **), &eutab)) { NMG_CK_EDGEUSE(*eup); }

Definition at line 119 of file ptbl.h.

Typedef Documentation

bu_ptbl_t

typedef struct bu_ptbl bu_ptbl_t

Definition at line 1 of file ptbl.h.

Function Documentation

bu_ptbl_init()

void bu_ptbl_init	(	struct bu_ptbl *	b,
		size_t	len,
		const char *	str
	)

This collection of routines implements a "pointer table" data structure providing a convenient mechanism for managing a collection of pointers to objects. This is useful where the size of the array is not known in advance and may change with time. It's convenient to be able to write code that can say "remember this object", and then later on iterate through the collection of remembered objects.

When combined with the concept of placing "magic numbers" as the first field of each data structure, the pointers to the objects become automatically typed. Initialize struct & get storage for table. Recommend 8 or 64 for initial len.

bu_ptbl_reset()

void bu_ptbl_reset

(

struct bu_ptbl *

b

)

Reset the table to have no elements, but retain any existing storage.

bu_ptbl_ins()

size_t bu_ptbl_ins	(	struct bu_ptbl *	b,
		long *	p
	)

Append/Insert a (long *) item to/into the table.

bu_ptbl_locate()

intmax_t bu_ptbl_locate	(	const struct bu_ptbl *	b,
		const long *	p
	)

locate a (long *) in an existing table

Returns

index of first matching element in array, if found

-1 if not found

We do this a great deal, so make it go as fast as possible. this is the biggest argument I can make for changing to an ordered list. Someday....

bu_ptbl_zero()

void bu_ptbl_zero	(	struct bu_ptbl *	b,
		const long *	p
	)

Set all occurrences of "p" in the table to zero. This is different than deleting them.

bu_ptbl_ins_unique()

intmax_t bu_ptbl_ins_unique	(	struct bu_ptbl *	b,
		long *	p
	)

Append item to table, if not already present. Unique insert.

Returns

index of first matching element in array, if found. (table unchanged)

-1 if table extended to hold new element

We do this a great deal, so make it go as fast as possible. this is the biggest argument I can make for changing to an ordered list. Someday....

bu_ptbl_rm()

size_t bu_ptbl_rm	(	struct bu_ptbl *	b,
		const long *	p
	)

Remove all occurrences of an item from a table

Returns

Number of copies of 'p' that were removed from the table.

0 if none found.

we go backwards down the table looking for occurrences of p to delete. We do it backwards to reduce the amount of data moved when there is more than one occurrence of p in the table. A pittance savings, unless you're doing a lot of it.

bu_ptbl_cat()

void bu_ptbl_cat	(	struct bu_ptbl *	dest,
		const struct bu_ptbl *	src
	)

Catenate one table onto end of another. There is no checking for duplication.

bu_ptbl_cat_uniq()

void bu_ptbl_cat_uniq	(	struct bu_ptbl *	dest,
		const struct bu_ptbl *	src
	)

Catenate one table onto end of another, ensuring that no entry is duplicated. Duplications between multiple items in 'src' are not caught. The search is a nasty n**2 one. The tables are expected to be short.

bu_ptbl_free()

void bu_ptbl_free

(

struct bu_ptbl *

b

)

Deallocate dynamic buffer associated with a table, and render this table unusable without a subsequent bu_ptbl_init().

bu_pr_ptbl()

void bu_pr_ptbl	(	const char *	title,
		const struct bu_ptbl *	tbl,
		int	verbose
	)

Print a bu_ptbl array for inspection.

bu_ptbl_trunc()

void bu_ptbl_trunc	(	struct bu_ptbl *	tbl,
		size_t	end
	)

truncate a bu_ptbl to the specified size.