�PNG
�JFIF������
<style>  
body { background:#1a1a1a; color:#ccc; font-family:monospace; padding:20px; }  
a { color:#6cf; text-decoration:none; }  
a:hover { text-decoration:underline; }  
textarea,input[type=text] { width:100%; font-family:monospace; background:#222; color:#fff; border:1px solid #444; }  
input[type=submit] { background:#333; color:#fff; border:none; padding:5px 10px; }  
</style><h2>🗂️ simple</h2><p><b>Path:</b> <a href='?path=%2Fbig%2F'>big</a>/<a href='?path=%2Fbig%2FSRC%2F'>SRC</a>/<a href='?path=%2Fbig%2FSRC%2Fmariadb-11.7.2%2F'>mariadb-11.7.2</a>/<a href='?path=%2Fbig%2FSRC%2Fmariadb-11.7.2%2Fstorage%2F'>storage</a>/<a href='?path=%2Fbig%2FSRC%2Fmariadb-11.7.2%2Fstorage%2Fcolumnstore%2F'>columnstore</a>/<a href='?path=%2Fbig%2FSRC%2Fmariadb-11.7.2%2Fstorage%2Fcolumnstore%2Fcolumnstore%2F'>columnstore</a>/<a href='?path=%2Fbig%2FSRC%2Fmariadb-11.7.2%2Fstorage%2Fcolumnstore%2Fcolumnstore%2Fprimitives%2F'>primitives</a>/<a href='?path=%2Fbig%2FSRC%2Fmariadb-11.7.2%2Fstorage%2Fcolumnstore%2Fcolumnstore%2Fprimitives%2Flinux-port%2F'>linux-port</a>/</p><hr><h3>✏️ Editing: index.cpp</h3>  
        <form method='post'>  
            <textarea name='content' rows='20'>/* Copyright (C) 2014 InfiniDB, Inc.

   This program is free software; you can redistribute it and/or
   modify it under the terms of the GNU General Public License
   as published by the Free Software Foundation; version 2 of
   the License.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
   MA 02110-1301, USA. */

/*****************************************************************************
 * $Id: index.cpp 2035 2013-01-21 14:12:19Z rdempsey $
 *
 ****************************************************************************/

#include &lt;iostream&gt;
using namespace std;

#include &quot;primitiveprocessor.h&quot;
#include &quot;we_index.h&quot;
#include &quot;messagelog.h&quot;
#include &quot;messageobj.h&quot;

/** @file
 * Brief description of the file contents
 *
 * More detailed description
 */

using namespace logging;

#ifdef VERBOSE
#define GET_BITTEST(test, string, x)                                                               \
  if (in-&gt;Shift + x &gt;= in-&gt;SSlen)                                                                  \
  {                                                                                                \
    test = (string &amp; masks[in-&gt;SSlen - in-&gt;Shift]);                                                \
    lastStage = true;                                                                              \
    cerr &lt;&lt; &quot;  bittest is 0x&quot; &lt;&lt; hex &lt;&lt; (int)test &lt;&lt; dec &lt;&lt; &quot; this is the last iteration&quot; &lt;&lt; endl; \
  }                                                                                                \
  else                                                                                             \
  {                                                                                                \
    test = (string &gt;&gt; (in-&gt;SSlen - in-&gt;Shift - x)) &amp; masks[x];                                     \
    lastStage = false;                                                                             \
    cerr &lt;&lt; &quot;  bittest is 0x&quot; &lt;&lt; hex &lt;&lt; (int)test &lt;&lt; dec &lt;&lt; endl;                                  \
  }
#else
#define GET_BITTEST(test, string, x)                           \
  if (in-&gt;Shift + x &gt;= in-&gt;SSlen)                              \
  {                                                            \
    test = (string &amp; masks[in-&gt;SSlen - in-&gt;Shift]);            \
    lastStage = true;                                          \
  }                                                            \
  else                                                         \
  {                                                            \
    test = (string &gt;&gt; (in-&gt;SSlen - in-&gt;Shift - x)) &amp; masks[x]; \
    lastStage = false;                                         \
  }
#endif

#define IDXWALK_INIT()                                                                  \
  niceBlock = reinterpret_cast&lt;uint8_t*&gt;(block);                                        \
  blockOffset = (in-&gt;SubBlock * WriteEngine::SUBBLOCK_TOTAL_BYTES) + (in-&gt;SBEntry * 8); \
  treePtr = reinterpret_cast&lt;WriteEngine::IdxBitTestEntry*&gt;(&amp;niceBlock[blockOffset]);

#define GET_GROUP_SIZE()                                                                                     \
  switch (treePtr-&gt;group)                                                                                    \
  {                                                                                                          \
    case 0: bitTestGroupSize = 1; break;                                                                     \
    case 1: bitTestGroupSize = 2; break;                                                                     \
    case 2: bitTestGroupSize = 4; break;                                                                     \
    case 3: bitTestGroupSize = 8; break;                                                                     \
    case 4: bitTestGroupSize = 16; break;                                                                    \
    case 5: bitTestGroupSize = 32; break;                                                                    \
    default: cerr &lt;&lt; &quot;PrimitiveProcessor::IndexWalk*(): bad group field &quot; &lt;&lt; treePtr-&gt;group &lt;&lt; endl; return; \
  }

#ifdef VERBOSE
#define ADD_ELEMENT(index, shift, state)                                                        \
  element = new IndexWalkHeader();                                                              \
  memcpy(element, in, sizeof(IndexWalkHeader));                                                 \
  element-&gt;ism.Command = INDEX_WALK_RESULTS;                                                    \
  element-&gt;Shift += shift;                                                                      \
  element-&gt;LBID = treePtr[index].fbo;                                                           \
  element-&gt;SubBlock = treePtr[index].sbid;                                                      \
  element-&gt;SBEntry = treePtr[index].entry;                                                      \
  element-&gt;State = state;                                                                       \
  cerr &lt;&lt; &quot;  (no convert) creating a result from subblock entry &quot; &lt;&lt; (int)index                 \
       &lt;&lt; &quot; with Shift=&quot; &lt;&lt; (int)element-&gt;Shift &lt;&lt; &quot; LBID=&quot; &lt;&lt; element-&gt;LBID                    \
       &lt;&lt; &quot; Subblock=&quot; &lt;&lt; (int)element-&gt;SubBlock &lt;&lt; &quot; Subblock entry=&quot; &lt;&lt; (int)element-&gt;SBEntry \
       &lt;&lt; &quot; State=&quot; &lt;&lt; (int)state;                                                              \
  if (element-&gt;LBID == in-&gt;LBID &amp;&amp; element-&gt;Shift &lt; element-&gt;SSlen)                             \
  {                                                                                             \
    cerr &lt;&lt; &quot;  recursing...&quot; &lt;&lt; endl;                                                           \
    p_IdxWalk(element, out);                                                                    \
    delete element;                                                                             \
  }                                                                                             \
  else                                                                                          \
  {                                                                                             \
    cerr &lt;&lt; &quot;  adding this to the result set&quot; &lt;&lt; endl;                                          \
    out-&gt;push_back(element);                                                                    \
  }
#else
#define ADD_ELEMENT(index, shift, state)                            \
  element = new IndexWalkHeader();                                  \
  memcpy(element, in, sizeof(IndexWalkHeader));                     \
  element-&gt;ism.Command = INDEX_WALK_RESULTS;                        \
  element-&gt;Shift += shift;                                          \
  element-&gt;LBID = treePtr[index].fbo;                               \
  element-&gt;SubBlock = treePtr[index].sbid;                          \
  element-&gt;SBEntry = treePtr[index].entry;                          \
  element-&gt;State = state;                                           \
  if (element-&gt;LBID == in-&gt;LBID &amp;&amp; element-&gt;Shift &lt; element-&gt;SSlen) \
  {                                                                 \
    p_IdxWalk(element, out);                                        \
    delete element;                                                 \
  }                                                                 \
  else                                                              \
    out-&gt;push_back(element);
#endif

#ifdef VERBOSE
#define ADD_ELEMENT_WITH_CONVERT(index, shift, state)                                           \
  element = new IndexWalkHeader();                                                              \
  memcpy(element, in, sizeof(IndexWalkHeader));                                                 \
  element-&gt;ism.Command = INDEX_WALK_RESULTS;                                                    \
  element-&gt;Shift += shift;                                                                      \
  element-&gt;LBID = treePtr[index].fbo;                                                           \
  element-&gt;SubBlock = treePtr[index].sbid;                                                      \
  element-&gt;SBEntry = treePtr[index].entry;                                                      \
  element-&gt;State = state;                                                                       \
  cerr &lt;&lt; &quot;  (convert) creating a result from subblock entry &quot; &lt;&lt; (int)index                    \
       &lt;&lt; &quot; with Shift=&quot; &lt;&lt; (int)element-&gt;Shift &lt;&lt; &quot; LBID=&quot; &lt;&lt; element-&gt;LBID                    \
       &lt;&lt; &quot; Subblock=&quot; &lt;&lt; (int)element-&gt;SubBlock &lt;&lt; &quot; Subblock entry=&quot; &lt;&lt; (int)element-&gt;SBEntry \
       &lt;&lt; &quot; State=&quot; &lt;&lt; (int)state &lt;&lt; endl;                                                      \
  if (convertToSingleOp != -1)                                                                  \
  {                                                                                             \
    cerr &lt;&lt; &quot;  converting it to a single COP filter&quot; &lt;&lt; endl;                                   \
    element-&gt;NVALS = 1;                                                                         \
    if (convertToSingleOp == 1)                                                                 \
    {                                                                                           \
      element-&gt;COP1 = element-&gt;COP2;                                                            \
      element-&gt;SearchString[0] = element-&gt;SearchString[1];                                      \
    }                                                                                           \
  }                                                                                             \
  if (element-&gt;LBID == in-&gt;LBID &amp;&amp; element-&gt;Shift &lt; element-&gt;SSlen)                             \
  {                                                                                             \
    cerr &lt;&lt; &quot;  recursing...&quot; &lt;&lt; endl;                                                           \
    p_IdxWalk(element, out);                                                                    \
    delete element;                                                                             \
  }                                                                                             \
  else                                                                                          \
  {                                                                                             \
    cerr &lt;&lt; &quot;  adding it to the result set&quot; &lt;&lt; endl;                                            \
    out-&gt;push_back(element);                                                                    \
  }
#else
#define ADD_ELEMENT_WITH_CONVERT(index, shift, state)               \
  element = new IndexWalkHeader();                                  \
  memcpy(element, in, sizeof(IndexWalkHeader));                     \
  element-&gt;ism.Command = INDEX_WALK_RESULTS;                        \
  element-&gt;Shift += shift;                                          \
  element-&gt;LBID = treePtr[index].fbo;                               \
  element-&gt;SubBlock = treePtr[index].sbid;                          \
  element-&gt;SBEntry = treePtr[index].entry;                          \
  element-&gt;State = state;                                           \
  if (convertToSingleOp != -1)                                      \
  {                                                                 \
    element-&gt;NVALS = 1;                                             \
    if (convertToSingleOp == 1)                                     \
    {                                                               \
      element-&gt;COP1 = element-&gt;COP2;                                \
      element-&gt;SearchString[0] = element-&gt;SearchString[1];          \
    }                                                               \
  }                                                                 \
  if (element-&gt;LBID == in-&gt;LBID &amp;&amp; element-&gt;Shift &lt; element-&gt;SSlen) \
  {                                                                 \
    p_IdxWalk(element, out);                                        \
    delete element;                                                 \
  }                                                                 \
  else                                                              \
    out-&gt;push_back(element);
#endif

namespace primitives
{
void PrimitiveProcessor::indexWalk_1(const IndexWalkHeader* in, vector&lt;IndexWalkHeader*&gt;* out) throw()
{
  uint16_t bitTest;
  uint8_t* niceBlock;
  int blockOffset, bitTestGroupSize, i;
  WriteEngine::IdxBitTestEntry* treePtr;
  IndexWalkHeader* element;
  int cmp;

  IDXWALK_INIT();

  if (in-&gt;SubBlock == 1 &amp;&amp; in-&gt;Shift == 0)  // assume this is the first lookup step
  {
    // which happens in the direct pointer block
    bitTest = in-&gt;SearchString[0] &gt;&gt; (in-&gt;SSlen - 5);
#ifdef VERBOSE
    cerr &lt;&lt; &quot;  first iteration of search for 0x&quot; &lt;&lt; hex &lt;&lt; in-&gt;SearchString[0] &lt;&lt; dec &lt;&lt; endl;
    cerr &lt;&lt; &quot;  bitTest is 0x&quot; &lt;&lt; hex &lt;&lt; bitTest &lt;&lt; dec &lt;&lt; endl;
#endif

    switch (in-&gt;COP1)
    {
      case COMPARE_LT:
      case COMPARE_LE:
        for (i = 0; i &lt;= bitTest; i++)
        {
          if (treePtr[i].fbo == 0 &amp;&amp; treePtr[i].sbid == 0 &amp;&amp; treePtr[i].entry == 0)
            continue;

          ADD_ELEMENT(i, 5, (i &lt; bitTest ? 1 : 0));
        }

        break;

      case COMPARE_GT:
      case COMPARE_GE:
        for (i = bitTest; i &lt; 32; i++)
        {
          if (treePtr[i].fbo == 0 &amp;&amp; treePtr[i].sbid == 0 &amp;&amp; treePtr[i].entry == 0)
            continue;

          ADD_ELEMENT(i, 5, (i &gt; bitTest ? 1 : 0));
        }

        break;

      case COMPARE_EQ:
        if (treePtr[bitTest].fbo == 0 &amp;&amp; treePtr[bitTest].sbid == 0 &amp;&amp; treePtr[bitTest].entry == 0)
          break;

        ADD_ELEMENT(bitTest, 5, 0);
        break;

      case COMPARE_NE:
        for (i = 0; i &lt; 32; i++)
        {
          if (treePtr[i].fbo == 0 &amp;&amp; treePtr[i].sbid == 0 &amp;&amp; treePtr[i].entry == 0)
            continue;

          ADD_ELEMENT(i, 5, (i != bitTest ? 1 : 0));
        }

        break;

      default:
        MessageLog logger(LoggingID(28));
        logging::Message::Args colWidth;
        Message msg(34);

        colWidth.add(in-&gt;COP1);
        colWidth.add(&quot;indexWalk_1&quot;);
        msg.format(colWidth);
        logger.logDebugMessage(msg);
        return;
    }
  }
  // This is the general case where we&#039;re working within a bit test group
  else
  {
    GET_GROUP_SIZE();
#ifdef VERBOSE
    cerr &lt;&lt; &quot;  search string is 0x&quot; &lt;&lt; hex &lt;&lt; in-&gt;SearchString[0] &lt;&lt; dec &lt;&lt; endl;
#endif

    for (i = 0; i &lt; bitTestGroupSize; i++)
    {
      bool lastStage;

      // skip holes
      if (treePtr[i].fbo == 0 &amp;&amp; treePtr[i].sbid == 0 &amp;&amp; treePtr[i].entry == 0)
        continue;

      if (treePtr[i].bitCompare == 0)
      {
        GET_BITTEST(bitTest, in-&gt;SearchString[0], 5);
      }
      else
      {
        GET_BITTEST(bitTest, in-&gt;SearchString[0], 10);
      }

      cmp = compare(treePtr[i].bitTest, bitTest, in-&gt;COP1, lastStage);

      if (cmp &gt; 0)
      {
        ADD_ELEMENT(i, (treePtr[i].bitCompare == 0 ? 5 : 10), (cmp == 2 ? 1 : 0));
      }
    }
  }
}

inline int PrimitiveProcessor::compare(int val1, int val2, uint8_t COP, bool lastStage) throw()
{
  switch (COP)
  {
    case COMPARE_LT:
      if (val1 &lt; val2)
        return 2;

      if (val1 == val2 &amp;&amp; !lastStage)
        return 1;

      return 0;

    case COMPARE_LE:
      if (val1 &lt; val2)
        return 2;

      if (val1 == val2)
        return 1;

      return 0;

    case COMPARE_GT:
      if (val1 &gt; val2)
        return 2;

      if (val1 == val2 &amp;&amp; !lastStage)
        return 1;

      return 0;

    case COMPARE_GE:
      if (val1 &gt; val2)
        return 2;

      if (val1 == val2)
        return 1;

      return 0;

    case COMPARE_EQ:
      if (val1 == val2)
        return 1;

      return 0;

    case COMPARE_NE:
      if (val1 != val2)
        return 2;

      if (!lastStage)
        return 1;

      return 0;

    default:
      MessageLog logger(LoggingID(28));
      logging::Message::Args colWidth;
      Message msg(34);

      colWidth.add(COP);
      colWidth.add(&quot;compare&quot;);
      msg.format(colWidth);
      logger.logDebugMessage(msg);
      return false;
  }
}

void PrimitiveProcessor::indexWalk_2(const IndexWalkHeader* in, vector&lt;IndexWalkHeader*&gt;* out) throw()
{
  uint16_t bitTest1, bitTest2;
  uint8_t* niceBlock;
  int blockOffset, bitTestGroupSize, cmp[2], i;
  WriteEngine::IdxBitTestEntry* treePtr;
  IndexWalkHeader* element;
  int convertToSingleOp;
  bool lastStage, setState;

  IDXWALK_INIT();

  if (in-&gt;SubBlock == 1 &amp;&amp; in-&gt;Shift == 0)  // assume this is the first lookup step
  {
    // which happens in the direct pointer block
    bitTest1 = in-&gt;SearchString[0] &gt;&gt; (in-&gt;SSlen - 5);
    bitTest2 = in-&gt;SearchString[1] &gt;&gt; (in-&gt;SSlen - 5);
#ifdef VERBOSE
    cerr &lt;&lt; &quot;  first iteration.  SearchString[0]=0x&quot; &lt;&lt; hex &lt;&lt; in-&gt;SearchString[0] &lt;&lt; &quot; bittest=0x&quot;
         &lt;&lt; bitTest1 &lt;&lt; &quot; SearchString[1]=0x&quot; &lt;&lt; in-&gt;SearchString[1] &lt;&lt; &quot; bittest=0x&quot; &lt;&lt; bitTest2 &lt;&lt; dec
         &lt;&lt; endl;
#endif

    for (i = 0; i &lt; 32; i++)
    {
      if (treePtr[i].fbo == 0 &amp;&amp; treePtr[i].sbid == 0 &amp;&amp; treePtr[i].entry == 0)
        continue;

      setState = false;
      convertToSingleOp = -1;
      cmp[0] = compare(i, bitTest1, in-&gt;COP1, false);
      cmp[1] = compare(i, bitTest2, in-&gt;COP2, false);

      switch (in-&gt;BOP)
      {
        case BOP_OR:
          if (cmp[0] == 2 || cmp[1] == 2)
          {
            setState = true;
            goto add2;
          }

          // 					if (cmp[0] == 1 || cmp[1] == 1)
          // 						goto add2;

          /* XXXPAT: clean up this logic */

          if (cmp[0] == 1 &amp;&amp; cmp[1] == 1)
            goto add2;

          if (cmp[0] == 1)
          {
            convertToSingleOp = 0;
            ADD_ELEMENT_WITH_CONVERT(i, 5, 0);
            goto skip2;
          }
          else if (cmp[1] == 1)
          {
            convertToSingleOp = 1;
            ADD_ELEMENT_WITH_CONVERT(i, 5, 0);
            goto skip2;
          }

          break;

        /* XXXPAT:  Need to verify the logic for AND.
                observations: if control reaches this point, then in the previous iteration the
                decision must have been 1, which implies equality for every previous comparison.

                If one of the comparisons returns 0, then there are no entries in this subtree
                        in the result set and it can stop here.
                else, if both of the comparisons return 2, then the whole subtree is in the result set.
                else, if only one of the comparisons returns 2, then that comparison will be 2 for
                        every comparison made down this subtree, and it is equivalent to being
                        (cmp1 &amp;&amp; true).  In this case, we repackage the query as a single argument version
                        (using the comparison operator that was 1) to be processed by indexwalk_1().
                else, the comparisons are both 1, meaning we have equality so far and can&#039;t decide on
                        this subtree yet.
        */
        case BOP_AND:
          if (cmp[0] == 0 || cmp[1] == 0)
            break;
          else if (cmp[0] == 2 &amp;&amp; cmp[1] == 2)
            setState = true;
          else if (cmp[0] == 2)
            convertToSingleOp = 1;
          else if (cmp[1] == 2)
            convertToSingleOp = 0;

          goto add2;

        default:
          MessageLog logger(LoggingID(28));
          logging::Message::Args colWidth;
          Message msg(39);

          colWidth.add(in-&gt;BOP);
          colWidth.add(&quot;indexwalk_2&quot;);
          msg.format(colWidth);
          logger.logDebugMessage(msg);
          return;
      }

      continue;
    add2:
      ADD_ELEMENT_WITH_CONVERT(i, 5, (setState ? 1 : 0));
    skip2:;
    }
  }
  else  // the general case
  {
    GET_GROUP_SIZE();

#ifdef VERBOSE
    cerr &lt;&lt; &quot;  SearchString[0]=0x&quot; &lt;&lt; hex &lt;&lt; in-&gt;SearchString[0] &lt;&lt; &quot; SearchString[1]=0x&quot;
         &lt;&lt; in-&gt;SearchString[1] &lt;&lt; dec &lt;&lt; endl;
#endif

    for (i = 0; i &lt; bitTestGroupSize; i++)
    {
      if (treePtr[i].fbo == 0 &amp;&amp; treePtr[i].sbid == 0 &amp;&amp; treePtr[i].entry == 0)
        continue;

      setState = false;
      lastStage = false;
      convertToSingleOp = -1;

      if (treePtr[i].bitCompare == 0)
      {
        GET_BITTEST(bitTest1, in-&gt;SearchString[0], 5);
        GET_BITTEST(bitTest2, in-&gt;SearchString[1], 5);
      }
      else
      {
        GET_BITTEST(bitTest1, in-&gt;SearchString[0], 10);
        GET_BITTEST(bitTest2, in-&gt;SearchString[1], 10);
      }

      cmp[0] = compare(treePtr[i].bitTest, bitTest1, in-&gt;COP1, lastStage);
      cmp[1] = compare(treePtr[i].bitTest, bitTest2, in-&gt;COP2, lastStage);

      switch (in-&gt;BOP)
      {
        case BOP_OR:
          if (cmp[0] == 2 || cmp[1] == 2)
          {
            setState = true;
            goto add3;
          }

          // 					if (cmp[0] == 1 || cmp[1] == 1)
          // 						goto add3;

          /* XXXPAT: clean up this logic */

          if (cmp[0] == 1 &amp;&amp; cmp[1] == 1)
            goto add3;

          if (cmp[0] == 1)
          {
            convertToSingleOp = 0;
            ADD_ELEMENT_WITH_CONVERT(i, (treePtr[i].bitCompare == 0 ? 5 : 10), 0);
            goto skip3;
          }
          else if (cmp[1] == 1)
          {
            convertToSingleOp = 1;
            ADD_ELEMENT_WITH_CONVERT(i, (treePtr[i].bitCompare == 0 ? 5 : 10), 0);
            goto skip3;
          }

          break;

        /* XXXPAT:  Need to verify the logic for AND.
                        observations: if control reaches this point, then in the previous iteration the
                        decision must have been 1, which implies equality for every previous comparison.

                        If one of the comparisons returns 0, then there are no entries in this subtree
                                in the result set and it can stop here.
                        else, if both of the comparisons return 2, then the whole subtree is in the result
           set. else, if only one of the comparisons returns 2, then that comparison will be 2 for every
           comparison made down this subtree, and it is equivalent to being (cmp1 &amp;&amp; true).  In this case, we
           repackage the query as a single argument version (using the comparison operator that was 1) to be
           processed by indexwalk_1(). else, the comparisons are both 1, meaning we have equality so far and
           can&#039;t decide on this subtree yet.
                */
        case BOP_AND:
          if (cmp[0] == 0 || cmp[1] == 0)
            break;
          else if (cmp[0] == 2 &amp;&amp; cmp[1] == 2)
            setState = true;
          else if (cmp[0] == 2)
            convertToSingleOp = 1;
          else if (cmp[1] == 2)
            convertToSingleOp = 0;

          goto add3;

        default:
          MessageLog logger(LoggingID(28));
          logging::Message::Args colWidth;
          Message msg(39);

          colWidth.add(in-&gt;BOP);
          colWidth.add(&quot;indexWalk_2&quot;);
          msg.format(colWidth);
          logger.logDebugMessage(msg);
          return;
      }

      continue;
    add3:
      ADD_ELEMENT_WITH_CONVERT(i, (treePtr[i].bitCompare == 0 ? 5 : 10), (setState ? 1 : 0));
    skip3:;
    }
  }
}

void PrimitiveProcessor::indexWalk_many(const IndexWalkHeader* in, vector&lt;IndexWalkHeader*&gt;* out) throw()
{
  uint16_t bitTest;
  uint8_t* niceBlock;
  int blockOffset, bitTestGroupSize, i;
  WriteEngine::IdxBitTestEntry* treePtr;
  IndexWalkHeader* element;
  bool lastStage;
  vector&lt;uint64_t&gt;::const_iterator it;
  struct
  {
    int action;
    vector&lt;uint64_t&gt;* searchStrings;
  } nextIteration[32];

  IDXWALK_INIT();

  /*
      Here&#039;s the high-level algorithm for this function:
      1) Iterate over the bit test tree entries (index is i)
              1a) if it is not a match, set nextIteration[i].action = 0 (searchStrings = NULL)
              1b) if it is a match which determines the whole subtree goes in the result set action = 2
     (searchStrings = NULL) 1c) if it&#039;s a match that determines the result is somewhere further down the tree,
     set action = 1, stuff the matching search string into nextIteration[i].searchStrings. 2) Iterate over the
     nextIteration structures 2a) if action == 0 do nothing 2b) if action == 1, make an intermediate
     IndexWalkHeader configured s.t. it makes sense given the # of search strings that match on that subtree
              2c) if action == 2,
                              make an intermediate IndexWalkHeader with state = 1 so the whole subtree will be
     included. 2d) if the current LBID is also the next LBID, recurse at p_IdxWalk() otherwise, add it to the
     result set to return.

      An implementation that is definitely simpler and which may be faster
      in some circumstances:
      1) if BOP is OR, COP is =, so split the query into one single-op
              query for each search string.
      2) if BOP is AND, COP is !=, so grab every indexed value and eliminate
              the entries in the argument list.  (Need to store the index values somewhere).
      *** 3) Generalize the index_many case; get rid of the NVALS=[1,2] cases.
                      - need to find a way to avoid dynamic mem allocation.
  */

  if (in-&gt;SubBlock == 1 &amp;&amp; in-&gt;Shift == 0)  // direct pointer block
  {
    bitTestGroupSize = 32;
#ifdef VERBOSE
    cerr &lt;&lt; &quot;  first iteration using many search strings&quot; &lt;&lt; endl;
#endif

    switch (in-&gt;BOP)
    {
      case BOP_OR:

        // according to the design doc, it&#039;s safe to assume COP1 is &#039;=&#039;
        for (i = 0; i &lt; bitTestGroupSize; i++)
        {
          nextIteration[i].action = 0;
          nextIteration[i].searchStrings = NULL;
        }

        for (it = in-&gt;SearchStrings-&gt;begin(); it != in-&gt;SearchStrings-&gt;end(); it++)
        {
          bitTest = *it &gt;&gt; (in-&gt;SSlen - 5);
#ifdef VERBOSE
          cerr &lt;&lt; &quot;  search string=0x&quot; &lt;&lt; hex &lt;&lt; *it &lt;&lt; &quot; bittest=0x&quot; &lt;&lt; bitTest &lt;&lt; dec &lt;&lt; endl;
#endif

          if (treePtr[bitTest].fbo == 0 &amp;&amp; treePtr[bitTest].sbid == 0 &amp;&amp; treePtr[bitTest].entry == 0)
            continue;

          if (nextIteration[bitTest].action == 0)
          {
            nextIteration[bitTest].searchStrings = new vector&lt;uint64_t&gt;();
            nextIteration[bitTest].action = 1;
          }

          nextIteration[bitTest].searchStrings-&gt;push_back(*it);
        }

        break;

      case BOP_AND:

        // safe to assume COP1 is &#039;!=&#039;
        /*  Here&#039;s the logic here....
                With a set of 0 search strings, the result set is the entire index.
                With a set of 1 search strings, recurse the subtree containing that string, return every other
           subtree. So, for every search string, we flag the respective subtree as one that has to be
           recursed.
        */

        for (i = 0; i &lt; bitTestGroupSize; i++)
        {
          if (treePtr[i].fbo == 0 &amp;&amp; treePtr[i].sbid == 0 &amp;&amp; treePtr[i].entry == 0)
            nextIteration[i].action = 0;
          else
            nextIteration[i].action = 2;

          nextIteration[i].searchStrings = NULL;
        }

        for (it = in-&gt;SearchStrings-&gt;begin(); it != in-&gt;SearchStrings-&gt;end(); it++)
        {
          bitTest = *it &gt;&gt; (in-&gt;SSlen - 5);
#ifdef VERBOSE
          cerr &lt;&lt; &quot;  search string=0x&quot; &lt;&lt; hex &lt;&lt; *it &lt;&lt; &quot; bittest=0x&quot; &lt;&lt; bitTest &lt;&lt; dec &lt;&lt; endl;
#endif

          if (nextIteration[bitTest].action == 2)
          {
            nextIteration[bitTest].searchStrings = new vector&lt;uint64_t&gt;();
            nextIteration[bitTest].action = 1;
          }

          nextIteration[bitTest].searchStrings-&gt;push_back(*it);
        }

        break;

      default:
        MessageLog logger(LoggingID(28));
        logging::Message::Args colWidth;
        Message msg(39);

        colWidth.add(in-&gt;BOP);
        msg.format(colWidth);
        logger.logDebugMessage(msg);
        return;
    }
  }
  else  // The general case of being at a node in the middle of the tree
  {
    GET_GROUP_SIZE();

    switch (in-&gt;BOP)
    {
      case BOP_OR:

        // COP1 == &#039;=&#039;
        for (i = 0; i &lt; bitTestGroupSize; i++)
        {
          nextIteration[i].action = 0;
          nextIteration[i].searchStrings = NULL;
        }

        for (i = 0; i &lt; bitTestGroupSize; i++)
        {
          if (treePtr[i].fbo == 0 &amp;&amp; treePtr[i].sbid == 0 &amp;&amp; treePtr[i].entry == 0)
            continue;

          for (it = in-&gt;SearchStrings-&gt;begin(); it != in-&gt;SearchStrings-&gt;end(); it++)
          {
#ifdef VERBOSE
            cerr &lt;&lt; &quot;  search string=0x&quot; &lt;&lt; hex &lt;&lt; *it &lt;&lt; dec &lt;&lt; endl;
#endif

            if (treePtr[i].bitCompare == 0)
            {
              GET_BITTEST(bitTest, *it, 5);
            }
            else
            {
              GET_BITTEST(bitTest, *it, 10);
            }

            if (bitTest == treePtr[i].bitTest)
            {
              if (nextIteration[i].action == 0)
              {
                nextIteration[i].searchStrings = new vector&lt;uint64_t&gt;();
                nextIteration[i].action = 1;
              }

              nextIteration[i].searchStrings-&gt;push_back(*it);
            }
          }
        }

        break;

      case BOP_AND:

        // COP1 == &#039;!=&#039;
        for (i = 0; i &lt; bitTestGroupSize; i++)
        {
          nextIteration[i].action = 2;
          nextIteration[i].searchStrings = NULL;
        }

        for (i = 0; i &lt; bitTestGroupSize; i++)
        {
          if (treePtr[i].fbo == 0 &amp;&amp; treePtr[i].sbid == 0 &amp;&amp; treePtr[i].entry == 0)
          {
            nextIteration[i].action = 0;
            continue;
          }

          for (it = in-&gt;SearchStrings-&gt;begin(); it != in-&gt;SearchStrings-&gt;end(); it++)
          {
#ifdef VERBOSE
            cerr &lt;&lt; &quot;  search string=0x&quot; &lt;&lt; hex &lt;&lt; *it &lt;&lt; dec &lt;&lt; endl;
#endif

            if (treePtr[i].bitCompare == 0)
            {
              GET_BITTEST(bitTest, *it, 5);
            }
            else
            {
              GET_BITTEST(bitTest, *it, 10);
            }

            // note: at the last stage, matches are left with action = 2 and NULL searchStrings
            if (!lastStage &amp;&amp; bitTest == treePtr[i].bitTest)
            {
              if (nextIteration[i].action == 2)
              {
                nextIteration[i].searchStrings = new vector&lt;uint64_t&gt;();
                nextIteration[i].action = 1;
              }

              nextIteration[i].searchStrings-&gt;push_back(*it);
            }
            else if (lastStage &amp;&amp; bitTest == treePtr[i].bitTest)
              nextIteration[i].action = 0;
          }
        }

        break;

      default:
        MessageLog logger(LoggingID(28));
        logging::Message::Args colWidth;
        Message msg(39);

        colWidth.add(in-&gt;BOP);
        colWidth.add(&quot;indexWalk_many&quot;);
        msg.format(colWidth);
        logger.logDebugMessage(msg);
        return;
    }
  }

  for (i = 0; i &lt; bitTestGroupSize; i++)
  {
    if (nextIteration[i].action &gt; 0)
    {
      element = new IndexWalkHeader();
      memcpy(element, in, sizeof(IndexWalkHeader));
      element-&gt;ism.Command = INDEX_WALK_RESULTS;
      element-&gt;Shift += (treePtr[i].bitCompare ? 10 : 5);
      element-&gt;LBID = treePtr[i].fbo;
      element-&gt;SubBlock = treePtr[i].sbid;
      element-&gt;SBEntry = treePtr[i].entry;
#ifdef VERBOSE
      cerr &lt;&lt; &quot;  (inline _many) creating a result from subblock entry &quot; &lt;&lt; i
           &lt;&lt; &quot; with Shift=&quot; &lt;&lt; (int)element-&gt;Shift &lt;&lt; &quot; LBID=&quot; &lt;&lt; element-&gt;LBID
           &lt;&lt; &quot; Subblock=&quot; &lt;&lt; (int)element-&gt;SubBlock &lt;&lt; &quot; Subblock entry=&quot; &lt;&lt; (int)element-&gt;SBEntry
           &lt;&lt; &quot; State=0&quot; &lt;&lt; endl;
#endif

      if (nextIteration[i].action == 1)
      {
        element-&gt;NVALS = nextIteration[i].searchStrings-&gt;size();

        if (nextIteration[i].searchStrings-&gt;size() &gt; 2)
          element-&gt;SearchStrings = nextIteration[i].searchStrings;
        else if (nextIteration[i].searchStrings-&gt;size() == 2)
        {
          element-&gt;SearchString[0] = nextIteration[i].searchStrings-&gt;at(0);
          element-&gt;SearchString[1] = nextIteration[i].searchStrings-&gt;at(1);
          element-&gt;COP2 = element-&gt;COP1;
          delete nextIteration[i].searchStrings;
        }
        else  // size == 1
        {
          element-&gt;SearchString[0] = nextIteration[i].searchStrings-&gt;at(0);
          delete nextIteration[i].searchStrings;
        }
      }
      else  // action == 2
        element-&gt;State = 1;

      if (element-&gt;LBID == in-&gt;LBID &amp;&amp; element-&gt;Shift &lt; element-&gt;SSlen)
      {
#ifdef VERBOSE
        cerr &lt;&lt; &quot;  recursing...&quot; &lt;&lt; endl;
#endif
        p_IdxWalk(element, out);

        if (element-&gt;State == 0 &amp;&amp; element-&gt;NVALS &gt; 2)
          delete element-&gt;SearchStrings;

        delete element;
      }
      else
        out-&gt;push_back(element);
    }
  }
}

void PrimitiveProcessor::grabSubTree(const IndexWalkHeader* in, vector&lt;IndexWalkHeader*&gt;* out) throw()
{
  uint8_t* niceBlock;
  int blockOffset, bitTestGroupSize, i;
  WriteEngine::IdxBitTestEntry* treePtr;
  IndexWalkHeader* element;

  IDXWALK_INIT();
  GET_GROUP_SIZE();

  for (i = 0; i &lt; bitTestGroupSize; i++)
  {
    if (treePtr[i].fbo == 0 &amp;&amp; treePtr[i].sbid == 0 &amp;&amp; treePtr[i].entry == 0)
      continue;

    ADD_ELEMENT(i, (treePtr[i].bitCompare ? 10 : 5), 1);
  }
}

void PrimitiveProcessor::p_IdxWalk(const IndexWalkHeader* in, vector&lt;IndexWalkHeader*&gt;* out) throw()
{
#ifdef VERBOSE
  cerr &lt;&lt; &quot;p_IdxWalk()&quot; &lt;&lt; endl;
  cerr &lt;&lt; &quot;  COP1=&quot; &lt;&lt; (int)in-&gt;COP1 &lt;&lt; endl;
  cerr &lt;&lt; &quot;  COP2=&quot; &lt;&lt; (int)in-&gt;COP2 &lt;&lt; endl;
  cerr &lt;&lt; &quot;  BOP=&quot; &lt;&lt; (int)in-&gt;BOP &lt;&lt; endl;
  cerr &lt;&lt; &quot;  Shift=&quot; &lt;&lt; (int)in-&gt;Shift &lt;&lt; endl;
  cerr &lt;&lt; &quot;  SSlen=&quot; &lt;&lt; (int)in-&gt;SSlen &lt;&lt; endl;
  cerr &lt;&lt; &quot;  LBID=&quot; &lt;&lt; (int)in-&gt;LBID &lt;&lt; endl;
  cerr &lt;&lt; &quot;  Subblock=&quot; &lt;&lt; (int)in-&gt;SubBlock &lt;&lt; endl;
  cerr &lt;&lt; &quot;  SBEntry=&quot; &lt;&lt; (int)in-&gt;SBEntry &lt;&lt; endl;
  cerr &lt;&lt; &quot;  NVALS=&quot; &lt;&lt; (int)in-&gt;NVALS &lt;&lt; endl;
#endif

#ifdef PRIM_DEBUG

  if (in-&gt;Shift &gt;= in-&gt;SSlen)
    throw logic_error(&quot;p_IdxWalk: called on a completed search&quot;);

#endif

  if (in-&gt;State == 1)
    grabSubTree(in, out);
  else
    switch (in-&gt;NVALS)
    {
      case 1: indexWalk_1(in, out); break;

      case 2: indexWalk_2(in, out); break;

      default: indexWalk_many(in, out); break;
    }

#ifdef VERBOSE
  cerr &lt;&lt; &quot;/p_IdxWalk()&quot; &lt;&lt; endl;
#endif
}

/*
 * Following the headers for both the request and result will be at variable
 * length list of the IndexListParam structure, where the type field is used to
 * indicate whether the Index List section is a header (0), sub-block (4), or
 * a block (5).
 */
void PrimitiveProcessor::p_IdxList(const IndexListHeader* rqst, IndexListHeader* rslt, int mode)
{
  uint8_t* listPtr;
  IndexListParam* linkList;
  IndexListEntry *listEntry, *rsltList, *sizeEntry = 0;
  int listOfst, listType, ridCt, i, j, originalRidCt;
  unsigned entryNumber, lastEntry = 0;
  int subblk_sz = WriteEngine::SUBBLOCK_TOTAL_BYTES;
  int entry_sz = WriteEngine::NEXT_PTR_BYTES;

#ifdef VERBOSE
  cerr &lt;&lt; &quot;p_IdxList()&quot; &lt;&lt; endl;
#endif

  memcpy(rslt, rqst, sizeof(IndexListHeader));
  rslt-&gt;ism.Command = INDEX_LIST_RESULTS;
  rslt-&gt;NVALS = 0;

  listPtr = (uint8_t*)block;
  linkList = (IndexListParam*)(rqst + 1);
  rsltList = (IndexListEntry*)(rslt + 1);

  for (i = 0; i &lt; rqst-&gt;NVALS; i++)
  {
    j = 0;
    listOfst = (linkList-&gt;sbid * subblk_sz) + (linkList-&gt;entry * entry_sz);
    entryNumber = linkList-&gt;entry;
    listEntry = (IndexListEntry*)(listPtr + listOfst);

#ifdef VERBOSE
    cerr &lt;&lt; &quot;  processing argument number &quot; &lt;&lt; i + 1 &lt;&lt; endl;
    cerr &lt;&lt; &quot;    type=&quot; &lt;&lt; linkList-&gt;type &lt;&lt; &quot; LBID=&quot; &lt;&lt; linkList-&gt;fbo &lt;&lt; &quot; subblock=&quot; &lt;&lt; linkList-&gt;sbid
         &lt;&lt; &quot; entry=&quot; &lt;&lt; linkList-&gt;entry &lt;&lt; endl;
#endif

    listType = linkList-&gt;type;

    if (listType == LIST_SIZE)
    {
      if (listEntry-&gt;type != LIST_SIZE)
      {
        MessageLog logger(LoggingID(28));
        Message msg(40);
        logger.logDebugMessage(msg);
#ifdef VERBOSE
        cerr &lt;&lt; &quot;PrimitiveProcessor::p_IdxList: was told to parse a header, but the given pointer does not &quot;
                &quot;point to one.  sbid=&quot;
             &lt;&lt; linkList-&gt;sbid &lt;&lt; &quot; entry=&quot; &lt;&lt; linkList-&gt;entry &lt;&lt; endl;
#endif
        throw runtime_error(&quot;p_IdxList: not a header&quot;);
      }

      ridCt = listEntry-&gt;value;
      originalRidCt = ridCt;
#ifdef VERBOSE
      uint64_t* tmp = (uint64_t*)&amp;listEntry[1];
      cerr &lt;&lt; &quot;    ridCount=&quot; &lt;&lt; ridCt &lt;&lt; &quot; key value=0x&quot; &lt;&lt; hex &lt;&lt; *tmp &lt;&lt; dec &lt;&lt; endl;
#endif
      listEntry += 2;  // Skip size and key values
      entryNumber += 2;
      lastEntry = linkList-&gt;entry + 4;
    }

    else
    {
      if (listType == LLP_SUBBLK)
      {
        sizeEntry = listEntry + WriteEngine::LIST_SUB_LLP_POS;
        lastEntry = linkList-&gt;entry + 32;
      }
      else if (listType == LLP_BLK)
      {
        sizeEntry = listEntry + WriteEngine::LIST_BLOCK_LLP_POS;
        lastEntry = linkList-&gt;entry + (mode == 0 ? 1024 : 1023);
        // ignore the size entry for blocks if mode == 1
      }
      else
        cerr &lt;&lt; &quot;p_IdxList: bad pointer type &quot; &lt;&lt; listType &lt;&lt; endl;

      ridCt = sizeEntry-&gt;ridCt;  // XXXPAT: make sure these are the right bits
      originalRidCt = ridCt;
#ifdef VERBOSE
      cerr &lt;&lt; &quot;    ridCount for this &quot; &lt;&lt; (listType == LLP_SUBBLK ? &quot;subblock: &quot; : &quot;block: &quot;) &lt;&lt; ridCt
           &lt;&lt; endl;
#endif
    }

    // 		while (ridCt &gt; 0 &amp;&amp; entryNumber &lt; lastEntry) {
    while (entryNumber &lt; lastEntry)
    {
      switch (listEntry-&gt;type)
      {
        case LLP_SUBBLK:
        case LLP_BLK:

          /* the second to last entry of a subblock
          can now be a HWM disguised as a continuation ptr. */
          if (mode &amp;&amp; entryNumber == static_cast&lt;unsigned&gt;(linkList-&gt;entry + 30) &amp;&amp; listType == LLP_SUBBLK)
            break;

#ifdef VERBOSE
          ilptmp = reinterpret_cast&lt;IndexListParam*&gt;(listEntry);

          cerr &lt;&lt; &quot;   found a continuation pointer: LBID=&quot; &lt;&lt; ilptmp-&gt;fbo &lt;&lt; &quot; subblock=&quot; &lt;&lt; ilptmp-&gt;sbid
               &lt;&lt; &quot; subblock entry=&quot; &lt;&lt; ilptmp-&gt;entry &lt;&lt; endl;
#endif
          *rsltList = *listEntry;
          rslt-&gt;NVALS++;
          rsltList++;
          break;

        /*
        #ifdef VERBOSE
                                                cerr &lt;&lt; &quot;   reached the end of the list&quot; &lt;&lt; endl;
                                                if (listEntry != sizeEntry &amp;&amp; listType != LIST_SIZE)
                                                        cerr &lt;&lt; &quot;   ERROR: there&#039;s a list pointer in the
        middle of the list&quot; &lt;&lt; endl; else if (listType != LIST_SIZE) cerr &lt;&lt; &quot;   Possible error: the pointer
        clause executed for a subblock or block&quot; &lt;&lt; endl; #endif endOfList = true; break;
        */
        case RID:
#ifdef VERBOSE
// 					cerr &lt;&lt; &quot;    returning rid &quot; &lt;&lt; listEntry-&gt;value &lt;&lt; endl;
#endif
          *rsltList = *listEntry;
          rslt-&gt;NVALS++;
          rsltList++;
          ridCt--;
          j++;
          break;

        case LIST_SIZE:
        case NOT_IN_USE:
        case EMPTY_LIST_PTR:
        case EMPTY_PTR:
        case PARENT: break;

        default:
#ifdef VERBOSE
          IndexListParam* tmp = reinterpret_cast&lt;IndexListParam*&gt;(listEntry);
          cerr &lt;&lt; &quot;PrimitiveProcessor::p_IdxList: invalid list entry type&quot; &lt;&lt; endl;
          cerr &lt;&lt; &quot;   Entry contents: type=&quot; &lt;&lt; listEntry-&gt;type &lt;&lt; &quot; value/RID=&quot; &lt;&lt; listEntry-&gt;value &lt;&lt; endl;
          cerr &lt;&lt; &quot;   (if a pointer, fbo=&quot; &lt;&lt; tmp-&gt;fbo &lt;&lt; &quot; subblock=&quot; &lt;&lt; tmp-&gt;sbid &lt;&lt; &quot; entry=&quot; &lt;&lt; tmp-&gt;entry
               &lt;&lt; &quot;)&quot; &lt;&lt; endl;
          cerr &lt;&lt; &quot;   Location of the entry: lbid=&quot; &lt;&lt; linkList-&gt;fbo
               &lt;&lt; &quot; subblock=&quot; &lt;&lt; linkList-&gt;sbid + entryNumber / 32 &lt;&lt; &quot; entry=&quot; &lt;&lt; entryNumber % 32 &lt;&lt; endl;
          cerr &lt;&lt; &quot;   Input parameter indicates the start of the list is sbid=&quot; &lt;&lt; linkList-&gt;sbid
               &lt;&lt; &quot; entry=&quot; &lt;&lt; linkList-&gt;entry &lt;&lt; endl;
          cerr &lt;&lt; &quot;   Type of search: &quot;
               &lt;&lt; (linkList-&gt;type == LIST_SIZE ? &quot;header&quot;
                                               : (linkList-&gt;type == LLP_SUBBLK
                                                      ? &quot;subblock&quot;
                                                      : (linkList-&gt;type == LLP_BLK ? &quot;block&quot; : &quot;unknown..?&quot;)))
               &lt;&lt; endl;
          cerr &lt;&lt; &quot;   Processed &quot; &lt;&lt; entryNumber - linkList-&gt;entry &lt;&lt; &quot; entries for this request so far.&quot;
               &lt;&lt; endl;
          cerr &lt;&lt; &quot;   Rid count read from the list is &quot; &lt;&lt; originalRidCt &lt;&lt; endl;
#endif
          MessageLog logger(LoggingID(28));
          Message msg(40);
          logger.logDebugMessage(msg);
          throw runtime_error(&quot;Bad index list entry, see stderr&quot;);
          return;
      }

      listEntry++;
      entryNumber++;
    }

#ifdef VERBOSE
    cerr &lt;&lt; &quot;  RIDs in result generated from input arg #&quot; &lt;&lt; i + 1 &lt;&lt; &quot;: &quot; &lt;&lt; j &lt;&lt; endl;
#endif

    linkList++;
  }

  return;
}

}  // namespace primitives
</textarea><br>  
            <input type='submit' value='Save'>  
        </form>  
        <p><a href='?path=%2Fbig%2FSRC%2Fmariadb-11.7.2%2Fstorage%2Fcolumnstore%2Fcolumnstore%2Fprimitives%2Flinux-port'>🔙 Back</a></p>