BRL-CAD
ptbl.c
Go to the documentation of this file.
1 /* P T B L . C
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 #include "common.h"
22 
23 #include <stdio.h>
24 #include <string.h>
25 
26 #include "bu/debug.h"
27 #include "bu/log.h"
28 #include "bu/malloc.h"
29 #include "bu/ptbl.h"
30 
31 void
32 bu_ptbl_init(struct bu_ptbl *b, size_t len, const char *str)
33 {
35  bu_log("bu_ptbl_init(%p, len=%zu, %s)\n", (void *)b, len, str);
36 
38 
39  if (UNLIKELY(len <= (size_t)0))
40  len = 64;
41 
42  b->blen = len;
43  b->buffer = (long **)bu_calloc(b->blen, sizeof(long *), str);
44  b->end = 0;
45 }
46 
47 
48 void
50 {
51  BU_CK_PTBL(b);
52 
54  bu_log("bu_ptbl_reset(%p)\n", (void *)b);
55  b->end = 0;
56  memset((char *)b->buffer, 0, b->blen*sizeof(long *)); /* no peeking */
57 }
58 
59 
60 int
61 bu_ptbl_ins(struct bu_ptbl *b, long int *p)
62 {
63  register int i;
64 
65  BU_CK_PTBL(b);
66 
68  bu_log("bu_ptbl_ins(%p, %p)\n", (void *)b, (void *)p);
69 
70  if (b->blen == 0)
71  bu_ptbl_init(b, 64, "bu_ptbl_ins() buffer");
72 
73  if ((size_t)b->end >= b->blen) {
74  b->buffer = (long **)bu_realloc((char *)b->buffer,
75  sizeof(long *)*(b->blen *= 4),
76  "bu_ptbl.buffer[] (ins)");
77  }
78 
79  i = b->end++;
80  b->buffer[i] = p;
81  return i;
82 }
83 
84 
85 int
86 bu_ptbl_locate(const struct bu_ptbl *b, const long int *p)
87 {
88  register int k;
89  register const long **pp;
90 
91  BU_CK_PTBL(b);
92 
93  pp = (const long **)b->buffer;
94  for (k = b->end-1; k >= 0; k--)
95  if (pp[k] == p) return k;
96 
97  return -1;
98 }
99 
100 
101 void
102 bu_ptbl_zero(struct bu_ptbl *b, const long int *p)
103 {
104  register int k;
105  register const long **pp;
106 
107  BU_CK_PTBL(b);
108 
109  pp = (const long **)b->buffer;
110  for (k = b->end-1; k >= 0; k--) {
111  if (pp[k] == p) {
112  pp[k] = (long *)0;
113  }
114  }
115 }
116 
117 
118 int
119 bu_ptbl_ins_unique(struct bu_ptbl *b, long int *p)
120 {
121  register int k;
122  register long **pp;
123 
124  BU_CK_PTBL(b);
125 
126  pp = b->buffer;
127 
128  /* search for existing */
129  for (k = b->end-1; k >= 0; k--) {
130  if (pp[k] == p) {
131  return k;
132  }
133  }
134 
136  bu_log("bu_ptbl_ins_unique(%p, %p)\n", (void *)b, (void *)p);
137 
138  if (b->blen <= 0 || (size_t)b->end >= b->blen) {
139  /* Table needs to grow */
140  bu_ptbl_ins(b, p);
141  return -1; /* To signal that it was added */
142  }
143 
144  b->buffer[k=b->end++] = p;
145  return -1; /* To signal that it was added */
146 }
147 
148 
149 int
150 bu_ptbl_rm(struct bu_ptbl *b, const long int *p)
151 {
152  register int end, j, k, l;
153  register long **pp;
154  int ndel = 0;
155 
156  BU_CK_PTBL(b);
157 
158  end = b->end;
159  pp = b->buffer;
160 
161  for (l = b->end-1; l >= 0; --l) {
162  if (pp[l] == p) {
163  /* delete consecutive occurrence(s) of p */
164  ndel++;
165 
166  j=l+1;
167  while (l >= 1 && pp[l-1] == p) --l, ndel++;
168  /* pp[l] through pp[j-1] match p */
169 
170  end -= j - l;
171  for (k=l; j < b->end;)
172  b->buffer[k++] = b->buffer[j++];
173  b->end = end;
174  }
175  }
177  bu_log("bu_ptbl_rm(%p, %p) ndel=%d\n", (void *)b, (void *)p, ndel);
178  return ndel;
179 }
180 
181 
182 void
183 bu_ptbl_cat(struct bu_ptbl *dest, const struct bu_ptbl *src)
184 {
185  BU_CK_PTBL(dest);
186  BU_CK_PTBL(src);
187 
189  bu_log("bu_ptbl_cat(%p, %p)\n", (void *)dest, (void *)src);
190 
191  if ((dest->blen - dest->end) < (size_t)src->end) {
192  dest->blen = (dest->blen + src->end) * 2 + 8;
193  dest->buffer = (long **)bu_realloc((char *)dest->buffer,
194  dest->blen * sizeof(long *),
195  "bu_ptbl.buffer[] (cat)");
196  }
197  memcpy((char *)&dest->buffer[dest->end], (char *)src->buffer, src->end*sizeof(long *));
198  dest->end += src->end;
199 }
200 
201 
202 void
203 bu_ptbl_cat_uniq(struct bu_ptbl *dest, const struct bu_ptbl *src)
204 {
205  register long **p;
206 
207  BU_CK_PTBL(dest);
208  BU_CK_PTBL(src);
209 
211  bu_log("bu_ptbl_cat_uniq(%p, %p)\n", (void *)dest, (void *)src);
212 
213  /* Assume the worst, ensure sufficient space to add all 'src' items */
214  if ((dest->blen - dest->end) < (size_t)src->end) {
215  dest->buffer = (long **)bu_realloc((char *)dest->buffer,
216  sizeof(long *)*(dest->blen += src->blen + 8),
217  "bu_ptbl.buffer[] (cat_uniq)");
218  }
219  for (BU_PTBL_FOR(p, (long **), src)) {
220  bu_ptbl_ins_unique(dest, *p);
221  }
222 }
223 
224 
225 void
227 {
228  BU_CK_PTBL(b);
229 
230  if (b->buffer) {
231  bu_free((void *)b->buffer, "bu_ptbl.buffer[]");
232  }
233  memset((char *)b, 0, sizeof(struct bu_ptbl)); /* sanity */
234 
236  bu_log("bu_ptbl_free(%p)\n", (void *)b);
237 }
238 
239 
240 void
241 bu_pr_ptbl(const char *title, const struct bu_ptbl *tbl, int verbose)
242 {
243  register long **lp;
244 
245  BU_CK_PTBL(tbl);
246 
247  bu_log("%s: bu_ptbl array with %ld entries\n",
248  title, (long int)tbl->end);
249 
250  if (!verbose)
251  return;
252 
253  /* Go in ascending order */
254  for (lp = (long **)BU_PTBL_BASEADDR(tbl);
255  lp <= (long **)BU_PTBL_LASTADDR(tbl); lp++
256  ) {
257  if (*lp == 0) {
258  bu_log(" %p NULL entry\n", (void *)*lp);
259  continue;
260  }
261  bu_log(" %p %s\n", (void *)*lp, bu_identify_magic(**lp));
262  }
263 }
264 
265 
266 void
267 bu_ptbl_trunc(struct bu_ptbl *tbl, int end)
268 {
269  BU_CK_PTBL(tbl);
270 
271  if (tbl->end <= end)
272  return;
273 
274  tbl->end = end;
275  return;
276 }
277 
278 /*
279  * Local Variables:
280  * mode: C
281  * tab-width: 8
282  * indent-tabs-mode: t
283  * c-file-style: "stroustrup"
284  * End:
285  * ex: shiftwidth=4 tabstop=8
286  */
long ** buffer
Definition: ptbl.h:66
void bu_log(const char *,...) _BU_ATTR_PRINTF12
Definition: log.c:176
#define BU_PTBL_FOR(ip, cast, ptbl)
Definition: ptbl.h:125
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 int *p)
Definition: ptbl.c:150
int bu_ptbl_ins_unique(struct bu_ptbl *b, long int *p)
Definition: ptbl.c:119
Header file for the BRL-CAD common definitions.
#define BU_CK_PTBL(_p)
Definition: ptbl.h:74
void bu_ptbl_reset(struct bu_ptbl *b)
Definition: ptbl.c:49
Definition: ptbl.h:62
void bu_ptbl_zero(struct bu_ptbl *b, const long int *p)
Definition: ptbl.c:102
void * memset(void *s, int c, size_t n)
void bu_pr_ptbl(const char *title, const struct bu_ptbl *tbl, int verbose)
Definition: ptbl.c:241
void * bu_calloc(size_t nelem, size_t elsize, const char *str)
Definition: malloc.c:321
#define BU_PTBL_LASTADDR(ptbl)
Definition: ptbl.h:105
void bu_ptbl_cat_uniq(struct bu_ptbl *dest, const struct bu_ptbl *src)
Definition: ptbl.c:203
#define BU_LIST_INIT_MAGIC(_hp, _magic)
Definition: list.h:156
void bu_ptbl_trunc(struct bu_ptbl *tbl, int end)
Definition: ptbl.c:267
struct bu_list l
Definition: ptbl.h:63
void * bu_realloc(void *ptr, size_t siz, const char *str)
#define BU_PTBL_MAGIC
Definition: magic.h:59
int bu_ptbl_locate(const struct bu_ptbl *b, const long int *p)
Definition: ptbl.c:86
size_t blen
Definition: ptbl.h:65
void bu_ptbl_free(struct bu_ptbl *b)
Definition: ptbl.c:226
#define BU_DEBUG_PTBL
Definition: debug.h:64
int bu_debug
Definition: globals.c:87
void bu_ptbl_cat(struct bu_ptbl *dest, const struct bu_ptbl *src)
Definition: ptbl.c:183
#define BU_PTBL_BASEADDR(ptbl)
Definition: ptbl.h:104
void bu_free(void *ptr, const char *str)
Definition: malloc.c:328
off_t end
Definition: ptbl.h:64
int bu_ptbl_ins(struct bu_ptbl *b, long int *p)
Definition: ptbl.c:61
HIDDEN void verbose(struct human_data_t *dude)
Definition: human.c:2008
const char * bu_identify_magic(uint32_t magic)
#define UNLIKELY(expression)
Definition: common.h:282