Branch data Line data Source code
1 : : /*
2 : : * Copyright (c) 2018 Intel Corporation
3 : : *
4 : : * SPDX-License-Identifier: Apache-2.0
5 : : */
6 : :
7 : : /* These assertions are very useful when debugging the tree code
8 : : * itself, but produce significant performance degradation as they are
9 : : * checked many times per operation. Leave them off unless you're
10 : : * working on the rbtree code itself
11 : : */
12 : : #define CHECK(n) /**/
13 : : /* #define CHECK(n) __ASSERT_NO_MSG(n) */
14 : :
15 : : #include <zephyr/kernel.h>
16 : : #include <zephyr/sys/rb.h>
17 : : #include <stdbool.h>
18 : :
19 : : enum rb_color { RED = 0U, BLACK = 1U };
20 : :
21 : 0 : static struct rbnode *get_child(struct rbnode *n, uint8_t side)
22 : : {
23 : 0 : CHECK(n);
24 [ # # ]: 0 : if (side != 0U) {
25 : 0 : return n->children[1];
26 : : }
27 : :
28 : 0 : uintptr_t l = (uintptr_t) n->children[0];
29 : :
30 : 0 : l &= ~1UL;
31 : 0 : return (struct rbnode *) l;
32 : : }
33 : :
34 : 0 : static void set_child(struct rbnode *n, uint8_t side, void *val)
35 : : {
36 : 0 : CHECK(n);
37 [ # # ]: 0 : if (side != 0U) {
38 : 0 : n->children[1] = val;
39 : : } else {
40 : 0 : uintptr_t old = (uintptr_t) n->children[0];
41 : 0 : uintptr_t new = (uintptr_t) val;
42 : :
43 : 0 : n->children[0] = (void *) (new | (old & 1UL));
44 : : }
45 : 0 : }
46 : :
47 : 0 : static enum rb_color get_color(struct rbnode *n)
48 : : {
49 : 0 : CHECK(n);
50 : 0 : return ((uintptr_t)n->children[0]) & 1UL;
51 : : }
52 : :
53 : 0 : static bool is_black(struct rbnode *n)
54 : : {
55 : 0 : return get_color(n) == BLACK;
56 : : }
57 : :
58 : 0 : static bool is_red(struct rbnode *n)
59 : : {
60 : 0 : return get_color(n) == RED;
61 : : }
62 : :
63 : 0 : static void set_color(struct rbnode *n, enum rb_color color)
64 : : {
65 : 0 : CHECK(n);
66 : :
67 : 0 : uintptr_t *p = (void *) &n->children[0];
68 : :
69 : 0 : *p = (*p & ~1UL) | (uint8_t)color;
70 : 0 : }
71 : :
72 : : /* Searches the tree down to a node that is either identical with the
73 : : * "node" argument or has an empty/leaf child pointer where "node"
74 : : * should be, leaving all nodes found in the resulting stack. Note
75 : : * that tree must not be empty and that stack should be allocated to
76 : : * contain at least tree->max_depth entries! Returns the number of
77 : : * entries pushed onto the stack.
78 : : */
79 : 0 : static int find_and_stack(struct rbtree *tree, struct rbnode *node,
80 : : struct rbnode **stack)
81 : : {
82 : 0 : int sz = 0;
83 : :
84 : 0 : stack[sz] = tree->root;
85 : 0 : ++sz;
86 : :
87 [ # # ]: 0 : while (stack[sz - 1] != node) {
88 : 0 : uint8_t side = tree->lessthan_fn(node, stack[sz - 1]) ? 0U : 1U;
89 : 0 : struct rbnode *ch = get_child(stack[sz - 1], side);
90 : :
91 [ # # ]: 0 : if (ch != NULL) {
92 : 0 : stack[sz] = ch;
93 : 0 : ++sz;
94 : : } else {
95 : : break;
96 : : }
97 : : }
98 : :
99 : 0 : return sz;
100 : : }
101 : :
102 : 0 : struct rbnode *z_rb_get_minmax(struct rbtree *tree, uint8_t side)
103 : : {
104 : 0 : struct rbnode *n;
105 : :
106 [ # # # # ]: 0 : for (n = tree->root; (n != NULL) && (get_child(n, side) != NULL);
107 : : n = get_child(n, side)) {
108 : : ;
109 : : }
110 : 0 : return n;
111 : : }
112 : :
113 : 0 : static uint8_t get_side(struct rbnode *parent, struct rbnode *child)
114 : : {
115 : 0 : CHECK(get_child(parent, 0U) == child || get_child(parent, 1U) == child);
116 : :
117 [ # # ]: 0 : return (get_child(parent, 1U) == child) ? 1U : 0U;
118 : : }
119 : :
120 : : /* Swaps the position of the two nodes at the top of the provided
121 : : * stack, modifying the stack accordingly. Does not change the color
122 : : * of either node. That is, it effects the following transition (or
123 : : * its mirror if N is on the other side of P, of course):
124 : : *
125 : : * P N
126 : : * N c --> a P
127 : : * a b b c
128 : : *
129 : : */
130 : 0 : static void rotate(struct rbnode **stack, int stacksz)
131 : : {
132 : 0 : CHECK(stacksz >= 2);
133 : :
134 : 0 : struct rbnode *parent = stack[stacksz - 2];
135 : 0 : struct rbnode *child = stack[stacksz - 1];
136 : 0 : uint8_t side = get_side(parent, child);
137 : 0 : struct rbnode *a = get_child(child, side);
138 : 0 : struct rbnode *b = get_child(child, (side == 0U) ? 1U : 0U);
139 : :
140 [ # # ]: 0 : if (stacksz >= 3) {
141 : 0 : struct rbnode *grandparent = stack[stacksz - 3];
142 : :
143 : 0 : set_child(grandparent, get_side(grandparent, parent), child);
144 : : }
145 : :
146 : 0 : set_child(child, side, a);
147 : 0 : set_child(child, (side == 0U) ? 1U : 0U, parent);
148 : 0 : set_child(parent, side, b);
149 : 0 : stack[stacksz - 2] = child;
150 : 0 : stack[stacksz - 1] = parent;
151 : 0 : }
152 : :
153 : : /* The node at the top of the provided stack is red, and its parent is
154 : : * too. Iteratively fix the tree so it becomes a valid red black tree
155 : : * again
156 : : */
157 : 0 : static void fix_extra_red(struct rbnode **stack, int stacksz)
158 : : {
159 [ # # ]: 0 : while (stacksz > 1) {
160 : 0 : struct rbnode *node = stack[stacksz - 1];
161 : 0 : struct rbnode *parent = stack[stacksz - 2];
162 : :
163 : : /* Correct child colors are a precondition of the loop */
164 : : CHECK((get_child(node, 0U) == NULL) ||
165 : 0 : is_black(get_child(node, 0U)));
166 : : CHECK((get_child(node, 1U) == NULL) ||
167 : 0 : is_black(get_child(node, 1U)));
168 : :
169 [ # # ]: 0 : if (is_black(parent)) {
170 : : return;
171 : : }
172 : :
173 : : /* We are guaranteed to have a grandparent if our
174 : : * parent is red, as red nodes cannot be the root
175 : : */
176 : 0 : CHECK(stacksz >= 2);
177 : :
178 : 0 : struct rbnode *grandparent = stack[stacksz - 3];
179 : 0 : uint8_t side = get_side(grandparent, parent);
180 : 0 : struct rbnode *aunt = get_child(grandparent,
181 : : (side == 0U) ? 1U : 0U);
182 : :
183 [ # # # # ]: 0 : if ((aunt != NULL) && is_red(aunt)) {
184 : 0 : set_color(grandparent, RED);
185 : 0 : set_color(parent, BLACK);
186 : 0 : set_color(aunt, BLACK);
187 : :
188 : : /* We colored the grandparent red, which might
189 : : * have a red parent, so continue iterating
190 : : * from there.
191 : : */
192 : 0 : stacksz -= 2;
193 : 0 : continue;
194 : : }
195 : :
196 : : /* We can rotate locally to fix the whole tree. First
197 : : * make sure that node is on the same side of parent
198 : : * as parent is of grandparent.
199 : : */
200 : 0 : uint8_t parent_side = get_side(parent, node);
201 : :
202 [ # # ]: 0 : if (parent_side != side) {
203 : 0 : rotate(stack, stacksz);
204 : : }
205 : :
206 : : /* Rotate the grandparent with parent, swapping colors */
207 : 0 : rotate(stack, stacksz - 1);
208 : 0 : set_color(stack[stacksz - 3], BLACK);
209 : 0 : set_color(stack[stacksz - 2], RED);
210 : 0 : return;
211 : : }
212 : :
213 : : /* If we exit the loop, it's because our node is now the root,
214 : : * which must be black.
215 : : */
216 : 0 : set_color(stack[0], BLACK);
217 : : }
218 : :
219 : 0 : void rb_insert(struct rbtree *tree, struct rbnode *node)
220 : 0 : {
221 : 0 : set_child(node, 0U, NULL);
222 : 0 : set_child(node, 1U, NULL);
223 : :
224 [ # # ]: 0 : if (tree->root == NULL) {
225 : 0 : tree->root = node;
226 : 0 : tree->max_depth = 1;
227 : 0 : set_color(node, BLACK);
228 : 0 : return;
229 : : }
230 : :
231 : : #ifdef CONFIG_MISRA_SANE
232 : : struct rbnode **stack = &tree->iter_stack[0];
233 : : #else
234 : 0 : struct rbnode *stack[tree->max_depth + 1];
235 : : #endif
236 : :
237 : 0 : int stacksz = find_and_stack(tree, node, stack);
238 : :
239 : 0 : struct rbnode *parent = stack[stacksz - 1];
240 : :
241 : 0 : uint8_t side = tree->lessthan_fn(node, parent) ? 0U : 1U;
242 : :
243 : 0 : set_child(parent, side, node);
244 : 0 : set_color(node, RED);
245 : :
246 : 0 : stack[stacksz] = node;
247 : 0 : ++stacksz;
248 : 0 : fix_extra_red(stack, stacksz);
249 : :
250 [ # # ]: 0 : if (stacksz > tree->max_depth) {
251 : 0 : tree->max_depth = stacksz;
252 : : }
253 : :
254 : : /* We may have rotated up into the root! */
255 : 0 : tree->root = stack[0];
256 : 0 : CHECK(is_black(tree->root));
257 : : }
258 : :
259 : : /* Called for a node N (at the top of the stack) which after a
260 : : * deletion operation is "missing a black" in its subtree. By
261 : : * construction N must be black (because if it was red it would be
262 : : * trivially fixed by recoloring and we wouldn't be here). Fixes up
263 : : * the tree to preserve red/black rules. The "null_node" pointer is
264 : : * for situations where we are removing a childless black node. The
265 : : * tree munging needs a real node for simplicity, so we use it and
266 : : * then clean it up (replace it with a simple NULL child in the
267 : : * parent) when finished.
268 : : */
269 : 0 : static void fix_missing_black(struct rbnode **stack, int stacksz,
270 : : struct rbnode *null_node)
271 : : {
272 : : /* Loop upward until we reach the root */
273 [ # # ]: 0 : while (stacksz > 1) {
274 : 0 : struct rbnode *c0, *c1, *inner, *outer;
275 : 0 : struct rbnode *n = stack[stacksz - 1];
276 : 0 : struct rbnode *parent = stack[stacksz - 2];
277 : 0 : uint8_t n_side = get_side(parent, n);
278 : 0 : struct rbnode *sib = get_child(parent,
279 : : (n_side == 0U) ? 1U : 0U);
280 : :
281 : 0 : CHECK(is_black(n));
282 : :
283 : : /* Guarantee the sibling is black, rotating N down a
284 : : * level if needed (after rotate() our parent is the
285 : : * child of our previous-sibling, so N is lower in the
286 : : * tree)
287 : : */
288 [ # # ]: 0 : if (!is_black(sib)) {
289 : 0 : stack[stacksz - 1] = sib;
290 : 0 : rotate(stack, stacksz);
291 : 0 : set_color(parent, RED);
292 : 0 : set_color(sib, BLACK);
293 : 0 : stack[stacksz] = n;
294 : 0 : ++stacksz;
295 : :
296 : 0 : parent = stack[stacksz - 2];
297 : 0 : sib = get_child(parent, (n_side == 0U) ? 1U : 0U);
298 : : }
299 : :
300 : 0 : CHECK(sib);
301 : :
302 : : /* Cases where the sibling has only black children
303 : : * have simple resolutions
304 : : */
305 : 0 : c0 = get_child(sib, 0U);
306 : 0 : c1 = get_child(sib, 1U);
307 [ # # # # : 0 : if (((c0 == NULL) || is_black(c0)) && ((c1 == NULL) ||
# # ]
308 [ # # ]: 0 : is_black(c1))) {
309 [ # # ]: 0 : if (n == null_node) {
310 : 0 : set_child(parent, n_side, NULL);
311 : : }
312 : :
313 : 0 : set_color(sib, RED);
314 [ # # ]: 0 : if (is_black(parent)) {
315 : : /* Balance the sibling's subtree by
316 : : * coloring it red, then our parent
317 : : * has a missing black so iterate
318 : : * upward
319 : : */
320 : 0 : stacksz--;
321 : 0 : continue;
322 : : } else {
323 : : /* Recoloring makes the whole tree OK */
324 : 0 : set_color(parent, BLACK);
325 : 0 : return;
326 : : }
327 : : }
328 : :
329 : 0 : CHECK((c0 && is_red(c0)) || (c1 && is_red(c1)));
330 : :
331 : : /* We know sibling has at least one red child. Fix it
332 : : * so that the far/outer position (i.e. on the
333 : : * opposite side from N) is definitely red.
334 : : */
335 : 0 : outer = get_child(sib, (n_side == 0U) ? 1U : 0U);
336 [ # # # # ]: 0 : if (!((outer != NULL) && is_red(outer))) {
337 : 0 : inner = get_child(sib, n_side);
338 : :
339 : 0 : stack[stacksz - 1] = sib;
340 : 0 : stack[stacksz] = inner;
341 : 0 : ++stacksz;
342 : 0 : rotate(stack, stacksz);
343 : 0 : set_color(sib, RED);
344 : 0 : set_color(inner, BLACK);
345 : :
346 : : /* Restore stack state to have N on the top
347 : : * and make sib reflect the new sibling
348 : : */
349 : 0 : sib = stack[stacksz - 2];
350 : 0 : outer = get_child(sib, (n_side == 0U) ? 1U : 0U);
351 : 0 : stack[stacksz - 2] = n;
352 : 0 : stacksz--;
353 : : }
354 : :
355 : : /* Finally, the sibling must have a red child in the
356 : : * far/outer slot. We can rotate sib with our parent
357 : : * and recolor to produce a valid tree.
358 : : */
359 : 0 : CHECK(is_red(outer));
360 : 0 : set_color(sib, get_color(parent));
361 : 0 : set_color(parent, BLACK);
362 : 0 : set_color(outer, BLACK);
363 : 0 : stack[stacksz - 1] = sib;
364 : 0 : rotate(stack, stacksz);
365 [ # # ]: 0 : if (n == null_node) {
366 : 0 : set_child(parent, n_side, NULL);
367 : : }
368 : : return;
369 : : }
370 : : }
371 : :
372 : 0 : void rb_remove(struct rbtree *tree, struct rbnode *node)
373 : 0 : {
374 : 0 : struct rbnode *tmp;
375 : : #ifdef CONFIG_MISRA_SANE
376 : : struct rbnode **stack = &tree->iter_stack[0];
377 : : #else
378 : 0 : struct rbnode *stack[tree->max_depth + 1];
379 : : #endif
380 : :
381 : 0 : int stacksz = find_and_stack(tree, node, stack);
382 : :
383 [ # # ]: 0 : if (node != stack[stacksz - 1]) {
384 : 0 : return;
385 : : }
386 : :
387 : : /* We can only remove a node with zero or one child, if we
388 : : * have two then pick the "biggest" child of side 0 (smallest
389 : : * of 1 would work too) and swap our spot in the tree with
390 : : * that one
391 : : */
392 [ # # # # ]: 0 : if ((get_child(node, 0U) != NULL) && (get_child(node, 1U) != NULL)) {
393 : 0 : int stacksz0 = stacksz;
394 : 0 : struct rbnode *hiparent, *loparent;
395 : 0 : struct rbnode *node2 = get_child(node, 0U);
396 : :
397 [ # # ]: 0 : hiparent = (stacksz > 1) ? stack[stacksz - 2] : NULL;
398 : 0 : stack[stacksz] = node2;
399 : 0 : ++stacksz;
400 [ # # ]: 0 : while (get_child(node2, 1U) != NULL) {
401 : 0 : node2 = get_child(node2, 1U);
402 : 0 : stack[stacksz] = node2;
403 : 0 : ++stacksz;
404 : : }
405 : :
406 : 0 : loparent = stack[stacksz - 2];
407 : :
408 : : /* Now swap the position of node/node2 in the tree.
409 : : * Design note: this is a spot where being an
410 : : * intrusive data structure hurts us fairly badly.
411 : : * The trees you see in textbooks do this by swapping
412 : : * the "data" pointers between the two nodes, but we
413 : : * have a few special cases to check. In principle
414 : : * this works by swapping the child pointers between
415 : : * the nodes and retargeting the nodes pointing to
416 : : * them from their parents, but: (1) the upper node
417 : : * may be the root of the tree and not have a parent,
418 : : * and (2) the lower node may be a direct child of the
419 : : * upper node. Remember to swap the color bits of the
420 : : * two nodes also. And of course we don't have parent
421 : : * pointers, so the stack tracking this structure
422 : : * needs to be swapped too!
423 : : */
424 [ # # ]: 0 : if (hiparent != NULL) {
425 : 0 : set_child(hiparent, get_side(hiparent, node), node2);
426 : : } else {
427 : 0 : tree->root = node2;
428 : : }
429 : :
430 [ # # ]: 0 : if (loparent == node) {
431 : 0 : set_child(node, 0U, get_child(node2, 0U));
432 : 0 : set_child(node2, 0U, node);
433 : : } else {
434 : 0 : set_child(loparent, get_side(loparent, node2), node);
435 : 0 : tmp = get_child(node, 0U);
436 : 0 : set_child(node, 0U, get_child(node2, 0U));
437 : 0 : set_child(node2, 0U, tmp);
438 : : }
439 : :
440 : 0 : set_child(node2, 1U, get_child(node, 1U));
441 : 0 : set_child(node, 1U, NULL);
442 : :
443 : 0 : tmp = stack[stacksz0 - 1];
444 : 0 : stack[stacksz0 - 1] = stack[stacksz - 1];
445 : 0 : stack[stacksz - 1] = tmp;
446 : :
447 : 0 : enum rb_color ctmp = get_color(node);
448 : :
449 : 0 : set_color(node, get_color(node2));
450 : 0 : set_color(node2, ctmp);
451 : : }
452 : :
453 : : CHECK((get_child(node, 0U) == NULL) ||
454 : 0 : (get_child(node, 1U) == NULL));
455 : :
456 : 0 : struct rbnode *child = get_child(node, 0U);
457 : :
458 [ # # ]: 0 : if (child == NULL) {
459 : 0 : child = get_child(node, 1U);
460 : : }
461 : :
462 : : /* Removing the root */
463 [ # # ]: 0 : if (stacksz < 2) {
464 : 0 : tree->root = child;
465 [ # # ]: 0 : if (child != NULL) {
466 : 0 : set_color(child, BLACK);
467 : : } else {
468 : 0 : tree->max_depth = 0;
469 : : }
470 : 0 : return;
471 : : }
472 : :
473 : 0 : struct rbnode *parent = stack[stacksz - 2];
474 : :
475 : : /* Special case: if the node to be removed is childless, then
476 : : * we leave it in place while we do the missing black
477 : : * rotations, which will replace it with a proper NULL when
478 : : * they isolate it.
479 : : */
480 [ # # ]: 0 : if (child == NULL) {
481 [ # # ]: 0 : if (is_black(node)) {
482 : 0 : fix_missing_black(stack, stacksz, node);
483 : : } else {
484 : : /* Red childless nodes can just be dropped */
485 : 0 : set_child(parent, get_side(parent, node), NULL);
486 : : }
487 : : } else {
488 : 0 : set_child(parent, get_side(parent, node), child);
489 : :
490 : : /* Check colors, if one was red (at least one must have been
491 : : * black in a valid tree), then we're done.
492 : : */
493 [ # # # # ]: 0 : __ASSERT(is_black(node) || is_black(child), "both nodes red?!");
494 [ # # # # ]: 0 : if (is_red(node) || is_red(child)) {
495 : 0 : set_color(child, BLACK);
496 : : }
497 : : }
498 : :
499 : : /* We may have rotated up into the root! */
500 : 0 : tree->root = stack[0];
501 : : }
502 : :
503 : : #ifndef CONFIG_MISRA_SANE
504 : 0 : void z_rb_walk(struct rbnode *node, rb_visit_t visit_fn, void *cookie)
505 : : {
506 [ # # ]: 0 : if (node != NULL) {
507 : 0 : z_rb_walk(get_child(node, 0U), visit_fn, cookie);
508 : 0 : visit_fn(node, cookie);
509 : 0 : z_rb_walk(get_child(node, 1U), visit_fn, cookie);
510 : : }
511 : 0 : }
512 : : #endif
513 : :
514 : 0 : struct rbnode *z_rb_child(struct rbnode *node, uint8_t side)
515 : : {
516 : 0 : return get_child(node, side);
517 : : }
518 : :
519 : 0 : int z_rb_is_black(struct rbnode *node)
520 : : {
521 : 0 : return is_black(node);
522 : : }
523 : :
524 : 0 : bool rb_contains(struct rbtree *tree, struct rbnode *node)
525 : : {
526 : 0 : struct rbnode *n = tree->root;
527 : :
528 [ # # ]: 0 : while ((n != NULL) && (n != node)) {
529 : 0 : n = get_child(n, tree->lessthan_fn(n, node));
530 : : }
531 : :
532 : 0 : return n == node;
533 : : }
534 : :
535 : : /* Pushes the node and its chain of left-side children onto the stack
536 : : * in the foreach struct, returning the last node, which is the next
537 : : * node to iterate. By construction node will always be a right child
538 : : * or the root, so is_left must be false.
539 : : */
540 : 0 : static inline struct rbnode *stack_left_limb(struct rbnode *n,
541 : : struct _rb_foreach *f)
542 : : {
543 : 0 : f->top++;
544 : 0 : f->stack[f->top] = n;
545 : 0 : f->is_left[f->top] = 0U;
546 : :
547 [ # # ]: 0 : for (n = get_child(n, 0U); n != NULL; n = get_child(n, 0U)) {
548 : 0 : f->top++;
549 : 0 : f->stack[f->top] = n;
550 : 0 : f->is_left[f->top] = 1;
551 : : }
552 : :
553 : 0 : return f->stack[f->top];
554 : : }
555 : :
556 : : /* The foreach tracking works via a dynamic stack allocated via
557 : : * alloca(). The current node is found in stack[top] (and its parent
558 : : * is thus stack[top-1]). The side of each stacked node from its
559 : : * parent is stored in is_left[] (i.e. if is_left[top] is true, then
560 : : * node/stack[top] is the left child of stack[top-1]). The special
561 : : * case of top == -1 indicates that the stack is uninitialized and we
562 : : * need to push an initial stack starting at the root.
563 : : */
564 : 0 : struct rbnode *z_rb_foreach_next(struct rbtree *tree, struct _rb_foreach *f)
565 : : {
566 : 0 : struct rbnode *n;
567 : :
568 [ # # ]: 0 : if (tree->root == NULL) {
569 : : return NULL;
570 : : }
571 : :
572 : : /* Initialization condition, pick the leftmost child of the
573 : : * root as our first node, initializing the stack on the way.
574 : : */
575 [ # # ]: 0 : if (f->top == -1) {
576 : 0 : return stack_left_limb(tree->root, f);
577 : : }
578 : :
579 : : /* The next child from a given node is the leftmost child of
580 : : * it's right subtree if it has a right child
581 : : */
582 : 0 : n = get_child(f->stack[f->top], 1U);
583 [ # # ]: 0 : if (n != NULL) {
584 : 0 : return stack_left_limb(n, f);
585 : : }
586 : :
587 : : /* Otherwise if the node is a left child of its parent, the
588 : : * next node is the parent (note that the root is stacked
589 : : * above with is_left set to 0, so this condition still works
590 : : * even if node has no parent).
591 : : */
592 [ # # ]: 0 : if (f->is_left[f->top] != 0U) {
593 : 0 : return f->stack[--f->top];
594 : : }
595 : :
596 : : /* If we had no left tree and are a right child then our
597 : : * parent was already walked, so walk up the stack looking for
598 : : * a left child (whose parent is unwalked, and thus next).
599 : : */
600 [ # # # # ]: 0 : while ((f->top > 0) && (f->is_left[f->top] == 0U)) {
601 : 0 : f->top--;
602 : : }
603 : :
604 : 0 : f->top--;
605 [ # # ]: 0 : return (f->top >= 0) ? f->stack[f->top] : NULL;
606 : : }
|
