From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Date: Sat, 1 Nov 2008 23:45:41 +0300 From: Alexey Tourbin To: ALT Linux Team development discussions Message-ID: <20081101204541.GO8739@altlinux.org> Mail-Followup-To: ALT Linux Team development discussions References: <20081026181507.GA8655@dad.imath.kiev.ua> <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> Mime-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="yLaBmHMi4cq+C/u4" Content-Disposition: inline In-Reply-To: <20081101180750.GN8739@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 20:47:22 -0000 Archived-At: List-Archive: List-Post: --yLaBmHMi4cq+C/u4 Content-Type: text/plain; charset=koi8-r Content-Disposition: inline Content-Transfer-Encoding: quoted-printable 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","bi= n","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. =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): ["=DE","=C1","=CA"] -> <=CE=C1=D0=C9=D4=CF=CB> ["=DE","=C1","=CA","=CB","=C1"] -> <=D0=D4=C9=C3=C1> =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. =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 i= node, =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. =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. --yLaBmHMi4cq+C/u4 Content-Type: application/pgp-signature Content-Disposition: inline -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) iEYEARECAAYFAkkMv/QACgkQfBKgtDjnu0Y2QwCbBDNVkTRYwrPjb9KoYHtdJuvo OaMAoLQv/XMhDAdaPAY3VrfVUV6k8IyZ =1M8n -----END PGP SIGNATURE----- --yLaBmHMi4cq+C/u4--