FOSSology  4.7.1
Open Source License Compliance by Open Source Software
test_walk_tree.c
Go to the documentation of this file.
1 /*
2  SPDX-FileCopyrightText: © 2026 Siemens Healthineers AG
3 
4  SPDX-License-Identifier: GPL-2.0-only
5 */
6 
16 #include <libfossology.h>
17 #include <libfocunit.h>
18 #include <sys/resource.h>
19 
20 static PGresult *capture_update(PGconn *connection, const char *query);
21 static void capture_clear(PGresult *result);
22 static void capture_heart(int items);
23 
24 /* Keep the real WalkTree(), replacing only its I/O and the agent entry point.
25  * Include library headers first so these macros cannot rename library APIs.
26  */
27 #define main adj2nest_main
28 #define PQexec capture_update
29 #define PQclear capture_clear
30 #define fo_scheduler_heart capture_heart
31 #include "../../agent/adj2nest.c"
32 #undef fo_scheduler_heart
33 #undef PQclear
34 #undef PQexec
35 #undef main
36 
37 extern volatile gint items_processed;
38 extern volatile int alive;
39 
40 typedef struct
41 {
42  long pk;
43  long lft;
44  long rgt;
45 } nested_set;
46 
47 static nested_set *actual;
48 static nested_set *expected;
49 static unsigned char *endpoints;
50 static PGresult *command_result;
51 static long update_count;
52 static long clear_count;
53 static long heart_count;
54 static long expected_count;
55 static struct rlimit saved_stack_limit;
56 static int stack_limited;
57 
58 static void set_up(void)
59 {
60  TreeSize = 0;
61  TreeSet = 0;
62  SetNum = 1;
63  agent_verbose = 0;
64  pgConn = NULL;
65  uploadtree_tablename = "uploadtree_a";
66  update_count = clear_count = heart_count = expected_count = 0;
67  g_atomic_int_set(&items_processed, 0);
68  alive = FALSE;
69 }
70 
71 static void tear_down(void)
72 {
73  if (stack_limited)
74  {
75  FO_ASSERT(setrlimit(RLIMIT_STACK, &saved_stack_limit) == 0);
76  stack_limited = 0;
77  }
78  PQclear(command_result);
79  command_result = NULL;
80  free(Tree);
81  Tree = NULL;
82  free(actual);
83  actual = NULL;
84  free(expected);
85  expected = NULL;
86  free(endpoints);
87  endpoints = NULL;
88 }
89 
90 static void make_tree(long count)
91 {
92  TreeSize = count;
93  Tree = calloc(count, sizeof(*Tree));
94  actual = calloc(count, sizeof(*actual));
95  expected = calloc(count, sizeof(*expected));
96  endpoints = calloc(2 * count + 1, sizeof(*endpoints));
97  /* A real successful PGresult lets fo_checkPQcommand() run unchanged. */
98  command_result = PQmakeEmptyPGresult(NULL, PGRES_COMMAND_OK);
99  FO_ASSERT_PTR_NOT_NULL_FATAL(Tree);
100  FO_ASSERT_PTR_NOT_NULL_FATAL(actual);
101  FO_ASSERT_PTR_NOT_NULL_FATAL(expected);
102  FO_ASSERT_PTR_NOT_NULL_FATAL(endpoints);
103  FO_ASSERT_PTR_NOT_NULL_FATAL(command_result);
104  for (long i = 0; i < count; ++i)
105  {
106  /* IDs are deliberately nonconsecutive and unrelated to traversal order. */
107  Tree[i].UploadtreePk = 1001 + 7 * (count - i);
108  Tree[i].Child = -1;
109  Tree[i].Sibling = -1;
110  }
111 }
112 
113 static PGresult *capture_update(PGconn *connection, const char *query)
114 {
115  char table[128];
116  int end = 0;
117  FO_ASSERT_PTR_EQUAL(connection, pgConn);
118  FO_ASSERT_FATAL(update_count < TreeSize);
119  /* The previous update must be cleared and heartbeated before the next one. */
120  FO_ASSERT(clear_count == update_count);
121  FO_ASSERT(heart_count == update_count);
122  nested_set *row = &actual[update_count];
123  int fields = sscanf(query,
124  "UPDATE %127s SET lft='%ld', rgt='%ld' WHERE uploadtree_pk='%ld'%n",
125  table, &row->lft, &row->rgt, &row->pk, &end);
126  FO_ASSERT_EQUAL_FATAL(fields, 4);
127  FO_ASSERT(query[end] == '\0');
128  FO_ASSERT_STRING_EQUAL(table, uploadtree_tablename);
129  ++update_count;
130  return command_result;
131 }
132 
133 static void capture_clear(PGresult *result)
134 {
135  FO_ASSERT_PTR_EQUAL(result, command_result);
136  FO_ASSERT(clear_count + 1 == update_count);
137  FO_ASSERT(heart_count + 1 == update_count);
138  ++clear_count;
139  /* Reuse the successful result; tear_down() frees it with the real PQclear. */
140 }
141 
142 static void capture_heart(int items)
143 {
144  FO_ASSERT_EQUAL(items, 1);
145  FO_ASSERT(clear_count == update_count);
146  FO_ASSERT(heart_count + 1 == update_count);
147  ++heart_count;
148 
149  /* Simulate the alive flag being reset between updates by the alarm handler.
150  * Each call must refresh it, not just increment the processed-item count.
151  */
152  alive = FALSE;
153  fo_scheduler_heart(items);
154  FO_ASSERT_TRUE(alive);
155  FO_ASSERT(g_atomic_int_get(&items_processed) == heart_count);
156 }
157 
158 static int compare_pk(const void *a, const void *b)
159 {
160  long left = ((const nested_set *)a)->pk;
161  long right = ((const nested_set *)b)->pk;
162  return (left > right) - (left < right);
163 }
164 
165 static const nested_set *find_row(long index)
166 {
167  nested_set key = {Tree[index].UploadtreePk, 0, 0};
168  return bsearch(&key, actual, TreeSize, sizeof(*actual), compare_pk);
169 }
170 
171 static void assert_range(long index, long lft, long rgt)
172 {
173  const nested_set *row = find_row(index);
174  FO_ASSERT_PTR_NOT_NULL_FATAL(row);
175  FO_ASSERT(row->lft == lft);
176  FO_ASSERT(row->rgt == rgt);
177 }
178 
179 static void run_walk(void)
180 {
181  WalkTree(0, 0);
182  FO_ASSERT_FATAL(update_count == TreeSize);
183  FO_ASSERT(clear_count == TreeSize);
184  FO_ASSERT(heart_count == TreeSize);
185  FO_ASSERT(g_atomic_int_get(&items_processed) == TreeSize);
186  FO_ASSERT(SetNum == 2 * TreeSize);
187  qsort(actual, TreeSize, sizeof(*actual), compare_pk);
188 
189  for (long i = 0; i < TreeSize; ++i)
190  {
191  const nested_set *row = &actual[i];
192  FO_ASSERT_FATAL(row->lft >= 1 && row->rgt <= 2 * TreeSize);
193  FO_ASSERT_FATAL(row->lft < row->rgt);
194  FO_ASSERT_FALSE(endpoints[row->lft]);
195  FO_ASSERT_FALSE(endpoints[row->rgt]);
196  endpoints[row->lft] = endpoints[row->rgt] = 1;
197  }
198  for (long i = 1; i <= 2 * TreeSize; ++i)
199  {
200  FO_ASSERT_TRUE(endpoints[i]);
201  }
202  for (long i = 0; i < TreeSize; ++i)
203  {
204  const nested_set *parent = find_row(i);
205  FO_ASSERT_PTR_NOT_NULL_FATAL(parent);
206  for (long child = Tree[i].Child; child >= 0; child = Tree[child].Sibling)
207  {
208  const nested_set *row = find_row(child);
209  FO_ASSERT_PTR_NOT_NULL_FATAL(row);
210  FO_ASSERT(parent->lft < row->lft);
211  FO_ASSERT(row->rgt < parent->rgt);
212  }
213  }
214  assert_range(0, 1, 2 * TreeSize);
215 }
216 
221 static void walk_recursive(long index, long *number)
222 {
223  long left = (*number)++;
224  if (Tree[index].Child > -1)
225  {
226  walk_recursive(Tree[index].Child, number);
227  ++*number;
228  }
229  expected[expected_count++] =
230  (nested_set){Tree[index].UploadtreePk, left, *number};
231  if (Tree[index].Sibling > -1)
232  {
233  ++*number;
234  walk_recursive(Tree[index].Sibling, number);
235  }
236 }
237 
238 static void assert_recursive_parity(void)
239 {
240  long number = 1;
241  walk_recursive(0, &number);
242  FO_ASSERT_FATAL(expected_count == TreeSize);
243  qsort(expected, TreeSize, sizeof(*expected), compare_pk);
244  run_walk();
245  FO_ASSERT(SetNum == number);
246  for (long i = 0; i < TreeSize; ++i)
247  {
248  FO_ASSERT(actual[i].pk == expected[i].pk);
249  FO_ASSERT(actual[i].lft == expected[i].lft);
250  FO_ASSERT(actual[i].rgt == expected[i].rgt);
251  }
252 }
253 
254 static void test_single_node(void)
255 {
256  make_tree(1);
257  uploadtree_tablename = "uploadtree";
258  assert_recursive_parity();
259  assert_range(0, 1, 2);
260 }
261 
262 static void test_siblings(void)
263 {
264  make_tree(4);
265  Tree[0].Child = 1;
266  Tree[1].Sibling = 2;
267  Tree[2].Sibling = 3;
268  assert_recursive_parity();
269  assert_range(0, 1, 8);
270  assert_range(1, 2, 3);
271  assert_range(2, 4, 5);
272  assert_range(3, 6, 7);
273 }
274 
275 static void test_mixed_tree(void)
276 {
277  /* 0 -> [1, 2], 1 -> [3, 4], 2 -> [5], 4 -> [6, 7]. */
278  make_tree(8);
279  Tree[0].Child = 1;
280  Tree[1].Sibling = 2;
281  Tree[1].Child = 3;
282  Tree[3].Sibling = 4;
283  Tree[2].Child = 5;
284  Tree[4].Child = 6;
285  Tree[6].Sibling = 7;
286  assert_recursive_parity();
287  /* Hand-calculated values also guard against errors shared with the oracle. */
288  assert_range(0, 1, 16);
289  assert_range(1, 2, 11);
290  assert_range(2, 12, 15);
291  assert_range(3, 3, 4);
292  assert_range(4, 5, 10);
293  assert_range(5, 13, 14);
294  assert_range(6, 6, 7);
295  assert_range(7, 8, 9);
296 }
297 
298 static void test_deep_tree(void)
299 {
300  make_tree(256);
301  for (long i = 0; i + 1 < TreeSize; ++i)
302  {
303  Tree[i].Child = i + 1;
304  }
305  assert_recursive_parity();
306  for (long i = 0; i < TreeSize; ++i)
307  {
308  assert_range(i, i + 1, 2 * TreeSize - i);
309  }
310 }
311 
312 static void test_generated_tree(void)
313 {
314  guint32 seed = 0xc0ffee;
315  make_tree(1024);
316  for (long i = 1; i < TreeSize; ++i)
317  {
318  /* Fixed seed makes this irregular tree reproducible on every platform. */
319  seed = seed * 1664525U + 1013904223U;
320  long parent = seed % i;
321  long *link = &Tree[parent].Child;
322  while (*link >= 0)
323  {
324  link = &Tree[*link].Sibling;
325  }
326  *link = i;
327  }
328  assert_recursive_parity();
329 }
330 
331 static void test_wide_tree(void)
332 {
333  make_tree(100001); /* One root and 100,000 siblings. */
334  uploadtree_tablename = "uploadtree_123";
335  Tree[0].Child = 1;
336  for (long i = 1; i + 1 < TreeSize; ++i)
337  {
338  Tree[i].Sibling = i + 1;
339  }
340 
341  /* Width must not require a large call stack, even in unoptimized builds.
342  * Save/restore the soft limit; never change the process's hard limit.
343  */
344  FO_ASSERT_FATAL(getrlimit(RLIMIT_STACK, &saved_stack_limit) == 0);
345  struct rlimit limit = saved_stack_limit;
346  if (limit.rlim_cur == RLIM_INFINITY || limit.rlim_cur > 256 * 1024)
347  {
348  limit.rlim_cur = 256 * 1024;
349  FO_ASSERT_FATAL(setrlimit(RLIMIT_STACK, &limit) == 0);
350  stack_limited = 1;
351  }
352  run_walk();
353  for (long i = 1; i < TreeSize; ++i)
354  {
355  assert_range(i, 2 * i, 2 * i + 1);
356  }
357 }
358 
359 static CU_TestInfo walk_tree_tests[] = {
360  {"single node", test_single_node},
361  {"siblings", test_siblings},
362  {"mixed tree", test_mixed_tree},
363  {"deep tree", test_deep_tree},
364  {"generated tree", test_generated_tree},
365  {"100000 siblings with bounded stack", test_wide_tree},
366  CU_TEST_INFO_NULL
367 };
368 
369 static CU_SuiteInfo suites[] = {
370  {"WalkTree", NULL, NULL, set_up, tear_down, walk_tree_tests},
371  CU_SUITE_INFO_NULL
372 };
373 
374 int main(int argc, char **argv)
375 {
376  return focunit_main(argc, argv, "adj2nest", suites);
377 }
long SetNum
Definition: adj2nest.c:103
PGconn * pgConn
Database connection.
Definition: adj2nest.c:86
long TreeSet
Definition: adj2nest.c:102
void WalkTree(long Index, long Depth)
Definition: adj2nest.c:114
char * uploadtree_tablename
upload.uploadtree_tablename
Definition: adj2nest.c:100
The main FOSSology C library.
int agent_verbose
Common verbose flags for the agents, this is used so that the scheduler can change the verbose level ...
long UploadtreePk
Definition: adj2nest.c:94
long Sibling
Definition: adj2nest.c:96
long Child
Definition: adj2nest.c:95
void set_up(void)
Since the fossscheduler library depends on reading and writing very specific data to stdin and stdout...
void tear_down(void)
This function closes the pipes created in the setup function and returns stdin and stdout to their or...
volatile int alive
If the agent has updated with a hearbeat.
volatile gint items_processed
The number of items processed by the agent.
static void walk_recursive(long index, long *number)