Mercurial > hg > Members > nobuyasu > CbC

annotate DPP/state_db.c @ 33:3946f8d26710 draft default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add benchmarck/binary-trees
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Tue, 09 Apr 2013 16:41:30 +0900
parents a89b61162c29
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 #include <stdlib.h>
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
2
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
3 #include "state_db.h"
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
4 #include "memory.h"
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
5
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
6 StateDB
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
7 create_stateDB()
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
8 {
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
9 StateDB s = (StateDB)malloc(sizeof(StateNode));
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
10 if (!s) die_exit("Cann't alloc state db node.");
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
11 return s;
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
12 }
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
13
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 static MemoryPtr mem_db;
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
15
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
16 static int state_count0;
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
17
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
18 void
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
19 reset_state_count()
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
20 {
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
21 state_count0 = 0;
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
22 }
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
23
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
24 int
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
25 state_count()
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
26 {
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
27 return state_count0;
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
28 }
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
29
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
30
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
31 /*
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
32
33
3946f8d26710 add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
33 lookup_StateDB(struct state *s, StateDB *parent, StatePtr *out)
0
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
34
33
3946f8d26710 add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
35 s->memory points the real memory
3946f8d26710 add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
36 if s is new, it is copied in the database (parent).
3946f8d26710 add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
37 if s is in the database, existing state is returned.
0
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
38
33
3946f8d26710 add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
39 if return value is 0, it returns new state.
3946f8d26710 add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
40 if out is null, no copy_state is created. (lookup mode)
0
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
41
33
3946f8d26710 add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
42 Founded state or newly created state is returned in out.
0
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
43
33
3946f8d26710 add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
44 */
0
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
45
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
46 int
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
47 lookup_StateDB(StateDB s, StateDB *parent, StateDB *out)
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
48 {
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
49 StateDB db;
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
50 int r;
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
51
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
52 while(1) {
33
3946f8d26710 add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
53 db = *parent;
3946f8d26710 add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
54 if (!db) {
3946f8d26710 add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
55 /* not found */
3946f8d26710 add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
56 if (out) {
3946f8d26710 add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
57 db = create_stateDB();
3946f8d26710 add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
58 db->left = db->right = 0;
3946f8d26710 add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
59 db->memory = copy_memory(s->memory,&mem_db);
3946f8d26710 add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
60 db->hash = s->hash;
3946f8d26710 add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
61 state_count0 ++;
3946f8d26710 add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
62 *parent = db;
3946f8d26710 add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
63 *out = db;
3946f8d26710 add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
64 }
3946f8d26710 add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
65 return 0;
3946f8d26710 add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
66 }
3946f8d26710 add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
67 if (s->hash == db->hash) {
3946f8d26710 add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
68 r = cmp_memory(s->memory,db->memory);
3946f8d26710 add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
69 } else
3946f8d26710 add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
70 r = (s->hash > db->hash)? 1 : -1;
3946f8d26710 add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
71 if(!r) {
3946f8d26710 add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
72 /* bingo */
3946f8d26710 add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
73 if (out) *out = db;
3946f8d26710 add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
74 return 1;
3946f8d26710 add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
75 } else if (r>0) {
3946f8d26710 add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
76 parent = &db->left;
3946f8d26710 add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
77 } else if (r<0) {
3946f8d26710 add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
78 parent = &db->right;
3946f8d26710 add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
79 }
0
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
80 }
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
81 }
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
82
a89b61162c29 add DPP
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
83 /* end */