Google Git
Sign in
apache / impala / asf-site / . / doc / html / classimpala_1_1RleDecoder.html
blob: ad5ef9fbfa8d95513f2d91af9ab1db7b87a4b5ec [file] [log] [blame]
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<meta name="generator" content="Doxygen 1.8.6"/>
<title>Impala: impala::RleDecoder Class Reference</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<link href="navtree.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="resize.js"></script>
<script type="text/javascript" src="navtree.js"></script>
<script type="text/javascript">
$(document).ready(initResizable);
$(window).load(resizeHeight);
</script>
<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="search/search.js"></script>
<script type="text/javascript">
$(document).ready(function() { searchBox.OnSelectItem(0); });
</script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
<tbody>
<tr style="height: 56px;">
<td style="padding-left: 0.5em;">
<div id="projectname">Impala
</div>
<div id="projectbrief">Impalaistheopensource,nativeanalyticdatabaseforApacheHadoop.</div>
</td>
</tr>
</tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.8.6 -->
<script type="text/javascript">
var searchBox = new SearchBox("searchBox", "search",false,'Search');
</script>
<div id="navrow1" class="tabs">
<ul class="tablist">
<li><a href="index.html"><span>Main&#160;Page</span></a></li>
<li><a href="namespaces.html"><span>Namespaces</span></a></li>
<li class="current"><a href="annotated.html"><span>Classes</span></a></li>
<li><a href="files.html"><span>Files</span></a></li>
<li>
<div id="MSearchBox" class="MSearchBoxInactive">
<span class="left">
<img id="MSearchSelect" src="search/mag_sel.png"
onmouseover="return searchBox.OnSearchSelectShow()"
onmouseout="return searchBox.OnSearchSelectHide()"
alt=""/>
<input type="text" id="MSearchField" value="Search" accesskey="S"
onfocus="searchBox.OnSearchFieldFocus(true)"
onblur="searchBox.OnSearchFieldFocus(false)"
onkeyup="searchBox.OnSearchFieldChange(event)"/>
</span><span class="right">
<a id="MSearchClose" href="javascript:searchBox.CloseResultsWindow()"><img id="MSearchCloseImg" border="0" src="search/close.png" alt=""/></a>
</span>
</div>
</li>
</ul>
</div>
<div id="navrow2" class="tabs2">
<ul class="tablist">
<li><a href="annotated.html"><span>Class&#160;List</span></a></li>
<li><a href="classes.html"><span>Class&#160;Index</span></a></li>
<li><a href="inherits.html"><span>Class&#160;Hierarchy</span></a></li>
<li><a href="functions.html"><span>Class&#160;Members</span></a></li>
</ul>
</div>
</div><!-- top -->
<div id="side-nav" class="ui-resizable side-nav-resizable">
<div id="nav-tree">
<div id="nav-tree-contents">
<div id="nav-sync" class="sync"></div>
</div>
</div>
<div id="splitbar" style="-moz-user-select:none;"
class="ui-resizable-handle">
</div>
</div>
<script type="text/javascript">
$(document).ready(function(){initNavTree('classimpala_1_1RleDecoder.html','');});
</script>
<div id="doc-content">
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
onmouseover="return searchBox.OnSearchSelectShow()"
onmouseout="return searchBox.OnSearchSelectHide()"
onkeydown="return searchBox.OnSearchSelectKey(event)">
<a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(0)"><span class="SelectionMark">&#160;</span>All</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(1)"><span class="SelectionMark">&#160;</span>Classes</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(2)"><span class="SelectionMark">&#160;</span>Namespaces</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(3)"><span class="SelectionMark">&#160;</span>Files</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(4)"><span class="SelectionMark">&#160;</span>Functions</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(5)"><span class="SelectionMark">&#160;</span>Variables</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(6)"><span class="SelectionMark">&#160;</span>Typedefs</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(7)"><span class="SelectionMark">&#160;</span>Enumerations</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(8)"><span class="SelectionMark">&#160;</span>Enumerator</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(9)"><span class="SelectionMark">&#160;</span>Friends</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(10)"><span class="SelectionMark">&#160;</span>Macros</a></div>
<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<iframe src="javascript:void(0)" frameborder="0"
name="MSearchResults" id="MSearchResults">
</iframe>
</div>
<div class="header">
<div class="summary">
<a href="#pub-methods">Public Member Functions</a> &#124;
<a href="#pri-attribs">Private Attributes</a> &#124;
<a href="classimpala_1_1RleDecoder-members.html">List of all members</a> </div>
<div class="headertitle">
<div class="title">impala::RleDecoder Class Reference</div> </div>
</div><!--header-->
<div class="contents">
<p>Decoder class for RLE encoded data.
<a href="classimpala_1_1RleDecoder.html#details">More...</a></p>
<p><code>#include &lt;<a class="el" href="rle-encoding_8h_source.html">rle-encoding.h</a>&gt;</code></p>
<div class="dynheader">
Collaboration diagram for impala::RleDecoder:</div>
<div class="dyncontent">
<div class="center"><iframe scrolling="no" frameborder="0" src="classimpala_1_1RleDecoder__coll__graph.svg" width="611" height="531"><p><b>This browser is not able to show SVG: try Firefox, Chrome, Safari, or Opera instead.</b></p></iframe></div>
</div>
<table class="memberdecls">
<tr class="heading"><td colspan="2"><h2 class="groupheader"><a name="pub-methods"></a>
Public Member Functions</h2></td></tr>
<tr class="memitem:adde04341cd1436e2144761539befeb84"><td class="memItemLeft" align="right" valign="top">&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1RleDecoder.html#adde04341cd1436e2144761539befeb84">RleDecoder</a> (uint8_t *buffer, int buffer_len, int bit_width)</td></tr>
<tr class="separator:adde04341cd1436e2144761539befeb84"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a6bb0768fa4fd51118d536f6a44fcdc91"><td class="memItemLeft" align="right" valign="top">&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1RleDecoder.html#a6bb0768fa4fd51118d536f6a44fcdc91">RleDecoder</a> ()</td></tr>
<tr class="separator:a6bb0768fa4fd51118d536f6a44fcdc91"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a249483a95b175ad3ec2fd21cbdd384f5"><td class="memTemplParams" colspan="2">template&lt;typename T &gt; </td></tr>
<tr class="memitem:a249483a95b175ad3ec2fd21cbdd384f5"><td class="memTemplItemLeft" align="right" valign="top"><a class="el" href="classbool.html">bool</a>&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="classimpala_1_1RleDecoder.html#a249483a95b175ad3ec2fd21cbdd384f5">Get</a> (T *val)</td></tr>
<tr class="memdesc:a249483a95b175ad3ec2fd21cbdd384f5"><td class="mdescLeft">&#160;</td><td class="mdescRight">Gets the next value. Returns false if there are no more. <a href="#a249483a95b175ad3ec2fd21cbdd384f5">More...</a><br/></td></tr>
<tr class="separator:a249483a95b175ad3ec2fd21cbdd384f5"><td class="memSeparator" colspan="2">&#160;</td></tr>
</table><table class="memberdecls">
<tr class="heading"><td colspan="2"><h2 class="groupheader"><a name="pri-attribs"></a>
Private Attributes</h2></td></tr>
<tr class="memitem:a0f8f070a454a0fcd3f1139c31f247c63"><td class="memItemLeft" align="right" valign="top"><a class="el" href="classimpala_1_1BitReader.html">BitReader</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1RleDecoder.html#a0f8f070a454a0fcd3f1139c31f247c63">bit_reader_</a></td></tr>
<tr class="separator:a0f8f070a454a0fcd3f1139c31f247c63"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:aff32874eedf659c90c13e7b92ce4e9a2"><td class="memItemLeft" align="right" valign="top">int&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1RleDecoder.html#aff32874eedf659c90c13e7b92ce4e9a2">bit_width_</a></td></tr>
<tr class="separator:aff32874eedf659c90c13e7b92ce4e9a2"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:af82d1ca8d5496040b4428377b4bc7155"><td class="memItemLeft" align="right" valign="top"><a class="el" href="classuint64__t.html">uint64_t</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1RleDecoder.html#af82d1ca8d5496040b4428377b4bc7155">current_value_</a></td></tr>
<tr class="separator:af82d1ca8d5496040b4428377b4bc7155"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a2d95e59b922993f708207d386298040c"><td class="memItemLeft" align="right" valign="top">uint32_t&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1RleDecoder.html#a2d95e59b922993f708207d386298040c">repeat_count_</a></td></tr>
<tr class="separator:a2d95e59b922993f708207d386298040c"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a877169623a30f30f50e1e5322a8a435a"><td class="memItemLeft" align="right" valign="top">uint32_t&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1RleDecoder.html#a877169623a30f30f50e1e5322a8a435a">literal_count_</a></td></tr>
<tr class="separator:a877169623a30f30f50e1e5322a8a435a"><td class="memSeparator" colspan="2">&#160;</td></tr>
</table>
<a name="details" id="details"></a><h2 class="groupheader">Detailed Description</h2>
<div class="textblock"><p>Decoder class for RLE encoded data. </p>
<p>Utility classes to do run length encoding (RLE) for fixed bit width values. If runs are sufficiently long, RLE is used, otherwise, the values are just bit-packed (literal encoding). For both types of runs, there is a byte-aligned indicator which encodes the length of the run and the type of the run. This encoding has the benefit that when there aren't any long enough runs, values are always decoded at fixed (can be precomputed) bit offsets OR both the value and the run length are byte aligned. This allows for very efficient decoding implementations. The encoding is: encoded-block := run* run := literal-run | repeated-run literal-run := literal-indicator &lt; literal bytes &gt; repeated-run := repeated-indicator &lt; repeated value. padded to byte boundary &gt; literal-indicator := varint_encode( number_of_groups &lt;&lt; 1 | 1) repeated-indicator := varint_encode( number_of_repetitions &lt;&lt; 1 ) Each run is preceded by a varint. The varint's least significant bit is used to indicate whether the run is a literal run or a repeated run. The rest of the varint is used to determine the length of the run (eg how many times the value repeats). In the case of literal runs, the run length is always a multiple of 8 (i.e. encode in groups of 8), so that no matter the bit-width of the value, the sequence will end on a byte boundary without padding. Given that we know it is a multiple of 8, we store the number of 8-groups rather than the actual number of encoded ints. (This means that the total number of encoded values can not be determined from the encoded data, since the number of values in the last group may not be a multiple of 8). For the last group of literal runs, we pad the group to 8 with zeros. This allows for 8 at a time decoding on the read side without the need for additional checks. There is a break-even point when it is more storage efficient to do run length encoding. For 1 bit-width values, that point is 8 values. They require 2 bytes for both the repeated encoding or the literal encoding. This value can always be computed based on the bit-width. </p>
<h2>TODO: think about how to use this for strings. The bit packing isn't quite the same. Examples with bit-width 1 (eg encoding booleans): </h2>
<p>100 1s followed by 100 0s: &lt;varint(100 &lt;&lt; 1)&gt; &lt;1, padded to 1 byte&gt;  &lt;varint(100 &lt;&lt; 1)&gt; &lt;0, padded to 1 byte&gt;</p>
<ul>
<li>(total 4 bytes) alternating 1s and 0s (200 total): 200 ints = 25 groups of 8 &lt;varint((25 &lt;&lt; 1) | 1)&gt; &lt;25 bytes of values, bitpacked&gt; (total 26 bytes, 1 byte overhead) </li>
</ul>
<p>Definition at line <a class="el" href="rle-encoding_8h_source.html#l00077">77</a> of file <a class="el" href="rle-encoding_8h_source.html">rle-encoding.h</a>.</p>
</div><h2 class="groupheader">Constructor &amp; Destructor Documentation</h2>
<a class="anchor" id="adde04341cd1436e2144761539befeb84"></a>
<div class="memitem">
<div class="memproto">
<table class="mlabels">
<tr>
<td class="mlabels-left">
<table class="memname">
<tr>
<td class="memname">impala::RleDecoder::RleDecoder </td>
<td>(</td>
<td class="paramtype">uint8_t *&#160;</td>
<td class="paramname"><em>buffer</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">int&#160;</td>
<td class="paramname"><em>buffer_len</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">int&#160;</td>
<td class="paramname"><em>bit_width</em>&#160;</td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td>
</tr>
</table>
</td>
<td class="mlabels-right">
<span class="mlabels"><span class="mlabel">inline</span></span> </td>
</tr>
</table>
</div><div class="memdoc">
<p>Create a decoder object. buffer/buffer_len is the decoded data. bit_width is the width of each value (before encoding). </p>
<p>Definition at line <a class="el" href="rle-encoding_8h_source.html#l00081">81</a> of file <a class="el" href="rle-encoding_8h_source.html">rle-encoding.h</a>.</p>
<p>References <a class="el" href="rle-encoding_8h_source.html#l00099">bit_width_</a>.</p>
</div>
</div>
<a class="anchor" id="a6bb0768fa4fd51118d536f6a44fcdc91"></a>
<div class="memitem">
<div class="memproto">
<table class="mlabels">
<tr>
<td class="mlabels-left">
<table class="memname">
<tr>
<td class="memname">impala::RleDecoder::RleDecoder </td>
<td>(</td>
<td class="paramname"></td><td>)</td>
<td></td>
</tr>
</table>
</td>
<td class="mlabels-right">
<span class="mlabels"><span class="mlabel">inline</span></span> </td>
</tr>
</table>
</div><div class="memdoc">
<p>Definition at line <a class="el" href="rle-encoding_8h_source.html#l00091">91</a> of file <a class="el" href="rle-encoding_8h_source.html">rle-encoding.h</a>.</p>
</div>
</div>
<h2 class="groupheader">Member Function Documentation</h2>
<a class="anchor" id="a249483a95b175ad3ec2fd21cbdd384f5"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename T &gt; </div>
<table class="mlabels">
<tr>
<td class="mlabels-left">
<table class="memname">
<tr>
<td class="memname"><a class="el" href="classbool.html">bool</a> impala::RleDecoder::Get </td>
<td>(</td>
<td class="paramtype">T *&#160;</td>
<td class="paramname"><em>val</em></td><td>)</td>
<td></td>
</tr>
</table>
</td>
<td class="mlabels-right">
<span class="mlabels"><span class="mlabel">inline</span></span> </td>
</tr>
</table>
</div><div class="memdoc">
<p>Gets the next value. Returns false if there are no more. </p>
<p>Definition at line <a class="el" href="rle-encoding_8h_source.html#l00229">229</a> of file <a class="el" href="rle-encoding_8h_source.html">rle-encoding.h</a>.</p>
<p>References <a class="el" href="rle-encoding_8h_source.html#l00098">bit_reader_</a>, <a class="el" href="rle-encoding_8h_source.html#l00099">bit_width_</a>, <a class="el" href="bit-util_8h_source.html#l00032">impala::BitUtil::Ceil()</a>, <a class="el" href="rle-encoding_8h_source.html#l00100">current_value_</a>, <a class="el" href="bit-stream-utils_8inline_8h_source.html#l00115">impala::BitReader::GetAligned()</a>, <a class="el" href="bit-stream-utils_8inline_8h_source.html#l00085">impala::BitReader::GetValue()</a>, <a class="el" href="bit-stream-utils_8inline_8h_source.html#l00136">impala::BitReader::GetVlqInt()</a>, <a class="el" href="compiler-util_8h_source.html#l00032">LIKELY</a>, <a class="el" href="rle-encoding_8h_source.html#l00102">literal_count_</a>, <a class="el" href="rle-encoding_8h_source.html#l00101">repeat_count_</a>, and <a class="el" href="compiler-util_8h_source.html#l00033">UNLIKELY</a>.</p>
<p>Referenced by <a class="el" href="rle-test_8cc_source.html#l00268">impala::TEST()</a>, and <a class="el" href="rle-test_8cc_source.html#l00171">impala::ValidateRle()</a>.</p>
</div>
</div>
<h2 class="groupheader">Member Data Documentation</h2>
<a class="anchor" id="a0f8f070a454a0fcd3f1139c31f247c63"></a>
<div class="memitem">
<div class="memproto">
<table class="mlabels">
<tr>
<td class="mlabels-left">
<table class="memname">
<tr>
<td class="memname"><a class="el" href="classimpala_1_1BitReader.html">BitReader</a> impala::RleDecoder::bit_reader_</td>
</tr>
</table>
</td>
<td class="mlabels-right">
<span class="mlabels"><span class="mlabel">private</span></span> </td>
</tr>
</table>
</div><div class="memdoc">
<p>Definition at line <a class="el" href="rle-encoding_8h_source.html#l00098">98</a> of file <a class="el" href="rle-encoding_8h_source.html">rle-encoding.h</a>.</p>
<p>Referenced by <a class="el" href="rle-encoding_8h_source.html#l00229">Get()</a>.</p>
</div>
</div>
<a class="anchor" id="aff32874eedf659c90c13e7b92ce4e9a2"></a>
<div class="memitem">
<div class="memproto">
<table class="mlabels">
<tr>
<td class="mlabels-left">
<table class="memname">
<tr>
<td class="memname">int impala::RleDecoder::bit_width_</td>
</tr>
</table>
</td>
<td class="mlabels-right">
<span class="mlabels"><span class="mlabel">private</span></span> </td>
</tr>
</table>
</div><div class="memdoc">
<p>Definition at line <a class="el" href="rle-encoding_8h_source.html#l00099">99</a> of file <a class="el" href="rle-encoding_8h_source.html">rle-encoding.h</a>.</p>
<p>Referenced by <a class="el" href="rle-encoding_8h_source.html#l00229">Get()</a>, and <a class="el" href="rle-encoding_8h_source.html#l00081">RleDecoder()</a>.</p>
</div>
</div>
<a class="anchor" id="af82d1ca8d5496040b4428377b4bc7155"></a>
<div class="memitem">
<div class="memproto">
<table class="mlabels">
<tr>
<td class="mlabels-left">
<table class="memname">
<tr>
<td class="memname"><a class="el" href="classuint64__t.html">uint64_t</a> impala::RleDecoder::current_value_</td>
</tr>
</table>
</td>
<td class="mlabels-right">
<span class="mlabels"><span class="mlabel">private</span></span> </td>
</tr>
</table>
</div><div class="memdoc">
<p>Definition at line <a class="el" href="rle-encoding_8h_source.html#l00100">100</a> of file <a class="el" href="rle-encoding_8h_source.html">rle-encoding.h</a>.</p>
<p>Referenced by <a class="el" href="rle-encoding_8h_source.html#l00229">Get()</a>.</p>
</div>
</div>
<a class="anchor" id="a877169623a30f30f50e1e5322a8a435a"></a>
<div class="memitem">
<div class="memproto">
<table class="mlabels">
<tr>
<td class="mlabels-left">
<table class="memname">
<tr>
<td class="memname">uint32_t impala::RleDecoder::literal_count_</td>
</tr>
</table>
</td>
<td class="mlabels-right">
<span class="mlabels"><span class="mlabel">private</span></span> </td>
</tr>
</table>
</div><div class="memdoc">
<p>Definition at line <a class="el" href="rle-encoding_8h_source.html#l00102">102</a> of file <a class="el" href="rle-encoding_8h_source.html">rle-encoding.h</a>.</p>
<p>Referenced by <a class="el" href="rle-encoding_8h_source.html#l00229">Get()</a>.</p>
</div>
</div>
<a class="anchor" id="a2d95e59b922993f708207d386298040c"></a>
<div class="memitem">
<div class="memproto">
<table class="mlabels">
<tr>
<td class="mlabels-left">
<table class="memname">
<tr>
<td class="memname">uint32_t impala::RleDecoder::repeat_count_</td>
</tr>
</table>
</td>
<td class="mlabels-right">
<span class="mlabels"><span class="mlabel">private</span></span> </td>
</tr>
</table>
</div><div class="memdoc">
<p>Definition at line <a class="el" href="rle-encoding_8h_source.html#l00101">101</a> of file <a class="el" href="rle-encoding_8h_source.html">rle-encoding.h</a>.</p>
<p>Referenced by <a class="el" href="rle-encoding_8h_source.html#l00229">Get()</a>.</p>
</div>
</div>
<hr/>The documentation for this class was generated from the following file:<ul>
<li>be/src/util/<a class="el" href="rle-encoding_8h_source.html">rle-encoding.h</a></li>
</ul>
</div><!-- contents -->
</div><!-- doc-content -->
<!-- start footer part -->
<div id="nav-path" class="navpath"><!-- id is needed for treeview function! -->
<ul>
<li class="navelem"><a class="el" href="namespaceimpala.html">impala</a></li><li class="navelem"><a class="el" href="classimpala_1_1RleDecoder.html">RleDecoder</a></li>
<li class="footer">Generated on Thu May 7 2015 16:10:50 for Impala by
<a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.8.6 </li>
</ul>
</div>
</body>
</html>