Mercurial > hg > Gears > GearsAgda

annotate src/llrb/llrbContext.c @ 73:2667c3251a00

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
implement llrb deletion
author Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
date Tue, 10 Nov 2015 10:21:37 +0900
parents 5c4b9d116eda
children 97387904add9
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
1 #include <stdlib.h>
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
2
19
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
3 #include "llrbContext.h"
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
4
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
5 extern __code code1_stub(struct Context*);
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
6 extern __code code2_stub(struct Context*);
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
7 extern __code code3_stub(struct Context*);
22
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
8 extern __code code4(struct Context*);
4c3c0ad4a75d add benchmark method
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
9 extern __code code5(struct Context*);
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
10 extern __code find(struct Context*);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
11 extern __code not_find(struct Context*);
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
12 extern __code code6(struct Context*);
19
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
13 extern __code meta(struct Context*);
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
14 extern __code put_stub(struct Context*);
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
15 extern __code replaceNode_stub(struct Context*);
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
16 extern __code insertNode_stub(struct Context*);
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
17 extern __code rotateLeft_stub(struct Context*);
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
18 extern __code rotateRight_stub(struct Context*);
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
19 extern __code colorFlip_stub(struct Context*);
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
20 extern __code fixUp_stub(struct Context*);
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
21 extern __code changeReference_stub(struct Context*);
72
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
22 extern __code balance1_stub(struct Context*);
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
23 extern __code balance2_stub(struct Context*);
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
24 extern __code balance3_stub(struct Context*);
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
25 extern __code get_stub(struct Context*);
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
26 extern __code findMin_stub(struct Context*);
69
368306e1bfed llrb deletion(not work).
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 65
diff changeset
27 extern __code delete_stub(struct Context*);
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
28 extern __code replaceNode_d1_stub(struct Context*);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
29 extern __code replaceNode_d2_stub(struct Context*);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
30 extern __code replaceNode_d3_stub(struct Context*);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
31 extern __code replaceNode_d4_stub(struct Context*);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
32 extern __code moveRedLeft1_stub(struct Context*);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
33 extern __code moveRedLeft2_stub(struct Context*);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
34 extern __code moveRedLeft3_stub(struct Context*);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
35 extern __code moveRedRight1_stub(struct Context*);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
36 extern __code moveRedRight2_stub(struct Context*);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
37 extern __code deleteMin1_stub(struct Context*);
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
38 extern __code deleteMin2_stub(struct Context*);
19
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
39 extern __code exit_code(struct Context*);
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
40
72
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
41 __code initLLRBContext(struct Context* context, int num) {
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
42 context->heapLimit = sizeof(union Data)*ALLOCATE_SIZE;
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
43 context->code = malloc(sizeof(__code*)*ALLOCATE_SIZE);
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
44 context->data = malloc(sizeof(union Data*)*ALLOCATE_SIZE);
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
45 context->heapStart = malloc(context->heapLimit);
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
46
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
47 context->codeNum = Exit;
73
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
48
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
49 context->code[Code1] = code1_stub;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
50 context->code[Code2] = code2_stub;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
51 context->code[Code3] = code3_stub;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
52 context->code[Code4] = code4;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
53 context->code[Code5] = code5;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
54 context->code[Find] = find;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
55 context->code[Not_find] = not_find;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
56 context->code[Code6] = code6;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
57 context->code[Put] = put_stub;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
58 context->code[Replace] = replaceNode_stub;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
59 context->code[Insert] = insertNode_stub;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
60 context->code[RotateL] = rotateLeft_stub;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
61 context->code[RotateR] = rotateRight_stub;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
62 context->code[ColorFlip] = colorFlip_stub;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
63 context->code[FixUp] = fixUp_stub;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
64 context->code[ChangeRef] = changeReference_stub;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
65 context->code[Balance1] = balance1_stub;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
66 context->code[Balance2] = balance2_stub;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
67 context->code[Balance3] = balance3_stub;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
68 context->code[Get] = get_stub;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
69 context->code[Delete] = delete_stub;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
70 context->code[FindMin] = findMin_stub;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
71 context->code[Replace_d1] = replaceNode_d1_stub;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
72 context->code[Replace_d2] = replaceNode_d2_stub;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
73 context->code[Replace_d3] = replaceNode_d3_stub;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
74 context->code[Replace_d4] = replaceNode_d4_stub;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
75 context->code[MoveRedL1] = moveRedLeft1_stub;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
76 context->code[MoveRedL2] = moveRedLeft2_stub;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
77 context->code[MoveRedL3] = moveRedLeft3_stub;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
78 context->code[MoveRedR1] = moveRedRight1_stub;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
79 context->code[MoveRedR2] = moveRedRight2_stub;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
80 context->code[DeleteMin1] = deleteMin1_stub;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
81 context->code[DeleteMin2] = deleteMin2_stub;
2667c3251a00 implement llrb deletion
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 72
diff changeset
82 context->code[Exit] = exit_code;
19
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
83
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
84 context->heap = context->heapStart;
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
85
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
86 context->data[Allocate] = context->heap;
19
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
87 context->heap += sizeof(struct Allocate);
20
324c44f2076f implement insert
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
88
23
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
89 context->data[Tree] = context->heap;
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
90 context->heap += sizeof(struct Tree);
868c2918b634 Non Destructive llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
91
42
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
92 context->data[Node] = context->heap;
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
93 context->heap += sizeof(struct Node);
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
94
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
95 context->dataNum = Node;
42
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
96
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
97 struct Tree* tree = &context->data[Tree]->tree;
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
98 tree->root = 0;
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
99 tree->current = 0;
44914699ee9b refactoring llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
100 tree->prev = 0;
56
c469c5ed5b4d modify syntax
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
101
72
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
102 context->node_stack = stack_init(sizeof(union Data*), num);
5c4b9d116eda use stack for code segment
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 69
diff changeset
103 context->code_stack = stack_init(sizeof(enum Code), 100);
19
9302b1a48008 add llrb
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
104 }