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 |
}
|