Blender  V3.3
BLI_listbase_test.cc
Go to the documentation of this file.
1 /* SPDX-License-Identifier: Apache-2.0 */
2 
3 #include "testing/testing.h"
4 
5 #include "MEM_guardedalloc.h"
6 
7 #include "BLI_array_utils.h"
8 #include "BLI_listbase.h"
9 #include "BLI_path_util.h"
10 #include "BLI_ressource_strings.h"
11 #include "BLI_string.h"
12 
13 /* local validation function */
14 static bool listbase_is_valid(const ListBase *listbase)
15 {
16 #define TESTFAIL(test) \
17  if (!(test)) { \
18  goto fail; \
19  } \
20  ((void)0)
21 
22  if (listbase->first) {
23  const Link *prev, *link;
24  link = (Link *)listbase->first;
25  TESTFAIL(link->prev == nullptr);
26 
27  link = (Link *)listbase->last;
28  TESTFAIL(link->next == nullptr);
29 
30  prev = nullptr;
31  link = (Link *)listbase->first;
32  do {
33  TESTFAIL(link->prev == prev);
34  } while ((void)(prev = link), (link = link->next));
35  TESTFAIL(prev == listbase->last);
36 
37  prev = nullptr;
38  link = (Link *)listbase->last;
39  do {
40  TESTFAIL(link->next == prev);
41  } while ((void)(prev = link), (link = link->prev));
42  TESTFAIL(prev == listbase->first);
43  }
44  else {
45  TESTFAIL(listbase->last == nullptr);
46  }
47 #undef TESTFAIL
48 
49  return true;
50 
51 fail:
52  return false;
53 }
54 
55 static int char_switch(char *string, char ch_src, char ch_dst)
56 {
57  int tot = 0;
58  while (*string != 0) {
59  if (*string == ch_src) {
60  *string = ch_dst;
61  tot++;
62  }
63  string++;
64  }
65  return tot;
66 }
67 
68 TEST(listbase, FindLinkOrIndex)
69 {
70  ListBase lb;
71  void *link1 = MEM_callocN(sizeof(Link), "link1");
72  void *link2 = MEM_callocN(sizeof(Link), "link2");
73 
74  /* Empty list */
75  BLI_listbase_clear(&lb);
76  EXPECT_EQ(BLI_findlink(&lb, -1), (void *)nullptr);
77  EXPECT_EQ(BLI_findlink(&lb, 0), (void *)nullptr);
78  EXPECT_EQ(BLI_findlink(&lb, 1), (void *)nullptr);
79  EXPECT_EQ(BLI_rfindlink(&lb, -1), (void *)nullptr);
80  EXPECT_EQ(BLI_rfindlink(&lb, 0), (void *)nullptr);
81  EXPECT_EQ(BLI_rfindlink(&lb, 1), (void *)nullptr);
82  EXPECT_EQ(BLI_findindex(&lb, link1), -1);
83  EXPECT_EQ(BLI_findlinkfrom((Link *)lb.first, -1), (void *)nullptr);
84  EXPECT_EQ(BLI_findlinkfrom((Link *)lb.first, 0), (void *)nullptr);
85  EXPECT_EQ(BLI_findlinkfrom((Link *)lb.first, 1), (void *)nullptr);
86 
87  /* One link */
88  BLI_addtail(&lb, link1);
89  EXPECT_EQ(BLI_findlink(&lb, 0), link1);
90  EXPECT_EQ(BLI_rfindlink(&lb, 0), link1);
91  EXPECT_EQ(BLI_findindex(&lb, link1), 0);
92  EXPECT_EQ(BLI_findlinkfrom((Link *)lb.first, 0), link1);
93 
94  /* Two links */
95  BLI_addtail(&lb, link2);
96  EXPECT_EQ(BLI_findlink(&lb, 1), link2);
97  EXPECT_EQ(BLI_rfindlink(&lb, 0), link2);
98  EXPECT_EQ(BLI_findindex(&lb, link2), 1);
99  EXPECT_EQ(BLI_findlinkfrom((Link *)lb.first, 1), link2);
100 
101  /* After end of list */
102  EXPECT_EQ(BLI_findlinkfrom((Link *)lb.first, 2), (void *)nullptr);
103 
104  BLI_freelistN(&lb);
105 }
106 
107 TEST(listbase, FindLinkFromStringOrPointer)
108 {
109  struct TestLink {
110  struct TestLink *prev, *next;
111  char name[64];
112  const void *ptr;
113  };
114 
115  const char *const link1_name = "Link1";
116  const char *const link2_name = "Link2";
117  const void *const link1_ptr = nullptr;
118  const void *const link2_ptr = link2_name;
119 
120  const size_t name_offset = offsetof(struct TestLink, name);
121  const size_t ptr_offset = offsetof(struct TestLink, ptr);
122 
123  ListBase lb;
124  struct TestLink *link1 = (struct TestLink *)MEM_callocN(sizeof(TestLink), "link1");
125  BLI_strncpy(link1->name, link1_name, sizeof(link1->name));
126  link1->ptr = link1_ptr;
127  struct TestLink *link2 = (struct TestLink *)MEM_callocN(sizeof(TestLink), "link2");
128  BLI_strncpy(link2->name, link2_name, sizeof(link2->name));
129  link2->ptr = link2_ptr;
130 
131  /* Empty list */
132  BLI_listbase_clear(&lb);
133  EXPECT_EQ(BLI_findptr(&lb, link1_ptr, ptr_offset), (void *)nullptr);
134  EXPECT_EQ(BLI_findstring(&lb, link1_name, name_offset), (void *)nullptr);
135  EXPECT_EQ(BLI_rfindptr(&lb, link1_ptr, ptr_offset), (void *)nullptr);
136  EXPECT_EQ(BLI_rfindstring(&lb, link1_name, name_offset), (void *)nullptr);
137  EXPECT_EQ(BLI_listbase_string_or_index_find(&lb, link1_name, name_offset, 0), (void *)nullptr);
138 
139  /* One link */
140  BLI_addtail(&lb, link1);
141  EXPECT_EQ(BLI_findptr(&lb, link1_ptr, ptr_offset), (void *)link1);
142  EXPECT_EQ(BLI_findstring(&lb, link1_name, name_offset), (void *)link1);
143  EXPECT_EQ(BLI_rfindptr(&lb, link1_ptr, ptr_offset), (void *)link1);
144  EXPECT_EQ(BLI_rfindstring(&lb, link1_name, name_offset), (void *)link1);
145  EXPECT_EQ(BLI_listbase_string_or_index_find(&lb, link1_name, name_offset, 0), (void *)link1);
146  EXPECT_EQ(BLI_listbase_string_or_index_find(&lb, "", name_offset, 0), (void *)link1);
147  EXPECT_EQ(BLI_listbase_string_or_index_find(&lb, nullptr, name_offset, 0), (void *)link1);
148  EXPECT_EQ(BLI_listbase_string_or_index_find(&lb, nullptr, name_offset, 1), (void *)nullptr);
149 
150  /* Two links */
151  BLI_addtail(&lb, link2);
152  EXPECT_EQ(BLI_findptr(&lb, link1_ptr, ptr_offset), (void *)link1);
153  EXPECT_EQ(BLI_findstring(&lb, link1_name, name_offset), (void *)link1);
154  EXPECT_EQ(BLI_rfindptr(&lb, link1_ptr, ptr_offset), (void *)link1);
155  EXPECT_EQ(BLI_rfindstring(&lb, link1_name, name_offset), (void *)link1);
156  EXPECT_EQ(BLI_listbase_string_or_index_find(&lb, link1_name, name_offset, 0), (void *)link1);
157  EXPECT_EQ(BLI_listbase_string_or_index_find(&lb, link2_name, name_offset, 0), (void *)link2);
158  EXPECT_EQ(BLI_listbase_string_or_index_find(&lb, nullptr, name_offset, 0), (void *)link1);
159  EXPECT_EQ(BLI_listbase_string_or_index_find(&lb, nullptr, name_offset, 1), (void *)link2);
160  EXPECT_EQ(BLI_listbase_string_or_index_find(&lb, nullptr, name_offset, -1), (void *)nullptr);
161 
162  BLI_freelistN(&lb);
163 }
164 
165 TEST(listbase, FromLink)
166 {
167  ListBase lb = {nullptr, nullptr};
168  Link *link1 = static_cast<Link *>(MEM_callocN(sizeof(Link), "link1"));
169  Link *link2 = static_cast<Link *>(MEM_callocN(sizeof(Link), "link2"));
170  Link *link3 = static_cast<Link *>(MEM_callocN(sizeof(Link), "link3"));
171 
172  /* NULL safety. */
173  EXPECT_EQ(lb, BLI_listbase_from_link(nullptr));
174 
175  /* One link. */
176  BLI_addtail(&lb, link1);
177  EXPECT_EQ(lb, BLI_listbase_from_link(link1));
178 
179  /* Two links. */
180  BLI_addtail(&lb, link2);
181  EXPECT_EQ(lb, BLI_listbase_from_link(link2));
182 
183  /* Three links, search from middle. */
184  BLI_addtail(&lb, link3);
185  EXPECT_EQ(lb, BLI_listbase_from_link(link2));
186 
187  BLI_freelistN(&lb);
188 }
189 
190 /* -------------------------------------------------------------------- */
191 /* Sort utilities & test */
192 
193 static int testsort_array_str_cmp(const void *a, const void *b)
194 {
195  int i = strcmp(*(const char **)a, *(const char **)b);
196  return (i > 0) ? 1 : (i < 0) ? -1 : 0;
197 }
198 
199 static int testsort_listbase_str_cmp(const void *a, const void *b)
200 {
201  const LinkData *link_a = (LinkData *)a;
202  const LinkData *link_b = (LinkData *)b;
203  int i = strcmp((const char *)link_a->data, (const char *)link_b->data);
204  return (i > 0) ? 1 : (i < 0) ? -1 : 0;
205 }
206 
207 static int testsort_array_str_cmp_reverse(const void *a, const void *b)
208 {
209  return -testsort_array_str_cmp(a, b);
210 }
211 
212 static int testsort_listbase_str_cmp_reverse(const void *a, const void *b)
213 {
214  return -testsort_listbase_str_cmp(a, b);
215 }
216 
217 /* check array and listbase compare */
218 static bool testsort_listbase_array_str_cmp(ListBase *lb, char **arr, int arr_num)
219 {
220  LinkData *link_step;
221  int i;
222 
223  link_step = (LinkData *)lb->first;
224  for (i = 0; i < arr_num; i++) {
225  if (strcmp(arr[i], (char *)link_step->data) != 0) {
226  return false;
227  }
228  link_step = link_step->next;
229  }
230  if (link_step) {
231  return false;
232  }
233 
234  return true;
235 }
236 
237 /* assumes nodes are allocated in-order */
238 static bool testsort_listbase_sort_is_stable(ListBase *lb, bool forward)
239 {
240  LinkData *link_step;
241 
242  link_step = (LinkData *)lb->first;
243  while (link_step && link_step->next) {
244  if (strcmp((const char *)link_step->data, (const char *)link_step->next->data) == 0) {
245  if ((link_step < link_step->next) != forward) {
246  return false;
247  }
248  }
249  link_step = link_step->next;
250  }
251  return true;
252 }
253 
254 TEST(listbase, Sort)
255 {
256  const int words_len = sizeof(words10k) - 1;
257  char *words = BLI_strdupn(words10k, words_len);
258  int words_num;
259  char **words_arr; /* qsort for comparison */
260  int i;
261  char *w_step;
262  ListBase words_lb;
263  LinkData *words_linkdata_arr;
264 
265  /* delimit words */
266  words_num = 1 + char_switch(words, ' ', '\0');
267 
268  words_arr = (char **)MEM_mallocN(sizeof(*words_arr) * words_num, __func__);
269 
270  words_linkdata_arr = (LinkData *)MEM_mallocN(sizeof(*words_linkdata_arr) * words_num, __func__);
271 
272  /* create array */
273  w_step = words;
274  for (i = 0; i < words_num; i++) {
275  words_arr[i] = w_step;
276  w_step += strlen(w_step) + 1;
277  }
278 
279  /* sort empty list */
280  {
281  BLI_listbase_clear(&words_lb);
283  EXPECT_TRUE(listbase_is_valid(&words_lb));
284  }
285 
286  /* Sort single list. */
287  {
288  LinkData link;
289  link.data = words;
290  BLI_addtail(&words_lb, &link);
292  EXPECT_TRUE(listbase_is_valid(&words_lb));
293  BLI_listbase_clear(&words_lb);
294  }
295 
296  /* create listbase */
297  BLI_listbase_clear(&words_lb);
298  w_step = words;
299  for (i = 0; i < words_num; i++) {
300  LinkData *link = &words_linkdata_arr[i];
301  link->data = w_step;
302  BLI_addtail(&words_lb, link);
303  w_step += strlen(w_step) + 1;
304  }
305  EXPECT_TRUE(listbase_is_valid(&words_lb));
306 
307  /* sort (forward) */
308  {
309  qsort(words_arr, words_num, sizeof(*words_arr), testsort_array_str_cmp);
310 
312  EXPECT_TRUE(listbase_is_valid(&words_lb));
313  EXPECT_TRUE(testsort_listbase_array_str_cmp(&words_lb, words_arr, words_num));
314  EXPECT_TRUE(testsort_listbase_sort_is_stable(&words_lb, true));
315  }
316 
317  /* sort (reverse) */
318  {
319  qsort(words_arr, words_num, sizeof(*words_arr), testsort_array_str_cmp_reverse);
320 
322  EXPECT_TRUE(listbase_is_valid(&words_lb));
323  EXPECT_TRUE(testsort_listbase_array_str_cmp(&words_lb, words_arr, words_num));
324  EXPECT_TRUE(testsort_listbase_sort_is_stable(&words_lb, true));
325  }
326 
327  /* sort (forward but after reversing, test stability in alternate direction) */
328  {
329  BLI_array_reverse(words_arr, words_num);
330  BLI_listbase_reverse(&words_lb);
331 
332  EXPECT_TRUE(listbase_is_valid(&words_lb));
333  EXPECT_TRUE(testsort_listbase_array_str_cmp(&words_lb, words_arr, words_num));
334  EXPECT_TRUE(testsort_listbase_sort_is_stable(&words_lb, false));
335 
336  /* and again */
337  BLI_array_reverse(words_arr, words_num);
339  EXPECT_TRUE(testsort_listbase_array_str_cmp(&words_lb, words_arr, words_num));
340  EXPECT_TRUE(testsort_listbase_sort_is_stable(&words_lb, false));
341  }
342 
343  MEM_freeN(words);
344  MEM_freeN(words_arr);
345  MEM_freeN(words_linkdata_arr);
346 }
Generic array manipulation API.
#define BLI_array_reverse(arr, arr_len)
EXPECT_EQ(BLI_expr_pylike_eval(expr, nullptr, 0, &result), EXPR_PYLIKE_INVALID)
void void * BLI_listbase_string_or_index_find(const struct ListBase *listbase, const char *string, size_t string_offset, int index) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
BLI_INLINE void BLI_listbase_clear(struct ListBase *lb)
Definition: BLI_listbase.h:273
void * BLI_rfindlink(const struct ListBase *listbase, int number) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
void * BLI_findlinkfrom(struct Link *start, int number) ATTR_WARN_UNUSED_RESULT
Definition: listbase.c:534
void void BLI_freelistN(struct ListBase *listbase) ATTR_NONNULL(1)
Definition: listbase.c:466
void void BLI_listbase_sort(struct ListBase *listbase, int(*cmp)(const void *, const void *)) ATTR_NONNULL(1
void BLI_addtail(struct ListBase *listbase, void *vlink) ATTR_NONNULL(1)
Definition: listbase.c:80
int BLI_findindex(const struct ListBase *listbase, const void *vlink) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
void * BLI_findlink(const struct ListBase *listbase, int number) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
void void void void void void BLI_listbase_reverse(struct ListBase *lb) ATTR_NONNULL(1)
Definition: listbase.c:797
ListBase BLI_listbase_from_link(struct Link *some_link)
Definition: listbase.c:761
void * BLI_findstring(const struct ListBase *listbase, const char *id, int offset) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
void * BLI_rfindstring(const struct ListBase *listbase, const char *id, int offset) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
void * BLI_rfindptr(const struct ListBase *listbase, const void *ptr, int offset) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
void * BLI_findptr(const struct ListBase *listbase, const void *ptr, int offset) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
static int testsort_listbase_str_cmp(const void *a, const void *b)
static int testsort_array_str_cmp(const void *a, const void *b)
static bool listbase_is_valid(const ListBase *listbase)
static bool testsort_listbase_array_str_cmp(ListBase *lb, char **arr, int arr_num)
static int testsort_array_str_cmp_reverse(const void *a, const void *b)
TEST(listbase, FindLinkOrIndex)
static int char_switch(char *string, char ch_src, char ch_dst)
static int testsort_listbase_str_cmp_reverse(const void *a, const void *b)
static bool testsort_listbase_sort_is_stable(ListBase *lb, bool forward)
#define TESTFAIL(test)
const char words10k[]
char * BLI_strdupn(const char *str, size_t len) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
Definition: string.c:33
char * BLI_strncpy(char *__restrict dst, const char *__restrict src, size_t maxncpy) ATTR_NONNULL()
Definition: string.c:64
Read Guarded memory(de)allocation.
void(* MEM_freeN)(void *vmemh)
Definition: mallocn.c:27
void *(* MEM_callocN)(size_t len, const char *str)
Definition: mallocn.c:31
void *(* MEM_mallocN)(size_t len, const char *str)
Definition: mallocn.c:33
static ulong * next
static unsigned a[3]
Definition: RandGen.cpp:78
SymEdge< T > * prev(const SymEdge< T > *se)
Definition: delaunay_2d.cc:105
static const pxr::TfToken b("b", pxr::TfToken::Immortal)
void * data
Definition: DNA_listBase.h:26
struct LinkData * next
Definition: DNA_listBase.h:25
void * last
Definition: DNA_listBase.h:31
void * first
Definition: DNA_listBase.h:31
PointerRNA * ptr
Definition: wm_files.c:3480