将递归函数非递归化的一般方法(cont)

1 #ifndef _LIBSTACK_H
2 #define _LIBSTACK_H
3
4 #ifdef __cplusplus
5 extern "C" {
6 #endif
7
8 typedef void * uintptr_t; /* generic pointer to any struct */
9
10 uintptr_t *stack_init(size_t size);
11 void stack_fini();
12 int stack_isFull();
13 int stack_isEmpty();
14 void push(uintptr_t e);
15 void pop(uintptr_t *e);
16
17 #ifdef __cplusplus
18 }
19 #endif
20
21 #endif /* _LIBSTACK_H */

1 #include
2 #include
3 #include "libstack.h"
4
5 /**
6 * Basic Stack OPs are supported, including:
7 *
8 * 1. Construct/Destruct a stack
9 * 2. Tell stack is full or empty
10 * 3. push() and pop()
11 *
12 * &＃61;&＃61; DESIGN NOTES &＃61;&＃61;
13 *
14 * There are 3 static variables reserved,
15 *
16 * ss: stack segment
17 * sp: stack pointer
18 * sz: stack size
19 *
20 * And the stack looks like:
21 *
22 * | RED | ss[-1] ; SHOULD NEVER BE ACCESSED
23 * low-addr &＃43;-----&＃43; <------------TopOfStack-----------
24 * ^ | | ss[0]
25 * | | | ss[1]
26 * | | ... |
27 * | | |
28 * | | | ss[sz-1]
29 * | &＃43;-----&＃43; <------------BottomOfStack--------
30 * high-addr | RED | ss[sz] ; SHOULD NEVER BE ACCESSED
31 *
32 * (1) If (sp - ss) &＃61;&＃61; 0, stack is full
33 * (2) If (sp - ss) &＃61;&＃61; sz, stack is empty
34 * (3) Push(E): { sp -&＃61; 1; *sp &＃61; E; }
35 * (4) Pop(&E): { *E &＃61; *sp; sp &＃43;&＃61; 1; }
36 */
37
38 static uintptr_t *ss &＃61; NULL; /* stack segment */
39 static uintptr_t *sp &＃61; NULL; /* stack pointer */
40 static size_t sz &＃61; 0; /* stack size */
41
42 int stack_isFull() { return (sp &＃61;&＃61; ss); }
43 int stack_isEmpty() { return (sp &＃61;&＃61; ss &＃43; sz); }
44
45 uintptr_t *
46 stack_init(size_t size)
47 {
48 ss &＃61; (uintptr_t *)malloc(sizeof (uintptr_t) * size);
49 if (ss &＃61;&＃61; NULL) {
50 fprintf(stderr, "failed to malloc\n");
51 return NULL;
52 }
53
54 sz &＃61; size;
55 sp &＃61; ss &＃43; size;
56 return ss;
57 }
58
59 void
60 stack_fini()
61 {
62 free(ss);
63 }
64
65 void
66 push(uintptr_t e)
67 {
68 sp -&＃61; 1;
69 *sp &＃61; e;
70 }
71
72 void
73 pop(uintptr_t *e)
74 {
75 *e &＃61; *sp;
76 sp &＃43;&＃61; 1;
77 }

1 /**
2 * A simple test against stack OPs, including:
3 * o stack_init(), stack_fini()
4 * o stack_isFull(), stack_isEmpty()
5 * o push(), pop()
6 */
7
8 #include
9 #include "libstack.h"
10
11 static void
12 dump_stack(uintptr_t *ss, size_t size)
13 {
14 (void) printf("%p: ", ss);
15 for (int i &＃61; 0; i ) {
16 if (ss[i] !&＃61; NULL)
17 (void) printf("%-10p ", *(ss&＃43;i));
18 else
19 (void) printf("0x%-8x ", 0x0);
20 }
21 printf("\n");
22 }
23
24 int
25 main(int argc, char *argv[])
26 {
27 size_t size &＃61; 4;
28
29 uintptr_t *ss &＃61; stack_init(size);
30 dump_stack(ss, size);
31
32 for (int i &＃61; 0; !stack_isFull(); i&＃43;&＃43;) {
33 push((uintptr_t)(ss&＃43;i));
34 dump_stack(ss, size);
35 }
36
37 (void) printf("\n");
38
39 uintptr_t e &＃61; NULL;
40 for (; !stack_isEmpty();) {
41 pop(&e);
42 (void) printf(" (pop) got %-10p\n", e);
43 }
44
45 stack_fini();
46
47 return 0;
48 }

1 CC &＃61; gcc
2 CFLAGS &＃61; -g -Wall -std&＃61;gnu99 -m32
3 INCS &＃61;
4
5 TARGET &＃61; foo
6
7 all: ${TARGET}
8
9 foo: foo.o libstack.o
10 ${CC} ${CFLAGS} -o $&＃64; $^
11
12 foo.o: foo.c
13 ${CC} ${CFLAGS} -c $< ${INCS}
14
15 libstack.o: libstack.c libstack.h
16 ${CC} ${CFLAGS} -c $<
17
18 clean:
19 rm -f *.o
20 clobber: clean
21 rm -f ${TARGET}

$ make
gcc -g -Wall -std&＃61;gnu99 -m32 -c foo.c
gcc -g -Wall -std&＃61;gnu99 -m32 -c libstack.c
gcc -g -Wall -std&＃61;gnu99 -m32 -o foo foo.o libstack.o$ ./foo
0x8ecc008: 0x0 0x0 0x0 0x0
0x8ecc008: 0x0 0x0 0x0 0x8ecc008
0x8ecc008: 0x0 0x0 0x8ecc00c 0x8ecc008
0x8ecc008: 0x0 0x8ecc010 0x8ecc00c 0x8ecc008
0x8ecc008: 0x8ecc014 0x8ecc010 0x8ecc00c 0x8ecc008(pop) got 0x8ecc014(pop) got 0x8ecc010(pop) got 0x8ecc00c(pop) got 0x8ecc008
$

1 void
2 bst_walk(bst_node_t *root)
3 {
4 if (root &＃61;&＃61; NULL)
5 return;
6
7 (void) stack_init(STACK_SIZE);
8
9 while (root !&＃61; NULL || !stack_isEmpty()) {
10 if (root !&＃61; NULL) {
11 push((uintptr_t)root);
12 root &＃61; root->left;
13 continue;
14 }
15
16 pop((uintptr_t *)(&root));
17 printf("%d\n", root->key);
18
19 root &＃61; root->right;
20 }
21
22 stack_fini();
23 }