tdbBtree.c 21.3 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
  u8            *pTmp;
H
Hongze Cheng 已提交
40 41
};

H
Hongze Cheng 已提交
42 43 44
typedef struct __attribute__((__packed__)) {
  SPgno rChild;
} SBtPageHdr;
H
more  
Hongze Cheng 已提交
45

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

H
Hongze Cheng 已提交
51 52 53 54 55 56 57 58 59
typedef struct {
  int   kLen;
  u8   *pKey;
  int   vLen;
  u8   *pVal;
  SPgno pgno;
  u8   *pTmpSpace;
} SCellDecoder;

H
Hongze Cheng 已提交
60
static int tdbBtCursorMoveTo(SBtCursor *pCur, const void *pKey, int kLen, int *pCRst);
H
Hongze Cheng 已提交
61
static int tdbDefaultKeyCmprFn(const void *pKey1, int keyLen1, const void *pKey2, int keyLen2);
H
Hongze Cheng 已提交
62
static int tdbBtreeOpenImpl(SBTree *pBt);
H
Hongze Cheng 已提交
63 64
static int tdbBtreeZeroPage(SPage *pPage, void *arg);
static int tdbBtreeInitPage(SPage *pPage, void *arg);
H
Hongze Cheng 已提交
65 66
static int tdbBtreeEncodeCell(SPage *pPage, const void *pKey, int kLen, const void *pVal, int vLen, SCell *pCell,
                              int *szCell);
H
Hongze Cheng 已提交
67
static int tdbBtreeDecodeCell(SPage *pPage, const SCell *pCell, SCellDecoder *pDecoder);
H
Hongze Cheng 已提交
68
static int tdbBtreeBalance(SBtCursor *pCur);
H
Hongze Cheng 已提交
69

H
Hongze Cheng 已提交
70
int tdbBtreeOpen(int keyLen, int valLen, SPager *pPager, FKeyComparator kcmpr, SBTree **ppBt) {
H
Hongze Cheng 已提交
71
  SBTree *pBt;
H
Hongze Cheng 已提交
72
  int     ret;
H
more  
Hongze Cheng 已提交
73

H
Hongze Cheng 已提交
74
  *ppBt = NULL;
H
Hongze Cheng 已提交
75 76 77 78 79 80 81 82 83 84

  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 已提交
85 86
  // pBt->pPager
  pBt->pPager = pPager;
H
Hongze Cheng 已提交
87 88
  // pBt->kcmpr
  pBt->kcmpr = kcmpr ? kcmpr : tdbDefaultKeyCmprFn;
H
more  
Hongze Cheng 已提交
89 90 91 92 93 94 95
  // pBt->fanout
  if (keyLen == TDB_VARIANT_LEN) {
    pBt->fanout = TDB_DEFAULT_FANOUT;
  } else {
    ASSERT(0);
    // TODO: pBt->fanout = 0;
  }
H
Hongze Cheng 已提交
96 97 98
  // pBt->pageSize
  pBt->pageSize = tdbPagerGetPageSize(pPager);
  // pBt->maxLocal
H
Hongze Cheng 已提交
99
  pBt->maxLocal = (pBt->pageSize - 14) / pBt->fanout;
H
Hongze Cheng 已提交
100
  // pBt->minLocal: Should not be allowed smaller than 15, which is [nPayload][nKey][nData]
H
Hongze Cheng 已提交
101
  pBt->minLocal = (pBt->pageSize - 14) / pBt->fanout / 2;
H
Hongze Cheng 已提交
102
  // pBt->maxLeaf
H
Hongze Cheng 已提交
103
  pBt->maxLeaf = pBt->pageSize - 14;
H
Hongze Cheng 已提交
104 105
  // pBt->minLeaf
  pBt->minLeaf = pBt->minLocal;
H
Hongze Cheng 已提交
106

H
Hongze Cheng 已提交
107 108 109 110 111 112 113
  // TODO: pBt->root
  ret = tdbBtreeOpenImpl(pBt);
  if (ret < 0) {
    free(pBt);
    return -1;
  }

H
Hongze Cheng 已提交
114
  *ppBt = pBt;
H
Hongze Cheng 已提交
115 116 117 118 119 120 121 122
  return 0;
}

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

H
more  
Hongze Cheng 已提交
123
int tdbBtreeCursor(SBtCursor *pCur, SBTree *pBt) {
H
more  
Hongze Cheng 已提交
124 125
  pCur->pBt = pBt;
  pCur->iPage = -1;
H
more  
Hongze Cheng 已提交
126
  pCur->pPage = NULL;
H
Hongze Cheng 已提交
127
  pCur->idx = -1;
H
more  
Hongze Cheng 已提交
128

H
more  
Hongze Cheng 已提交
129 130 131
  return 0;
}

H
Hongze Cheng 已提交
132
int tdbBtCursorInsert(SBtCursor *pCur, const void *pKey, int kLen, const void *pVal, int vLen) {
H
Hongze Cheng 已提交
133
  int     ret;
H
Hongze Cheng 已提交
134
  int     idx;
H
Hongze Cheng 已提交
135
  SPager *pPager;
H
Hongze Cheng 已提交
136 137 138
  SCell  *pCell;
  int     szCell;
  int     cret;
H
Hongze Cheng 已提交
139
  SBTree *pBt;
H
Hongze Cheng 已提交
140

H
Hongze Cheng 已提交
141
  ret = tdbBtCursorMoveTo(pCur, pKey, kLen, &cret);
H
Hongze Cheng 已提交
142 143 144 145 146
  if (ret < 0) {
    // TODO: handle error
    return -1;
  }

H
Hongze Cheng 已提交
147
  if (pCur->idx == -1) {
H
Hongze Cheng 已提交
148
    ASSERT(TDB_PAGE_NCELLS(pCur->pPage) == 0);
H
Hongze Cheng 已提交
149 150 151
    idx = 0;
  } else {
    if (cret > 0) {
H
Hongze Cheng 已提交
152
      idx = pCur->idx + 1;
H
Hongze Cheng 已提交
153
    } else if (cret < 0) {
H
Hongze Cheng 已提交
154
      idx = pCur->idx;
H
Hongze Cheng 已提交
155 156 157 158 159 160
    } else {
      /* TODO */
      ASSERT(0);
    }
  }

H
Hongze Cheng 已提交
161 162 163 164 165 166 167 168 169 170 171
  // TODO: refact code here
  pBt = pCur->pBt;
  if (!pBt->pTmp) {
    pBt->pTmp = (u8 *)malloc(pBt->pageSize);
    if (pBt->pTmp == NULL) {
      return -1;
    }
  }

  pCell = pBt->pTmp;

H
Hongze Cheng 已提交
172
  // Encode the cell
H
Hongze Cheng 已提交
173 174 175 176
  ret = tdbBtreeEncodeCell(pCur->pPage, pKey, kLen, pVal, vLen, pCell, &szCell);
  if (ret < 0) {
    return -1;
  }
H
Hongze Cheng 已提交
177 178 179 180 181

  // Insert the cell to the index
  ret = tdbPageInsertCell(pCur->pPage, idx, pCell, szCell);
  if (ret < 0) {
    return -1;
H
Hongze Cheng 已提交
182 183
  }

H
Hongze Cheng 已提交
184 185 186 187 188 189 190 191
  // If page is overflow, balance the tree
  if (pCur->pPage->nOverflow > 0) {
    ret = tdbBtreeBalance(pCur);
    if (ret < 0) {
      return -1;
    }
  }

H
more  
Hongze Cheng 已提交
192 193 194
  return 0;
}

H
Hongze Cheng 已提交
195 196 197 198 199
static int tdbBtCursorMoveToChild(SBtCursor *pCur, SPgno pgno) {
  // TODO
  return 0;
}

H
Hongze Cheng 已提交
200
static int tdbBtCursorMoveTo(SBtCursor *pCur, const void *pKey, int kLen, int *pCRst) {
H
Hongze Cheng 已提交
201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220
  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 已提交
221
    if (TDB_PAGE_NCELLS(pCur->pPage) == 0) {
H
Hongze Cheng 已提交
222
      // Current page is empty
H
Hongze Cheng 已提交
223
      ASSERT(TDB_FLAG_IS(TDB_PAGE_FLAGS(pCur->pPage), TDB_BTREE_ROOT | TDB_BTREE_LEAF));
H
Hongze Cheng 已提交
224 225 226
      return 0;
    }

H
Hongze Cheng 已提交
227
    for (;;) {
H
Hongze Cheng 已提交
228
      int          lidx, ridx, midx, c, nCells;
H
Hongze Cheng 已提交
229 230 231 232 233
      SCell       *pCell;
      SPage       *pPage;
      SCellDecoder cd = {0};

      pPage = pCur->pPage;
H
Hongze Cheng 已提交
234
      nCells = TDB_PAGE_NCELLS(pPage);
H
Hongze Cheng 已提交
235
      lidx = 0;
H
Hongze Cheng 已提交
236 237 238 239
      ridx = nCells - 1;

      ASSERT(nCells > 0);

H
Hongze Cheng 已提交
240
      for (;;) {
H
Hongze Cheng 已提交
241 242 243 244
        if (lidx > ridx) break;

        midx = (lidx + ridx) >> 1;

H
Hongze Cheng 已提交
245 246 247 248 249 250 251
        pCell = TDB_PAGE_CELL_AT(pPage, midx);
        ret = tdbBtreeDecodeCell(pPage, pCell, &cd);
        if (ret < 0) {
          // TODO: handle error
          ASSERT(0);
          return -1;
        }
H
Hongze Cheng 已提交
252

H
Hongze Cheng 已提交
253 254 255
        // Compare the key values
        c = pBt->kcmpr(pKey, kLen, cd.pKey, cd.kLen);
        if (c < 0) {
H
Hongze Cheng 已提交
256 257
          /* input-key < cell-key */
          ridx = midx - 1;
H
Hongze Cheng 已提交
258
        } else if (c > 0) {
H
Hongze Cheng 已提交
259 260
          /* input-key > cell-key */
          lidx = midx + 1;
H
Hongze Cheng 已提交
261
        } else {
H
Hongze Cheng 已提交
262 263 264 265 266
          /* input-key == cell-key */
          break;
        }
      }

H
Hongze Cheng 已提交
267
      // Move downward or break
H
Hongze Cheng 已提交
268 269 270 271
      u16 flags = TDB_PAGE_FLAGS(pPage);
      u8  leaf = TDB_BTREE_PAGE_IS_LEAF(flags);
      if (leaf) {
        pCur->idx = midx;
H
Hongze Cheng 已提交
272
        *pCRst = c;
H
Hongze Cheng 已提交
273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289
        break;
      } else {
        if (c <= 0) {
          pCur->idx = midx;
          tdbBtCursorMoveToChild(pCur, cd.pgno);
        } else {
          if (midx == nCells - 1) {
            /* Move to right-most child */
            pCur->idx = midx + 1;
            tdbBtCursorMoveToChild(pCur, ((SBtPageHdr *)(pPage->pAmHdr))->rChild);
          } else {
            // TODO: reset cd as uninitialized
            pCur->idx = midx + 1;
            pCell = TDB_PAGE_CELL_AT(pPage, midx + 1);
            tdbBtreeDecodeCell(pPage, pCell, &cd);
            tdbBtCursorMoveToChild(pCur, cd.pgno);
          }
H
Hongze Cheng 已提交
290 291
        }
      }
H
Hongze Cheng 已提交
292 293 294 295
    }

  } else {
    // TODO: Move the cursor from a some position instead of a clear state
H
Hongze Cheng 已提交
296
    ASSERT(0);
H
Hongze Cheng 已提交
297
  }
H
more  
Hongze Cheng 已提交
298

H
Hongze Cheng 已提交
299 300
  return 0;
}
H
more  
Hongze Cheng 已提交
301

H
more  
Hongze Cheng 已提交
302
static int tdbBtCursorMoveToRoot(SBtCursor *pCur) {
H
refact  
Hongze Cheng 已提交
303 304
  SBTree *pBt;
  SPager *pPager;
H
Hongze Cheng 已提交
305
  SPage  *pPage;
H
refact  
Hongze Cheng 已提交
306
  int     ret;
H
more  
Hongze Cheng 已提交
307 308

  pBt = pCur->pBt;
H
refact  
Hongze Cheng 已提交
309
  pPager = pBt->pPager;
H
more  
Hongze Cheng 已提交
310

H
Hongze Cheng 已提交
311 312 313 314
  // pPage = tdbPagerGet(pPager, pBt->root, true);
  // if (pPage == NULL) {
  //   // TODO: handle error
  // }
H
more  
Hongze Cheng 已提交
315

H
Hongze Cheng 已提交
316 317 318 319 320
  // ret = tdbInitBtPage(pPage, &pBtPage);
  // if (ret < 0) {
  //   // TODO
  //   return 0;
  // }
H
more  
Hongze Cheng 已提交
321

H
Hongze Cheng 已提交
322 323
  // pCur->pPage = pBtPage;
  // pCur->iPage = 0;
H
more  
Hongze Cheng 已提交
324 325 326 327

  return 0;
}

H
Hongze Cheng 已提交
328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345
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 已提交
346 347 348 349 350 351 352 353 354 355
}

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 已提交
356
    // 1. TODO: Search the main DB to check if the DB exists
H
Hongze Cheng 已提交
357 358 359 360 361 362 363 364 365
    pgno = 0;
  }

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

  // Try to create a new database
H
Hongze Cheng 已提交
366 367 368 369 370 371 372
  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 已提交
373

H
Hongze Cheng 已提交
374 375
  ASSERT(pgno != 0);
  pBt->root = pgno;
H
Hongze Cheng 已提交
376

H
Hongze Cheng 已提交
377 378 379
  return 0;
}

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

H
Hongze Cheng 已提交
385
  pBt = (SBTree *)arg;
H
Hongze Cheng 已提交
386

H
Hongze Cheng 已提交
387
  flags = TDB_PAGE_FLAGS(pPage);
H
Hongze Cheng 已提交
388 389
  isLeaf = TDB_BTREE_PAGE_IS_LEAF(flags);
  if (isLeaf) {
H
Hongze Cheng 已提交
390 391 392 393
    pPage->szAmHdr = 0;
  } else {
    pPage->szAmHdr = sizeof(SBtPageHdr);
  }
H
Hongze Cheng 已提交
394
  pPage->pPageHdr = pPage->pData;
H
Hongze Cheng 已提交
395
  pPage->pAmHdr = pPage->pPageHdr + pPage->pPageMethods->szPageHdr;
H
Hongze Cheng 已提交
396
  pPage->pCellIdx = pPage->pAmHdr + pPage->szAmHdr;
H
Hongze Cheng 已提交
397
  pPage->pFreeStart = pPage->pCellIdx + pPage->pPageMethods->szOffset * TDB_PAGE_NCELLS(pPage);
H
Hongze Cheng 已提交
398 399
  pPage->pFreeEnd = pPage->pData + TDB_PAGE_CCELLS(pPage);
  pPage->pPageFtr = (SPageFtr *)(pPage->pData + pPage->pageSize - sizeof(SPageFtr));
H
Hongze Cheng 已提交
400

H
Hongze Cheng 已提交
401 402
  TDB_BTREE_ASSERT_FLAG(flags);

H
Hongze Cheng 已提交
403
  // Init other fields
H
Hongze Cheng 已提交
404
  if (isLeaf) {
H
Hongze Cheng 已提交
405 406 407 408 409 410 411 412 413 414
    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 已提交
415

H
Hongze Cheng 已提交
416 417
  // TODO: need to update the SPage.nFree
  pPage->nFree = pPage->pFreeEnd - pPage->pFreeStart;
H
Hongze Cheng 已提交
418
  pPage->nOverflow = 0;
H
Hongze Cheng 已提交
419

H
Hongze Cheng 已提交
420 421 422
  return 0;
}

H
Hongze Cheng 已提交
423
static int tdbBtreeZeroPage(SPage *pPage, void *arg) {
H
Hongze Cheng 已提交
424
  u16     flags;
H
Hongze Cheng 已提交
425
  SBTree *pBt;
H
Hongze Cheng 已提交
426

H
Hongze Cheng 已提交
427 428
  flags = ((SBtreeZeroPageArg *)arg)->flags;
  pBt = ((SBtreeZeroPageArg *)arg)->pBt;
H
Hongze Cheng 已提交
429

H
Hongze Cheng 已提交
430
  pPage->pPageHdr = pPage->pData;
H
Hongze Cheng 已提交
431

H
Hongze Cheng 已提交
432 433 434 435 436 437
  // Init the page header
  TDB_PAGE_FLAGS_SET(pPage, flags);
  TDB_PAGE_NCELLS_SET(pPage, 0);
  TDB_PAGE_CCELLS_SET(pPage, pBt->pageSize - sizeof(SPageFtr));
  TDB_PAGE_FCELL_SET(pPage, 0);
  TDB_PAGE_NFREE_SET(pPage, 0);
H
Hongze Cheng 已提交
438

H
Hongze Cheng 已提交
439
  tdbBtreeInitPage(pPage, (void *)pBt);
H
Hongze Cheng 已提交
440

H
Hongze Cheng 已提交
441
  return 0;
H
Hongze Cheng 已提交
442 443 444
}

#ifndef TDB_BTREE_BALANCE
H
Hongze Cheng 已提交
445 446 447 448
typedef struct {
  SBTree *pBt;
  SPage  *pParent;
  int     idx;
H
Hongze Cheng 已提交
449
  i8      nOld;
H
Hongze Cheng 已提交
450 451 452 453 454
  SPage  *pOldPages[3];
  i8      nNewPages;
  SPage  *pNewPages[5];
} SBtreeBalanceHelper;

H
Hongze Cheng 已提交
455
static int tdbBtreeCopyPageContent(SPage *pFrom, SPage *pTo) {
H
Hongze Cheng 已提交
456 457 458 459 460
  int nCells = TDB_PAGE_NCELLS(pFrom);
  int cCells = TDB_PAGE_CCELLS(pFrom);
  int fCell = TDB_PAGE_FCELL(pFrom);
  int nFree = TDB_PAGE_NFREE(pFrom);

H
Hongze Cheng 已提交
461 462
  pTo->pFreeStart = pTo->pCellIdx + nCells * pFrom->pPageMethods->szOffset;
  memcpy(pTo->pCellIdx, pFrom->pCellIdx, nCells * pFrom->pPageMethods->szOffset);
H
Hongze Cheng 已提交
463 464
  pTo->pFreeEnd = (u8 *)pTo->pPageFtr - (u8 *)(pFrom->pPageFtr) + pFrom->pFreeEnd;
  memcpy(pTo->pFreeEnd, pFrom->pFreeEnd, (u8 *)pFrom->pPageFtr - pFrom->pFreeEnd);
H
Hongze Cheng 已提交
465 466 467 468 469 470 471

  TDB_PAGE_NCELLS_SET(pTo, nCells);
  TDB_PAGE_CCELLS_SET(pTo, cCells);
  TDB_PAGE_FCELL_SET(pTo, fCell);
  TDB_PAGE_NFREE_SET(pTo, nFree);

  // TODO: update other fields
H
Hongze Cheng 已提交
472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498

  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;
  }

H
Hongze Cheng 已提交
499 500 501 502
  pChild->nOverflow = pRoot->nOverflow;
  for (int i = 0; i < pChild->nOverflow; i++) {
    pChild->apOvfl[i] = pRoot->apOvfl[i];
    pChild->aiOvfl[i] = pRoot->aiOvfl[i];
H
Hongze Cheng 已提交
503 504 505 506 507 508 509 510 511 512
  }

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

H
Hongze Cheng 已提交
513 514
  ((SBtPageHdr *)pRoot->pAmHdr)[0].rChild = pgnoChild;

H
Hongze Cheng 已提交
515 516 517 518
  *ppChild = pChild;
  return 0;
}

H
Hongze Cheng 已提交
519
static int tdbBtreeBalanceStep1(SBtreeBalanceHelper *pBlh) {
H
Hongze Cheng 已提交
520 521 522 523 524 525 526 527 528 529
  int          nCells;
  int          i;
  int          idxStart;
  int          nChild;
  int          ret;
  SPage       *pParent;
  SPgno        pgno;
  SCell       *pCell;
  SCellDecoder cd;
  SBTree      *pBt;
H
Hongze Cheng 已提交
530 531

  pParent = pBlh->pParent;
H
Hongze Cheng 已提交
532 533 534
  nCells = TDB_PAGE_NCELLS(pParent);
  nChild = nCells + 1;
  pBt = pBlh->pBt;
H
Hongze Cheng 已提交
535

H
Hongze Cheng 已提交
536 537 538 539 540 541 542
  // TODO:  ASSERT below needs to be removed
  ASSERT(pParent->nOverflow == 0);
  ASSERT(pBlh->idx <= nCells);

  if (nChild < 3) {
    idxStart = 0;
    pBlh->nOld = nChild;
H
Hongze Cheng 已提交
543
  } else {
H
Hongze Cheng 已提交
544
    if (pBlh->idx == 0) {
H
Hongze Cheng 已提交
545 546 547
      idxStart = 0;
    } else if (pBlh->idx == nCells) {
      idxStart = pBlh->idx - 2;
H
Hongze Cheng 已提交
548
    } else {
H
Hongze Cheng 已提交
549
      idxStart = pBlh->idx - 1;
H
Hongze Cheng 已提交
550
    }
H
Hongze Cheng 已提交
551
    pBlh->nOld = 3;
H
Hongze Cheng 已提交
552
  }
H
Hongze Cheng 已提交
553

H
Hongze Cheng 已提交
554 555 556 557
  i = pBlh->nOld - 1;

  if (idxStart + i == nCells) {
    pgno = ((SBtPageHdr *)(pParent->pAmHdr))[0].rChild;
H
Hongze Cheng 已提交
558
  } else {
H
Hongze Cheng 已提交
559 560 561 562 563 564 565 566 567
    pCell = TDB_PAGE_CELL_AT(pParent, idxStart + i);
    // TODO: no need to decode the payload part, and even the kLen, vLen part
    // we only need the pgno part
    ret = tdbBtreeDecodeCell(pParent, pCell, &cd);
    if (ret < 0) {
      ASSERT(0);
      return -1;
    }
    pgno = cd.pgno;
H
Hongze Cheng 已提交
568 569
  }
  for (;;) {
H
Hongze Cheng 已提交
570
    ret = tdbPagerFetchPage(pBt->pPager, pgno, &(pBlh->pOldPages[i]), tdbBtreeInitPage, pBt);
H
Hongze Cheng 已提交
571
    if (ret < 0) {
H
Hongze Cheng 已提交
572
      ASSERT(0);
H
Hongze Cheng 已提交
573
      return -1;
H
Hongze Cheng 已提交
574
    }
H
Hongze Cheng 已提交
575

H
Hongze Cheng 已提交
576
    // Loop over
H
Hongze Cheng 已提交
577 578
    if ((i--) == 0) break;

H
Hongze Cheng 已提交
579 580 581
    {
      // TODO
      // ASSERT(0);
H
Hongze Cheng 已提交
582 583 584
    }
  }

H
Hongze Cheng 已提交
585 586 587 588
  return 0;
}

static int tdbBtreeBalanceStep2(SBtreeBalanceHelper *pBlh) {
H
Hongze Cheng 已提交
589
#if 0
H
Hongze Cheng 已提交
590
  SPage *pPage;
H
Hongze Cheng 已提交
591 592 593 594
  int    oidx;
  int    cidx;
  int    limit;
  SCell *pCell;
H
Hongze Cheng 已提交
595

H
Hongze Cheng 已提交
596
  for (int i = 0; i < pBlh->nOld; i++) {
H
Hongze Cheng 已提交
597
    pPage = pBlh->pOldPages[i];
H
Hongze Cheng 已提交
598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626
    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 已提交
627 628 629 630

    {
      // TODO: Copy divider cells here
    }
H
Hongze Cheng 已提交
631 632 633 634
  }

  /* TODO */

H
Hongze Cheng 已提交
635
#endif
H
Hongze Cheng 已提交
636 637 638 639
  return 0;
}

static int tdbBtreeBalanceStep3(SBtreeBalanceHelper *pBlh) {
H
Hongze Cheng 已提交
640
  // Figure out number of pages needed after balance
H
Hongze Cheng 已提交
641
  for (int i = 0; i < pBlh->nOld; i++) {
H
Hongze Cheng 已提交
642
    /* TODO */
H
Hongze Cheng 已提交
643 644
  }

H
Hongze Cheng 已提交
645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666
  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;

H
Hongze Cheng 已提交
667 668
  ASSERT(!TDB_BTREE_PAGE_IS_LEAF(TDB_PAGE_FLAGS(pParent)));

H
Hongze Cheng 已提交
669 670 671 672 673 674 675 676 677
  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 已提交
678 679
  }

H
Hongze Cheng 已提交
680 681 682 683 684
  // 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 已提交
685 686
  }

H
Hongze Cheng 已提交
687 688 689 690 691
  // 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 已提交
692 693
  }

H
Hongze Cheng 已提交
694 695 696 697 698
  // 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 已提交
699 700
  }

H
Hongze Cheng 已提交
701 702 703 704 705 706 707 708 709 710 711 712
  // 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 已提交
713 714 715 716 717 718 719 720 721
  }

  {
      // TODO: Reset states
  }

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

H
Hongze Cheng 已提交
723 724 725 726 727
  return 0;
}

static int tdbBtreeBalance(SBtCursor *pCur) {
  int    iPage;
H
Hongze Cheng 已提交
728
  SPage *pParent;
H
Hongze Cheng 已提交
729
  SPage *pPage;
H
Hongze Cheng 已提交
730
  int    ret;
H
Hongze Cheng 已提交
731 732 733
  u16    flags;
  u8     leaf;
  u8     root;
H
Hongze Cheng 已提交
734 735 736 737

  // Main loop to balance the BTree
  for (;;) {
    iPage = pCur->iPage;
H
Hongze Cheng 已提交
738 739 740 741
    pPage = pCur->pPage;
    flags = TDB_PAGE_FLAGS(pPage);
    leaf = TDB_BTREE_PAGE_IS_LEAF(flags);
    root = TDB_BTREE_PAGE_IS_ROOT(flags);
H
Hongze Cheng 已提交
742 743 744 745 746 747 748 749

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

H
Hongze Cheng 已提交
750 751
    // when the page is not overflow and not too empty, the balance work
    // is finished. Just break out the balance loop.
H
Hongze Cheng 已提交
752
    if (pPage->nOverflow == 0 /* TODO: && pPage->nFree <= */) {
H
Hongze Cheng 已提交
753 754 755 756
      break;
    }

    if (iPage == 0) {
H
Hongze Cheng 已提交
757 758 759
      // For the root page, only balance when the page is overfull,
      // ignore the case of empty
      if (pPage->nOverflow == 0) break;
H
Hongze Cheng 已提交
760 761 762 763 764 765 766 767 768 769 770

      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 已提交
771
    } else {
H
Hongze Cheng 已提交
772
      // Generalized balance step
H
Hongze Cheng 已提交
773
      pParent = pCur->pgStack[iPage - 1];
H
Hongze Cheng 已提交
774

H
Hongze Cheng 已提交
775
      ret = tdbBtreeBalanceNonRoot(pCur->pBt, pParent, pCur->idxStack[pCur->iPage - 1]);
H
Hongze Cheng 已提交
776 777 778 779 780 781
      if (ret < 0) {
        return -1;
      }

      pCur->iPage--;
      pCur->pPage = pCur->pgStack[pCur->iPage];
H
Hongze Cheng 已提交
782 783 784 785 786
    }
  }

  return 0;
}
H
Hongze Cheng 已提交
787 788
#endif

H
Hongze Cheng 已提交
789
#ifndef TDB_BTREE_CELL  // =========================================================
H
Hongze Cheng 已提交
790
static int tdbBtreeEncodePayload(SPage *pPage, u8 *pPayload, const void *pKey, int kLen, const void *pVal, int vLen,
H
Hongze Cheng 已提交
791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819
                                 int *szPayload) {
  int nPayload;

  ASSERT(pKey != NULL);

  if (pVal == NULL) {
    vLen = 0;
  }

  nPayload = kLen + vLen;
  if (nPayload <= pPage->maxLocal) {
    // General case without overflow
    memcpy(pPayload, pKey, kLen);
    if (pVal) {
      memcpy(pPayload + kLen, pVal, vLen);
    }

    *szPayload = nPayload;
    return 0;
  }

  {
    // TODO: handle overflow case
    ASSERT(0);
  }

  return 0;
}

H
Hongze Cheng 已提交
820 821
static int tdbBtreeEncodeCell(SPage *pPage, const void *pKey, int kLen, const void *pVal, int vLen, SCell *pCell,
                              int *szCell) {
H
Hongze Cheng 已提交
822
  u16 flags;
H
Hongze Cheng 已提交
823 824 825 826
  u8  leaf;
  int nHeader;
  int nPayload;
  int ret;
H
Hongze Cheng 已提交
827 828 829 830

  ASSERT(pPage->kLen == TDB_VARIANT_LEN || pPage->kLen == kLen);
  ASSERT(pPage->vLen == TDB_VARIANT_LEN || pPage->vLen == vLen);

H
Hongze Cheng 已提交
831 832 833 834
  nPayload = 0;
  nHeader = 0;
  flags = TDB_PAGE_FLAGS(pPage);
  leaf = TDB_BTREE_PAGE_IS_LEAF(flags);
H
Hongze Cheng 已提交
835

H
Hongze Cheng 已提交
836 837
  // 1. Encode Header part
  /* Encode kLen if need */
H
Hongze Cheng 已提交
838
  if (pPage->kLen == TDB_VARIANT_LEN) {
H
Hongze Cheng 已提交
839
    nHeader += tdbPutVarInt(pCell + nHeader, kLen);
H
Hongze Cheng 已提交
840 841
  }

H
Hongze Cheng 已提交
842
  /* Encode vLen if need */
H
Hongze Cheng 已提交
843
  if (pPage->vLen == TDB_VARIANT_LEN) {
H
Hongze Cheng 已提交
844
    nHeader += tdbPutVarInt(pCell + nHeader, vLen);
H
Hongze Cheng 已提交
845 846
  }

H
Hongze Cheng 已提交
847 848
  /* Encode SPgno if interior page */
  if (!leaf) {
H
Hongze Cheng 已提交
849 850
    ASSERT(pPage->vLen == sizeof(SPgno));

H
Hongze Cheng 已提交
851 852 853 854 855 856 857 858 859 860 861 862 863
    ((SPgno *)(pCell + nHeader))[0] = ((SPgno *)pVal)[0];
    nHeader = nHeader + sizeof(SPgno);
  }

  // 2. Encode payload part
  if (leaf) {
    ret = tdbBtreeEncodePayload(pPage, pCell + nHeader, pKey, kLen, pVal, vLen, &nPayload);
  } else {
    ret = tdbBtreeEncodePayload(pPage, pCell + nHeader, pKey, kLen, NULL, 0, &nPayload);
  }
  if (ret < 0) {
    // TODO: handle error
    return -1;
H
Hongze Cheng 已提交
864 865
  }

H
Hongze Cheng 已提交
866
  *szCell = nHeader + nPayload;
H
Hongze Cheng 已提交
867 868 869
  return 0;
}

H
Hongze Cheng 已提交
870 871 872 873
static int tdbBtreeDecodePayload(SPage *pPage, const u8 *pPayload, SCellDecoder *pDecoder) {
  int nPayload;

  ASSERT(pDecoder->pKey == NULL);
H
Hongze Cheng 已提交
874

H
Hongze Cheng 已提交
875 876
  if (pDecoder->pVal) {
    nPayload = pDecoder->kLen + pDecoder->vLen;
H
Hongze Cheng 已提交
877
  } else {
H
Hongze Cheng 已提交
878
    nPayload = pDecoder->kLen;
H
Hongze Cheng 已提交
879 880
  }

H
Hongze Cheng 已提交
881 882 883
  if (nPayload <= pPage->maxLocal) {
    // General case without overflow
    pDecoder->pKey = (void *)pPayload;
H
Hongze Cheng 已提交
884 885
    if (!pDecoder->pVal) {
      pDecoder->pVal = (void *)(pPayload + pDecoder->kLen);
H
Hongze Cheng 已提交
886
    }
H
Hongze Cheng 已提交
887
  } else {
H
Hongze Cheng 已提交
888 889
    // TODO: handle overflow case
    ASSERT(0);
H
Hongze Cheng 已提交
890 891
  }

H
Hongze Cheng 已提交
892 893 894 895 896 897 898 899 900 901
  return 0;
}

static int tdbBtreeDecodeCell(SPage *pPage, const SCell *pCell, SCellDecoder *pDecoder) {
  u16 flags;
  u8  leaf;
  int nHeader;
  int ret;

  nHeader = 0;
H
Hongze Cheng 已提交
902
  flags = TDB_PAGE_FLAGS(pPage);
H
Hongze Cheng 已提交
903 904
  leaf = TDB_BTREE_PAGE_IS_LEAF(flags);

H
Hongze Cheng 已提交
905 906 907 908 909 910 911
  // Clear the state of decoder
  pDecoder->kLen = -1;
  pDecoder->pKey = NULL;
  pDecoder->vLen = -1;
  pDecoder->pVal = NULL;
  pDecoder->pgno = 0;

H
Hongze Cheng 已提交
912 913 914 915 916 917 918 919 920
  // 1. Decode header part
  if (pPage->kLen == TDB_VARIANT_LEN) {
    nHeader += tdbGetVarInt(pCell + nHeader, &(pDecoder->kLen));
  } else {
    pDecoder->kLen = pPage->kLen;
  }

  if (pPage->vLen == TDB_VARIANT_LEN) {
    nHeader += tdbGetVarInt(pCell + nHeader, &(pDecoder->vLen));
H
Hongze Cheng 已提交
921
  } else {
H
Hongze Cheng 已提交
922 923
    pDecoder->vLen = pPage->vLen;
  }
H
Hongze Cheng 已提交
924

H
Hongze Cheng 已提交
925 926
  if (!leaf) {
    ASSERT(pPage->vLen == sizeof(SPgno));
H
Hongze Cheng 已提交
927

H
Hongze Cheng 已提交
928 929 930 931 932 933 934 935 936
    pDecoder->pgno = ((SPgno *)(pCell + nHeader))[0];
    pDecoder->pVal = (u8 *)(&(pDecoder->pgno));
    nHeader = nHeader + sizeof(SPgno);
  }

  // 2. Decode payload part
  ret = tdbBtreeDecodePayload(pPage, pCell + nHeader, pDecoder);
  if (ret < 0) {
    return -1;
H
Hongze Cheng 已提交
937 938 939 940 941
  }

  return 0;
}

H
Hongze Cheng 已提交
942
#endif