Mercurial > hg > Members > innparusu > Gears

annotate src/llrb/stack.h @ 25:390cf0523ea7

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add file
author Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
date Fri, 01 May 2015 05:35:10 +0900
parents
children 368306e1bfed
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
25
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 #include <string.h>
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
2
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
3 typedef struct {
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
4 size_t size;
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
5 int max;
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
6 int num;
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
7 void* data;
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
8 } stack, *stack_ptr;
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
9
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
10 stack_ptr stack_init(size_t size, int max) {
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
11 stack_ptr stack_ptr;
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
12
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
13 if ((stack_ptr = calloc(1, sizeof(stack))) == NULL)
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 return NULL;
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
15
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
16 if ((stack_ptr->data = calloc(max, size)) == NULL) {
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
17 free(stack_ptr);
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
18 return NULL;
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
19 }
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
20
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
21 stack_ptr->size = size;
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
22 stack_ptr->max = max;
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
23 stack_ptr->num = 0;
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
24
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
25 return stack_ptr;
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
26 }
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
27
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
28 stack_ptr stack_realloc(stack_ptr stack_ptr, int max) {
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
29 if (stack_ptr == NULL)
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
30 return NULL;
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
31
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
32 if ((stack_ptr->data = realloc(stack_ptr->data, stack_ptr->size*max)) == NULL)
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
33 return NULL;
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
34
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
35 stack_ptr->max = max;
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
36
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
37 return stack_ptr;
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
38 }
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
39
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
40 void stack_free(stack_ptr stack_ptr) {
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
41 if (stack_ptr != NULL && stack_ptr->data != NULL) {
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
42 free(stack_ptr->data);
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
43 free(stack_ptr);
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
44 }
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
45 }
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
46
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
47 int stack_push(stack_ptr stack_ptr, void* data) {
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
48 if (stack_ptr->max <= stack_ptr->num)
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
49 return -1;
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
50
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
51 memcpy((char*)stack_ptr->data+stack_ptr->num*stack_ptr->size, data, stack_ptr->size);
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
52 stack_ptr->num++;
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
53
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
54 return 0;
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
55 }
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
56
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
57 int stack_pop(stack_ptr stack_ptr, void* data) {
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
58 if (stack_ptr->num == 0)
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
59 return -1;
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
60
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
61 stack_ptr->num--;
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
62
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
63 memcpy(data, (char*)stack_ptr->data+stack_ptr->num*stack_ptr->size, stack_ptr->size);
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
64
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
65 return 0;
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
66 }
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
67
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
68 int isMax(const stack_ptr stack_ptr) {
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
69 return stack_ptr->max<=stack_ptr->num;
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
70 }
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
71
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
72 int isEmpty(const stack_ptr stack_ptr) {
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
73 return stack_ptr->num<=0;
390cf0523ea7 add file
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
74 }