1

Topic: The compiled search tree.

There is a task of fast search of the named objects in a tree structure reminding file system with directories and files, files it is objects of type "1" and directories it is objects of type "2" to give an example easier - 1:1 1:2 1:3 1:4 2:5 2:6 2:1 2:3 3:10 3:11 3:12 3:14 Within the limits of a directory objects are unique. In analogy to file system - there can not be two files with the same name. Directories also are unique. An example close to the real: \aaaa\eeee\yyyyy\ooooo (01): \bbbb\cccc\dddd\eeeee \aaaa\eeee\yyyyy\ooooo (01): \bbbb\cccc\dddd\qqqqqq \aaaa\eeee\yyyyy\ooooo (01): \bbbb\cccc\dddd\hhhhh \aaaa\eeee\yyyyy\vvvvv (02): \bbbb\cccc\dddd\eeeee \aaaa\eeee\yyyyy\vvvvv (02): \bbbb\cccc\dddd\qqqqqq \aaaa\eeee\yyyyy\vvvvv (02): \bbbb\cccc\dddd\jjjjjj \aaaa\eeee\yyyyy\ddddd (03): \bbbb\cccc\dddd\eeeee \aaaa\eeee\yyyyy\ddddd (03): \bbbb\cccc\dddd\qqqqqq \aaaa\eeee\yyyyy\ddddd (03): \bbbb\cccc\dddd\wwwww \aaaa\eeee\yyyyy\lllll (04): \bbbb\cccc\dddd\eeeee \aaaa\eeee\yyyyy\lllll (04): \bbbb\cccc\dddd\qqqqqq \aaaa\eeee\yyyyy\lllll (04): \bbbb\cccc\dddd\ffffff In brackets before a colon it not a part of a line DIR, and certain ID for this purpose DIR-a. It is required: 1) quickly to search on requests of type: 1) to find ID for DIR =\aaaa\eeee\yyyyy\ooooo, 2) to find object \aaaa\eeee\yyyyy\vvvvv if ID=102) to Store it in somebody  (binary file) which at loading can be transformed already into a certain tree or everything. Yes, forgot important to add - ID for DIR, it is assigned in , that is it is not known in advance - at "a compilation" stage. Well we tell, in runtime there is a certain event a name to which and is DIR, it should be found in our basis, and at this event is certain ID which to it should be appropriated. Such events can arise simultaneously a little. Then there is a second type of event a name to which OBJECT and for it is known ID and here it is necessary to find this object in our basis. Then there is a third type of event a name to which DIR and it ID is known, and it is necessary to find it in basis and to delete this ID from DIR. ps: In advance thanks!

2

Re: The compiled search tree.

Hello, BLov, you wrote: BL> There is a task of fast search of the named objects in a tree structure reminding file system with directories and files, files it is objects of type "1" and directories these are objects of type "2" BL> It is required: BL> BL> 1) quickly to search on requests of type: BL> BL> 1) to find ID for  =\aaaa\eeee\yyyyy\ooooo, BL> 2) to find object \aaaa\eeee\yyyyy\vvvvv if ID=10 BL> BL> 2) to Store it in somebody  (the binary file) which at loading can be transformed already into a certain tree or everything. BL> 1) and structure static? Tasks to replenish/delete are not present? 2) ID objects are set, or only names? ID it is possible to select as conveniently? If  "yes" both times than the closed hash table is bad? It is possible even ideal  to screw...

3

Re: The compiled search tree.

Hello, Erop, you wrote: Outstripped! E> 1) and structure static? Tasks to replenish/delete are not present? Structure of 200 % the static. E> 2) ID objects are set, or only names? ID it is possible to select as conveniently? Described in the description. No, ID can just be a little and they are not known for earlier. E> If  "yes" both times than the closed hash table is bad? It is possible even ideal  to screw... Yes I too think over it, but here one more problem - is not present any libraries - it is necessary to do all in the manual.

4

Re: The compiled search tree.

Hello, BLov, you wrote: BL> Described in the description. No, ID can just be a little and they are not known for earlier. Well then two tables direct and reverse, if id not the dense. E>> if  "yes" both times than the closed hash table is bad? It is possible even ideal  to screw... BL> Yes I too think over it, but here one more problem - is not present any libraries - it is necessary to do all in the manual. And language what? As a whole to write the closed hash - business of a pair of clocks a maximum. It if with  and coffee There only affairs. On  we calculate a position in the table, and from it we go forward on a circle, yet we do not meet that we search or blank cell. In cells we store offsets of the data or ID objects or that there still happens in this construction... Well and calculation  too from a half-kick is written.

5

Re: The compiled search tree.

Hello, Erop, you wrote: E> Well and calculation  too from a half-kick is written. "Problem" not in making "somehow", and the task to make close to an ideal. That you offer that it is far not . The Search tree, this tree of the static (constant) data in which it is necessary to search. What for here a hash? Think.

6

Re: The compiled search tree.

Hello, BLov, you wrote: BL> the Search tree, this tree of the static (constant) data in which it is necessary to search. What for here a hash? Think. So it like as well as is the typical task for an ideal hash. You are finite, can take lex/yacc, feed to it the lexicon and receive a fast parcer, but generally it for a long time already made in a type gperf. That a bicycle to invent?

7

Re: The compiled search tree.

Hello, BLov, you wrote: And it is impossible to fasten here the coding of type of Haffmana on kol-vu objects in a directory? Or it at all that?