This source file includes following definitions.
- gl_tree_search_from_to
- gl_tree_indexof_from_to
- gl_tree_list_free
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 static gl_list_node_t
21 gl_tree_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
22 const void *elt)
23 {
24 if (!(start_index <= end_index
25 && end_index <= (list->root != NULL ? list->root->branch_size : 0)))
26
27 abort ();
28 {
29 size_t hashcode =
30 (list->base.hashcode_fn != NULL
31 ? list->base.hashcode_fn (elt)
32 : (size_t)(uintptr_t) elt);
33 size_t bucket = hashcode % list->table_size;
34 gl_listelement_equals_fn equals = list->base.equals_fn;
35 gl_hash_entry_t entry;
36
37 if (list->base.allow_duplicates)
38 {
39 for (entry = list->table[bucket]; entry != NULL; entry = entry->hash_next)
40 if (entry->hashcode == hashcode)
41 {
42 if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC)
43 {
44
45 gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes;
46
47 gl_list_node_t node = gl_oset_first (nodes);
48 if (equals != NULL ? equals (elt, node->value) : elt == node->value)
49 {
50
51 if (start_index == 0)
52 {
53
54
55
56 if (end_index == list->root->branch_size
57 || node_position (node) < end_index)
58 return node;
59 }
60 else
61 {
62
63
64 const void *nodes_elt;
65 if (gl_oset_search_atleast (nodes,
66 compare_position_threshold,
67 (void *)(uintptr_t)start_index,
68 &nodes_elt))
69 {
70 node = (gl_list_node_t) nodes_elt;
71 if (end_index == list->root->branch_size
72 || node_position (node) < end_index)
73 return node;
74 }
75 }
76 break;
77 }
78 }
79 else
80 {
81
82 gl_list_node_t node = (struct gl_list_node_impl *) entry;
83 if (equals != NULL ? equals (elt, node->value) : elt == node->value)
84 {
85 bool position_in_bounds;
86 if (start_index == 0 && end_index == list->root->branch_size)
87 position_in_bounds = true;
88 else
89 {
90 size_t position = node_position (node);
91 position_in_bounds =
92 (position >= start_index && position < end_index);
93 }
94 if (position_in_bounds)
95 return node;
96 break;
97 }
98 }
99 }
100 }
101 else
102 {
103
104 for (entry = list->table[bucket]; entry != NULL; entry = entry->hash_next)
105 if (entry->hashcode == hashcode)
106 {
107 gl_list_node_t node = (struct gl_list_node_impl *) entry;
108 if (equals != NULL ? equals (elt, node->value) : elt == node->value)
109 {
110 bool position_in_bounds;
111 if (start_index == 0 && end_index == list->root->branch_size)
112 position_in_bounds = true;
113 else
114 {
115 size_t position = node_position (node);
116 position_in_bounds =
117 (position >= start_index && position < end_index);
118 }
119 if (position_in_bounds)
120 return node;
121 break;
122 }
123 }
124 }
125
126 return NULL;
127 }
128 }
129
130 static size_t
131 gl_tree_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
132 const void *elt)
133 {
134 gl_list_node_t node =
135 gl_tree_search_from_to (list, start_index, end_index, elt);
136
137 if (node != NULL)
138 return node_position (node);
139 else
140 return (size_t)(-1);
141 }
142
143 static void
144 gl_tree_list_free (gl_list_t list)
145 {
146 if (list->base.allow_duplicates)
147 {
148
149 size_t i;
150
151 for (i = list->table_size; i > 0; )
152 {
153 gl_hash_entry_t entry = list->table[--i];
154
155 while (entry != NULL)
156 {
157 gl_hash_entry_t next = entry->hash_next;
158
159 if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC)
160 {
161 gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes;
162
163 gl_oset_free (nodes);
164 free (entry);
165 }
166
167 entry = next;
168 }
169 }
170 }
171
172
173 {
174 gl_list_node_t node = list->root;
175 iterstack_t stack;
176 iterstack_item_t *stack_ptr = &stack[0];
177
178 for (;;)
179 {
180
181 for (;;)
182 {
183 if (node == NULL)
184 break;
185 stack_ptr->node = node;
186 stack_ptr->rightp = false;
187 node = node->left;
188 stack_ptr++;
189 }
190
191 for (;;)
192 {
193 if (stack_ptr == &stack[0])
194 goto done_iterate;
195 stack_ptr--;
196 node = stack_ptr->node;
197 if (!stack_ptr->rightp)
198 break;
199
200 if (list->base.dispose_fn != NULL)
201 list->base.dispose_fn (node->value);
202 free (node);
203 }
204
205 stack_ptr->rightp = true;
206 node = node->right;
207 stack_ptr++;
208 }
209 }
210 done_iterate:
211 free (list->table);
212 free (list);
213 }