SHARE
TWEET

Untitled

a guest Dec 13th, 2018 61 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /** \brief Для не полностью заполненного текущего узла разделяет напополам его
  2.  *  полностью заполненного ребенка, определяемого курсором номер \c iChild на два нода/страницы.
  3.  *
  4.  *  Параметр \c iChild представляет индекс курсора, который не может быть 0, что означает
  5.  *  нарушение целостности (нет страницы с таким ребенком).
  6.  *  Т.к. в процессе сплита один из ключей ребенка уйдет в этот родительский нод,
  7.  *  данный нод должен иметь хотя бы один свободный слот под этот ключ. Если это не так,
  8.  *  полетит исключительная ситуация.
  9.  *  Для того, чтобы не было неопределенности по поводу индексов, заполненности и проч.
  10.  *  в соответствующем ребенке, подразумеваем, что он полностью заполнен. Если это не так,
  11.  *  кидаем искл. ситуацию.
  12.  */
  13. void BaseBTree::PageWrapper::splitChild(UShort iChild)
  14. {
  15.     if (isFull())
  16.         throw std::domain_error("A parent node is full, so its child can't be splitted");
  17.  
  18.     if (iChild > getKeysNum())
  19.         throw std::invalid_argument("Cursor not exists");
  20.  
  21.     // Ребенок, которого мы будем сплитить - полностью заполнен
  22.     PageWrapper* currentChild = new PageWrapper(_tree);
  23.     currentChild->readPageFromChild(*this, iChild);
  24.     // Позиция центрального элемента
  25.     UShort midPos = currentChild->getKeysNum() / 2;
  26.     Byte* midKey = currentChild->getKey(midPos);
  27.  
  28.     // Новый ребенок идущий от текущей вершины
  29.     PageWrapper* newAddedChild = new PageWrapper(_tree);
  30.     newAddedChild->allocPage(currentChild->getKeysNum() - iChild, true);
  31.     UShort j = 0;
  32.     // Копируем в newAddedChild ключи начиная после центрального элемента из currentChild
  33.     for(UShort i = midPos + 1; i < currentChild->getKeysNum(); i++)
  34.     {
  35.         newAddedChild->copyKey(newAddedChild->getKey(j), currentChild->getKey(i));
  36.         j++;
  37.     }
  38.  
  39.     // Добавляем центральный ключ в текущую вершину
  40.     insertNonFull(currentChild->getKey(midPos));
  41.  
  42.     // Уменьшаем количество ключей в currentChild: теперь значащие ключи лежат ДО mid pos
  43.     currentChild->setKeyNum(midPos);
  44.  
  45.     // Теперь надо найти позицию куда ключ был вставлен в текущей вершине
  46.     // и установить курсор справа от этой позиции на newAddedChild
  47.     UShort  pos;
  48.     for(pos = 0; pos < getKeysNum(); pos++)
  49.     {
  50.         // Если ключ равен вставленому, то позиция найдена
  51.         if(_tree->_comparator->isEqual(getKey(pos), midKey, _tree->getRecSize()))
  52.             break;
  53.     }
  54.     // Позиция была найдена
  55.     if(pos < getKeysNum())
  56.     {
  57.         // Устанавливаем значение правого курсора вставленной вершины на newAddedChild
  58.         setCursor(pos + 1, newAddedChild->getPageNum());
  59.     }
  60.     writePage();
  61.     currentChild->writePage();
  62.     newAddedChild->writePage();
  63. }
  64.  
  65. /** \brief Вставляет в не полностью заполненный узел ключ k с учетом порядка.
  66.  *
  67.  *  Если узел полный, кидает исключение.
  68.  *  Если для дерева не задан компаратор, кидает исключение.
  69.  */
  70. void BaseBTree::PageWrapper::insertNonFull(const Byte* toInsert)
  71. {
  72.     if (isFull())
  73.         throw std::domain_error("Node is full. Can't insert");
  74.  
  75.     IComparator* c = _tree->getComparator();
  76.     if (!c)
  77.         throw std::runtime_error("Comparator not set. Can't insert");
  78.  
  79.     UShort amount_Of_Keys = getKeysNum();
  80.     UShort pos = 0;
  81.     UShort recordSize = _tree->getRecSize();
  82.     Byte* key = getKey(pos);
  83.     // Пока ключ не null и меньше чем то что нужно вставить
  84.     while (key && c->compare(key,toInsert,recordSize))
  85.     {
  86.         // Встретили пустое значение
  87.         if((pos > 0 && *(getKey(pos - 1)) != 0 && *(getKey(pos)) == 0))
  88.             break;
  89.         pos++;
  90.         key = getKey(pos);
  91.     }
  92.  
  93.     // Если последний ключ уже занят, то увеличиваем кол-во ключей
  94.     if(*(getKey(amount_Of_Keys - 1)) != 0)
  95.         setKeyNum(amount_Of_Keys + 1);
  96.  
  97.  
  98.  
  99.     // Перемещаем ключи начиная с pos на одну ячейку вперед
  100.     UShort lastElPos = getKeysNum() - 1;
  101.     if(lastElPos > pos)
  102.         // Перемещаем курсоры начиная с pos на одну ячейку вперед
  103.         copyCursors(getCursorPtr(pos + 1), getCursorPtr(pos), CURSOR_SZ);
  104.     // Добавленный курсор(справа) от вставленной вершины обозначим как 0 для наглядности
  105.     setCursor(pos + 1, 0);
  106.     while(lastElPos > pos)
  107.     {
  108.         copyKey(getKey(lastElPos), getKey(lastElPos - 1));
  109.         lastElPos--;
  110.     }
  111.  
  112.     // В освобожденную ячейку помещаем значение, которое хотели вставить
  113.     *(getKey(pos)) = *toInsert;
  114.  
  115.     writePage();
  116. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top