tests/checkasm/ext/src/function.c

Line	Branch	Exec	Source
1			/*
2			* Copyright © 2025, Niklas Haas
3			* Copyright © 2018, VideoLAN and dav1d authors
4			* Copyright © 2018, Two Orioles, LLC
5			* All rights reserved.
6			*
7			* Redistribution and use in source and binary forms, with or without
8			* modification, are permitted provided that the following conditions are met:
9			*
10			* 1. Redistributions of source code must retain the above copyright notice,
11			* this list of conditions and the following disclaimer.
12			*
13			* 2. Redistributions in binary form must reproduce the above copyright notice,
14			* this list of conditions and the following disclaimer in the documentation
15			* and/or other materials provided with the distribution.
16			*
17			* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18			* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19			* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20			* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
21			* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22			* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23			* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24			* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25			* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26			* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27			* POSSIBILITY OF SUCH DAMAGE.
28			*/
29
30			#include <stdio.h>
31			#include <stdlib.h>
32
33			#include "function.h"
34			#include "internal.h"
35
36			/* Deallocate a tree */
37		57101	static void func_uninit(CheckasmFunc *const f)
38			{
39	2/2 ✓ Branch 2 → 3 taken 28602 times. ✓ Branch 2 → 4 taken 28499 times.	57101	if (!f)
40		28602	return;
41
42		28499	CheckasmFuncVersion *v = f->versions.next;
43	2/2 ✓ Branch 6 → 5 taken 15517 times. ✓ Branch 6 → 7 taken 28499 times.	44016	while (v) {
44		15517	CheckasmFuncVersion *next = v->next;
45		15517	free(v->suffix);
46		15517	free(v);
47		15517	v = next;
48			}
49
50		28499	CheckasmFunc *const left = f->child[0];
51		28499	CheckasmFunc *const right = f->child[1];
52		28499	free(f->report_name);
53		28499	free(f);
54
55		28499	func_uninit(right);
56		28499	func_uninit(left);
57			}
58
59		103	void checkasm_func_tree_uninit(CheckasmFuncTree *tree)
60			{
61		103	func_uninit(tree->root);
62		103	memset(tree, 0, sizeof(*tree));
63		103	}
64
65			#define is_digit(x) ((x) >= '0' && (x) <= '9')
66
67			/* ASCIIbetical sort except preserving natural order for numbers */
68		4604359	static int cmp_func_names(const char a, const char b)
69			{
70		4604359	const char *const start = a;
71
72			int ascii_diff, digit_diff;
73	4/4 ✓ Branch 4 → 5 taken 108273241 times. ✓ Branch 4 → 6 taken 4226071 times. ✓ Branch 5 → 3 taken 107894953 times. ✓ Branch 5 → 6 taken 378288 times.	112499312	for (; !(ascii_diff = (const unsigned char ) a - (const unsigned char ) b) && *a;
74		107894953	a++, b++)
75			;
76	8/8 ✓ Branch 8 → 9 taken 8158177 times. ✓ Branch 8 → 12 taken 555333 times. ✓ Branch 9 → 10 taken 4747386 times. ✓ Branch 9 → 12 taken 3410791 times. ✓ Branch 10 → 11 taken 4521432 times. ✓ Branch 10 → 12 taken 225954 times. ✓ Branch 11 → 7 taken 4109151 times. ✓ Branch 11 → 12 taken 412281 times.	8713510	for (; is_digit(a) && is_digit(b); a++, b++)
77			;
78
79	16/16 ✓ Branch 12 → 13 taken 4529368 times. ✓ Branch 12 → 25 taken 74991 times. ✓ Branch 13 → 14 taken 4527465 times. ✓ Branch 13 → 25 taken 1903 times. ✓ Branch 14 → 15 taken 3512857 times. ✓ Branch 14 → 25 taken 1014608 times. ✓ Branch 15 → 16 taken 3000292 times. ✓ Branch 15 → 18 taken 512565 times. ✓ Branch 16 → 17 taken 606893 times. ✓ Branch 16 → 18 taken 2393399 times. ✓ Branch 19 → 20 taken 2800412 times. ✓ Branch 19 → 22 taken 712445 times. ✓ Branch 20 → 21 taken 422692 times. ✓ Branch 20 → 22 taken 2377720 times. ✓ Branch 23 → 24 taken 1029585 times. ✓ Branch 23 → 25 taken 2483272 times.	4604359	if (a > start && is_digit(a[-1]) && (digit_diff = is_digit(a) - is_digit(b)))
80		1029585	return digit_diff;
81
82		3574774	return ascii_diff;
83			}
84
85			/* Perform a tree rotation in the specified direction and return the new root */
86		26509	static CheckasmFunc tree_rotate(CheckasmFunc const f, const int dir)
87			{
88		26509	CheckasmFunc *const r = f->child[dir ^ 1];
89
90		26509	f->child[dir ^ 1] = r->child[dir];
91		26509	r->child[dir] = f;
92		26509	r->color = f->color;
93		26509	f->color = 0;
94		26509	return r;
95			}
96
97			#define is_red(f) ((f) && !(f)->color)
98
99			/* Balance a left-leaning red-black tree at the specified node */
100		324761	static void tree_balance(CheckasmFunc **const root)
101			{
102		324761	CheckasmFunc const f = root;
103
104	8/8 ✓ Branch 2 → 3 taken 311063 times. ✓ Branch 2 → 7 taken 13698 times. ✓ Branch 3 → 4 taken 125154 times. ✓ Branch 3 → 7 taken 185909 times. ✓ Branch 4 → 5 taken 113948 times. ✓ Branch 4 → 7 taken 11206 times. ✓ Branch 5 → 6 taken 19554 times. ✓ Branch 5 → 7 taken 94394 times.	324761	if (is_red(f->child[0]) && is_red(f->child[1])) {
105		19554	f->color ^= 1;
106		19554	f->child[0]->color = f->child[1]->color = 1;
107	7/8 ✓ Branch 7 → 8 taken 291509 times. ✓ Branch 7 → 9 taken 13698 times. ✓ Branch 8 → 9 taken 185909 times. ✓ Branch 8 → 13 taken 105600 times. ✓ Branch 9 → 10 taken 199607 times. ✗ Branch 9 → 13 not taken. ✓ Branch 10 → 11 taken 19525 times. ✓ Branch 10 → 13 taken 180082 times.	305207	} else if (!is_red(f->child[0]) && is_red(f->child[1]))
108		19525	root = tree_rotate(f, 0); / Rotate left */
109	7/8 ✓ Branch 13 → 14 taken 285682 times. ✗ Branch 13 → 19 not taken. ✓ Branch 14 → 15 taken 105600 times. ✓ Branch 14 → 19 taken 180082 times. ✓ Branch 15 → 16 taken 97978 times. ✓ Branch 15 → 19 taken 7622 times. ✓ Branch 16 → 17 taken 6984 times. ✓ Branch 16 → 19 taken 90994 times.	285682	else if (is_red(f->child[0]) && is_red(f->child[0]->child[0]))
110		6984	root = tree_rotate(f, 1); / Rotate right */
111		324761	}
112
113			/* Get a node with the specified name, creating it if it doesn't exist; returns
114			* 1 if a new node was inserted, 0 otherwise. */
115		4632858	static int func_get(CheckasmFunc *const root, const char const name,
116			CheckasmFunc **const out_func)
117			{
118		4632858	CheckasmFunc f = root;
119	2/2 ✓ Branch 2 → 3 taken 28499 times. ✓ Branch 2 → 5 taken 4604359 times.	4632858	if (!f) {
120			/* Allocate and insert a new node into the tree */
121		28499	const size_t name_length = strlen(name) + 1;
122		28499	f = checkasm_mallocz(offsetof(CheckasmFunc, name) + name_length);
123		28499	memcpy(f->name, name, name_length);
124		28499	out_func = root = f;
125		28499	return 1;
126			}
127
128			/* Search the tree for a matching node */
129		4604359	const int cmp = cmp_func_names(name, f->name);
130	2/2 ✓ Branch 6 → 7 taken 378288 times. ✓ Branch 6 → 8 taken 4226071 times.	4604359	if (!cmp) {
131		378288	*out_func = f;
132		378288	return 0;
133			}
134
135		4226071	int inserted = func_get(&f->child[cmp > 0], name, out_func);
136	2/2 ✓ Branch 9 → 10 taken 324761 times. ✓ Branch 9 → 11 taken 3901310 times.	4226071	if (inserted)
137		324761	tree_balance(root); /* Rebalance the tree on the way up */
138		4226071	return inserted;
139			}
140
141		406787	CheckasmFunc checkasm_func_get(CheckasmFuncTree tree, const char *const name)
142			{
143		406787	CheckasmFunc *func = NULL;
144		406787	int inserted = func_get(&tree->root, name, &func);
145	2/2 ✓ Branch 3 → 4 taken 28499 times. ✓ Branch 3 → 5 taken 378288 times.	406787	if (inserted)
146		28499	tree->root->color = 1; /* Ensure root is black */
147		406787	return func;
148			}
149

FFmpeg coverage