Routino SVN Repository Browser

Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino

/[routino]/trunk/src/waysx.c
ViewVC logotype

Contents of /trunk/src/waysx.c

Parent Directory Parent Directory | Revision Log Revision Log

Revision 262 - (show annotations) (download) (as text)
Thu Sep 17 12:55:15 2009 UTC (15 years, 6 months ago) by amb
File MIME type: text/x-csrc
File size: 18041 byte(s) 
Added the slim mode to Ways as well.
1 /***************************************
2 $Header: /home/amb/CVS/routino/src/waysx.c,v 1.20 2009-09-17 12:55:15 amb Exp $
3
4 Extended Way data type functions.
5
6 Part of the Routino routing software.
7 ******************/ /******************
8 This file Copyright 2008,2009 Andrew M. Bishop
9
10 This program is free software: you can redistribute it and/or modify
11 it under the terms of the GNU Affero General Public License as published by
12 the Free Software Foundation, either version 3 of the License, or
13 (at your option) any later version.
14
15 This program is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU Affero General Public License for more details.
19
20 You should have received a copy of the GNU Affero General Public License
21 along with this program. If not, see <http://www.gnu.org/licenses/>.
22 ***************************************/
23
24
25 #include <assert.h>
26 #include <stdlib.h>
27 #include <string.h>
28
29 #include "functions.h"
30 #include "waysx.h"
31 #include "ways.h"
32
33
34 /* Variables */
35
36 extern int option_slim;
37 extern char *tmpdirname;
38
39 /* Functions */
40
41 static int sort_by_id(way_t *a,way_t *b);
42 static int sort_by_name(char **a,char **b);
43 static index_t index_way_name(char** names,int number,char *name);
44 static int sort_by_name_and_properties(Way **a,Way **b);
45 static index_t index_way(Way** data,int number,Way *way);
46
47
48 /*++++++++++++++++++++++++++++++++++++++
49 Allocate a new way list.
50
51 WaysX *NewWayList Returns the way list.
52 ++++++++++++++++++++++++++++++++++++++*/
53
54 WaysX *NewWayList(void)
55 {
56 WaysX *waysx;
57
58 waysx=(WaysX*)calloc(1,sizeof(WaysX));
59
60 assert(waysx); /* Check calloc() worked */
61
62 waysx->filename=(char*)malloc(strlen(tmpdirname)+24);
63 sprintf(waysx->filename,"%s/ways.%p.tmp",tmpdirname,waysx);
64
65 waysx->fd=OpenFile(waysx->filename);
66
67 waysx->nfilename=(char*)malloc(strlen(tmpdirname)+24);
68 sprintf(waysx->nfilename,"%s/waynames.%p.tmp",tmpdirname,waysx);
69
70 waysx->nfd=OpenFile(waysx->nfilename);
71
72 return(waysx);
73 }
74
75
76 /*++++++++++++++++++++++++++++++++++++++
77 Free a way list.
78
79 WaysX *waysx The list to be freed.
80 ++++++++++++++++++++++++++++++++++++++*/
81
82 void FreeWayList(WaysX *waysx)
83 {
84 DeleteFile(waysx->filename);
85
86 if(waysx->xdata)
87 UnmapFile(waysx->filename);
88
89 if(waysx->idata)
90 free(waysx->idata);
91
92 DeleteFile(waysx->nfilename);
93
94 free(waysx);
95 }
96
97
98 /*++++++++++++++++++++++++++++++++++++++
99 Save the way list to a file.
100
101 WaysX* waysx The set of ways to save.
102
103 const char *filename The name of the file to save.
104 ++++++++++++++++++++++++++++++++++++++*/
105
106 void SaveWayList(WaysX* waysx,const char *filename)
107 {
108 index_t i;
109 int fd;
110 Ways *ways;
111
112 printf("Writing Ways: Ways=0");
113 fflush(stdout);
114
115 if(option_slim)
116 waysx->xdata=MapFile(waysx->filename);
117
118 /* Fill in a Ways structure with the offset of the real data in the file after
119 the Way structure itself. */
120
121 ways=calloc(1,sizeof(Ways));
122
123 assert(ways); /* Check calloc() worked */
124
125 ways->number=waysx->cnumber;
126 ways->onumber=waysx->number;
127
128 ways->data=NULL;
129
130 ways->ways=(void*)sizeof(Ways);
131 ways->names=(void*)(sizeof(Ways)+ways->number*sizeof(Way));
132
133 /* Write out the Ways structure and then the real data. */
134
135 fd=OpenFile(filename);
136
137 WriteFile(fd,ways,sizeof(Ways));
138
139 for(i=0;i<waysx->number;i++)
140 {
141 SeekFile(fd,sizeof(Ways)+waysx->xdata[i].cid*sizeof(Way));
142 WriteFile(fd,&waysx->xdata[i].way,sizeof(Way));
143
144 if(!((i+1)%10000))
145 {
146 printf("\rWriting Ways: Ways=%d",i+1);
147 fflush(stdout);
148 }
149 }
150
151 if(option_slim)
152 waysx->xdata=UnmapFile(waysx->filename);
153
154 waysx->names=MapFile(waysx->nfilename);
155
156 SeekFile(fd,sizeof(Ways)+waysx->cnumber*sizeof(Way));
157 WriteFile(fd,waysx->names,waysx->nlength);
158
159 waysx->names=UnmapFile(waysx->nfilename);
160
161 CloseFile(fd);
162
163 printf("\rWrote Ways: Ways=%d \n",waysx->number);
164 fflush(stdout);
165
166 /* Free the fake Ways */
167
168 free(ways);
169 }
170
171
172 /*++++++++++++++++++++++++++++++++++++++
173 Find a particular way index.
174
175 index_t IndexWayX Returns the index of the extended way with the specified id.
176
177 WaysX* waysx The set of ways to process.
178
179 way_t id The way id to look for.
180 ++++++++++++++++++++++++++++++++++++++*/
181
182 index_t IndexWayX(WaysX* waysx,way_t id)
183 {
184 int start=0;
185 int end=waysx->number-1;
186 int mid;
187
188 assert(waysx->idata); /* Must have idata filled in => sorted */
189
190 /* Binary search - search key exact match only is required.
191 *
192 * # <- start | Check mid and move start or end if it doesn't match
193 * # |
194 * # | Since an exact match is wanted we can set end=mid-1
195 * # <- mid | or start=mid+1 because we know that mid doesn't match.
196 * # |
197 * # | Eventually either end=start or end=start+1 and one of
198 * # <- end | start or end is the wanted one.
199 */
200
201 if(end<start) /* There are no ways */
202 return(NO_WAY);
203 else if(id<waysx->idata[start]) /* Check key is not before start */
204 return(NO_WAY);
205 else if(id>waysx->idata[end]) /* Check key is not after end */
206 return(NO_WAY);
207 else
208 {
209 do
210 {
211 mid=(start+end)/2; /* Choose mid point */
212
213 if(waysx->idata[mid]<id) /* Mid point is too low */
214 start=mid+1;
215 else if(waysx->idata[mid]>id) /* Mid point is too high */
216 end=mid-1;
217 else /* Mid point is correct */
218 return(mid);
219 }
220 while((end-start)>1);
221
222 if(waysx->idata[start]==id) /* Start is correct */
223 return(start);
224
225 if(waysx->idata[end]==id) /* End is correct */
226 return(end);
227 }
228
229 return(NO_WAY);
230 }
231
232
233 /*++++++++++++++++++++++++++++++++++++++
234 Lookup a particular way.
235
236 WayX *LookupWayX Returns a pointer to the extended way with the specified id.
237
238 WaysX* waysx The set of ways to process.
239
240 index_t index The way index to look for.
241
242 int position The position in the cache to use.
243 ++++++++++++++++++++++++++++++++++++++*/
244
245 WayX *LookupWayX(WaysX* waysx,index_t index,int position)
246 {
247 assert(index!=NO_WAY); /* Must be a valid way */
248
249 if(option_slim)
250 {
251 SeekFile(waysx->fd,index*sizeof(WayX));
252
253 ReadFile(waysx->fd,&waysx->cached[position-1],sizeof(WayX));
254
255 return(&waysx->cached[position-1]);
256 }
257 else
258 {
259 return(&waysx->xdata[index]);
260 }
261 }
262
263
264 /*++++++++++++++++++++++++++++++++++++++
265 Append a way to a way list.
266
267 void AppendWay Returns the newly appended way.
268
269 WaysX* waysx The set of ways to process.
270
271 way_t id The ID of the way.
272
273 Way *way The way data itself.
274
275 const char *name The name or reference of the way.
276 ++++++++++++++++++++++++++++++++++++++*/
277
278 void AppendWay(WaysX* waysx,way_t id,Way *way,const char *name)
279 {
280 WayX wayx;
281
282 assert(!waysx->idata); /* Must not have idata filled in => unsorted */
283
284 wayx.id=id;
285 wayx.way=*way;
286 wayx.name=waysx->nlength;
287
288 WriteFile(waysx->fd,&wayx,sizeof(WayX));
289
290 waysx->xnumber++;
291
292 WriteFile(waysx->nfd,name,strlen(name)+1);
293
294 waysx->nlength+=strlen(name)+1;
295 }
296
297
298 /*++++++++++++++++++++++++++++++++++++++
299 Sort the list of ways.
300
301 WaysX* waysx The set of ways to process.
302 ++++++++++++++++++++++++++++++++++++++*/
303
304 void SortWayList(WaysX* waysx)
305 {
306 WayX wayx;
307 index_t i;
308 int duplicate;
309 int fd;
310
311 assert(!waysx->idata); /* Must not have idata filled in => unsorted */
312
313 printf("Sorting Ways");
314 fflush(stdout);
315
316 /* Close the files and re-open them */
317
318 CloseFile(waysx->fd);
319 waysx->fd=ReOpenFile(waysx->filename);
320
321 CloseFile(waysx->nfd);
322 waysx->nfd=ReOpenFile(waysx->nfilename);
323
324 /* Allocate the array of pointers and fill them */
325
326 waysx->idata=(way_t*)malloc(waysx->xnumber*sizeof(way_t));
327
328 assert(waysx->idata); /* Check malloc() worked */
329
330 waysx->number=0;
331
332 while(!ReadFile(waysx->fd,&wayx,sizeof(WayX)))
333 {
334 waysx->idata[waysx->number]=wayx.id;
335 waysx->number++;
336 }
337
338 /* Sort the way indexes */
339
340 do
341 {
342 qsort(waysx->idata,waysx->number,sizeof(way_t),(int (*)(const void*,const void*))sort_by_id);
343
344 duplicate=0;
345
346 while(waysx->idata[waysx->number-1]==NO_WAY)
347 waysx->number--;
348
349 for(i=1;i<waysx->number;i++)
350 if(waysx->idata[i]==waysx->idata[i-1])
351 {
352 waysx->idata[i-1]=NO_WAY;
353 duplicate++;
354 }
355
356 if(duplicate)
357 {
358 printf(" - %d duplicates found; trying again.\nSorting Ways",duplicate);
359 fflush(stdout);
360 }
361 }
362 while(duplicate);
363
364 /* Sort the on-disk image */
365
366 DeleteFile(waysx->filename);
367
368 fd=OpenFile(waysx->filename);
369 SeekFile(waysx->fd,0);
370
371 while(!ReadFile(waysx->fd,&wayx,sizeof(WayX)))
372 {
373 index_t index=IndexWayX(waysx,wayx.id);
374
375 if(index!=NO_WAY)
376 {
377 SeekFile(fd,index*sizeof(WayX));
378 WriteFile(fd,&wayx,sizeof(WayX));
379 }
380 }
381
382 /* Close the files and re-open them */
383
384 CloseFile(waysx->fd);
385 CloseFile(fd);
386
387 waysx->fd=ReOpenFile(waysx->filename);
388
389 if(!option_slim)
390 waysx->xdata=MapFile(waysx->filename);
391
392 printf("\rSorted Ways \n");
393 fflush(stdout);
394 }
395
396
397 /*++++++++++++++++++++++++++++++++++++++
398 Sort the ways into id order.
399
400 int sort_by_id Returns the comparison of the id fields.
401
402 way_t *a The first way id.
403
404 way_t *b The second way id.
405 ++++++++++++++++++++++++++++++++++++++*/
406
407 static int sort_by_id(way_t *a,way_t *b)
408 {
409 node_t a_id=*a;
410 node_t b_id=*b;
411
412 if(a_id<b_id)
413 return(-1);
414 else if(a_id>b_id)
415 return(1);
416 else
417 return(0);
418 }
419
420
421 /*++++++++++++++++++++++++++++++++++++++
422 Compact the list of way names.
423
424 WaysX* waysx The set of ways to process.
425 ++++++++++++++++++++++++++++++++++++++*/
426
427 void CompactWayNames(WaysX* waysx)
428 {
429 index_t i,*offsets;
430 char **cnames;
431 WayX wayx;
432 int duplicate;
433 int fd,nfd;
434
435 /* Sort the names */
436
437 printf("Sorting Way names");
438 fflush(stdout);
439
440 if(option_slim)
441 waysx->xdata=MapFile(waysx->filename);
442
443 waysx->names=MapFile(waysx->nfilename);
444
445 waysx->nnumber=waysx->number;
446
447 cnames=(char**)malloc(waysx->nnumber*sizeof(char*));
448
449 assert(cnames); /* Check malloc() worked */
450
451 for(i=0;i<waysx->nnumber;i++)
452 cnames[i]=&waysx->names[waysx->xdata[i].name];
453
454 do
455 {
456 qsort(cnames,waysx->nnumber,sizeof(char*),(int (*)(const void*,const void*))sort_by_name);
457
458 duplicate=0;
459
460 while(cnames[waysx->nnumber-1]==NULL)
461 waysx->nnumber--;
462
463 for(i=1;i<waysx->nnumber;i++)
464 if(!strcmp(cnames[i],cnames[i-1]))
465 {
466 cnames[i-1]=NULL;
467 duplicate++;
468 }
469
470 if(duplicate)
471 {
472 printf(" - %d duplicates found; trying again.\nSorting Way names",duplicate);
473 fflush(stdout);
474 }
475 }
476 while(duplicate);
477
478 DeleteFile(waysx->nfilename);
479
480 nfd=OpenFile(waysx->nfilename);
481
482 offsets=(index_t*)malloc(waysx->nnumber*sizeof(index_t));
483
484 assert(offsets); /* Check malloc() worked */
485
486 waysx->nlength=0;
487
488 for(i=0;i<waysx->nnumber;i++)
489 {
490 offsets[i]=waysx->nlength;
491 waysx->nlength+=strlen(cnames[i])+1;
492 WriteFile(nfd,cnames[i],strlen(cnames[i])+1);
493 }
494
495 CloseFile(waysx->nfd);
496 CloseFile(nfd);
497
498 waysx->nfd=ReOpenFile(waysx->nfilename);
499
500 printf("\rSorted Way names \n");
501 fflush(stdout);
502
503 /* Compact the way names */
504
505 printf("Compacting Way names");
506 fflush(stdout);
507
508 /* Update the on-disk image */
509
510 DeleteFile(waysx->filename);
511
512 fd=OpenFile(waysx->filename);
513 SeekFile(waysx->fd,0);
514
515 while(!ReadFile(waysx->fd,&wayx,sizeof(WayX)))
516 {
517 wayx.way.name=offsets[index_way_name(cnames,waysx->nnumber,&waysx->names[wayx.name])];
518
519 WriteFile(fd,&wayx,sizeof(WayX));
520 }
521
522 CloseFile(waysx->fd);
523 CloseFile(fd);
524
525 waysx->xdata=UnmapFile(waysx->filename);
526 waysx->names=UnmapFile(waysx->nfilename);
527
528 waysx->fd=ReOpenFile(waysx->filename);
529
530 if(!option_slim)
531 waysx->xdata=MapFile(waysx->filename);
532
533 printf("\rCompacted Way names: Ways=%d Names=%d\n",waysx->number,waysx->nnumber);
534 fflush(stdout);
535
536 free(cnames);
537 free(offsets);
538 }
539
540
541 /*++++++++++++++++++++++++++++++++++++++
542 Sort the way names.
543
544 int sort_by_name Returns the comparison of the name fields.
545
546 char **a The first extended Way.
547
548 char **b The second extended Way.
549 ++++++++++++++++++++++++++++++++++++++*/
550
551 static int sort_by_name(char **a,char **b)
552 {
553 if(*a==NULL)
554 return(1);
555 else if(*b==NULL)
556 return(-1);
557 else
558 return(strcmp(*a,*b));
559 }
560
561
562 /*++++++++++++++++++++++++++++++++++++++
563 Find a particular name within the sorted list of names.
564
565 index_t index_way_name Returns the index of the name within the list.
566
567 char **names The set of names to search.
568
569 int number The number of names.
570
571 char *name The name to look for.
572 ++++++++++++++++++++++++++++++++++++++*/
573
574 static index_t index_way_name(char** names,int number,char *name)
575 {
576 int start=0;
577 int end=number-1;
578 int mid;
579
580 /* Binary search - search key exact match only is required.
581 *
582 * # <- start | Check mid and move start or end if it doesn't match
583 * # |
584 * # | Since an exact match is wanted we can set end=mid-1
585 * # <- mid | or start=mid+1 because we know that mid doesn't match.
586 * # |
587 * # | Eventually either end=start or end=start+1 and one of
588 * # <- end | start or end is the wanted one.
589 */
590
591 do
592 {
593 mid=(start+end)/2; /* Choose mid point */
594
595 if(strcmp(name,names[mid])>0) /* Mid point is too low */
596 start=mid+1;
597 else if(strcmp(name,names[mid])<0) /* Mid point is too high */
598 end=mid-1;
599 else /* Mid point is correct */
600 return(mid);
601 }
602 while((end-start)>1);
603
604 if(strcmp(name,names[start])==0) /* Start is correct */
605 return(start);
606
607 if(strcmp(name,names[end])==0) /* End is correct */
608 return(end);
609
610 assert(0);
611
612 return(NO_WAY);
613 }
614
615
616 /*++++++++++++++++++++++++++++++++++++++
617 Compact the list of way properties.
618
619 WaysX* waysx The set of ways to process.
620 ++++++++++++++++++++++++++++++++++++++*/
621
622 void CompactWayProperties(WaysX* waysx)
623 {
624 index_t i;
625 WayX wayx;
626 Way **cdata;
627 int duplicate;
628 int fd;
629
630 /* Sort the ways by name and way properties */
631
632 printf("Sorting Ways by properties");
633 fflush(stdout);
634
635 if(option_slim)
636 waysx->xdata=MapFile(waysx->filename);
637
638 waysx->cnumber=waysx->number;
639
640 cdata=(Way**)malloc(waysx->cnumber*sizeof(Way*));
641
642 assert(cdata); /* Check malloc() worked */
643
644 for(i=0;i<waysx->cnumber;i++)
645 cdata[i]=&waysx->xdata[i].way;
646
647 do
648 {
649 qsort(cdata,waysx->cnumber,sizeof(Way*),(int (*)(const void*,const void*))sort_by_name_and_properties);
650
651 duplicate=0;
652
653 while(cdata[waysx->cnumber-1]==NULL)
654 waysx->cnumber--;
655
656 for(i=1;i<waysx->cnumber;i++)
657 if(cdata[i-1]->name==cdata[i]->name && !WaysCompare(cdata[i-1],cdata[i]))
658 {
659 cdata[i-1]=NULL;
660 duplicate++;
661 }
662
663 if(duplicate)
664 {
665 printf(" - %d duplicates found; trying again.\nSorting Ways by properties",duplicate);
666 fflush(stdout);
667 }
668 }
669 while(duplicate);
670
671 printf("\rSorted Ways by properties \n");
672 fflush(stdout);
673
674 /* Compact the way properties */
675
676 printf("Compacting Way properties");
677 fflush(stdout);
678
679 /* Update the on-disk image */
680
681 DeleteFile(waysx->filename);
682
683 fd=OpenFile(waysx->filename);
684 SeekFile(waysx->fd,0);
685
686 while(!ReadFile(waysx->fd,&wayx,sizeof(WayX)))
687 {
688 wayx.cid=index_way(cdata,waysx->cnumber,&wayx.way);
689
690 WriteFile(fd,&wayx,sizeof(WayX));
691 }
692
693 CloseFile(waysx->fd);
694 CloseFile(fd);
695
696 waysx->fd=ReOpenFile(waysx->filename);
697
698 waysx->xdata=UnmapFile(waysx->filename);
699
700 if(!option_slim)
701 waysx->xdata=MapFile(waysx->filename);
702
703 printf("\rCompacted Way properties: Ways=%d Compacted=%d\n",waysx->number,waysx->cnumber);
704 fflush(stdout);
705
706 free(cdata);
707 }
708
709
710 /*++++++++++++++++++++++++++++++++++++++
711 Sort the ways into name and properties order.
712
713 int sort_by_name_and_properties Returns the comparison of the name and properties fields.
714
715 Way **a The first Way.
716
717 Way **b The second Way.
718 ++++++++++++++++++++++++++++++++++++++*/
719
720 static int sort_by_name_and_properties(Way **a,Way **b)
721 {
722 if(*a==NULL)
723 return(1);
724 else if(*b==NULL)
725 return(-1);
726 else
727 {
728 index_t a_name=(*a)->name;
729 index_t b_name=(*b)->name;
730
731 if(a_name<b_name)
732 return(-1);
733 else if(a_name>b_name)
734 return(1);
735 else
736 {
737 Way *a_way=*a;
738 Way *b_way=*b;
739
740 return(WaysCompare(a_way,b_way));
741 }
742 }
743 }
744
745
746 /*++++++++++++++++++++++++++++++++++++++
747 Find a particular Way within the sorted list of ways.
748
749 index_t index_way Returns the index of the Way within the list.
750
751 Way **data The set of Ways to search.
752
753 int number The number of Ways.
754
755 Way *way The name to look for.
756 ++++++++++++++++++++++++++++++++++++++*/
757
758 static index_t index_way(Way** data,int number,Way *way)
759 {
760 int start=0;
761 int end=number-1;
762 int mid;
763
764 /* Binary search - search key exact match only is required.
765 *
766 * # <- start | Check mid and move start or end if it doesn't match
767 * # |
768 * # | Since an exact match is wanted we can set end=mid-1
769 * # <- mid | or start=mid+1 because we know that mid doesn't match.
770 * # |
771 * # | Eventually either end=start or end=start+1 and one of
772 * # <- end | start or end is the wanted one.
773 */
774
775 do
776 {
777 mid=(start+end)/2; /* Choose mid point */
778
779 if(way->name>data[mid]->name) /* Mid point is too low */
780 start=mid+1;
781 else if(way->name<data[mid]->name) /* Mid point is too high */
782 end=mid-1;
783 else if(WaysCompare(way,data[mid])>0) /* Mid point is too low */
784 start=mid+1;
785 else if(WaysCompare(way,data[mid])<0) /* Mid point is too high */
786 end=mid-1;
787 else /* Mid point is correct */
788 return(mid);
789 }
790 while((end-start)>1);
791
792 if(way->name==data[start]->name && WaysCompare(way,data[start])==0) /* Start is correct */
793 return(start);
794
795 if(way->name==data[end]->name && WaysCompare(way,data[end])==0) /* End is correct */
796 return(end);
797
798 assert(0);
799
800 return(NO_WAY);
801 }

Properties

Name Value
cvs:description Extended ways functions.
Index: This Site Routino Software Download Source Code Documentation XML Files Links
Index: View SVN Development Recent changes Development (destination-access branch) Version 3.4.2 (destination-access branch) Version 3.4.2 Version 3.4.1 (destination-access branch) Version 3.4.1 Version 3.4 (destination-access branch) Version 3.4 Version 3.3.3 (destination-access branch) Version 3.3.3 Version 3.3.2 (destination-access branch) Version 3.3.2 Version 3.3.1 (destination-access branch) Version 3.3.1 Version 3.3 (destination-access branch) Version 3.3 Version 3.2 Version 3.1.1 Version 3.1 Version 3.0 Version 2.7.3 Version 2.7.2 Version 2.7.1 Version 2.7 Version 2.6 Version 2.5.1 Version 2.5 Version 2.4.1 Version 2.4 Version 2.3.2 Version 2.3.1 Version 2.3 Version 2.2 Version 2.1.2 Version 2.1.1 Version 2.1 Version 2.0.3 Version 2.0.2 Version 2.0.1 Version 2.0 Version 1.5.1 Version 1.5 Version 1.4.1 Version 1.4 Version 1.3 Version 1.2 Version 1.1 Version 1.0
Powered by ViewVC 1.3.0-dev ViewVC Help
© Andrew M. Bishop = < amb @ ... >
Root