BRL-CAD
ptbl.h
Go to the documentation of this file.
1 /* P T B L . H
2  * BRL-CAD
3  *
4  * Copyright (c) 2004-2014 United States Government as represented by
5  * the U.S. Army Research Laboratory.
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public License
9  * version 2.1 as published by the Free Software Foundation.
10  *
11  * This library is distributed in the hope that it will be useful, but
12  * WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with this file; see the file named COPYING for more
18  * information.
19  */
20 
21 /** @defgroup container Data Containers */
22 /** @defgroup ptbl Pointer Tables */
23 
24 /** @file ptbl.h
25  *
26  */
27 #ifndef BU_PTBL_H
28 #define BU_PTBL_H
29 
30 #include "common.h"
31 
32 #include <stddef.h> /* for size_t */
33 #include <sys/types.h> /* for off_t */
34 
35 #include "bu/defines.h"
36 #include "bu/magic.h"
37 #include "bu/list.h"
38 
40 
41 /* ptbl.c */
42 /** @addtogroup ptbl */
43 /** @{ */
44 /** @file libbu/ptbl.c
45  *
46  * Support for generalized "pointer tables"
47  *
48  * Support for generalized "pointer tables", kept compactly in a
49  * dynamic array.
50  *
51  * The table is currently un-ordered, and is merely an array of
52  * pointers. The support routines BU_*PTBL* and bu_ptbl* manipulate the
53  * array for you. Pointers to be operated on (inserted, deleted, searched
54  * for) are passed as a "pointer to long".
55  *
56  */
57 
58 
59 /**
60  * Support for generalized "pointer tables".
61  */
62 struct bu_ptbl {
63  struct bu_list l; /**< linked list for caller's use */
64  off_t end; /**< index into buffer of first available location */
65  size_t blen; /**< # of (long *)'s worth of storage at *buffer */
66  long **buffer; /**< data storage area */
67 };
68 typedef struct bu_ptbl bu_ptbl_t;
69 #define BU_PTBL_NULL ((struct bu_ptbl *)0)
70 
71 /**
72  * assert the integrity of a bu_ptbl struct pointer.
73  */
74 #define BU_CK_PTBL(_p) BU_CKMAG(_p, BU_PTBL_MAGIC, "bu_ptbl")
75 
76 /**
77  * initialize a bu_ptbl struct without allocating any memory. this
78  * macro is not suitable for initializing a list head node.
79  */
80 #define BU_PTBL_INIT(_p) { \
81  BU_LIST_INIT_MAGIC(&(_p)->l, BU_PTBL_MAGIC); \
82  (_p)->end = 0; \
83  (_p)->blen = 0; \
84  (_p)->buffer = NULL; \
85  }
86 
87 /**
88  * macro suitable for declaration statement initialization of a
89  * bu_ptbl struct. does not allocate memory. not suitable for
90  * initializing a list head node.
91  */
92 #define BU_PTBL_INIT_ZERO { {BU_PTBL_MAGIC, BU_LIST_NULL, BU_LIST_NULL}, 0, 0, NULL }
93 
94 /**
95  * returns truthfully whether a bu_ptbl has been initialized via
96  * BU_PTBL_INIT() or BU_PTBL_INIT_ZERO.
97  */
98 #define BU_PTBL_IS_INITIALIZED(_p) (((struct bu_ptbl *)(_p) != BU_PTBL_NULL) && LIKELY((_p)->l.magic == BU_PTBL_MAGIC))
99 
100 
101 /*
102  * For those routines that have to "peek" into the ptbl a little bit.
103  */
104 #define BU_PTBL_BASEADDR(ptbl) ((ptbl)->buffer)
105 #define BU_PTBL_LASTADDR(ptbl) ((ptbl)->buffer + (ptbl)->end - 1)
106 #define BU_PTBL_END(ptbl) ((ptbl)->end)
107 #define BU_PTBL_LEN(ptbl) ((size_t)(ptbl)->end)
108 #define BU_PTBL_GET(ptbl, i) ((ptbl)->buffer[(i)])
109 #define BU_PTBL_SET(ptbl, i, val) ((ptbl)->buffer[(i)] = (long*)(val))
110 #define BU_PTBL_TEST(ptbl) ((ptbl)->l.magic == BU_PTBL_MAGIC)
111 #define BU_PTBL_CLEAR_I(_ptbl, _i) ((_ptbl)->buffer[(_i)] = (long *)0)
112 
113 /**
114  * A handy way to visit all the elements of the table is:
115  *
116  * struct edgeuse **eup;
117  * for (eup = (struct edgeuse **)BU_PTBL_LASTADDR(&eutab); eup >= (struct edgeuse **)BU_PTBL_BASEADDR(&eutab); eup--) {
118  * NMG_CK_EDGEUSE(*eup);
119  * }
120  * --- OR ---
121  * for (BU_PTBL_FOR(eup, (struct edgeuse **), &eutab)) {
122  * NMG_CK_EDGEUSE(*eup);
123  * }
124  */
125 #define BU_PTBL_FOR(ip, cast, ptbl) \
126  ip = cast BU_PTBL_LASTADDR(ptbl); ip >= cast BU_PTBL_BASEADDR(ptbl); ip--
127 
128 /**
129  * This collection of routines implements a "pointer table" data
130  * structure providing a convenient mechanism for managing a collection
131  * of pointers to objects. This is useful where the size of the array
132  * is not known in advance and may change with time. It's convenient
133  * to be able to write code that can say "remember this object", and
134  * then later on iterate through the collection of remembered objects.
135  *
136  * When combined with the concept of placing "magic numbers" as the
137  * first field of each data structure, the pointers to the objects
138  * become automatically typed.
139  */
140 
141 /**
142  * Initialize struct & get storage for table.
143  * Recommend 8 or 64 for initial len.
144  */
145 BU_EXPORT extern void bu_ptbl_init(struct bu_ptbl *b,
146  size_t len,
147  const char *str);
148 
149 /**
150  * Reset the table to have no elements, but retain any existing
151  * storage.
152  */
153 BU_EXPORT extern void bu_ptbl_reset(struct bu_ptbl *b);
154 
155 /**
156  * Append/Insert a (long *) item to/into the table.
157  */
158 BU_EXPORT extern int bu_ptbl_ins(struct bu_ptbl *b,
159  long *p);
160 
161 /**
162  * locate a (long *) in an existing table
163  *
164  *
165  * @return index of first matching element in array, if found
166  * @return -1 if not found
167  *
168  * We do this a great deal, so make it go as fast as possible. this
169  * is the biggest argument I can make for changing to an ordered list.
170  * Someday....
171  */
172 BU_EXPORT extern int bu_ptbl_locate(const struct bu_ptbl *b,
173  const long *p);
174 
175 /**
176  * Set all occurrences of "p" in the table to zero. This is different
177  * than deleting them.
178  */
179 BU_EXPORT extern void bu_ptbl_zero(struct bu_ptbl *b,
180  const long *p);
181 
182 /**
183  * Append item to table, if not already present. Unique insert.
184  *
185  * @return index of first matching element in array, if found. (table unchanged)
186  * @return -1 if table extended to hold new element
187  *
188  * We do this a great deal, so make it go as fast as possible. this
189  * is the biggest argument I can make for changing to an ordered list.
190  * Someday....
191  */
192 BU_EXPORT extern int bu_ptbl_ins_unique(struct bu_ptbl *b, long *p);
193 
194 /**
195  * Remove all occurrences of an item from a table
196  *
197  * @return Number of copies of 'p' that were removed from the table.
198  * @return 0 if none found.
199  *
200  * we go backwards down the table looking for occurrences of p to
201  * delete. We do it backwards to reduce the amount of data moved when
202  * there is more than one occurrence of p in the table. A pittance
203  * savings, unless you're doing a lot of it.
204  */
205 BU_EXPORT extern int bu_ptbl_rm(struct bu_ptbl *b,
206  const long *p);
207 
208 /**
209  * Catenate one table onto end of another. There is no checking for
210  * duplication.
211  */
212 BU_EXPORT extern void bu_ptbl_cat(struct bu_ptbl *dest,
213  const struct bu_ptbl *src);
214 
215 /**
216  * Catenate one table onto end of another, ensuring that no entry is
217  * duplicated. Duplications between multiple items in 'src' are not
218  * caught. The search is a nasty n**2 one. The tables are expected
219  * to be short.
220  */
221 BU_EXPORT extern void bu_ptbl_cat_uniq(struct bu_ptbl *dest,
222  const struct bu_ptbl *src);
223 
224 /**
225  * Deallocate dynamic buffer associated with a table, and render this
226  * table unusable without a subsequent bu_ptbl_init().
227  */
228 BU_EXPORT extern void bu_ptbl_free(struct bu_ptbl *b);
229 
230 /**
231  * Print a bu_ptbl array for inspection.
232  */
233 BU_EXPORT extern void bu_pr_ptbl(const char *title,
234  const struct bu_ptbl *tbl,
235  int verbose);
236 
237 /**
238  * truncate a bu_ptbl
239  */
240 BU_EXPORT extern void bu_ptbl_trunc(struct bu_ptbl *tbl,
241  int end);
242 
243 /** @} */
244 
246 
247 #endif /* BU_PTBL_H */
248 
249 /*
250  * Local Variables:
251  * mode: C
252  * tab-width: 8
253  * indent-tabs-mode: t
254  * c-file-style: "stroustrup"
255  * End:
256  * ex: shiftwidth=4 tabstop=8
257  */
long ** buffer
Definition: ptbl.h:66
Definition: list.h:118
void bu_ptbl_init(struct bu_ptbl *b, size_t len, const char *str)
Definition: ptbl.c:32
int bu_ptbl_rm(struct bu_ptbl *b, const long *p)
Header file for the BRL-CAD common definitions.
int bu_ptbl_ins_unique(struct bu_ptbl *b, long *p)
int bu_ptbl_ins(struct bu_ptbl *b, long *p)
void bu_ptbl_reset(struct bu_ptbl *b)
Definition: ptbl.c:49
Definition: ptbl.h:62
void bu_pr_ptbl(const char *title, const struct bu_ptbl *tbl, int verbose)
Definition: ptbl.c:241
#define __BEGIN_DECLS
Definition: common.h:73
void bu_ptbl_cat_uniq(struct bu_ptbl *dest, const struct bu_ptbl *src)
Definition: ptbl.c:203
void bu_ptbl_trunc(struct bu_ptbl *tbl, int end)
Definition: ptbl.c:267
struct bu_list l
Definition: ptbl.h:63
int bu_ptbl_locate(const struct bu_ptbl *b, const long *p)
size_t blen
Definition: ptbl.h:65
void bu_ptbl_free(struct bu_ptbl *b)
Definition: ptbl.c:226
void bu_ptbl_zero(struct bu_ptbl *b, const long *p)
void bu_ptbl_cat(struct bu_ptbl *dest, const struct bu_ptbl *src)
Definition: ptbl.c:183
#define __END_DECLS
Definition: common.h:74
off_t end
Definition: ptbl.h:64
HIDDEN void verbose(struct human_data_t *dude)
Definition: human.c:2008