BRL-CAD
list.c
Go to the documentation of this file.
1 /* L I S T . 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 "bu/list.h"
25 #include "bu/log.h"
26 #include "bu/malloc.h"
27 #include "bu/parallel.h"
28 
29 struct bu_list *
31 {
32  struct bu_list *new_list;
33 
34  BU_ALLOC(new_list, struct bu_list);
35  BU_LIST_INIT(new_list);
36 
37  return new_list;
38 }
39 
40 struct bu_list *
41 bu_list_pop(struct bu_list *hp)
42 {
43  struct bu_list *p;
44 
45  BU_LIST_POP(bu_list, hp, p);
46 
47  return p;
48 }
49 
50 int
51 bu_list_len(register const struct bu_list *hd)
52 {
53  register int count = 0;
54  register const struct bu_list *ep;
55 
56  for (BU_LIST_FOR(ep, bu_list, hd)) {
57  count++;
58  }
59  return count;
60 }
61 
62 void
63 bu_list_reverse(register struct bu_list *hd)
64 {
65  struct bu_list tmp_hd;
66  register struct bu_list *ep = NULL;
67 
68  BU_LIST_INIT(&tmp_hd);
69  BU_CK_LIST_HEAD(hd);
70  BU_LIST_INSERT_LIST(&tmp_hd, hd);
71 
72  while (BU_LIST_WHILE(ep, bu_list, &tmp_hd)) {
73  BU_LIST_DEQUEUE(ep);
74  BU_LIST_APPEND(hd, ep);
75  }
76 }
77 
78 void
79 bu_list_free(struct bu_list *hd)
80 {
81  struct bu_list *p;
82 
83  while (BU_LIST_WHILE(p, bu_list, hd)) {
84  BU_LIST_DEQUEUE(p);
85  bu_free(p, "struct bu_list");
86  }
87 }
88 
89 void
90 bu_list_parallel_append(struct bu_list *headp, struct bu_list *itemp)
91 {
93  BU_LIST_INSERT(headp, itemp); /* insert before head = append */
95 }
96 
97 struct bu_list *
99 {
100  for (;;) {
101  register struct bu_list *p;
102 
104  p = BU_LIST_FIRST(bu_list, headp);
105  if (BU_LIST_NOT_HEAD(p, headp)) {
106  BU_LIST_DEQUEUE(p);
108  return p;
109  }
111  }
112  /* NOTREACHED */
113 }
114 
115 void
116 bu_ck_list(const struct bu_list *hd, const char *str)
117 {
118  register const struct bu_list *cur;
119  int head_count = 0;
120 
121  cur = hd;
122  do {
123  if (cur->magic == BU_LIST_HEAD_MAGIC)
124  head_count++;
125 
126  if (UNLIKELY(!cur->forw)) {
127  bu_log("bu_ck_list(%s) cur=%p, cur->forw=%p, hd=%p\n",
128  str, (void *)cur, (void *)cur->forw, (void *)hd);
129  bu_bomb("bu_ck_list() forw\n");
130  }
131  if (UNLIKELY(cur->forw->back != cur)) {
132  bu_log("bu_ck_list(%s) cur=%p, cur->forw=%p, cur->forw->back=%p, hd=%p\n",
133  str, (void *)cur, (void *)cur->forw, (void *)cur->forw->back, (void *)hd);
134  bu_bomb("bu_ck_list() forw->back\n");
135  }
136  if (UNLIKELY(!cur->back)) {
137  bu_log("bu_ck_list(%s) cur=%p, cur->back=%p, hd=%p\n",
138  str, (void *)cur, (void *)cur->back, (void *)hd);
139  bu_bomb("bu_ck_list() back\n");
140  }
141  if (UNLIKELY(cur->back->forw != cur)) {
142  bu_log("bu_ck_list(%s) cur=%p, cur->back=%p, cur->back->forw=%p, hd=%p\n",
143  str, (void *)cur, (void *)cur->back, (void *)cur->back->forw, (void *)hd);
144  bu_bomb("bu_ck_list() back->forw\n");
145  }
146  cur = cur->forw;
147  } while (cur != hd);
148 
149  if (UNLIKELY(head_count != 1)) {
150  bu_log("bu_ck_list(%s) head_count = %d, hd=%p\n",
151  str, head_count, (void *)hd);
152  bu_bomb("bu_ck_list() headless!\n");
153  }
154 }
155 
156 void
157 bu_ck_list_magic(const struct bu_list *hd, const char *str, const uint32_t magic)
158 {
159  register const struct bu_list *cur;
160  int head_count = 0;
161  int item = 0;
162 
163  cur = hd;
164  do {
165  if (cur->magic == BU_LIST_HEAD_MAGIC) {
166  head_count++;
167  } else if (UNLIKELY(cur->magic != magic)) {
168  void *curmagic = (void *)(ptrdiff_t)cur->magic;
169  void *formagic = (void *)(ptrdiff_t)cur->forw->magic;
170  void *hdmagic = (void *)(ptrdiff_t)hd->magic;
171  bu_log("bu_ck_list(%s) cur magic=(%s)%p, cur->forw magic=(%s)%p, hd magic=(%s)%p, item=%d\n",
172  str,
173  bu_identify_magic(cur->magic), curmagic,
174  bu_identify_magic(cur->forw->magic), formagic,
175  bu_identify_magic(hd->magic), hdmagic,
176  item);
177  bu_bomb("bu_ck_list_magic() cur->magic\n");
178  }
179 
180  if (UNLIKELY(!cur->forw)) {
181  bu_log("bu_ck_list_magic(%s) cur=%p, cur->forw=%p, hd=%p, item=%d\n",
182  str, (void *)cur, (void *)cur->forw, (void *)hd, item);
183  bu_bomb("bu_ck_list_magic() forw NULL\n");
184  }
185  if (UNLIKELY(cur->forw->back != cur)) {
186  bu_log("bu_ck_list_magic(%s) cur=%p, cur->forw=%p, cur->forw->back=%p, hd=%p, item=%d\n",
187  str,
188  (void *)cur, (void *)cur->forw, (void *)cur->forw->back, (void *)hd, item);
189  bu_log(" cur=%s, cur->forw=%s, cur->forw->back=%s\n",
190  bu_identify_magic(cur->magic),
192  bu_identify_magic(cur->forw->back->magic));
193  bu_bomb("bu_ck_list_magic() cur->forw->back != cur\n");
194  }
195  if (UNLIKELY(!cur->back)) {
196  bu_log("bu_ck_list_magic(%s) cur=%p, cur->back=%p, hd=%p, item=%d\n",
197  str, (void *)cur, (void *)cur->back, (void *)hd, item);
198  bu_bomb("bu_ck_list_magic() back NULL\n");
199  }
200  if (UNLIKELY(cur->back->forw != cur)) {
201  bu_log("bu_ck_list_magic(%s) cur=%p, cur->back=%p, cur->back->forw=%p, hd=%p, item=%d\n",
202  str, (void *)cur, (void *)cur->back, (void *)cur->back->forw, (void *)hd, item);
203  bu_bomb("bu_ck_list_magic() cur->back->forw != cur\n");
204  }
205  cur = cur->forw;
206  item++;
207  } while (cur != hd);
208 
209  if (UNLIKELY(head_count != 1)) {
210  bu_log("bu_ck_list_magic(%s) head_count = %d, hd=%p, items=%d\n",
211  str, head_count, (void *)hd, item);
212  bu_bomb("bu_ck_list_magic() headless!\n");
213  }
214 }
215 
216 /* XXX - apparently needed by muves */
217 struct bu_list *
219 {
220  struct bu_list *p2;
221 
222  p2 = BU_LIST_NEXT(bu_list, p);
223  BU_LIST_DEQUEUE(p2);
224 
225  return p2;
226 }
227 
228 /*
229  * Local Variables:
230  * mode: C
231  * tab-width: 8
232  * indent-tabs-mode: t
233  * c-file-style: "stroustrup"
234  * End:
235  * ex: shiftwidth=4 tabstop=8
236  */
#define BU_LIST_FOR(p, structure, hp)
Definition: list.h:365
struct bu_list * bu_list_parallel_dequeue(struct bu_list *headp)
Definition: list.c:98
void bu_log(const char *,...) _BU_ATTR_PRINTF12
Definition: log.c:176
#define BU_LIST_INSERT(old, new)
Definition: list.h:183
Definition: list.h:118
#define BU_SEM_LISTS
Definition: parallel.h:179
void bu_semaphore_acquire(unsigned int i)
Definition: semaphore.c:180
Header file for the BRL-CAD common definitions.
#define BU_LIST_POP(structure, hp, p)
Definition: list.h:249
#define BU_LIST_APPEND(old, new)
Definition: list.h:197
struct bu_list * bu_list_pop(struct bu_list *hp)
Definition: list.c:41
#define BU_ALLOC(_ptr, _type)
Definition: malloc.h:223
struct bu_list * back
"back", "last"
Definition: list.h:121
void bu_ck_list(const struct bu_list *hd, const char *str)
Definition: list.c:116
oldeumate l2 magic
Definition: nmg_mod.c:3843
#define UNUSED(parameter)
Definition: common.h:239
uint32_t magic
Magic # for mem id/check.
Definition: list.h:119
#define BU_LIST_WHILE(p, structure, hp)
Definition: list.h:410
void bu_semaphore_release(unsigned int i)
Definition: semaphore.c:218
void bu_list_parallel_append(struct bu_list *headp, struct bu_list *itemp)
Definition: list.c:90
#define BU_LIST_INIT(_hp)
Definition: list.h:148
struct bu_list * bu_list_dequeue_next(struct bu_list *hp, struct bu_list *p)
Definition: list.c:218
int bu_list_len(register const struct bu_list *hd)
Definition: list.c:51
void bu_free(void *ptr, const char *str)
Definition: malloc.c:328
#define BU_CK_LIST_HEAD(_p)
Definition: list.h:142
struct bu_list * bu_list_new(void)
Definition: list.c:30
#define BU_LIST_DEQUEUE(cur)
Definition: list.h:209
struct bu_list * forw
"forward", "next"
Definition: list.h:120
void bu_list_free(struct bu_list *hd)
Definition: list.c:79
#define BU_LIST_HEAD_MAGIC
Definition: magic.h:56
void bu_ck_list_magic(const struct bu_list *hd, const char *str, const uint32_t magic)
Definition: list.c:157
#define BU_LIST_INSERT_LIST(dest_hp, src_hp)
Definition: list.h:270
void bu_bomb(const char *str) _BU_ATTR_NORETURN
Definition: bomb.c:91
const char * bu_identify_magic(uint32_t magic)
#define BU_LIST_NEXT(structure, hp)
Definition: list.h:316
#define BU_LIST_NOT_HEAD(p, hp)
Definition: list.h:324
void bu_list_reverse(register struct bu_list *hd)
Definition: list.c:63
#define BU_LIST_FIRST(structure, hp)
Definition: list.h:312
#define UNLIKELY(expression)
Definition: common.h:282