/[zanavi_public1]/navit/navit/map/mg/tree.c
ZANavi

Contents of /navit/navit/map/mg/tree.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 2 - (show annotations) (download)
Fri Oct 28 21:19:04 2011 UTC (9 years, 5 months ago) by zoff99
File MIME type: text/plain
File size: 8457 byte(s)
import files
1 /**
2 * Navit, a modular navigation system.
3 * Copyright (C) 2005-2008 Navit Team
4 *
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License
7 * version 2 as published by the Free Software Foundation.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the
16 * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
17 * Boston, MA 02110-1301, USA.
18 */
19
20 #include <stdio.h>
21 #include <string.h>
22 #include "debug.h"
23 #include "mg.h"
24
25 struct tree_hdr {
26 /*unsigned int addr;
27 unsigned int size;
28 unsigned int low;*/
29 unsigned char p[12];
30 };
31 static inline unsigned int tree_hdr_get_addr(struct tree_hdr * tree) { unsigned char *p = tree->p; return get_u32(&p); }
32 static inline unsigned int tree_hdr_get_size(struct tree_hdr * tree) { unsigned char *p = tree->p+4; return get_u32(&p); }
33 static inline unsigned int tree_hdr_get_low(struct tree_hdr * tree) { unsigned char *p = tree->p+8; return get_u32(&p); }
34
35 struct tree_hdr_h {
36 /* unsigned int addr;
37 unsigned int size;*/
38 unsigned char p[8];
39 };
40 static inline unsigned int tree_hdr_h_get_addr(struct tree_hdr_h * tree) { unsigned char *p = tree->p; return get_u32(&p); }
41 static inline unsigned int tree_hdr_h_get_size(struct tree_hdr_h * tree) { unsigned char *p = tree->p+4; return get_u32(&p); }
42
43 struct tree_leaf_h {
44 /* unsigned int lower;
45 unsigned int higher;
46 unsigned int match;
47 unsigned int value;*/
48 unsigned char p[16];
49 };
50 static inline unsigned int tree_leaf_h_get_lower(struct tree_leaf_h * tree) { unsigned char *p = tree->p; return get_u32(&p); }
51 static inline unsigned int tree_leaf_h_get_higher(struct tree_leaf_h * tree) { unsigned char *p = tree->p+4; return get_u32(&p); }
52 static inline unsigned int tree_leaf_h_get_match(struct tree_leaf_h * tree) { unsigned char *p = tree->p+8; return get_u32(&p); }
53 static inline unsigned int tree_leaf_h_get_value(struct tree_leaf_h * tree) { unsigned char *p = tree->p+12; return get_u32(&p); }
54
55
56 struct tree_hdr_v {
57 /*unsigned int count;
58 unsigned int next;
59 unsigned int unknown;*/
60 unsigned char p[12];
61 };
62 static inline unsigned int tree_hdr_v_get_count(struct tree_hdr_v * tree) { unsigned char *p = tree->p; return get_u32_unal(&p); }
63 static inline unsigned int tree_hdr_v_get_next(struct tree_hdr_v * tree) { unsigned char *p = tree->p+4; return get_u32_unal(&p); }
64 static inline unsigned int tree_hdr_v_get_unknown(struct tree_hdr_v * tree) { unsigned char *p = tree->p+8; return get_u32_unal(&p); }
65
66 struct tree_leaf_v {
67 unsigned char key;
68 /*int value;*/
69 unsigned char p[4];
70 } __attribute__((packed));
71 static inline int tree_leaf_v_get_value(struct tree_leaf_v * tree) { unsigned char *p = tree->p; return get_u32_unal(&p); }
72
73 static int
74 tree_search_h(struct file *file, unsigned int search)
75 {
76 unsigned char *p=file->begin,*end;
77 int last,i=0,value,lower;
78 struct tree_hdr_h *thdr;
79 struct tree_leaf_h *tleaf;
80
81 dbg(1,"enter\n");
82 while (i++ < 1000) {
83 thdr=(struct tree_hdr_h *)p;
84 p+=sizeof(*thdr);
85 end=p+tree_hdr_h_get_size(thdr);
86 dbg(1,"@0x%x\n", p-file->begin);
87 last=0;
88 while (p < end) {
89 tleaf=(struct tree_leaf_h *)p;
90 p+=sizeof(*tleaf);
91 dbg(1,"low:0x%x high:0x%x match:0x%x val:0x%x search:0x%x\n", tree_leaf_h_get_lower(tleaf), tree_leaf_h_get_higher(tleaf), tree_leaf_h_get_match(tleaf), tree_leaf_h_get_value(tleaf), search);
92 value=tree_leaf_h_get_value(tleaf);
93 if (value == search)
94 return tree_leaf_h_get_match(tleaf);
95 if (value > search) {
96 dbg(1,"lower\n");
97 lower=tree_leaf_h_get_lower(tleaf);
98 if (lower)
99 last=lower;
100 break;
101 }
102 last=tree_leaf_h_get_higher(tleaf);
103 }
104 if (! last || last == -1)
105 return 0;
106 p=file->begin+last;
107 }
108 return 0;
109 }
110
111 static int
112 tree_search_v(struct file *file, int offset, int search)
113 {
114 unsigned char *p=file->begin+offset;
115 int i=0,count,next;
116 struct tree_hdr_v *thdr;
117 struct tree_leaf_v *tleaf;
118 while (i++ < 1000) {
119 thdr=(struct tree_hdr_v *)p;
120 p+=sizeof(*thdr);
121 count=tree_hdr_v_get_count(thdr);
122 dbg(1,"offset=0x%x count=0x%x\n", p-file->begin, count);
123 while (count--) {
124 tleaf=(struct tree_leaf_v *)p;
125 p+=sizeof(*tleaf);
126 dbg(1,"0x%x 0x%x\n", tleaf->key, search);
127 if (tleaf->key == search)
128 return tree_leaf_v_get_value(tleaf);
129 }
130 next=tree_hdr_v_get_next(thdr);
131 if (! next)
132 break;
133 p=file->begin+next;
134 }
135 return 0;
136 }
137
138 int
139 tree_search_hv(char *dirname, char *filename, unsigned int search_h, unsigned int search_v, int *result)
140 {
141 struct file *f_idx_h, *f_idx_v;
142 char buffer[4096];
143 int h,v;
144
145 dbg(1,"enter(%s, %s, 0x%x, 0x%x, %p)\n",dirname, filename, search_h, search_v, result);
146 sprintf(buffer, "%s/%s.h1", dirname, filename);
147 f_idx_h=file_create_caseinsensitive(buffer, 0);
148 if ((!f_idx_h) || (!file_mmap(f_idx_h)))
149 return 0;
150 sprintf(buffer, "%s/%s.v1", dirname, filename);
151 f_idx_v=file_create_caseinsensitive(buffer, 0);
152 dbg(1,"%p %p\n", f_idx_h, f_idx_v);
153 if ((!f_idx_v) || (!file_mmap(f_idx_v))) {
154 file_destroy(f_idx_h);
155 return 0;
156 }
157 if ((h=tree_search_h(f_idx_h, search_h))) {
158 dbg(1,"h=0x%x\n", h);
159 if ((v=tree_search_v(f_idx_v, h, search_v))) {
160 dbg(1,"v=0x%x\n", v);
161 *result=v;
162 file_destroy(f_idx_v);
163 file_destroy(f_idx_h);
164 dbg(1,"return 1\n");
165 return 1;
166 }
167 }
168 file_destroy(f_idx_v);
169 file_destroy(f_idx_h);
170 dbg(1,"return 0\n");
171 return 0;
172 }
173
174 static struct tree_search_node *
175 tree_search_enter(struct tree_search *ts, int offset)
176 {
177 struct tree_search_node *tsn=&ts->nodes[++ts->curr_node];
178 unsigned char *p;
179 p=ts->f->begin+offset;
180 tsn->hdr=(struct tree_hdr *)p;
181 tsn->p=p+sizeof(struct tree_hdr);
182 tsn->last=tsn->p;
183 tsn->end=p+tree_hdr_get_size(tsn->hdr);
184 tsn->low=tree_hdr_get_low(tsn->hdr);
185 tsn->high=tree_hdr_get_low(tsn->hdr);
186 dbg(1,"pos 0x%x addr 0x%x size 0x%x low 0x%x end 0x%x\n", p-ts->f->begin, tree_hdr_get_addr(tsn->hdr), tree_hdr_get_size(tsn->hdr), tree_hdr_get_low(tsn->hdr), tsn->end-ts->f->begin);
187 return tsn;
188 }
189
190 int tree_search_next(struct tree_search *ts, unsigned char **p, int dir)
191 {
192 struct tree_search_node *tsn=&ts->nodes[ts->curr_node];
193
194 if (! *p)
195 *p=tsn->p;
196 dbg(1,"next *p=%p dir=%d\n", *p, dir);
197 dbg(1,"low1=0x%x high1=0x%x\n", tsn->low, tsn->high);
198 if (dir <= 0) {
199 dbg(1,"down 0x%x\n", tsn->low);
200 if (tsn->low != 0xffffffff) {
201 tsn=tree_search_enter(ts, tsn->low);
202 *p=tsn->p;
203 tsn->high=get_u32(p);
204 ts->last_node=ts->curr_node;
205 dbg(1,"saving last2 %d 0x%x\n", ts->curr_node, tsn->last-ts->f->begin);
206 dbg(1,"high2=0x%x\n", tsn->high);
207 return 0;
208 }
209 return -1;
210 }
211 tsn->low=tsn->high;
212 tsn->last=*p;
213 tsn->high=get_u32_unal(p);
214 dbg(1,"saving last3 %d %p\n", ts->curr_node, tsn->last);
215 if (*p < tsn->end)
216 return (tsn->low == 0xffffffff ? 1 : 0);
217 dbg(1,"end reached high=0x%x\n",tsn->high);
218 if (tsn->low != 0xffffffff) {
219 dbg(1,"low 0x%x\n", tsn->low);
220 tsn=tree_search_enter(ts, tsn->low);
221 *p=tsn->p;
222 tsn->high=get_u32_unal(p);
223 ts->last_node=ts->curr_node;
224 dbg(1,"saving last4 %d 0x%x\n", ts->curr_node, tsn->last-ts->f->begin);
225 dbg(1,"high4=0x%x\n", tsn->high);
226 return 0;
227 }
228 return -1;
229 }
230
231 int tree_search_next_lin(struct tree_search *ts, unsigned char **p)
232 {
233 struct tree_search_node *tsn=&ts->nodes[ts->curr_node];
234 int high;
235
236 dbg(1,"pos=%d 0x%x\n", ts->curr_node, *p-ts->f->begin);
237 if (*p)
238 ts->nodes[ts->last_node].last=*p;
239 *p=tsn->last;
240 for (;;) {
241 high=get_u32_unal(p);
242 if (*p < tsn->end) {
243 ts->last_node=ts->curr_node;
244 while (high != 0xffffffff) {
245 tsn=tree_search_enter(ts, high);
246 dbg(1,"reload %d\n",ts->curr_node);
247 high=tsn->low;
248 }
249 return 1;
250 }
251 dbg(1,"eon %d 0x%x 0x%x\n", ts->curr_node, *p-ts->f->begin, tsn->end-ts->f->begin);
252 if (! ts->curr_node)
253 break;
254 ts->curr_node--;
255 tsn=&ts->nodes[ts->curr_node];
256 *p=tsn->last;
257 }
258
259 return 0;
260 }
261
262 void
263 tree_search_init(char *dirname, char *filename, struct tree_search *ts, int offset)
264 {
265 char buffer[4096];
266 sprintf(buffer, "%s/%s", dirname, filename);
267 ts->f=file_create_caseinsensitive(buffer, 0);
268 ts->curr_node=-1;
269 if (ts->f) {
270 file_mmap(ts->f);
271 tree_search_enter(ts, offset);
272 }
273 }
274
275 void
276 tree_search_free(struct tree_search *ts)
277 {
278 if (ts->f)
279 file_destroy(ts->f);
280 }

   
Visit the ZANavi Wiki