<!DOCTYPE html> <html> <head> </head> <body> <dl style="line-height: 1.5; margin-left: 2em"> <dt style="clear: both; float: left; font-weight: bold; width: 8em">Author</dt> <dd style="margin-left: 8.5em">susumu.yata <susum****@gmail*****></dd> <dt style="clear: both; float: left; font-weight: bold; width: 8em">Date</dt> <dd style="margin-left: 8.5em">2013-06-24 16:33:41 +0900 (Mon, 24 Jun 2013)</dd> <dt style="clear: both; float: left; font-weight: bold; width: 8em">New Revision</dt> <dd style="margin-left: 8.5em"><a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f">0b09d5b8a6673564aa22b83955337939d392814f</a></dd> <dt style="clear: both; float: left; font-weight: bold; width: 8em">Message</dt> <dd style="margin-left: 8.5em"><pre style="border: 1px solid #aaa; font-family: Consolas, Menlo, "Liberation Mono", Courier, monospace; line-height: 1.2; padding: 0.5em; width: auto">Use a history to make grnxx::map::Patricia::add() fast.</pre></dd> <dt style="clear: both; float: left; font-weight: bold; width: 8em">Modified files</dt> <dd style="margin-left: 8.5em"> <ul> <li><a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#diff-0">lib/grnxx/map/patricia.cpp</a></li> </ul> </dd> </dl> <div class="diff-section" style="clear: both"> <table style="border-collapse: collapse; border: 1px solid #aaa"> <thead> <tr class="diff-header" style="border: 1px solid #aaa"> <td colspan="3"> <pre style="border: 0; font-family: Consolas, Menlo, "Liberation Mono", Courier, monospace; line-height: 1.2; margin: 0; padding: 0.5em; white-space: normal; width: auto"> Modified: lib/grnxx/map/patricia.cpp (+132 -122) =================================================================== </pre> </td> </tr> </thead> <tbody> <tr> <th class="diff-line-number" style="border: 1px solid #aaa"> <pre style="border: 0; font-family: Consolas, Menlo, "Liberation Mono", Courier, monospace; line-height: 1.2; margin: 0; padding: 0.5em; white-space: normal; width: auto"><a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L674">...</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L675">675</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L676">676</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L677">677</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L678">678</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L679">679</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L680">680</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L681">681</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L682">682</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L683">683</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L684">684</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L685">685</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L686">686</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L687">687</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L688">688</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L689">689</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L690">690</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L691">691</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L692">692</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L693">693</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L694">694</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L695">695</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L696">696</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L697">697</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L698">698</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L699">699</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L700">700</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L701">701</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L702">702</a>                                                   <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L703">703</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L704">704</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L705">705</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L706">706</a>       <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L707">707</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L708">708</a>             <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L709">709</a>   <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L710">710</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L711">711</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L712">712</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L713">713</a>                 <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L714">714</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L715">715</a>   <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L716">716</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L717">717</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L718">718</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L725">...</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L726">726</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L727">727</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L728">728</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L729">729</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L730">730</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L731">731</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L732">732</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L733">733</a>   <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L734">734</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L735">735</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L736">736</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L737">...</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L738">738</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L739">739</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L740">740</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L741">741</a>                                                     <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L742">742</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L743">743</a>                                                                                 <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L744">744</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L745">745</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L746">746</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L747">747</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L748">748</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L749">749</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L750">750</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L751">751</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L752">752</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L753">753</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L754">754</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L755">755</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L756">756</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L757">757</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L758">758</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L759">759</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L760">760</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L761">761</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L762">762</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L763">763</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L764">764</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L765">765</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L766">766</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L767">767</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L768">768</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L769">769</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L770">770</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L771">771</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L772">772</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L773">773</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L774">774</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L775">775</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L776">776</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L777">777</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L778">778</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L779">779</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L780">780</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L781">781</a>                     <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L782">782</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L783">783</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L784">784</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L785">785</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L786">786</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L787">787</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L788">788</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L789">789</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L790">790</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L791">791</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L792">792</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L793">793</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L794">794</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L795">795</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L796">796</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L797">797</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L798">798</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L799">799</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L800">800</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L801">801</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L802">802</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L803">803</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L804">804</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L805">805</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L806">806</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L807">807</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L808">808</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L809">809</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L810">810</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L811">811</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L812">812</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L813">813</a>       <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L814">814</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L815">815</a>   <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L816">816</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L817">817</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L818">818</a>     <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L819">819</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L820">820</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L821">821</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L823">...</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L824">824</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L825">825</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L826">826</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L827">827</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L828">828</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L829">829</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L830">830</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L831">831</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L832">832</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L833">833</a>     <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L834">834</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L835">835</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L836">836</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L837">837</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L838">838</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L839">839</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L840">840</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L841">841</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L842">842</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L843">843</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L844">844</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L845">845</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L846">846</a>     <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L847">847</a>   <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L848">848</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L849">849</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0L850">850</a> </pre> </th> <th class="diff-line-number" style="border: 1px solid #aaa"> <pre style="border: 0; font-family: Consolas, Menlo, "Liberation Mono", Courier, monospace; line-height: 1.2; margin: 0; padding: 0.5em; white-space: normal; width: auto"><a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R674">...</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R675">675</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R676">676</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R677">677</a>   <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R678">678</a>                                               <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R679">679</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R680">680</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R681">681</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R682">682</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R683">683</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R684">684</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R685">685</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R686">686</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R687">687</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R688">688</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R689">689</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R690">690</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R691">691</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R692">692</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R693">693</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R694">694</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R695">695</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R696">696</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R697">697</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R698">698</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R699">699</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R700">700</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R701">701</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R702">702</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R703">703</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R704">704</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R705">705</a>     <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R706">706</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R707">707</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R708">708</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R709">709</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R710">710</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R711">711</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R712">712</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R713">713</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R714">714</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R715">715</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R716">716</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R717">717</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R718">718</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R719">719</a>       <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R720">720</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R721">721</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R722">722</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R723">723</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R724">724</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R725">725</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R726">726</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R727">727</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R728">728</a>   <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R729">729</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R730">730</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R731">731</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R732">732</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R739">...</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R740">740</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R741">741</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R742">742</a>           <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R743">743</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R744">744</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R745">745</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R746">746</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R747">...</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R748">748</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R749">749</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R750">750</a>   <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R751">751</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R752">752</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R753">753</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R754">754</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R755">755</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R756">756</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R757">757</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R758">758</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R759">759</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R760">760</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R761">761</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R762">762</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R763">763</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R764">764</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R765">765</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R766">766</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R767">767</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R768">768</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R769">769</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R770">770</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R771">771</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R772">772</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R773">773</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R774">774</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R775">775</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R776">776</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R777">777</a>   <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R778">778</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R779">779</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R780">780</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R781">781</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R782">782</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R783">783</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R784">784</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R785">785</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R786">786</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R787">787</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R788">788</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R789">789</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R790">790</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R791">791</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R792">792</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R793">793</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R794">794</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R795">795</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R796">796</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R797">797</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R798">798</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R799">799</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R800">800</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R801">801</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R802">802</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R803">803</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R804">804</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R805">805</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R806">806</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R807">807</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R808">808</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R809">809</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R810">810</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R811">811</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R812">812</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R813">813</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R814">814</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R815">815</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R816">816</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R817">817</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R818">818</a>                                                                           <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R819">819</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R820">820</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R821">821</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R822">822</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R823">823</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R824">824</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R825">825</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R826">826</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R827">827</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R828">828</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R829">829</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R830">830</a>                                                             <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R831">831</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R832">832</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R833">833</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R834">834</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R835">835</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R836">836</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R837">837</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R838">838</a>   <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R839">839</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R840">840</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R841">841</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R842">842</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R843">843</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R845">...</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R846">846</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R847">847</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R848">848</a>               <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R849">849</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R850">850</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R851">851</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R852">852</a>   <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R853">853</a>                   <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R854">854</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R855">855</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R856">856</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R857">857</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R858">858</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R859">859</a> <a href="https://github.com/groonga/grnxx/commit/0b09d5b8a6673564aa22b83955337939d392814f#L0R860">860</a> </pre> </th> <td class="diff-content" style="border: 1px solid #aaa"> <pre style="border: 0; font-family: Consolas, Menlo, "Liberation Mono", Courier, monospace; line-height: 1.2; margin: 0; padding: 0.5em; white-space: normal; width: auto">@@ -675,44 +675,58 @@ bool Patricia<Bytes>::find(KeyArg key, int64_t *key_id) { } bool Patricia<Bytes>::add(KeyArg key, int64_t *key_id) { - const uint64_t bit_size = key.size() * 8; uint64_t node_id = ROOT_NODE_ID; - Node * node; - for (node = nodes_->get_pointer(node_id); - node && (node->status() != NODE_LEAF); - node = nodes_->get_pointer(node_id)) { - switch (node->status()) { - case NODE_DEAD: { - // The patricia is empty. - int64_t next_key_id; - if (!keys_->add(key, &next_key_id)) { - // Error. - return false; - } - *node = Node::leaf_node(next_key_id); - if (key_id) { - *key_id = next_key_id; - } - return true; - } - case NODE_BRANCH: { - node_id = node->offset(); - if (node->bit_pos() < bit_size) { - node_id += get_ith_bit(key, node->bit_pos()); - } + Node *node = nodes_->get_pointer(node_id); + if (!node) { + // Error. + return false; + } + if (node->status() == NODE_DEAD) { + // The patricia is empty. + int64_t next_key_id; + if (!keys_->add(key, &next_key_id)) { + // Error. + return false; + } + *node = Node::leaf_node(next_key_id); + if (key_id) { + *key_id = next_key_id; + } + return true; + } + const uint64_t bit_size = key.size() * 8; + Node *history[8]; + int depth = 0; + history[0] = node; + while (node->status() != NODE_LEAF) { + if (node->status() == NODE_BRANCH) { + if (node->bit_pos() >= bit_size) { break; } - case NODE_TERMINAL: { - node_id = node->offset() + (node->bit_size() < bit_size); + node_id = node->offset() + get_ith_bit(key, node->bit_pos()); + } else { + if (node->bit_size() >= bit_size) { break; } + node_id = node->offset() + 1; + } + node = nodes_->get_pointer(node_id); + if (!node) { + // Error. + return false; } + history[++depth % 8] = node; } - if (!node) { - // Error. - return false; + // Find a leaf node. + while (node->status() != NODE_LEAF) { + node_id = node->offset(); + node = nodes_->get_pointer(node_id); + if (!node) { + // Error. + return false; + } } - // "node" points to a leaf node. + // Count the number of the common prefix bits. Key stored_key; if (!keys_->get_key(node->key_id(), &stored_key)) { // Error. @@ -726,11 +740,7 @@ bool Patricia<Bytes>::add(KeyArg key, int64_t *key_id) { break; } } - if (count < min_size) { - const uint8_t diff = key[count] ^ stored_key[count]; - count *= 8; - count += 7 - bit_scan_reverse(diff); - } else { + if (count == min_size) { if (key.size() == stored_key.size()) { // Found. if (key_id) { @@ -738,84 +748,96 @@ bool Patricia<Bytes>::add(KeyArg key, int64_t *key_id) { } return false; } - count *= 8; + node = history[depth % 8]; + Node * const next_nodes = nodes_->get_pointer(header_->next_node_id); + if (!next_nodes) { + return false; + } + int64_t next_key_id; + if (!keys_->add(key, &next_key_id)) { + // Error. + return false; + } + if (count == key.size()) { + // "key" is a prefix of "stored_key". + next_nodes[0] = Node::leaf_node(next_key_id); + next_nodes[1] = *node; + *node = Node::terminal_node(count * 8, header_->next_node_id); + } else { + // "stored_key" is a prefix of "key". + next_nodes[0] = *node; + next_nodes[1] = Node::leaf_node(next_key_id); + *node = Node::terminal_node(count * 8, header_->next_node_id); + } + header_->next_node_id += 2; + if (key_id) { + *key_id = next_key_id; + } + return true; } - Node * const next_nodes = nodes_->get_pointer(header_->next_node_id); + count = (count * 8) + 7 - bit_scan_reverse(key[count] ^ stored_key[count]); + // Find the branching point in "history". + int min_depth = (depth < 8) ? 0 : depth - 7; + while (--depth >= min_depth) { + node = history[depth % 8]; + if (node->status() == NODE_BRANCH) { + if (node->bit_pos() < count) { + break; + } + } else if (node->bit_size() < count) { + break; + } + } + if (depth >= min_depth) { + // The branching point exists in "history". + node = history[(depth + 1) % 8]; + Node * const next_nodes = nodes_->get_pointer(header_->next_node_id); + if (!next_nodes) { + return false; + } + int64_t next_key_id; + if (!keys_->add(key, &next_key_id)) { + // Error. + return false; + } + if (get_ith_bit(key, count)) { + next_nodes[0] = *node; + next_nodes[1] = Node::leaf_node(next_key_id); + } else { + next_nodes[0] = Node::leaf_node(next_key_id); + next_nodes[1] = *node; + } + *node = Node::branch_node(count, header_->next_node_id); + header_->next_node_id += 2; + if (key_id) { + *key_id = next_key_id; + } + return true; + } + // Find the branching point with the naive method. node_id = ROOT_NODE_ID; - for (node = nodes_->get_pointer(node_id); - node && (node->status() != NODE_LEAF); - node = nodes_->get_pointer(node_id)) { - switch (node->status()) { - case NODE_BRANCH: { - if (count <= node->bit_pos()) { - int64_t next_key_id; - if (!keys_->add(key, &next_key_id)) { - // Error. - return false; - } - if (count == bit_size) { - // Create a terminal node. - next_nodes[0] = Node::leaf_node(next_key_id); - next_nodes[1] = *node; - *node = Node::terminal_node(count, header_->next_node_id); - } else { - // Create a branch node. - if (get_ith_bit(key, count)) { - next_nodes[0] = *node; - next_nodes[1] = Node::leaf_node(next_key_id); - } else { - next_nodes[0] = Node::leaf_node(next_key_id); - next_nodes[1] = *node; - } - *node = Node::branch_node(count, header_->next_node_id); - } - header_->next_node_id += 2; - if (key_id) { - *key_id = next_key_id; - } - return true; - } - node_id = node->offset(); - if (node->bit_pos() < count) { - node_id += get_ith_bit(key, node->bit_pos()); - } + for ( ; ; ) { + node = nodes_->get_pointer(node_id); + if (!node) { + // Error. + return false; + } + if (node->status() == NODE_LEAF) { + break; + } else if (node->status() == NODE_BRANCH) { + if (node->bit_pos() >= count) { break; } - case NODE_TERMINAL: { - if (count < node->bit_size()) { - int64_t next_key_id; - if (!keys_->add(key, &next_key_id)) { - // Error. - return false; - } - if (count == bit_size) { - // Create a terminal node. - next_nodes[0] = Node::leaf_node(next_key_id); - next_nodes[1] = *node; - *node = Node::terminal_node(count, header_->next_node_id); - } else { - // Create a branch node. - if (get_ith_bit(key, count)) { - next_nodes[0] = *node; - next_nodes[1] = Node::leaf_node(next_key_id); - } else { - next_nodes[0] = Node::leaf_node(next_key_id); - next_nodes[1] = *node; - } - *node = Node::branch_node(count, header_->next_node_id); - } - header_->next_node_id += 2; - if (key_id) { - *key_id = next_key_id; - } - return true; - } - node_id = node->offset() + (node->bit_size() < bit_size); + node_id = node->offset() + get_ith_bit(key, node->bit_pos()); + } else { + if (node->bit_size() > count) { break; } + node_id = node->offset() + 1; } } - if (!node) { + Node * const next_nodes = nodes_->get_pointer(header_->next_node_id); + if (!next_nodes) { // Error. return false; } @@ -824,27 +846,15 @@ bool Patricia<Bytes>::add(KeyArg key, int64_t *key_id) { // Error. return false; } - if (count == bit_size) { - // Create a terminal node. - next_nodes[0] = Node::leaf_node(next_key_id); - next_nodes[1] = *node; - *node = Node::terminal_node(count, header_->next_node_id); - } else if (count == (stored_key.size() * 8)) { - // Create a terminal node. + // Create a branch node. + if (get_ith_bit(key, count)) { next_nodes[0] = *node; next_nodes[1] = Node::leaf_node(next_key_id); - *node = Node::terminal_node(count, header_->next_node_id); } else { - // Create a branch node. - if (get_ith_bit(key, count)) { - next_nodes[0] = *node; - next_nodes[1] = Node::leaf_node(next_key_id); - } else { - next_nodes[0] = Node::leaf_node(next_key_id); - next_nodes[1] = *node; - } - *node = Node::branch_node(count, header_->next_node_id); + next_nodes[0] = Node::leaf_node(next_key_id); + next_nodes[1] = *node; } + *node = Node::branch_node(count, header_->next_node_id); header_->next_node_id += 2; if (key_id) { *key_id = next_key_id; </pre> </td> </tr> </tbody> </table> </div> </body> </html>