tdbBtree.c 15.6 KB
Newer Older
H
Hongze Cheng 已提交
1 2 3 4 5 6 7 8 9 10 11 12 13
/*
 * Copyright (c) 2019 TAOS Data, Inc. <jhtao@taosdata.com>
 *
 * This program is free software: you can use, redistribute, and/or modify
 * it under the terms of the GNU Affero General Public License, version 3
 * or later ("AGPL"), as published by the Free Software Foundation.
 *
 * 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.
 *
 * You should have received a copy of the GNU Affero General Public License
 * along with this program. If not, see <http://www.gnu.org/licenses/>.
H
refact  
Hongze Cheng 已提交
14 15
 */

H
Hongze Cheng 已提交
16 17
#include "tdbInt.h"

H
Hongze Cheng 已提交
18 19 20 21 22
#define TDB_BTREE_ROOT 0x1
#define TDB_BTREE_LEAF 0x2

#define TDB_BTREE_PAGE_IS_ROOT(flags) TDB_FLAG_HAS(flags, TDB_BTREE_ROOT)
#define TDB_BTREE_PAGE_IS_LEAF(flags) TDB_FLAG_HAS(flags, TDB_BTREE_LEAF)
H
Hongze Cheng 已提交
23 24 25
#define TDB_BTREE_ASSERT_FLAG(flags)                                                 \
  ASSERT(TDB_FLAG_IS(flags, TDB_BTREE_ROOT) || TDB_FLAG_IS(flags, TDB_BTREE_LEAF) || \
         TDB_FLAG_IS(flags, TDB_BTREE_ROOT | TDB_BTREE_LEAF) || TDB_FLAG_IS(flags, 0))
H
Hongze Cheng 已提交
26

H
Hongze Cheng 已提交
27
struct SBTree {
H
more  
Hongze Cheng 已提交
28 29 30
  SPgno          root;
  int            keyLen;
  int            valLen;
H
Hongze Cheng 已提交
31
  SPager        *pPager;
H
more  
Hongze Cheng 已提交
32
  FKeyComparator kcmpr;
H
more  
Hongze Cheng 已提交
33
  u8             fanout;
H
Hongze Cheng 已提交
34
  int            pageSize;
H
more  
Hongze Cheng 已提交
35 36 37 38
  int            maxLocal;
  int            minLocal;
  int            maxLeaf;
  int            minLeaf;
H
Hongze Cheng 已提交
39 40
};

H
more  
Hongze Cheng 已提交
41 42 43 44 45
typedef struct SFreeCell {
  u16 size;
  u16 next;
} SFreeCell;

H
Hongze Cheng 已提交
46 47 48 49 50
typedef struct {
  u16     flags;
  SBTree *pBt;
} SBtreeZeroPageArg;

H
Hongze Cheng 已提交
51
static int tdbBtCursorMoveTo(SBtCursor *pCur, const void *pKey, int kLen);
H
more  
Hongze Cheng 已提交
52
static int tdbEncodeLength(u8 *pBuf, uint32_t len);
H
more  
Hongze Cheng 已提交
53
static int tdbCompareKeyAndCell(const void *pKey, int kLen, const void *pCell);
H
Hongze Cheng 已提交
54
static int tdbDefaultKeyCmprFn(const void *pKey1, int keyLen1, const void *pKey2, int keyLen2);
H
Hongze Cheng 已提交
55
static int tdbBtreeOpenImpl(SBTree *pBt);
H
Hongze Cheng 已提交
56 57
static int tdbBtreeZeroPage(SPage *pPage, void *arg);
static int tdbBtreeInitPage(SPage *pPage, void *arg);
H
Hongze Cheng 已提交
58

H
Hongze Cheng 已提交
59
int tdbBtreeOpen(int keyLen, int valLen, SPager *pPager, FKeyComparator kcmpr, SBTree **ppBt) {
H
Hongze Cheng 已提交
60
  SBTree *pBt;
H
Hongze Cheng 已提交
61
  int     ret;
H
more  
Hongze Cheng 已提交
62

H
Hongze Cheng 已提交
63
  *ppBt = NULL;
H
Hongze Cheng 已提交
64 65 66 67 68 69 70 71 72 73

  pBt = (SBTree *)calloc(1, sizeof(*pBt));
  if (pBt == NULL) {
    return -1;
  }

  // pBt->keyLen
  pBt->keyLen = keyLen;
  // pBt->valLen
  pBt->valLen = valLen;
H
refact  
Hongze Cheng 已提交
74 75
  // pBt->pPager
  pBt->pPager = pPager;
H
Hongze Cheng 已提交
76 77
  // pBt->kcmpr
  pBt->kcmpr = kcmpr ? kcmpr : tdbDefaultKeyCmprFn;
H
more  
Hongze Cheng 已提交
78 79 80 81 82 83 84
  // pBt->fanout
  if (keyLen == TDB_VARIANT_LEN) {
    pBt->fanout = TDB_DEFAULT_FANOUT;
  } else {
    ASSERT(0);
    // TODO: pBt->fanout = 0;
  }
H
Hongze Cheng 已提交
85 86 87 88
  // pBt->pageSize
  pBt->pageSize = tdbPagerGetPageSize(pPager);
  // pBt->maxLocal
  pBt->maxLocal = (pBt->pageSize - sizeof(SPageHdr)) / pBt->fanout;
H
Hongze Cheng 已提交
89
  // pBt->minLocal: Should not be allowed smaller than 15, which is [nPayload][nKey][nData]
H
Hongze Cheng 已提交
90 91 92 93 94
  pBt->minLocal = (pBt->pageSize - sizeof(SPageHdr)) / pBt->fanout / 2;
  // pBt->maxLeaf
  pBt->maxLeaf = pBt->pageSize - sizeof(SPageHdr);
  // pBt->minLeaf
  pBt->minLeaf = pBt->minLocal;
H
Hongze Cheng 已提交
95

H
Hongze Cheng 已提交
96 97 98 99 100 101 102
  // TODO: pBt->root
  ret = tdbBtreeOpenImpl(pBt);
  if (ret < 0) {
    free(pBt);
    return -1;
  }

H
Hongze Cheng 已提交
103
  *ppBt = pBt;
H
Hongze Cheng 已提交
104 105 106 107 108 109 110 111
  return 0;
}

int tdbBtreeClose(SBTree *pBt) {
  // TODO
  return 0;
}

H
more  
Hongze Cheng 已提交
112
int tdbBtreeCursor(SBtCursor *pCur, SBTree *pBt) {
H
more  
Hongze Cheng 已提交
113 114
  pCur->pBt = pBt;
  pCur->iPage = -1;
H
more  
Hongze Cheng 已提交
115
  pCur->pPage = NULL;
H
Hongze Cheng 已提交
116
  pCur->idx = -1;
H
more  
Hongze Cheng 已提交
117

H
more  
Hongze Cheng 已提交
118 119 120
  return 0;
}

H
Hongze Cheng 已提交
121
int tdbBtCursorInsert(SBtCursor *pCur, const void *pKey, int kLen, const void *pVal, int vLen) {
H
Hongze Cheng 已提交
122 123
  int     ret;
  SPager *pPager;
H
Hongze Cheng 已提交
124 125 126 127 128 129 130

  ret = tdbBtCursorMoveTo(pCur, pKey, kLen);
  if (ret < 0) {
    // TODO: handle error
    return -1;
  }

H
Hongze Cheng 已提交
131
  if (pCur->idx == -1) {
H
Hongze Cheng 已提交
132
    ASSERT(TDB_PAGE_NCELLS(pCur->pPage) == 0);
H
Hongze Cheng 已提交
133 134 135
    // TODO: insert the K-V pair to idx 0
  }

H
more  
Hongze Cheng 已提交
136 137 138
  return 0;
}

H
Hongze Cheng 已提交
139
static int tdbBtCursorMoveTo(SBtCursor *pCur, const void *pKey, int kLen) {
H
Hongze Cheng 已提交
140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159
  int     ret;
  SBTree *pBt;
  SPager *pPager;

  pBt = pCur->pBt;
  pPager = pBt->pPager;

  if (pCur->iPage < 0) {
    ASSERT(pCur->iPage == -1);
    ASSERT(pCur->idx == -1);

    // Move from the root
    ret = tdbPagerFetchPage(pPager, pBt->root, &(pCur->pPage), tdbBtreeInitPage, pBt);
    if (ret < 0) {
      ASSERT(0);
      return -1;
    }

    pCur->iPage = 0;

H
Hongze Cheng 已提交
160
    if (TDB_PAGE_NCELLS(pCur->pPage) == 0) {
H
Hongze Cheng 已提交
161
      // Current page is empty
H
Hongze Cheng 已提交
162
      ASSERT(TDB_FLAG_IS(TDB_PAGE_FLAGS(pCur->pPage), TDB_BTREE_ROOT | TDB_BTREE_LEAF));
H
Hongze Cheng 已提交
163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205
      return 0;
    }

    // Search from root page down to leaf
    {
      // TODO
      ASSERT(0);
      // ret = tdbBtCursorMoveToRoot(pCur);
      // if (ret < 0) {
      //   return -1;
      // }

      // if (pCur->pPage->pHdr->nCells == 0) {
      //   // Tree is empty
      // } else {
      //   for (;;) {
      //     int lidx, ridx, midx, c;

      //     pBtPage = pCur->pPage;
      //     lidx = 0;
      //     ridx = pBtPage->pHdr->nCells - 1;
      //     while (lidx <= ridx) {
      //       midx = (lidx + ridx) >> 1;
      //       pCell = (void *)(pBtPage->aData + pBtPage->aCellIdx[midx]);

      //       c = tdbCompareKeyAndCell(pKey, kLen, pCell);
      //       if (c == 0) {
      //         break;
      //       } else if (c < 0) {
      //         lidx = lidx + 1;
      //       } else {
      //         ridx = ridx - 1;
      //       }
      //     }
      //   }

      //   /* code */
      // }
    }

  } else {
    // TODO: Move the cursor from a some position instead of a clear state
  }
H
more  
Hongze Cheng 已提交
206

H
Hongze Cheng 已提交
207 208
  return 0;
}
H
more  
Hongze Cheng 已提交
209

H
Hongze Cheng 已提交
210 211 212
static int tdbEncodeKeyValue(const void *pKey, int kLen, int kLenG, const void *pVal, int vLen, int vLenG, void *pBuf,
                             int *bLen) {
  u8 *pPtr;
H
more  
Hongze Cheng 已提交
213

H
Hongze Cheng 已提交
214 215 216 217 218 219 220 221 222 223 224
  ASSERT(kLen > 0 && vLen > 0);
  ASSERT(kLenG == TDB_VARIANT_LEN || kLenG == kLen);
  ASSERT(vLenG == TDB_VARIANT_LEN || vLenG == vLen);

  pPtr = (u8 *)pBuf;
  if (kLenG == TDB_VARIANT_LEN) {
    pPtr += tdbEncodeLength(pPtr, kLen);
  }

  if (vLenG == TDB_VARIANT_LEN) {
    pPtr += tdbEncodeLength(pPtr, vLen);
H
more  
Hongze Cheng 已提交
225
  }
H
more  
Hongze Cheng 已提交
226

H
Hongze Cheng 已提交
227 228 229 230 231 232 233
  memcpy(pPtr, pKey, kLen);
  pPtr += kLen;

  memcpy(pPtr, pVal, vLen);
  pPtr += vLen;

  *bLen = pPtr - (u8 *)pBuf;
H
more  
Hongze Cheng 已提交
234
  return 0;
H
Hongze Cheng 已提交
235 236 237
}

static int tdbDecodeKeyValue(const void *pBuf, void *pKey, int *kLen, void *pVal, int *vLen) {
H
more  
Hongze Cheng 已提交
238 239 240 241 242 243 244 245 246 247
  if (*kLen == TDB_VARIANT_LEN) {
    // Decode the key length
  }

  if (*vLen == TDB_VARIANT_LEN) {
    // Decode the value length
  }

  // TODO: decode the key and value

H
Hongze Cheng 已提交
248 249 250
  return 0;
}

H
more  
Hongze Cheng 已提交
251
static int tdbEncodeLength(u8 *pBuf, uint32_t len) {
H
Hongze Cheng 已提交
252 253 254 255 256 257 258 259 260 261
  int iCount = 0;

  while (len > 127) {
    pBuf[iCount++] = (u8)((len & 0xff) | 128);
    len >>= 7;
  }

  pBuf[iCount++] = (u8)len;

  return iCount;
H
more  
Hongze Cheng 已提交
262 263 264
}

static int tdbBtCursorMoveToRoot(SBtCursor *pCur) {
H
refact  
Hongze Cheng 已提交
265 266
  SBTree *pBt;
  SPager *pPager;
H
Hongze Cheng 已提交
267
  SPage  *pPage;
H
refact  
Hongze Cheng 已提交
268
  int     ret;
H
more  
Hongze Cheng 已提交
269 270

  pBt = pCur->pBt;
H
refact  
Hongze Cheng 已提交
271
  pPager = pBt->pPager;
H
more  
Hongze Cheng 已提交
272

H
Hongze Cheng 已提交
273 274 275 276
  // pPage = tdbPagerGet(pPager, pBt->root, true);
  // if (pPage == NULL) {
  //   // TODO: handle error
  // }
H
more  
Hongze Cheng 已提交
277

H
Hongze Cheng 已提交
278 279 280 281 282
  // ret = tdbInitBtPage(pPage, &pBtPage);
  // if (ret < 0) {
  //   // TODO
  //   return 0;
  // }
H
more  
Hongze Cheng 已提交
283

H
Hongze Cheng 已提交
284 285
  // pCur->pPage = pBtPage;
  // pCur->iPage = 0;
H
more  
Hongze Cheng 已提交
286 287 288 289

  return 0;
}

H
more  
Hongze Cheng 已提交
290 291
static int tdbCompareKeyAndCell(const void *pKey, int kLen, const void *pCell) {
  /* TODO */
H
more  
Hongze Cheng 已提交
292
  return 0;
H
Hongze Cheng 已提交
293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312
}

static int tdbDefaultKeyCmprFn(const void *pKey1, int keyLen1, const void *pKey2, int keyLen2) {
  int mlen;
  int cret;

  ASSERT(keyLen1 > 0 && keyLen2 > 0 && pKey1 != NULL && pKey2 != NULL);

  mlen = keyLen1 < keyLen2 ? keyLen1 : keyLen2;
  cret = memcmp(pKey1, pKey2, mlen);
  if (cret == 0) {
    if (keyLen1 < keyLen2) {
      cret = -1;
    } else if (keyLen1 > keyLen2) {
      cret = 1;
    } else {
      cret = 0;
    }
  }
  return cret;
H
Hongze Cheng 已提交
313 314 315 316 317 318 319 320 321 322
}

static int tdbBtreeOpenImpl(SBTree *pBt) {
  // Try to get the root page of the an existing btree

  SPgno  pgno;
  SPage *pPage;
  int    ret;

  {
H
Hongze Cheng 已提交
323
    // 1. TODO: Search the main DB to check if the DB exists
H
Hongze Cheng 已提交
324 325 326 327 328 329 330 331 332
    pgno = 0;
  }

  if (pgno != 0) {
    pBt->root = pgno;
    return 0;
  }

  // Try to create a new database
H
Hongze Cheng 已提交
333 334 335 336 337 338 339
  SBtreeZeroPageArg zArg = {.flags = TDB_BTREE_ROOT | TDB_BTREE_LEAF, .pBt = pBt};
  ret = tdbPagerNewPage(pBt->pPager, &pgno, &pPage, tdbBtreeZeroPage, &zArg);
  if (ret < 0) {
    return -1;
  }

  // TODO: Unref the page
H
Hongze Cheng 已提交
340

H
Hongze Cheng 已提交
341 342
  ASSERT(pgno != 0);
  pBt->root = pgno;
H
Hongze Cheng 已提交
343

H
Hongze Cheng 已提交
344 345 346 347
  return 0;
}

static int tdbBtreeZeroPage(SPage *pPage, void *arg) {
H
Hongze Cheng 已提交
348 349 350 351 352 353
  u16     flags;
  SBTree *pBt;

  flags = ((SBtreeZeroPageArg *)arg)->flags;
  pBt = ((SBtreeZeroPageArg *)arg)->pBt;

H
Hongze Cheng 已提交
354
  pPage->pPageHdr = pPage->pData;
H
Hongze Cheng 已提交
355
  pPage->aCellIdx = (u8 *)(&(pPage->pPageHdr[1]));
H
Hongze Cheng 已提交
356 357

  // Init the page header
H
Hongze Cheng 已提交
358 359 360 361 362
  TDB_PAGE_FLAGS_SET(pPage, flags);
  TDB_PAGE_NCELLS_SET(pPage, 0);
  TDB_PAGE_CCELLS_SET(pPage, pBt->pageSize);
  TDB_PAGE_FCELL_SET(pPage, 0);
  TDB_PAGE_NFREE_SET(pPage, 0);
H
Hongze Cheng 已提交
363

H
Hongze Cheng 已提交
364 365
  TDB_BTREE_ASSERT_FLAG(flags);

H
Hongze Cheng 已提交
366
  if (TDB_BTREE_PAGE_IS_LEAF(flags)) {
H
Hongze Cheng 已提交
367 368 369 370 371 372 373 374 375 376
    pPage->kLen = pBt->keyLen;
    pPage->vLen = pBt->valLen;
    pPage->maxLocal = pBt->maxLeaf;
    pPage->minLocal = pBt->minLeaf;
  } else {
    pPage->kLen = pBt->keyLen;
    pPage->vLen = sizeof(SPgno);
    pPage->maxLocal = pBt->maxLocal;
    pPage->minLocal = pBt->minLocal;
  }
H
Hongze Cheng 已提交
377 378 379 380 381

  return 0;
}

static int tdbBtreeInitPage(SPage *pPage, void *arg) {
H
Hongze Cheng 已提交
382
  SBTree *pBt;
H
Hongze Cheng 已提交
383
  u16     flags;
H
Hongze Cheng 已提交
384 385 386

  pBt = (SBTree *)arg;

H
Hongze Cheng 已提交
387 388 389
  flags = TDB_PAGE_FLAGS(pPage);
  pPage->pPageHdr = pPage->pData;
  pPage->aCellIdx = pPage->pPageHdr + pPage->szPageHdr;
H
Hongze Cheng 已提交
390

H
Hongze Cheng 已提交
391
  TDB_BTREE_ASSERT_FLAG(flags);
H
Hongze Cheng 已提交
392

H
Hongze Cheng 已提交
393
  // Init other fields
H
Hongze Cheng 已提交
394
  if (TDB_BTREE_PAGE_IS_LEAF(flags)) {
H
Hongze Cheng 已提交
395 396 397 398 399 400 401 402 403
    pPage->kLen = pBt->keyLen;
    pPage->vLen = pBt->valLen;
    pPage->maxLocal = pBt->maxLeaf;
    pPage->minLocal = pBt->minLeaf;
  } else {
    pPage->kLen = pBt->keyLen;
    pPage->vLen = sizeof(SPgno);
    pPage->maxLocal = pBt->maxLocal;
    pPage->minLocal = pBt->minLocal;
H
Hongze Cheng 已提交
404 405
  }

H
Hongze Cheng 已提交
406
  return 0;
H
Hongze Cheng 已提交
407 408 409
}

#ifndef TDB_BTREE_BALANCE
H
Hongze Cheng 已提交
410 411 412 413 414 415 416 417 418 419
typedef struct {
  SBTree *pBt;
  SPage  *pParent;
  int     idx;
  i8      nOldPages;
  SPage  *pOldPages[3];
  i8      nNewPages;
  SPage  *pNewPages[5];
} SBtreeBalanceHelper;

H
Hongze Cheng 已提交
420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460
static int tdbBtreeCopyPageContent(SPage *pFrom, SPage *pTo) {
  /* TODO */

  return 0;
}

static int tdbBtreeBalanceDeeper(SBTree *pBt, SPage *pRoot, SPage **ppChild) {
  SPager           *pPager;
  SPage            *pChild;
  SPgno             pgnoChild;
  int               ret;
  SBtreeZeroPageArg zArg;

  pPager = pRoot->pPager;

  // Allocate a new child page
  zArg.flags = TDB_BTREE_LEAF;
  zArg.pBt = pBt;
  ret = tdbPagerNewPage(pPager, &pgnoChild, &pChild, tdbBtreeZeroPage, &zArg);
  if (ret < 0) {
    return -1;
  }

  // Copy the root page content to the child page
  ret = tdbBtreeCopyPageContent(pRoot, pChild);
  if (ret < 0) {
    return -1;
  }

  {
    // TODO: Copy the over flow part of the page
  }

  // Reinitialize the root page
  zArg.flags = TDB_BTREE_ROOT;
  zArg.pBt = pBt;
  ret = tdbBtreeZeroPage(pRoot, &zArg);
  if (ret < 0) {
    return -1;
  }

H
Hongze Cheng 已提交
461 462 463 464
  *ppChild = pChild;
  return 0;
}

H
Hongze Cheng 已提交
465
static int tdbBtreeBalanceStep1(SBtreeBalanceHelper *pBlh) {
H
Hongze Cheng 已提交
466
#if 0
H
Hongze Cheng 已提交
467 468 469 470 471 472 473 474
  int    i;
  SPage *pParent;
  int    nDiv;
  SPgno  pgno;
  SPage *pPage;
  int    ret;

  pParent = pBlh->pParent;
H
Hongze Cheng 已提交
475
  i = pParent->pPageHdr->nCells + pParent->nOverflow;
H
Hongze Cheng 已提交
476

H
Hongze Cheng 已提交
477 478 479
  if (i < 1) {
    nDiv = 0;
  } else {
H
Hongze Cheng 已提交
480
    if (pBlh->idx == 0) {
H
Hongze Cheng 已提交
481
      nDiv = 0;
H
Hongze Cheng 已提交
482
    } else if (pBlh->idx == i) {
H
Hongze Cheng 已提交
483
      nDiv = i - 2;
H
Hongze Cheng 已提交
484
    } else {
H
Hongze Cheng 已提交
485
      nDiv = pBlh->idx - 1;
H
Hongze Cheng 已提交
486
    }
H
Hongze Cheng 已提交
487 488
    i = 2;
  }
H
Hongze Cheng 已提交
489
  pBlh->nOldPages = i + 1;
H
Hongze Cheng 已提交
490

H
Hongze Cheng 已提交
491
  if (i + nDiv - pParent->nOverflow == pParent->pPageHdr->nCells) {
H
Hongze Cheng 已提交
492
    // pgno = pParent->pPageHdr->rChild;
H
Hongze Cheng 已提交
493 494 495 496 497 498
  } else {
    ASSERT(0);
    // TODO
    pgno = 0;
  }
  for (;;) {
H
Hongze Cheng 已提交
499
    ret = tdbPagerFetchPage(pBlh->pBt->pPager, pgno, &pPage, tdbBtreeInitPage, pBlh->pBt);
H
Hongze Cheng 已提交
500
    if (ret < 0) {
H
Hongze Cheng 已提交
501
      ASSERT(0);
H
Hongze Cheng 已提交
502
      return -1;
H
Hongze Cheng 已提交
503
    }
H
Hongze Cheng 已提交
504

H
Hongze Cheng 已提交
505
    pBlh->pOldPages[i] = pPage;
H
Hongze Cheng 已提交
506 507 508 509

    if ((i--) == 0) break;

    if (pParent->nOverflow && i + nDiv == pParent->aiOvfl[0]) {
H
Hongze Cheng 已提交
510
      // pCellDiv[i] = pParent->apOvfl[0];
H
Hongze Cheng 已提交
511 512 513 514 515 516 517 518 519 520 521 522 523
      // pgno = 0;
      // szNew[i] = tdbPageCellSize(pPage, pCell);
      pParent->nOverflow = 0;
    } else {
      // pCellDiv[i] = TDB_PAGE_CELL_AT(pPage, i + nDiv - pParent->nOverflow);
      // pgno = 0;
      // szNew[i] = tdbPageCellSize(pPage, pCell);

      // Drop the cell from the page
      // ret = tdbPageDropCell(pPage, i + nDiv - pParent->nOverflow, szNew[i]);
      // if (ret < 0) {
      //   return -1;
      // }
H
Hongze Cheng 已提交
524 525 526
    }
  }

H
Hongze Cheng 已提交
527
#endif
H
Hongze Cheng 已提交
528 529 530 531
  return 0;
}

static int tdbBtreeBalanceStep2(SBtreeBalanceHelper *pBlh) {
H
Hongze Cheng 已提交
532
#if 0
H
Hongze Cheng 已提交
533
  SPage *pPage;
H
Hongze Cheng 已提交
534 535 536 537
  int    oidx;
  int    cidx;
  int    limit;
  SCell *pCell;
H
Hongze Cheng 已提交
538 539 540

  for (int i = 0; i < pBlh->nOldPages; i++) {
    pPage = pBlh->pOldPages[i];
H
Hongze Cheng 已提交
541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569
    oidx = 0;
    cidx = 0;

    if (oidx < pPage->nOverflow) {
      limit = pPage->aiOvfl[oidx];
    } else {
      limit = pPage->pPageHdr->nCells;
    }

    // Loop to copy each cell pointer out
    for (;;) {
      if (oidx >= pPage->nOverflow && cidx >= pPage->pPageHdr->nCells) break;

      if (cidx < limit) {
        // Get local cells
        pCell = TDB_PAGE_CELL_AT(pPage, cidx);
      } else if (cidx == limit) {
        // Get overflow cells
        pCell = pPage->apOvfl[oidx++];

        if (oidx < pPage->nOverflow) {
          limit = pPage->aiOvfl[oidx];
        } else {
          limit = pPage->pPageHdr->nCells;
        }
      } else {
        ASSERT(0);
      }
    }
H
Hongze Cheng 已提交
570 571 572 573

    {
      // TODO: Copy divider cells here
    }
H
Hongze Cheng 已提交
574 575 576 577
  }

  /* TODO */

H
Hongze Cheng 已提交
578
#endif
H
Hongze Cheng 已提交
579 580 581 582
  return 0;
}

static int tdbBtreeBalanceStep3(SBtreeBalanceHelper *pBlh) {
H
Hongze Cheng 已提交
583 584 585 586
  for (int i = 0; i < pBlh->nOldPages; i++) {
    /* code */
  }

H
Hongze Cheng 已提交
587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617
  return 0;
}

static int tdbBtreeBalanceStep4(SBtreeBalanceHelper *pBlh) {
  // TODO
  return 0;
}

static int tdbBtreeBalanceStep5(SBtreeBalanceHelper *pBlh) {
  // TODO
  return 0;
}

static int tdbBtreeBalanceStep6(SBtreeBalanceHelper *pBlh) {
  // TODO
  return 0;
}

static int tdbBtreeBalanceNonRoot(SBTree *pBt, SPage *pParent, int idx) {
  int                 ret;
  SBtreeBalanceHelper blh;

  blh.pBt = pBt;
  blh.pParent = pParent;
  blh.idx = idx;

  // Step 1: find two sibling pages and get engough info about the old pages
  ret = tdbBtreeBalanceStep1(&blh);
  if (ret < 0) {
    ASSERT(0);
    return -1;
H
Hongze Cheng 已提交
618 619
  }

H
Hongze Cheng 已提交
620 621 622 623 624
  // Step 2: Load all cells on the old page and the divider cells
  ret = tdbBtreeBalanceStep2(&blh);
  if (ret < 0) {
    ASSERT(0);
    return -1;
H
Hongze Cheng 已提交
625 626
  }

H
Hongze Cheng 已提交
627 628 629 630 631
  // Step 3: Get the number of pages needed to hold all cells
  ret = tdbBtreeBalanceStep3(&blh);
  if (ret < 0) {
    ASSERT(0);
    return -1;
H
Hongze Cheng 已提交
632 633
  }

H
Hongze Cheng 已提交
634 635 636 637 638
  // Step 4: Allocate enough new pages. Reuse old pages as much as possible
  ret = tdbBtreeBalanceStep4(&blh);
  if (ret < 0) {
    ASSERT(0);
    return -1;
H
Hongze Cheng 已提交
639 640
  }

H
Hongze Cheng 已提交
641 642 643 644 645 646 647 648 649 650 651 652
  // Step 5: Insert new divider cells into pParent
  ret = tdbBtreeBalanceStep5(&blh);
  if (ret < 0) {
    ASSERT(0);
    return -1;
  }

  // Step 6: Update the sibling pages
  ret = tdbBtreeBalanceStep6(&blh);
  if (ret < 0) {
    ASSERT(0);
    return -1;
H
Hongze Cheng 已提交
653 654 655 656 657 658 659 660 661
  }

  {
      // TODO: Reset states
  }

  {
    // TODO: Clear resources
  }
H
Hongze Cheng 已提交
662

H
Hongze Cheng 已提交
663 664 665 666 667
  return 0;
}

static int tdbBtreeBalance(SBtCursor *pCur) {
  int    iPage;
H
Hongze Cheng 已提交
668 669
  SPage *pParent;
  int    ret;
H
Hongze Cheng 已提交
670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686

  // Main loop to balance the BTree
  for (;;) {
    iPage = pCur->iPage;

    // TODO: Get the page free space if not get yet
    // if (pPage->nFree < 0) {
    //   if (tdbBtreeComputeFreeSpace(pPage) < 0) {
    //     return -1;
    //   }
    // }

    if (0 /*TODO: balance is over*/) {
      break;
    }

    if (iPage == 0) {
H
Hongze Cheng 已提交
687 688
      // Balance the root page by copy the root page content to
      // a child page and set the root page as empty first
H
Hongze Cheng 已提交
689
      // ASSERT(TDB_BTREE_PAGE_IS_ROOT(pCur->pPage->pPageHdr->flags));
H
Hongze Cheng 已提交
690 691 692 693 694 695 696 697 698 699 700

      ret = tdbBtreeBalanceDeeper(pCur->pBt, pCur->pPage, &(pCur->pgStack[1]));
      if (ret < 0) {
        return -1;
      }

      pCur->idx = 0;
      pCur->idxStack[0] = 0;
      pCur->pgStack[0] = pCur->pPage;
      pCur->iPage = 1;
      pCur->pPage = pCur->pgStack[1];
H
Hongze Cheng 已提交
701 702

    } else {
H
Hongze Cheng 已提交
703 704 705
      // Generalized balance step
      pParent = pCur->pgStack[pCur->iPage - 1];

H
Hongze Cheng 已提交
706
      ret = tdbBtreeBalanceNonRoot(pCur->pBt, pParent, pCur->idxStack[pCur->iPage - 1]);
H
Hongze Cheng 已提交
707 708 709 710 711 712
      if (ret < 0) {
        return -1;
      }

      pCur->iPage--;
      pCur->pPage = pCur->pgStack[pCur->iPage];
H
Hongze Cheng 已提交
713 714 715 716 717 718
    }
  }

  return 0;
}
#endif