<!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-21 13:42:54 +0900 (Fri, 21 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/e983146b63b70db4167e1e17f84889e451b12713">e983146b63b70db4167e1e17f84889e451b12713</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">Update grnxx::map::Patricia to support grnxx::GeoPoint.</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/e983146b63b70db4167e1e17f84889e451b12713#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"><span class="diff-header" style="background-color: #eaf2f5; color: #999999; display: block; white-space: pre"> Modified: lib/grnxx/map/patricia.cpp (+13 -6)</span>
<span class="diff-header-mark" style="background-color: #eaf2f5; color: #999999; display: block; white-space: pre">===================================================================</span>
</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"><span class="diff-line-number-hunk-header" style="display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0L438">...</a></span>
<span class="diff-line-number-not-changed" style="display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0L439">439</a></span>
<span class="diff-line-number-not-changed" style="display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0L440">440</a></span>
<span class="diff-line-number-not-changed" style="display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0L441">441</a></span>
<span class="diff-line-number-deleted" style="background-color: #ffaaaa; color: #000000; display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0L442">442</a></span>
<span class="diff-line-number-deleted" style="background-color: #ffaaaa; color: #000000; display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0L443">443</a></span>
<span class="diff-line-number-nothing" style="display: block; white-space: pre"> </span>
<span class="diff-line-number-nothing" style="display: block; white-space: pre"> </span>
<span class="diff-line-number-nothing" style="display: block; white-space: pre"> </span>
<span class="diff-line-number-not-changed" style="display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0L444">444</a></span>
<span class="diff-line-number-not-changed" style="display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0L445">445</a></span>
<span class="diff-line-number-not-changed" style="display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0L446">446</a></span>
<span class="diff-line-number-not-changed" style="display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0L447">447</a></span>
<span class="diff-line-number-not-changed" style="display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0L448">448</a></span>
<span class="diff-line-number-deleted" style="background-color: #ffaaaa; color: #000000; display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0L449">449</a></span>
<span class="diff-line-number-deleted" style="background-color: #ffaaaa; color: #000000; display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0L450">450</a></span>
<span class="diff-line-number-nothing" style="display: block; white-space: pre"> </span>
<span class="diff-line-number-nothing" style="display: block; white-space: pre"> </span>
<span class="diff-line-number-not-changed" style="display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0L451">451</a></span>
<span class="diff-line-number-not-changed" style="display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0L452">452</a></span>
<span class="diff-line-number-not-changed" style="display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0L453">453</a></span>
<span class="diff-line-number-hunk-header" style="display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0L469">...</a></span>
<span class="diff-line-number-not-changed" style="display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0L470">470</a></span>
<span class="diff-line-number-not-changed" style="display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0L471">471</a></span>
<span class="diff-line-number-not-changed" style="display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0L472">472</a></span>
<span class="diff-line-number-deleted" style="background-color: #ffaaaa; color: #000000; display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0L473">473</a></span>
<span class="diff-line-number-deleted" style="background-color: #ffaaaa; color: #000000; display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0L474">474</a></span>
<span class="diff-line-number-nothing" style="display: block; white-space: pre"> </span>
<span class="diff-line-number-nothing" style="display: block; white-space: pre"> </span>
<span class="diff-line-number-nothing" style="display: block; white-space: pre"> </span>
<span class="diff-line-number-nothing" style="display: block; white-space: pre"> </span>
<span class="diff-line-number-nothing" style="display: block; white-space: pre"> </span>
<span class="diff-line-number-nothing" style="display: block; white-space: pre"> </span>
<span class="diff-line-number-nothing" style="display: block; white-space: pre"> </span>
<span class="diff-line-number-nothing" style="display: block; white-space: pre"> </span>
<span class="diff-line-number-not-changed" style="display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0L475">475</a></span>
<span class="diff-line-number-not-changed" style="display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0L476">476</a></span>
<span class="diff-line-number-not-changed" style="display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0L477">477</a></span>
</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"><span class="diff-line-number-hunk-header" style="display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0R438">...</a></span>
<span class="diff-line-number-not-changed" style="display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0R439">439</a></span>
<span class="diff-line-number-not-changed" style="display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0R440">440</a></span>
<span class="diff-line-number-not-changed" style="display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0R441">441</a></span>
<span class="diff-line-number-nothing" style="display: block; white-space: pre"> </span>
<span class="diff-line-number-nothing" style="display: block; white-space: pre"> </span>
<span class="diff-line-number-added" style="background-color: #aaffaa; color: #000000; display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0R442">442</a></span>
<span class="diff-line-number-added" style="background-color: #aaffaa; color: #000000; display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0R443">443</a></span>
<span class="diff-line-number-added" style="background-color: #aaffaa; color: #000000; display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0R444">444</a></span>
<span class="diff-line-number-not-changed" style="display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0R445">445</a></span>
<span class="diff-line-number-not-changed" style="display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0R446">446</a></span>
<span class="diff-line-number-not-changed" style="display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0R447">447</a></span>
<span class="diff-line-number-not-changed" style="display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0R448">448</a></span>
<span class="diff-line-number-not-changed" style="display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0R449">449</a></span>
<span class="diff-line-number-nothing" style="display: block; white-space: pre"> </span>
<span class="diff-line-number-nothing" style="display: block; white-space: pre"> </span>
<span class="diff-line-number-added" style="background-color: #aaffaa; color: #000000; display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0R450">450</a></span>
<span class="diff-line-number-added" style="background-color: #aaffaa; color: #000000; display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0R451">451</a></span>
<span class="diff-line-number-not-changed" style="display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0R452">452</a></span>
<span class="diff-line-number-not-changed" style="display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0R453">453</a></span>
<span class="diff-line-number-not-changed" style="display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0R454">454</a></span>
<span class="diff-line-number-hunk-header" style="display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0R470">...</a></span>
<span class="diff-line-number-not-changed" style="display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0R471">471</a></span>
<span class="diff-line-number-not-changed" style="display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0R472">472</a></span>
<span class="diff-line-number-not-changed" style="display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0R473">473</a></span>
<span class="diff-line-number-nothing" style="display: block; white-space: pre"> </span>
<span class="diff-line-number-nothing" style="display: block; white-space: pre"> </span>
<span class="diff-line-number-added" style="background-color: #aaffaa; color: #000000; display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0R474">474</a></span>
<span class="diff-line-number-added" style="background-color: #aaffaa; color: #000000; display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0R475">475</a></span>
<span class="diff-line-number-added" style="background-color: #aaffaa; color: #000000; display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0R476">476</a></span>
<span class="diff-line-number-added" style="background-color: #aaffaa; color: #000000; display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0R477">477</a></span>
<span class="diff-line-number-added" style="background-color: #aaffaa; color: #000000; display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0R478">478</a></span>
<span class="diff-line-number-added" style="background-color: #aaffaa; color: #000000; display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0R479">479</a></span>
<span class="diff-line-number-added" style="background-color: #aaffaa; color: #000000; display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0R480">480</a></span>
<span class="diff-line-number-added" style="background-color: #aaffaa; color: #000000; display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0R481">481</a></span>
<span class="diff-line-number-not-changed" style="display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0R482">482</a></span>
<span class="diff-line-number-not-changed" style="display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0R483">483</a></span>
<span class="diff-line-number-not-changed" style="display: block; white-space: pre"><a href="https://github.com/groonga/grnxx/commit/e983146b63b70db4167e1e17f84889e451b12713#L0R484">484</a></span>
</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"><span class="diff-hunk-header" style="background-color: #eaf2f5; color: #999999; display: block; white-space: pre">@@ -439,15 +439,16 @@ <span class="diff-context" style="background-color: #ffffaa; color: #000000">uint64_t Patricia<T>::get_ith_bit(KeyArg key, uint64_t bit_pos) {</span></span>
<span class="diff-not-changed" style="display: block; white-space: pre"> </span>
<span class="diff-not-changed" style="display: block; white-space: pre"> template <></span>
<span class="diff-not-changed" style="display: block; white-space: pre"> uint64_t Patricia<double>::get_ith_bit(KeyArg key, uint64_t bit_pos) {</span>
<span class="diff-deleted" style="background-color: #ffaaaa; color: #000000; display: block; white-space: pre">- int64_t x = *reinterpret_cast<const int64_t *>(&key);</span>
<span class="diff-deleted" style="background-color: #ffaaaa; color: #000000; display: block; white-space: pre">- x ^= (x >> 63) | (1ULL << 63);</span>
<span class="diff-added" style="background-color: #aaffaa; color: #000000; display: block; white-space: pre">+ constexpr uint64_t MASK[2] = { 1ULL << 63, ~0ULL };</span>
<span class="diff-added" style="background-color: #aaffaa; color: #000000; display: block; white-space: pre">+ uint64_t x = *reinterpret_cast<const uint64_t *>(&key);</span>
<span class="diff-added" style="background-color: #aaffaa; color: #000000; display: block; white-space: pre">+ x ^= MASK[x >> 63];</span>
<span class="diff-not-changed" style="display: block; white-space: pre"> return (x >> ((sizeof(Key) * 8) - 1 - bit_pos)) & 1;</span>
<span class="diff-not-changed" style="display: block; white-space: pre"> }</span>
<span class="diff-not-changed" style="display: block; white-space: pre"> </span>
<span class="diff-not-changed" style="display: block; white-space: pre"> template <></span>
<span class="diff-not-changed" style="display: block; white-space: pre"> uint64_t Patricia<GeoPoint>::get_ith_bit(KeyArg key, uint64_t bit_pos) {</span>
<span class="diff-deleted" style="background-color: #ffaaaa; color: #000000; display: block; white-space: pre">- // TODO</span>
<span class="diff-deleted" style="background-color: #ffaaaa; color: #000000; display: block; white-space: pre">- return 0;</span>
<span class="diff-added" style="background-color: #aaffaa; color: #000000; display: block; white-space: pre">+ const uint32_t x = reinterpret_cast<const uint32_t *>(&key)[bit_pos & 1];</span>
<span class="diff-added" style="background-color: #aaffaa; color: #000000; display: block; white-space: pre">+ return (x >> (31 - (bit_pos >> 1))) & 1;</span>
<span class="diff-not-changed" style="display: block; white-space: pre"> }</span>
<span class="diff-not-changed" style="display: block; white-space: pre"> </span>
<span class="diff-not-changed" style="display: block; white-space: pre"> template <typename T></span>
<span class="diff-hunk-header" style="background-color: #eaf2f5; color: #999999; display: block; white-space: pre">@@ -470,8 +471,14 @@ <span class="diff-context" style="background-color: #ffffaa; color: #000000">uint64_t Patricia<double>::count_common_prefix_bits(KeyArg lhs, KeyArg rhs) {</span></span>
<span class="diff-not-changed" style="display: block; white-space: pre"> </span>
<span class="diff-not-changed" style="display: block; white-space: pre"> template <></span>
<span class="diff-not-changed" style="display: block; white-space: pre"> uint64_t Patricia<GeoPoint>::count_common_prefix_bits(KeyArg lhs, KeyArg rhs) {</span>
<span class="diff-deleted" style="background-color: #ffaaaa; color: #000000; display: block; white-space: pre">- // TODO</span>
<span class="diff-deleted" style="background-color: #ffaaaa; color: #000000; display: block; white-space: pre">- return 0;</span>
<span class="diff-added" style="background-color: #aaffaa; color: #000000; display: block; white-space: pre">+ if (lhs == rhs) {</span>
<span class="diff-added" style="background-color: #aaffaa; color: #000000; display: block; white-space: pre">+ return sizeof(GeoPoint) * 8;</span>
<span class="diff-added" style="background-color: #aaffaa; color: #000000; display: block; white-space: pre">+ }</span>
<span class="diff-added" style="background-color: #aaffaa; color: #000000; display: block; white-space: pre">+ const GeoPoint x = GeoPoint(lhs.value() ^ rhs.value());</span>
<span class="diff-added" style="background-color: #aaffaa; color: #000000; display: block; white-space: pre">+ const uint32_t latitude = x.latitude();</span>
<span class="diff-added" style="background-color: #aaffaa; color: #000000; display: block; white-space: pre">+ const uint32_t longitude = x.longitude();</span>
<span class="diff-added" style="background-color: #aaffaa; color: #000000; display: block; white-space: pre">+ const uint8_t y = bit_scan_reverse(latitude | longitude);</span>
<span class="diff-added" style="background-color: #aaffaa; color: #000000; display: block; white-space: pre">+ return ((31 - y) << 1) + 1 - (latitude >> y);</span>
<span class="diff-not-changed" style="display: block; white-space: pre"> }</span>
<span class="diff-not-changed" style="display: block; white-space: pre"> </span>
<span class="diff-not-changed" style="display: block; white-space: pre"> template class Patricia<int8_t>;</span>
</pre>
</td>
</tr>
</tbody>
</table>
</div>
</body>
</html>