1 |
zoff99 |
2 |
/**
|
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 |
|
|
}
|