/[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 - (hide annotations) (download)
Fri Oct 28 21:19:04 2011 UTC (12 years, 5 months ago) by zoff99
File MIME type: text/plain
File size: 8457 byte(s)
import files
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     }

   
Visit the ZANavi Wiki