From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Date: Sun, 2 Nov 2008 00:19:30 +0300 From: Alexey Tourbin To: ALT Linux Team development discussions Message-ID: <20081101211930.GP8739@altlinux.org> Mail-Followup-To: ALT Linux Team development discussions References: <87zlkrz0cx.fsf@frontier.dottedmag.net> <20081028062728.GA8739@altlinux.org> <87mygpmdrs.fsf@frontier.dottedmag.net> <20081028070413.GB8739@altlinux.org> <87iqrdmbk7.fsf@frontier.dottedmag.net> <20081028075013.GC8739@altlinux.org> <20081101154207.GA21180@mw.office.seiros.ru> <20081101180136.GM8739@altlinux.org> <20081101180750.GN8739@altlinux.org> <20081101204541.GO8739@altlinux.org> Mime-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="xXygN3QAmJYWdGtb" Content-Disposition: inline In-Reply-To: <20081101204541.GO8739@altlinux.org> Subject: Re: [devel] contents_index trie X-BeenThere: devel@lists.altlinux.org X-Mailman-Version: 2.1.10b3 Precedence: list Reply-To: ALT Linux Team development discussions List-Id: ALT Linux Team development discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 01 Nov 2008 21:21:11 -0000 Archived-At: List-Archive: List-Post: --xXygN3QAmJYWdGtb Content-Type: text/plain; charset=koi8-r Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Sat, Nov 01, 2008 at 11:45:41PM +0300, Alexey Tourbin wrote: > On Sat, Nov 01, 2008 at 09:07:50PM +0300, Alexey Tourbin wrote: > > On Sat, Nov 01, 2008 at 09:01:36PM +0300, Alexey Tourbin wrote: > > > On Sat, Nov 01, 2008 at 06:42:07PM +0300, =E4=C5=CE=C9=D3 =F3=CD=C9= =D2=CE=CF=D7 wrote: > > > > On Tue, Oct 28, 2008 at 10:50:13AM +0300, =E1=CC=C5=CB=D3=C5=CA =F4= =D5=D2=C2=C9=CE wrote: > > > >=20 > > > > =F0=D2=C1=D7=C9=CC=D8=CE=CF =CC=C9 =D1 =D0=CF=CE=C9=CD=C1=C0 =DE=D4= =CF =D2=C5=DE=D8 =C9=C4=C5=D4 =CF =DA=C1=C4=C1=DE=C5 =D3=CF=DA=C4=C1=CE=C9= =D1 =DE=C5=C7=CF-=D4=CF =D7=D2=CF=C4=C5 cdb, > > > > =D3 =CE=C5=CB=CF=D4=CF=D2=D9=CD=C9 =D5=D4=CF=DE=CE=C5=CE=C9=D1=CD= =C9: > > > > - =CE=C5=D4 key/data, =C5=D3=D4=D8 =D4=CF=CC=D8=CB=CF key > > > > - =D0=CF=C4=C4=C5=D2=D6=C9=D7=C1=C5=D4=D3=D1 =C5=C4=C9=CE=D3=D4=D7= =C5=CE=CE=C1=D1 =CF=D0=C5=D2=C1=C3=C9=D1 "=D0=D2=CF=D7=C5=D2=C9=D4=D8 =CE= =C1 =D3=D5=DD=C5=D3=D4=D7=CF=D7=C1=CE=C9=C5 =C4=C1=CE=CE=D9=CA > > > > key" > > > > - =CE=D5=D6=CE=CF =CF=C2=C5=D3=D0=C5=DE=C9=D4=D8 =CD=C9=CE=C9=CD=C1= =CC=D8=CE=CF=C5 =CB=CF=CC=C9=DE=C5=D3=D4=D7=CF pagefaults =D0=D2=C9 =D7=D9= =D0=CF=CC=CE=C5=CE=C9=C9 =DC=D4=CF=CA > > > > =CF=D0=C5=D2=C1=C3=C9=C9 > > > >=20 > > > > =F1 =D0=D2=C1=D7=C9=CC=D8=CE=CF =D0=CF=CE=D1=CC? > > >=20 > > > =EE=C5=D4, =C9=CD=C5=C5=C5=D4=D3=D1 =D7 =D7=C9=C4=D5 trie. =FC=D4=CF= =C4=C5=D2=C5=D7=CF. =F3 =CB=C1=D6=C4=D9=CD =CB=CC=C0=DE=CF=CD =C1=D3=D3= =CF=C3=C9=C9=D2=CF=D7=C1=CE=CF > > > =DA=CE=C1=DE=C5=CE=C9=C5 _=C9_ =D0=CF=D3=CC=C5=C4=D5=C0=DD=C9=C5 =D7= =CC=CF=D6=C5=CE=CE=D9=C5 =CB=CC=C0=DE=C9. =F4=C1=CB =DE=D4=CF =C9=C4=A3=D4= =C4=CF=D3=D4=D5=D0 =D0=CF > > > =D3=CF=D3=D4=C1=D7=CE=CF=CD=D5 =CB=CC=C0=DE=D5, =D4=C9=D0=C1 ["usr","= bin","perl"]->"perl-base". =F4=CF =C5=D3=D4=D8 > > > =DA=CE=C1=DE=C5=CE=C9=C5 =CB=CC=C0=DE=C1 "=CE=C1=CB=C1=D0=CC=C9=D7=C1= =C5=D4=D3=D1", =C1 =C4=CF=D0=CF=CC=CE=C9=D4=C5=CC=D8=CE=D9=CA =D0=C5=D2=C5= =C8=CF=C4 =CE=C1 =CB=C1=D6=C4=CF=CD =DC=D4=C1=D0=C5 > > > =D7=D9=D0=CF=CC=CE=D1=C5=D4=D3=D1 =D2=C5=CB=D5=D2=D3=C9=D7=CE=CF (=C8= =D7=CF=D3=D4=CF=D7=C1=D1 =D2=C5=CB=D5=D2=D3=C9=D1 =D3 "=CF=D3=D4=C1=D4=CB= =CF=CD" =D3=CF=D3=D4=C1=D7=CE=CF=C7=CF =CB=CC=C0=DE=C1). > > > http://en.wikipedia.org/wiki/Trie > >=20 > > =FC=D4=CF =D0=CF=C8=CF=D6=C5 =CE=C1 =C6=C1=CC=CF=D7=D5=C0 =D3=C9=D3=D4= =C5=CD=D5, =D4=CF=CC=D8=CB=CF =D7 =C6=C1=CA=CC=CF=D7=CF=CA =D3=C9=D3=D4=C5= =CD=C5 =CB=CC=C0=DE =CE=C5 =CD=CF=D6=C5=D4 > > =C2=D9=D4=D8 =CF=C4=CE=CF=D7=D2=C5=CD=C5=CE=CE=CF =C9 =C6=C1=CA=CC=CF= =CD, =C9 =CB=C1=D4=C1=CC=CF=C7=CF=CD. >=20 > =F4=CF =C5=D3=D4=D8 =DC=D4=CF =D0=D2=C5=C6=C9=CB=D3=CE=CF=C5 =C4=C5=D2=C5= =D7=CF =D7 =CF=C2=DD=C5=CD =D7=C9=C4=C5. > =F7=CF=D4 =C4=D2=D5=C7=CF=CA =D0=D2=C9=CD=C5=D2 (=D3=CC=CF=D7=C1=D2=D8): >=20 > ["=DE","=C1","=CA"] -> <=CE=C1=D0=C9=D4=CF=CB> > ["=DE","=C1","=CA","=CB","=C1"] -> <=D0=D4=C9=C3=C1> =F5=D3=CC=CF=D7=C9=C5 =CC=CF=CB=C1=CC=D8=CE=CF=D3=D4=C9 =D3=D3=D9=CC=CF=CB = =C4=CF=D0=CF=CC=CE=C9=D4=C5=CC=D8=CE=CF =D3=CF=D3=D4=CF=C9=D4 =D7 =D4=CF=CD= , =DE=D4=CF =C7=D2=D5=D0=D0=C9=D2=CF=D7=CB=C1 =C4=C1=CE=CE=D9=C8 =C4=CF=CC=D6=CE=C1 =D5=D3=C9=CC=C9=D7=C1=D4=D8=D3=D1 =D0= =D2=C9 =CE=C1=D2=C1=D3=D4=C1=CE=C9=C9 =D7=CC=CF=D6=C5=CE=CE=CF=D3=D4=C9. = =EE=C1 =D0=C1=CC=D8=C3=C1=C8 =DC=D4=CF =CF=DA=CE=C1=DE=C1=C5=D4, =DE=D4=CF =D7=C1=D2=C9=C1=D4=C9=D7=CE=CF=D3=D4=D8= =CF=CB=CF=CE=DE=C1=CE=C9=CA =D3=CC=C5=C4=D5=C5=D4 =D3=CF=CF=D4=CE=CF=D3=C9= =D4=D8 =D3 =CF=D3=CE=CF=D7=CE=D9=CD "=D0=CF=CE=D1=D4=C9=C5=CD". =F0=D2=C9=CD=C5=D2 (=D3=CC=CF=D7=C1=D2=D8): ["=DE","=C1","=CA"] -> <=CE=C1=D0=C9=D4=CF=CB> ["=DE","=C1","=CA","=CE","=D9","=CA"] -> =D0=D2=C9=CC. =CD=D5=D6. =CF=D4=CE= =CF=D3=D1=DD=C9=CA=D3=D1 =CB "=DE=C1=CA" ["=DE","=C1","=CA","=CE","=C1","=D1"] -> =D0=D2=C9=CC. =D6=C5=CE. =CF=D4=CE= =CF=D3=D1=DD=C9=CA=D3=D1 =CB "=DE=C1=CA" =F0=D2=C9=CD=C5=D2 =D3 =D4=CF=DE=CB=C9 =DA=D2=C5=CE=C9=D1 =C6=D3: /usr/lib/perl5 -> perl-base /usr/lib/perl5/Test -> perl-devel /usr/lib/perl5/Test.pm -> perl-devel /usr/lib/perl5/Test/More.pm -> perl-devel =FA=C4=C5=D3=D8 =D0=D2=C9 =D5=C7=CC=D5=C2=CC=C5=CE=C9=C9 =D7 =D0=CF=C4=CB= =C1=D4=C1=CC=CF=C7=C9 =CE=C1=D2=C1=D3=D4=C1=C5=D4 =D0=C5=D2=CC=CF=D7=C1=D1 = =D3=D0=C5=C3=C9=C6=C9=CB=C1, =DE=D4=CF, =CB=D3=D4=C1=D4=C9, "=D0=C1=D2=C1=CC=CC=C5=CC=D8=CE=CF" =CF=D4=D2=C1=D6=C1= =C5=D4=D3=D1 =CE=C1 =CE=C1=DA=D7=C1=CE=C9=C9 =D0=C1=CB=C5=D4=CF=D7. =F0=D2= =C5=C6=C9=CB=D3=CE=C1=D1 =C7=D2=D5=D0=D0=C9=D2=CF=D7=CB=C1 =D3=D4=C1=D4=C9=D3=D4=C9=DE=C5=D3=CB=C9 = =C8=CF=D2=CF=DB=CF =D3=CF=CF=D4=D7=C5=D4=D3=D4=D7=D5=C5=D4 =D3=CD=D9=D3=CC= =CF=D7=CF=CA =C7=D2=D5=D0=D0=C9=D2=CF=D7=CB=C5, =C1 =D3=CD=D9=D3=CC=CF=D7=C1=D1 =C7=D2=D5=D0=D0=C9=D2=CF=D7=CB=C1 =C8=CF=D2= =CF=DB=CF =D2=C5=C1=CC=C9=DA=D5=C5=D4 =D5=D3=CC=CF=D7=C9=C5 =CC=CF=CB=C1=CC= =D8=CE=CF=D3=D4=C9 =D3=D3=D9=CC=CF=CB. > =EF=D2=C7=C1=CE=C9=DA=C1=C3=C9=D1 =D0=C1=CD=D1=D4=C9 =D7 =D0=D2=C5=C6=C9= =CB=D3=CE=CF=CD =C4=C5=D2=C5=D7=C5 =C4=CF=CC=D6=CE=C1 =C2=D9=D4=D8 =D4=C1= =CB=CF=CA, =DE=D4=CF=C2=D9 =D0=D2=C9 > =CF=DE=C5=D2=C5=C4=CE=CF=CD =D0=C5=D2=C5=C8=CF=C4=C5 =D0=CF =D3=CF=D3=D4= =C1=D7=CE=CF=CD=D5 =CB=CC=C0=DE=D5, =D4.=C5. "=DE"->"=C1", "=C1"->"=CA" =C9= =D4.=C4. > =D7=D9=D0=CF=CC=CE=D1=CC=CF=D3=D8 =D5=D3=CC=CF=D7=C9=C5 =CC=CF=CB=C1=CC= =D8=CE=CF=D3=D4=C9 =D3=D3=D9=CC=CF=CB: =CB=CC=C0=DE=C9 =C9 =DA=CE=C1=DE=C5= =CE=C9=D1 =D7 =D0=C1=CD=D1=D4=C9 > =C4=CF=CC=D6=CE=D9 =C2=D9=D4=D8 =D2=C1=DA=CD=C5=DD=C5=CE=D9 (=D3=C7=D2=D5= =D0=D0=C9=D2=CF=D7=C1=CE=D9) "=C2=CC=C9=DA=CB=CF" =C4=D2=D5=C7 =CB =C4=D2= =D5=C7=D5, =D4=CF =C5=D3=D4=D8 > =DE=D4=CF=C2=D9 =D0=D2=C9 =D0=D2=CF=C8=CF=C4=C5 =D0=CF =D3=CF=D3=D4=C1=D7= =CE=CF=CD=D5 =CB=CC=C0=DE=D5 =D7=C7=CC=D5=C2=D8 =C4=C5=D2=C5=D7=C1 =DA=C1= =D4=D2=C1=C7=C9=D7=C1=CC=CF=D3=D8 > =CD=C9=CE=C9=CD=C1=CC=D8=CE=CF=C5 =DE=C9=D3=CC=CF =D3=C5=C7=CD=C5=CE=D4= =CF=D7 =D0=C1=CD=D1=D4=C9. >=20 > =F7 =C6=C1=CA=CC=CF=D7=CF=CA =D3=C9=D3=D4=C5=CD=C5 =D4=C1=CB =C9 =D0=D2= =CF=C9=D3=C8=CF=C4=C9=D4: =CB=C1=D4=C1=CC=CF=C7 =D4=CF=D6=C5 =C9=CD=C5=C5= =D4 inode, =C9 =C4=C1=CE=CE=D9=C5 > =CB=C1=D4=C1=CC=CF=C7=C1 (dirent.h) =CC=CF=CB=CC=D8=CE=CF "=D3=C7=D2=D5= =D0=D0=C9=D2=CF=D7=C1=CE=D9" =D7 "=C6=C1=CA=CC=C5" =CB=C1=D4=C1=CC=CF=C7=C1= . =F4=C1=CB =DE=D4=CF > =D0=C5=D2=C5=C8=CF=C4 =C9=DA =CB=C1=D4=C1=CC=CF=C7=C1 =D7 =D0=CF=C4=CB=C1= =D4=C1=CC=CF=C7 =DA=C1=D4=D2=C1=C7=C9=D7=C1=C5=D4 =CD=C9=CE=C9=CD=C1=CC=D8= =CE=CF=C5 =CB=CF=CC=C9=DE=C5=D3=D4=D7=CF > =C4=C9=D3=CB=CF=D7=D9=C8 =D3=D4=D2=C1=CE=C9=C3. =E1 =C5=D3=CC=C9 =C2=D9 = =C9=CE=C6=CF=D2=CD=C1=C3=C9=D1 =CF =D3=CF=C4=C5=D2=D6=C9=CD=CF=CD =CB=C1=D4= =C1=CC=CF=C7=C1 =C2=D9=CC=C1 > =D0=D2=CF=C9=DA=D7=CF=CC=D8=CE=CF =D2=C1=DA=C2=D2=CF=D3=C1=CE=C1 =D0=CF = =C4=C9=D3=CB=D5 (=CB=C1=CB =D5=CB=C1=DA=C1=D4=C5=CC=C9 =CE=C1 =D3=D4=D2=CF= =CB=C9 =D0=D2=C9 > =C9=D3=D0=CF=CC=D8=DA=CF=D7=C1=CE=C9=C9 malloc), =D4=CF=C7=C4=C1 =C4=CC= =D1 =CE=C1=D0=D2. readdir(2) =D0=CF=D4=D2=C5=C2=CF=D7=C1=CC=CF=D3=D8 =C2=D9 > =DE=C9=D4=C1=D4=D8 =D3 =C4=C9=D3=CB=C1 =D7 =C2=D5=C6=C5=D2=CE=D9=CA =CB= =C5=DB =C2=CF=CC=D8=DB=CF=C5 =CB=CF=CC=C9=DE=C5=D3=D4=D7=CF =CC=C9=DB=CE=C9= =C8 =D3=D4=D2=C1=CE=C9=C3. >=20 > =EB=CF=D2=CF=DE=C5, =CF=D0=D4=C9=CD=C1=CC=D8=CE=CF=C5 =D2=C1=DA=CD=C5=DD= =C5=CE=C9=C5 =D7 =D0=C1=CD=D1=D4=C9 =D0=D2=C5=C6=C9=CB=D3=CE=CF=C7=CF =C4= =C5=D2=C5=D7=C1 -- > =D0=CF =D3=CC=CF=D6=CE=CF=D3=D4=C9 =DC=D4=CF =DA=C1=C4=C1=DE=C1 =C7=C4=C5= -=D4=CF =CE=C1 =D5=D2=CF=D7=CE=C5 =D2=C5=C1=CC=C9=DA=C1=C3=C9=C9 =C6=C1=CA= =CC=CF=D7=CF=CA =D3=C9=D3=D4=C5=CD=D9. --xXygN3QAmJYWdGtb Content-Type: application/pgp-signature Content-Disposition: inline -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) iEYEARECAAYFAkkMx+IACgkQfBKgtDjnu0bApwCfc9ExXFzvFKhFv4kKcQS8Xa5v hUQAn3uAxXVjlkhS6JEe2208zrF/SpLe =dzUN -----END PGP SIGNATURE----- --xXygN3QAmJYWdGtb--