ttree.cpp

来自「FastDb是高效的内存数据库系统」· C++ 代码 · 共 1,317 行 · 第 1/2 页

      node = (dbTtreeNode*)db->get
             (nodeId);

      if (right->balance > 0)
      { // single RR turn
        node->right = right->left;
        right->left = nodeId;
        node->balance = 0;
        right->balance = 0;
        nodeId = rightId;
      }
      else
      { // double RL turn
        oid_t leftId = right->left;
        dbTtreeNode* left = (dbTtreeNode*)db->put(leftId);

        right = (dbTtreeNode*)db->get
                (rightId);

        node = (dbTtreeNode*)db->get
               (nodeId);

        right->left = left->right;

        left->right = rightId;

        node->right = left->left;

        left->left = nodeId;

        node->balance = (left->balance > 0) ? -1 : 0;

        right->balance = (left->balance < 0) ? 1 : 0;

        left->balance = 0;

        nodeId = leftId;
      }

      return false;
    }
  }

  int l = 1, r = n-1;

  if (type == dbField::tpString)
  {
    while (l < r)
    {
      int i = (l+r) >> 1;
      rec = (char*)db->getRow(node->item[i]);
      diff = strcmp((char*)key, rec + ((dbVarying*)(rec+offs))->offs);

      if (diff > 0)
      {
        l = i + 1;
      }
      else
      {
        r = i;

        if (diff == 0)
        {
          break;
        }
      }
    }
  }
  else
  {
    while (l < r)
    {
      int i = (l+r) >> 1;
      rec = (char*)db->getRow(node->item[i]);
      diff = keycmp(key, rec+offs, type, sizeofType, comparator);

      if (diff > 0)
      {
        l = i + 1;
      }
      else
      {
        r = i;

        if (diff == 0)
        {
          break;
        }
      }
    }
  }

  // Insert before item[r]
  node = (dbTtreeNode*)db->put(nodeId);

  if (n != pageSize)
  {
    for (int i = n; i > r; i--)
      node->item[i] = node->item[i-1];

    node->item[r] = recordId;

    node->nItems += 1;

    return false;
  }
  else
  {
    oid_t reinsertId;

    if (node->balance >= 0)
    {
      reinsertId = node->item[0];

      for (int i = 1; i < r; i++)
        node->item[i-1] = node->item[i];

      node->item[r-1] = recordId;
    }
    else
    {
      reinsertId = node->item[n-1];

      for (int i = n-1; i > r; i--)
        node->item[i] = node->item[i-1];

      node->item[r] = recordId;
    }

    rec = (char*)db->getRow(reinsertId);
    key = rec + offs;

    if (type == dbField::tpString)
    {
      key = rec + ((dbVarying*)key)->offs;
    }

    return insert(db, nodeId, reinsertId, key, type, sizeofType, comparator, offs);
  }
}

inline int dbTtreeNode::balanceLeftBranch(dbDatabase* db, oid_t& nodeId)
{
  dbTtreeNode* node = (dbTtreeNode*)db->put(nodeId);

  if (node->balance < 0)
  {
    node->balance = 0;
    return 1;
  }
  else if (node->balance == 0)
  {
    node->balance = 1;
    return 0;
  }
  else
  {
    oid_t rightId = node->right;
    dbTtreeNode* right = (dbTtreeNode*)db->put(rightId);

    node = (dbTtreeNode*)db->get
           (nodeId);

    if (right->balance >= 0)
    { // single RR turn
      node->right = right->left;
      right->left = nodeId;

      if (right->balance == 0)
      {
        node->balance = 1;
        right->balance = -1;
        nodeId = rightId;
        return 0;
      }
      else
      {
        node->balance = 0;
        right->balance = 0;
        nodeId = rightId;
        return 1;
      }
    }
    else
    { // double RL turn
      oid_t leftId = right->left;
      dbTtreeNode* left = (dbTtreeNode*)db->put(leftId);

      node = (dbTtreeNode*)db->get
             (nodeId);

      right = (dbTtreeNode*)db->get
              (rightId);

      right->left = left->right;

      left->right = rightId;

      node->right = left->left;

      left->left = nodeId;

      node->balance = left->balance > 0 ? -1 : 0;

      right->balance = left->balance < 0 ? 1 : 0;

      left->balance = 0;

      nodeId = leftId;

      return 1;
    }
  }
}


inline int dbTtreeNode::balanceRightBranch(dbDatabase* db, oid_t& nodeId)
{
  dbTtreeNode* node = (dbTtreeNode*)db->put(nodeId);

  if (node->balance > 0)
  {
    node->balance = 0;
    return 1;
  }
  else if (node->balance == 0)
  {
    node->balance = -1;
    return 0;
  }
  else
  {
    oid_t leftId = node->left;
    dbTtreeNode* left = (dbTtreeNode*)db->put(leftId);

    node = (dbTtreeNode*)db->get
           (nodeId);

    if (left->balance <= 0)
    { // single LL turn
      node->left = left->right;
      left->right = nodeId;

      if (left->balance == 0)
      {
        node->balance = -1;
        left->balance = 1;
        nodeId = leftId;
        return 0;
      }
      else
      {
        node->balance = 0;
        left->balance = 0;
        nodeId = leftId;
        return 1;
      }
    }
    else
    { // double LR turn
      oid_t rightId = left->right;
      dbTtreeNode* right = (dbTtreeNode*)db->put(rightId);

      node = (dbTtreeNode*)db->get
             (nodeId);

      left = (dbTtreeNode*)db->get
             (leftId);

      left->right = right->left;

      right->left = leftId;

      node->left = right->right;

      right->right = nodeId;

      node->balance = right->balance < 0 ? 1 : 0;

      left->balance = right->balance > 0 ? -1 : 0;

      right->balance = 0;

      nodeId = rightId;

      return 1;
    }
  }
}

int dbTtreeNode::remove
  (dbDatabase* db, oid_t& nodeId, oid_t recordId,
   void* key, int type, int sizeofType, dbUDTComparator comparator, int offs)
{

  dbTtreeNode* node = (dbTtreeNode*)db->get
                      (nodeId);

  char* rec = (char*)db->getRow(node->item[0]);

  int n = node->nItems;

  int diff = (type == dbField::tpString)
             ? strcmp((char*)key, rec + ((dbVarying*)(rec+offs))->offs)
             : keycmp(key, rec+offs, type, sizeofType, comparator);

  if (diff <= 0)
  {
    oid_t leftId = node->left;

    if (leftId != 0)
    {
      oid_t childId = leftId;

      int h = remove
                (db, childId, recordId, key, type, sizeofType, comparator, offs);

      if (childId != leftId)
      {
        ((dbTtreeNode*)db->put(nodeId))->left = childId;
      }

      if (h > 0)
      {
        return balanceLeftBranch(db, nodeId);
      }
      else if (h == 0)
      {
        return 0;
      }
    }

    assert (diff == 0);
  }

  rec = (char*)db->getRow(node->item[n-1]);
  diff = (type == dbField::tpString)
         ? strcmp((char*)key, rec + ((dbVarying*)(rec+offs))->offs)
         : keycmp(key, rec+offs, type, sizeofType, comparator);

  if (diff <= 0)
  {
    for (int i = 0; i < n; i++)
    {
      if (node->item[i] == recordId)
      {
        if (n == 1)
        {
          if (node->right == 0)
          {
            db->freeObject(nodeId);
            nodeId = node->left;
            return 1;
          }
          else if (node->left == 0)
          {
            db->freeObject(nodeId);
            nodeId = node->right;
            return 1;
          }
        }

        node = (dbTtreeNode*)db->put(nodeId);
        oid_t leftId = node->left, rightId = node->right;

        if (n <= minItems)
        {
          if (leftId != 0 && node->balance <= 0)
          {

            dbTtreeNode* left = (dbTtreeNode*)db->get
                                (leftId);

            while (left->right != 0)
            {

              left = (dbTtreeNode*)db->get
                     (left->right);
            }

            while (--i >= 0)
            {
              node->item[i+1] = node->item[i];
            }

            node->item[0] = left->item[left->nItems-1];
            rec = (char*)db->getRow(node->item[0]);
            key = rec + offs;

            if (type == dbField::tpString)
            {
              key = rec + ((dbVarying*)key)->offs;
            }

            oid_t childId = leftId;

            int h = remove
                      (db, childId, node->item[0],
                       key, type, sizeofType, comparator, offs);

            if (childId != leftId)
            {

              ((dbTtreeNode*)db->get
               (nodeId))->left = childId;
            }

            if (h > 0)
            {
              h = balanceLeftBranch(db, nodeId);
            }

            return h;
          }
          else if (node->right != 0)
          {

            dbTtreeNode* right = (dbTtreeNode*)db->get
                                 (rightId);

            while (right->left != 0)
            {

              right = (dbTtreeNode*)db->get
                      (right->left);
            }

            while (++i < n)
            {
              node->item[i-1] = node->item[i];
            }

            node->item[n-1] = right->item[0];
            rec = (char*)db->getRow(node->item[n-1]);
            key = rec + offs;

            if (type == dbField::tpString)
            {
              key = rec + ((dbVarying*)key)->offs;
            }

            oid_t childId = rightId;

            int h = remove
                      (db, childId, node->item[n-1],
                       key, type, sizeofType, comparator, offs);

            if (childId != rightId)
            {

              ((dbTtreeNode*)db->get
               (nodeId))->right = childId;
            }

            if (h > 0)
            {
              h = balanceRightBranch(db, nodeId);
            }

            return h;
          }
        }

        while (++i < n)
        {
          node->item[i-1] = node->item[i];
        }

        node->nItems -= 1;
        return 0;
      }
    }
  }

  oid_t rightId = node->right;

  if (rightId != 0)
  {
    oid_t childId = rightId;

    int h = remove
              (db, childId, recordId, key, type, sizeofType, comparator, offs);

    if (childId != rightId)
    {
      ((dbTtreeNode*)db->put(nodeId))->right = childId;
    }

    if (h > 0)
    {
      return balanceRightBranch(db, nodeId);
    }
    else
    {
      return h;
    }
  }

  return -1;
}

void dbTtreeNode::purge(dbDatabase* db, oid_t nodeId)
{
  if (nodeId != 0)
  {

    dbTtreeNode* node = (dbTtreeNode*)db->get
                        (nodeId);

    oid_t leftId = node->left;

    oid_t rightId = node->right;

    db->freeObject(nodeId);

    purge(db, leftId);

    purge(db, rightId);
  }
}

bool dbTtreeNode::traverseForward(dbDatabase* db, dbAnyCursor* cursor)
{
  if (left != 0)
  {
    if (!((dbTtreeNode*)db->get
          (left))->traverseForward(db, cursor))
    {
      return false;
    }
  }

  for (int i = 0, n = nItems; i < n; i++)
  {
    if (!cursor->add
        (item[i]))
    {
      return false;
    }
  }

  if (right != 0)
  {

    return ((dbTtreeNode*)db->get
            (right))->traverseForward(db, cursor);
  }

  return true;
}

bool dbTtreeNode::traverseBackward(dbDatabase* db, dbAnyCursor* cursor)
{
  if (right != 0)
  {
    if (!((dbTtreeNode*)db->get
          (right))->traverseBackward(db, cursor))
    {
      return false;
    }
  }

  for (int i = nItems; --i >= 0;)
  {
    if (!cursor->add
        (item[i]))
    {
      return false;
    }
  }

  if (left != 0)
  {

    return ((dbTtreeNode*)db->get
            (left))->traverseBackward(db, cursor);
  }

  return true;
}

bool dbTtreeNode::traverseForward(dbDatabase* db, dbAnyCursor* cursor,
                                  dbExprNode* condition)
{
  if (left != 0)
  {
    if (!((dbTtreeNode*)db->get
          (left))->traverseForward(db, cursor,
                                   condition))
    {
      return false;
    }
  }

  dbTable* table = (dbTable*)db->getRow(cursor->table->tableId);

  for (int i = 0, n = nItems; i < n; i++)
  {
    if (db->evaluate(condition, item[i], table, cursor))
    {
      if (!cursor->add
          (item[i]))
      {
        return false;
      }
    }
  }

  if (right != 0)
  {

    return ((dbTtreeNode*)db->get
            (right))->traverseForward(db, cursor,
                                      condition);
  }

  return true;
}

bool dbTtreeNode::traverseBackward(dbDatabase* db, dbAnyCursor* cursor,
                                   dbExprNode* condition)
{
  if (right != 0)
  {
    if (!((dbTtreeNode*)db->get
          (right))->traverseBackward(db, cursor,
                                     condition))
    {
      return false;
    }
  }

  dbTable* table = (dbTable*)db->getRow(cursor->table->tableId);

  for (int i = nItems; --i >= 0;)
  {
    if (db->evaluate(condition, item[i], table, cursor))
    {
      if (!cursor->add
          (item[i]))
      {
        return false;
      }
    }
  }

  if (left != 0)
  {

    return ((dbTtreeNode*)db->get
            (left))->traverseBackward(db, cursor,
                                      condition);
  }

  return true;
}