Obsah / Utility / RBTREE / Prohledávání RB-stromu
Zdrojový kód: INCLUDE\UTIL\RBTREE.INC, UTIL\RBTREE.ASM
Prohledávání RB-stromu
Funkce pro prohledávání RB-stromu vyhledávají položky ve stromu podle třídicích klíčů. Hodnota klíče může mít různou formu - adresa položky v paměti, slovo v proměnné RB_DataW, dvojslovo na adrese RBN_Data nebo jiná data podle porovnávací funkce.
Ve všech případech má prohledávací funkce zhruba stejný tvar - z kořene stromu se načte ukazatel na výchozí (kořenovou) položku stromu. Strom se prochází od této položky po uzlech stromu a to tak, že porovnáním třídicího klíče se rozliší tři případy - 1) klíč souhlasí, položka byla nalezena, 2) klíč je menší, pokračuje se levým potomkem, 3) klíč je větší, pokračuje se pravým potomkem. Pro zefektivnění algoritmu se využívá toho, že ukazatel na pravou položku bezprostředně následuje za ukazatelem na levou položku - k ukazatelům se přistupuje indexově.
|
Funkce RBTreeSrcAddr vyhledá v RB-stromu položku podle dané adresy. Funkce se používá například při vyhledávání HANDLE objektů jádra. Strom musí být tříděný podle adresy položky, tj. všechny položky byly do stromu vkládány pomocí funkce RBTreeInsAddr (viz dále - kapitola vkládání položek). Vstupními parametry funkce jsou v registru EAX adresa hledané položky a v registru EDX ukazatel na kořen stromu. Registr EAX nemusí obsahovat platný ukazatel na uzel stromu. Je-li položka ve stromu nalezena, navrátí funkce vynulovaný příznak chyby CF. Není-li nalezena, navrátí nastavený příznak chyby CF. Na rozdíl od následujících funkcí nevrací tato funkce ukazatel na nalezený uzel, protože ten je shodný s obsahem registru EAX.
Funkce používá registry EBX a ECX, jejich obsahy jsou proto uchovány pomocí instrukcí PUSH/POP.
Na začátku funkce se do registru ECX připraví ukazatel na výchozí (kořenový) uzel stromu (z proměnné RBR_Node kořene stromu). Je-li ukazatel nulový, strom neobsahuje žádnou položku a funkce se předčasně ukončí s nastaveným příznakem chyby.
Jinak ukazuje ukazatel v ECX na platný uzel stromu. Ukazatel se uloží do registru EBX a obsah registru ECX se přednastaví na 0.
Nyní se porovná hodnota třídicího klíče - v tomto případě se jedná o hledanou adresu v registru EAX, která se porovná s adresou nalezeného uzlu v registru EBX. Jsou-li klíče shodné, funkce se úspěšně ukončí s vynulovaným příznakem chyby.
Nejsou-li klíče shodné, nastaví se podle výsledku porovnání obsah registru CL a to tak, že je-li klíč hledané položky větší, nastaví se obsah registru CL na hodnotu 1. Byl-li klíč hledané položky menší, bude mít registr CL hodnotu 0. Registr ECX je využit jako index do pole ukazatelů - pro menší hodnotu klíče (=0) je načten ukazatel RBN_Left, pro větší hodnotu klíče (=1) je načten ukazatel RBN_Right. Jedná-li se o platný ukazatel na další uzel stromu (tj. nenulový ukazatel), pokračuje funkce testováním dalšího uzlu. Jinak se funkce ukončí s nastaveným příznakem chyby.
|
Funkce RBTreeSrcW vyhledá v RB-stromu položku podle daných dat o velikosti slovo bez znaménka, která jsou uložena v proměnné RB_DataW uzlu stromu. Strom musí být tříděný podle obsahu položky RB_DataW bez znaménka, tj. všechny položky byly do stromu vkládány pomocí funkce RBTreeInsertW (viz dále - kapitola vkládání položek). Vstupními parametry funkce jsou v registru AX data hledané položky a v registru EDX ukazatel na kořen stromu. Je-li položka ve stromu nalezena, navrátí funkce vynulovaný příznak chyby CF a v registru EBX ukazatel na nalezenou položku stromu. Není-li nalezena, navrátí nastavený příznak chyby CF a registr EBX bude vynulovaný.
Funkce používá registr ECX, jeho obsah je proto uchován pomocí instrukcí PUSH/POP.
Na začátku funkce se do registru ECX připraví ukazatel na výchozí (kořenový) uzel stromu (z proměnné RBR_Node kořene stromu). Je-li ukazatel nulový, strom neobsahuje žádnou položku a funkce se předčasně ukončí s nastaveným příznakem chyby.
Jinak ukazuje ukazatel v ECX na platný uzel stromu. Ukazatel se uloží do registru EBX a obsah registru ECX se přednastaví na 0.
Nyní se porovná hodnota třídicího klíče - v tomto případě se jedná o data v registru AX, která se porovnají s obsahem proměnné RB_DataW v uzlu EBX. Jsou-li klíče shodné, funkce se úspěšně ukončí s vynulovaným příznakem chyby.
Nejsou-li klíče shodné, nastaví se podle výsledku porovnání obsah registru CL a to tak, že je-li klíč hledané položky větší, nastaví se obsah registru CL na hodnotu 1. Byl-li klíč hledané položky menší, bude mít registr CL hodnotu 0. Registr ECX je využit jako index do pole ukazatelů - pro menší hodnotu klíče (=0) je načten ukazatel RBN_Left, pro větší hodnotu klíče (=1) je načten ukazatel RBN_Right. Jedná-li se o platný ukazatel na další uzel stromu (tj. nenulový ukazatel), pokračuje funkce testováním dalšího uzlu. Jinak se funkce ukončí s nastaveným příznakem chyby a vynulovaným registrem EBX.
|
Funkce RBTreeSrcWS je obměnou funkce RBTreeSrcW - vyhledá v RB-stromu položku podle daných dat o velikosti slovo se znaménkem, která jsou uložena v proměnné RB_DataW uzlu stromu. Liší se pouze instrukcí "setg cl", která vybere ukazatel na pravého potomka v případě, že položka je větší při porovnání se znaménkem. Strom musí být tříděný podle obsahu položky RB_DataW se znaménkem, tj. všechny položky byly do stromu vkládány pomocí funkce RBTreeInsertWS (viz dále - kapitola vkládání položek).
|
Funkce RBTreeSrcDW vyhledá v RB-stromu položku podle daných dat o velikosti dvojslovo bez znaménka, která jsou uložena na offsetu RBN_Data uzlu stromu. Strom musí být tříděný podle obsahu položky RBN_Data bez znaménka, tj. všechny položky byly do stromu vkládány pomocí funkce RBTreeInsertDW (viz dále - kapitola vkládání položek). Vstupními parametry funkce jsou v registru EAX data hledané položky a v registru EDX ukazatel na kořen stromu. Je-li položka ve stromu nalezena, navrátí funkce vynulovaný příznak chyby CF a v registru EBX ukazatel na nalezenou položku stromu. Není-li nalezena, navrátí nastavený příznak chyby CF a registr EBX bude vynulovaný.
Funkce používá registr ECX, jeho obsah je proto uchován pomocí instrukcí PUSH/POP.
Na začátku funkce se do registru ECX připraví ukazatel na výchozí (kořenový) uzel stromu (z proměnné RBR_Node kořene stromu). Je-li ukazatel nulový, strom neobsahuje žádnou položku a funkce se předčasně ukončí s nastaveným příznakem chyby.
Jinak ukazuje ukazatel v ECX na platný uzel stromu. Ukazatel se uloží do registru EBX a obsah registru ECX se přednastaví na 0.
Nyní se porovná hodnota třídicího klíče - v tomto případě se jedná o data v registru EAX, která se porovnají s obsahem dvojslova na offsetu RBN_Data v uzlu EBX. Jsou-li klíče shodné, funkce se úspěšně ukončí s vynulovaným příznakem chyby.
Nejsou-li klíče shodné, nastaví se podle výsledku porovnání obsah registru CL a to tak, že je-li klíč hledané položky větší, nastaví se obsah registru CL na hodnotu 1. Byl-li klíč hledané položky menší, bude mít registr CL hodnotu 0. Registr ECX je využit jako index do pole ukazatelů - pro menší hodnotu klíče (=0) je načten ukazatel RBN_Left, pro větší hodnotu klíče (=1) je načten ukazatel RBN_Right. Jedná-li se o platný ukazatel na další uzel stromu (tj. nenulový ukazatel), pokračuje funkce testováním dalšího uzlu. Jinak se funkce ukončí s nastaveným příznakem chyby a vynulovaným registrem EBX.
|
Funkce RBTreeSrcDWS je obměnou funkce RBTreeSrcDW - vyhledá v RB-stromu položku podle daných dat o velikosti dvojslovo se znaménkem, která jsou uložena na offsetu RBN_Data uzlu stromu. Liší se pouze instrukcí "setg cl", která vybere ukazatel na pravého potomka v případě, že položka je větší při porovnání se znaménkem. Strom musí být tříděný podle obsahu položky RBN_Data se znaménkem, tj. všechny položky byly do stromu vkládány pomocí funkce RBTreeInsertDWS (viz dále - kapitola vkládání položek).
|
Funkce RBTreeSrcFnc vyhledá v RB-stromu položku podle obecného klíče a porovnávací callback funkce. Strom musí být tříděný podle stejného klíče, tj. všechny položky byly do stromu vkládány pomocí funkce RBTreeInsert se stejnou porovnávací funkcí (viz dále - kapitola vkládání položek). Vstupními parametry funkce jsou v registru EAX uživatelská data hledané položky (může to být např. ukazatel na uzel s hledanými daty), v registru EDX ukazatel na kořen stromu a v registru ESI ukazatel na porovnávací callback funkci. Je-li položka ve stromu nalezena, navrátí funkce vynulovaný příznak chyby CF a v registru EBX ukazatel na nalezenou položku stromu. Není-li nalezena, navrátí nastavený příznak chyby CF a registr EBX bude vynulovaný.
Porovnávací callback funkce má jako vstupní parametr v registru EAX uživatelská data hledané položky (může to být např. ukazatel na uzel s hledanými daty) a v registru EBX ukazatel na testovanou položku. Porovnávací funkce navrací nastavené příznaky tak, jako by to udělala porovnávací instrukce - jsou-li položky shodné, navrátí nastavený příznak ZF a vynulovaný příznak CF. Je-li hledaný klíč menší než porovnávaná položka, navrátí vynulovaný příznak ZF a nastavený příznak CF. Je-li hledaný klíč větší, navrátí vynulovaný příznak ZF i příznak CF.
Funkce používá registr ECX, jeho obsah je proto uchován pomocí instrukcí PUSH/POP.
Na začátku funkce se do registru ECX připraví ukazatel na výchozí (kořenový) uzel stromu (z proměnné RBR_Node kořene stromu). Je-li ukazatel nulový, strom neobsahuje žádnou položku a funkce se předčasně ukončí s nastaveným příznakem chyby.
Jinak ukazuje ukazatel v ECX na platný uzel stromu. Ukazatel se uloží do registru EBX a obsah registru ECX se přednastaví na 0.
Nyní se porovná hodnota třídicího klíče - v tomto případě se zavolá porovnávací callback funkce, jejíž adresa je v registru ESI. Jsou-li klíče shodné, funkce se úspěšně ukončí s vynulovaným příznakem chyby.
Nejsou-li klíče shodné, nastaví se podle výsledku porovnání obsah registru CL a to tak, že je-li klíč hledané položky větší, nastaví se obsah registru CL na hodnotu 1. Byl-li klíč hledané položky menší, bude mít registr CL hodnotu 0. Registr ECX je využit jako index do pole ukazatelů - pro menší hodnotu klíče (=0) je načten ukazatel RBN_Left, pro větší hodnotu klíče (=1) je načten ukazatel RBN_Right. Jedná-li se o platný ukazatel na další uzel stromu (tj. nenulový ukazatel), pokračuje funkce testováním dalšího uzlu. Jinak se funkce ukončí s nastaveným příznakem chyby a vynulovaným registrem EBX.
|
Funkce RBTreeSrcHigh vyhledá v RB-stromu nejbližší vyšší položku podle obecného klíče a porovnávací callback funkce. Strom musí být tříděný podle stejného klíče, tj. všechny položky byly do stromu vkládány pomocí funkce RBTreeInsert se stejnou porovnávací funkcí (viz dále - kapitola vkládání položek). Vstupními parametry funkce jsou v registru EAX uživatelská data hledané položky (může to být např. ukazatel na uzel s hledanými daty), v registru EDX ukazatel na kořen stromu a v registru ESI ukazatel na porovnávací callback funkci. Je-li položka ve stromu nalezena (nebo je nalezena nejbližší vyšší položka), navrátí funkce vynulovaný příznak chyby CF a v registru EBX ukazatel na nalezenou položku stromu. Není-li nalezena, navrátí nastavený příznak chyby CF a registr EBX bude vynulovaný.
Porovnávací callback funkce má jako vstupní parametr v registru EAX uživatelská data hledané položky (může to být např. ukazatel na uzel s hledanými daty) a v registru EBX ukazatel na testovanou položku. Porovnávací funkce navrací nastavené příznaky tak, jako by to udělala porovnávací instrukce - jsou-li položky shodné, navrátí nastavený příznak ZF a vynulovaný příznak CF. Je-li hledaný klíč menší než porovnávaná položka, navrátí vynulovaný příznak ZF a nastavený příznak CF. Je-li hledaný klíč větší, navrátí vynulovaný příznak ZF i příznak CF.
Funkce RBTreeSrcHigh používá registry ECX a EDI, jejich obsahy jsou proto uchovány pomocí instrukcí PUSH/POP.
Na začátku funkce se vynuluje registr EDI jako příznak, že nejbližší položka nebyla dosud nalezena. Do registru ECX se připraví ukazatel na výchozí (kořenový) uzel stromu (z proměnné RBR_Node kořene stromu). Je-li ukazatel nulový, strom neobsahuje žádnou položku a funkce se předčasně ukončí s nastaveným příznakem chyby.
Jinak ukazuje ukazatel v ECX na platný uzel stromu. Ukazatel se uloží do registru EBX a obsah registru ECX se přednastaví na 0.
Nyní se porovná hodnota třídicího klíče - v tomto případě se zavolá porovnávací callback funkce, jejíž adresa je v registru ESI. Jsou-li klíče shodné, funkce se úspěšně ukončí s vynulovaným příznakem chyby. Je-li hledaný klíč menší, uchová se adresa položky do registru EDI. Využívá se přitom faktu, že hledání se dostává postupnými iteracemi stále blíže k hledané hodnotě, takže každá nově nalezená větší položka leží blíže k hledané hodnotě.
Nejsou-li klíče shodné, nastaví se podle výsledku porovnání obsah registru CL a to tak, že je-li klíč hledané položky větší, nastaví se obsah registru CL na hodnotu 1. Byl-li klíč hledané položky menší, bude mít registr CL hodnotu 0. Registr ECX je využit jako index do pole ukazatelů - pro menší hodnotu klíče (=0) je načten ukazatel RBN_Left, pro větší hodnotu klíče (=1) je načten ukazatel RBN_Right. Jedná-li se o platný ukazatel na další uzel stromu (tj. nenulový ukazatel), pokračuje funkce testováním dalšího uzlu.
Není-li nalezen další uzel, použije se obsah registru EDI s uschovaným ukazatelem na nejbližší uzel jako výsledek operace. Příznak chyby CF se nastaví v případě, že ukazatel má nulovou hodnotu, tj. nebyl nalezen žádný nejbližší vyšší uzel.
|
Funkce RBTreeSrcLow vyhledá v RB-stromu nejbližší nižší položku podle obecného klíče a porovnávací callback funkce. Strom musí být tříděný podle stejného klíče, tj. všechny položky byly do stromu vkládány pomocí funkce RBTreeInsert se stejnou porovnávací funkcí (viz dále - kapitola vkládání položek). Vstupními parametry funkce jsou v registru EAX uživatelská data hledané položky (může to být např. ukazatel na uzel s hledanými daty), v registru EDX ukazatel na kořen stromu a v registru ESI ukazatel na porovnávací callback funkci. Je-li položka ve stromu nalezena (nebo je nalezena nejbližší nižší položka), navrátí funkce vynulovaný příznak chyby CF a v registru EBX ukazatel na nalezenou položku stromu. Není-li nalezena, navrátí nastavený příznak chyby CF a registr EBX bude vynulovaný.
Porovnávací callback funkce má jako vstupní parametr v registru EAX uživatelská data hledané položky (může to být např. ukazatel na uzel s hledanými daty) a v registru EBX ukazatel na testovanou položku. Porovnávací funkce navrací nastavené příznaky tak, jako by to udělala porovnávací instrukce - jsou-li položky shodné, navrátí nastavený příznak ZF a vynulovaný příznak CF. Je-li hledaný klíč menší než porovnávaná položka, navrátí vynulovaný příznak ZF a nastavený příznak CF. Je-li hledaný klíč větší, navrátí vynulovaný příznak ZF i příznak CF.
Funkce RBTreeSrcLow používá registry ECX a EDI, jejich obsahy jsou proto uchovány pomocí instrukcí PUSH/POP.
Na začátku funkce se vynuluje registr EDI jako příznak, že nejbližší položka nebyla dosud nalezena. Do registru ECX se připraví ukazatel na výchozí (kořenový) uzel stromu (z proměnné RBR_Node kořene stromu). Je-li ukazatel nulový, strom neobsahuje žádnou položku a funkce se předčasně ukončí s nastaveným příznakem chyby.
Jinak ukazuje ukazatel v ECX na platný uzel stromu. Ukazatel se uloží do registru EBX a obsah registru ECX se přednastaví na 0.
Nyní se porovná hodnota třídicího klíče - v tomto případě se zavolá porovnávací callback funkce, jejíž adresa je v registru ESI. Jsou-li klíče shodné, funkce se úspěšně ukončí s vynulovaným příznakem chyby. Je-li hledaný klíč větší, uchová se adresa položky do registru EDI. Využívá se přitom faktu, že hledání se dostává postupnými iteracemi stále blíže k hledané hodnotě, takže každá nově nalezená menší položka leží blíže k hledané hodnotě.
Nejsou-li klíče shodné, nastaví se podle výsledku porovnání obsah registru CL a to tak, že je-li klíč hledané položky větší, nastaví se obsah registru CL na hodnotu 1. Byl-li klíč hledané položky menší, bude mít registr CL hodnotu 0. Registr ECX je využit jako index do pole ukazatelů - pro menší hodnotu klíče (=0) je načten ukazatel RBN_Left, pro větší hodnotu klíče (=1) je načten ukazatel RBN_Right. Jedná-li se o platný ukazatel na další uzel stromu (tj. nenulový ukazatel), pokračuje funkce testováním dalšího uzlu.
Není-li nalezen další uzel, použije se obsah registru EDI s uschovaným ukazatelem na nejbližší uzel jako výsledek operace. Příznak chyby CF se nastaví v případě, že ukazatel má nulovou hodnotu, tj. nebyl nalezen žádný nejbližší nižší uzel.
Obsah / Utility / RBTREE / Prohledávání RB-stromu
