/* Copyright (c) 2003-2007 MySQL AB
   Use is subject to license terms

   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 */


#define DBTUP_C
#define DBTUP_TAB_DES_MAN_CPP
#include "Dbtup.hpp"
#include <RefConvert.hpp>
#include <ndb_limits.h>
#include <pc.hpp>

/*
 * TABLE DESCRIPTOR MEMORY MANAGER
 *
 * Each table has a descriptor which is a contiguous array of words.
 * The descriptor is allocated from a global array using a buddy
 * algorithm.  Free lists exist for each power of 2 words.  Freeing
 * a piece first merges with free right and left neighbours and then
 * divides itself up into free list chunks.
 */

Uint32
Dbtup::getTabDescrOffsets(const Tablerec* regTabPtr, Uint32* offset)
{
  // belongs to configure.in
  unsigned sizeOfPointer = sizeof(CHARSET_INFO*);
  ndbrequire((sizeOfPointer & 0x3) == 0);
  sizeOfPointer = (sizeOfPointer >> 2);
  // do in layout order and return offsets (see DbtupMeta.cpp)
  Uint32 allocSize = 0;
  // magically aligned to 8 bytes
  offset[0] = allocSize += ZTD_SIZE;
  offset[1] = allocSize += regTabPtr->m_no_of_attributes* sizeOfReadFunction();
  offset[2] = allocSize += regTabPtr->m_no_of_attributes* sizeOfReadFunction();
  offset[3] = allocSize += regTabPtr->noOfCharsets * sizeOfPointer;
  offset[4] = allocSize += regTabPtr->noOfKeyAttr;
  offset[5] = allocSize += regTabPtr->m_no_of_attributes * ZAD_SIZE;
  offset[6] = allocSize += (regTabPtr->m_no_of_attributes + 1) >> 1; // real order
  allocSize += ZTD_TRAILER_SIZE;
  // return number of words
  return allocSize;
}

Uint32 Dbtup::allocTabDescr(const Tablerec* regTabPtr, Uint32* offset)
{
  Uint32 reference = RNIL;
  Uint32 allocSize = getTabDescrOffsets(regTabPtr, offset);
/* ---------------------------------------------------------------- */
/*       ALWAYS ALLOCATE A MULTIPLE OF 16 WORDS                     */
/* ---------------------------------------------------------------- */
  allocSize = (((allocSize - 1) >> 4) + 1) << 4;
  Uint32 list = nextHigherTwoLog(allocSize - 1);	/* CALCULATE WHICH LIST IT BELONGS TO     */
  for (Uint32 i = list; i < 16; i++) {
    jam();
    if (cfreeTdList[i] != RNIL) {
      jam();
      reference = cfreeTdList[i];
      removeTdArea(reference, i);	                /* REMOVE THE AREA FROM THE FREELIST      */
      Uint32 retNo = (1 << i) - allocSize;	        /* CALCULATE THE DIFFERENCE               */
      if (retNo >= ZTD_FREE_SIZE) {
        jam();
        // return unused words, of course without attempting left merge
        Uint32 retRef = reference + allocSize;
        freeTabDescr(retRef, retNo, false);
      } else {
        jam();
        allocSize = 1 << i;
      }//if
      break;
    }//if
  }//for
  if (reference == RNIL) {
    jam();
    terrorCode = ZMEM_NOTABDESCR_ERROR;
    return RNIL;
  } else {
    jam();
    setTabDescrWord((reference + allocSize) - ZTD_TR_TYPE, ZTD_TYPE_NORMAL);
    setTabDescrWord(reference + ZTD_DATASIZE, allocSize);

     /* INITIALIZE THE TRAILER RECORD WITH TYPE AND SIZE     */
     /* THE TRAILER IS USED TO SIMPLIFY MERGE OF FREE AREAS  */

    setTabDescrWord(reference + ZTD_HEADER, ZTD_TYPE_NORMAL);
    setTabDescrWord((reference + allocSize) - ZTD_TR_SIZE, allocSize);
    return reference;
  }//if
}//Dbtup::allocTabDescr()

void Dbtup::freeTabDescr(Uint32 retRef, Uint32 retNo, bool normal)
{
  itdaMergeTabDescr(retRef, retNo, normal);       /* MERGE WITH POSSIBLE NEIGHBOURS   */
  while (retNo >= ZTD_FREE_SIZE) {
    jam();
    Uint32 list = nextHigherTwoLog(retNo);
    list--;	/* RETURN TO NEXT LOWER LIST    */
    Uint32 sizeOfChunk = 1 << list;
    insertTdArea(retRef, list);
    retRef += sizeOfChunk;
    retNo -= sizeOfChunk;
  }//while
  ndbassert(retNo == 0);
}//Dbtup::freeTabDescr()

Uint32
Dbtup::getTabDescrWord(Uint32 index)
{
  ndbrequire(index < cnoOfTabDescrRec);
  return tableDescriptor[index].tabDescr;
}//Dbtup::getTabDescrWord()

void
Dbtup::setTabDescrWord(Uint32 index, Uint32 word)
{
  ndbrequire(index < cnoOfTabDescrRec);
  tableDescriptor[index].tabDescr = word;
}//Dbtup::setTabDescrWord()

void Dbtup::insertTdArea(Uint32 tabDesRef, Uint32 list) 
{
  ndbrequire(list < 16);
  setTabDescrWord(tabDesRef + ZTD_FL_HEADER, ZTD_TYPE_FREE);
  setTabDescrWord(tabDesRef + ZTD_FL_NEXT, cfreeTdList[list]);
  if (cfreeTdList[list] != RNIL) {
    jam();                                                /* PREVIOUSLY EMPTY SLOT     */
    setTabDescrWord(cfreeTdList[list] + ZTD_FL_PREV, tabDesRef);
  }//if
  cfreeTdList[list] = tabDesRef;	/* RELINK THE LIST           */

  setTabDescrWord(tabDesRef + ZTD_FL_PREV, RNIL);
  setTabDescrWord(tabDesRef + ZTD_FL_SIZE, 1 << list);
  setTabDescrWord((tabDesRef + (1 << list)) - ZTD_TR_TYPE, ZTD_TYPE_FREE);
  setTabDescrWord((tabDesRef + (1 << list)) - ZTD_TR_SIZE, 1 << list);
}//Dbtup::insertTdArea()

/*
 * Merge to-be-removed chunk (which need not be initialized with header
 * and trailer) with left and right buddies.  The start point retRef
 * moves to left and the size retNo increases to match the new chunk.
 */
void Dbtup::itdaMergeTabDescr(Uint32& retRef, Uint32& retNo, bool normal)
{
  // merge right
  while ((retRef + retNo) < cnoOfTabDescrRec) {
    jam();
    Uint32 tabDesRef = retRef + retNo;
    Uint32 headerWord = getTabDescrWord(tabDesRef + ZTD_FL_HEADER);
    if (headerWord == ZTD_TYPE_FREE) {
      jam();
      Uint32 sizeOfMergedPart = getTabDescrWord(tabDesRef + ZTD_FL_SIZE);

      retNo += sizeOfMergedPart;
      Uint32 list = nextHigherTwoLog(sizeOfMergedPart - 1);
      removeTdArea(tabDesRef, list);
    } else {
      jam();
      break;
    }
  }
  // merge left
  const bool mergeLeft = normal;
  while (mergeLeft && retRef > 0) {
    jam();
    Uint32 trailerWord = getTabDescrWord(retRef - ZTD_TR_TYPE);
    if (trailerWord == ZTD_TYPE_FREE) {
      jam();
      Uint32 sizeOfMergedPart = getTabDescrWord(retRef - ZTD_TR_SIZE);
      ndbrequire(retRef >= sizeOfMergedPart);
      retRef -= sizeOfMergedPart;
      retNo += sizeOfMergedPart;
      Uint32 list = nextHigherTwoLog(sizeOfMergedPart - 1);
      removeTdArea(retRef, list);
    } else {
      jam();
      break;
    }
  }
  ndbrequire((retRef + retNo) <= cnoOfTabDescrRec);
}//Dbtup::itdaMergeTabDescr()

/* ---------------------------------------------------------------- */
/* ------------------------ REMOVE_TD_AREA ------------------------ */
/* ---------------------------------------------------------------- */
/*                                                                  */
/* THIS ROUTINE REMOVES A TD CHUNK FROM THE POOL OF TD RECORDS      */
/*                                                                  */
/* INPUT:  TLIST          LIST TO USE                               */
/*         TAB_DESCR_PTR  POINTS TO THE CHUNK TO BE REMOVED         */
/*                                                                  */
/* SHORTNAME:   RMTA                                                */
/* -----------------------------------------------------------------*/
void Dbtup::removeTdArea(Uint32 tabDesRef, Uint32 list) 
{
  ndbrequire(list < 16);
  Uint32 tabDescrNextPtr = getTabDescrWord(tabDesRef + ZTD_FL_NEXT);
  Uint32 tabDescrPrevPtr = getTabDescrWord(tabDesRef + ZTD_FL_PREV);

  setTabDescrWord(tabDesRef + ZTD_HEADER, ZTD_TYPE_NORMAL);
  setTabDescrWord((tabDesRef + (1 << list)) - ZTD_TR_TYPE, ZTD_TYPE_NORMAL);

  if (tabDesRef == cfreeTdList[list]) {
    jam();
    cfreeTdList[list] = tabDescrNextPtr;	/* RELINK THE LIST           */
  }//if
  if (tabDescrNextPtr != RNIL) {
    jam();
    setTabDescrWord(tabDescrNextPtr + ZTD_FL_PREV, tabDescrPrevPtr);
  }//if
  if (tabDescrPrevPtr != RNIL) {
    jam();
    setTabDescrWord(tabDescrPrevPtr + ZTD_FL_NEXT, tabDescrNextPtr);
  }//if
}//Dbtup::removeTdArea()

#ifdef VM_TRACE
void
Dbtup::verifytabdes()
{
  struct WordType {
    short fl;   // free list 0-15
    short ti;   // table id
    WordType() : fl(-1), ti(-1) {}
  };
  WordType* wt = new WordType [cnoOfTabDescrRec];
  uint free_frags = 0;
  // free lists
  {
    for (uint i = 0; i < 16; i++) {
      Uint32 desc2 = RNIL;
      Uint32 desc = cfreeTdList[i];
      while (desc != RNIL) {
        const Uint32 size = (1 << i);
        ndbrequire(size >= ZTD_FREE_SIZE);
        ndbrequire(desc + size <= cnoOfTabDescrRec);
        { Uint32 index = desc + ZTD_FL_HEADER;
          ndbrequire(tableDescriptor[index].tabDescr == ZTD_TYPE_FREE);
        }
        { Uint32 index = desc + ZTD_FL_SIZE;
          ndbrequire(tableDescriptor[index].tabDescr == size);
        }
        { Uint32 index = desc + size - ZTD_TR_TYPE;
          ndbrequire(tableDescriptor[index].tabDescr == ZTD_TYPE_FREE);
        }
        { Uint32 index = desc + size - ZTD_TR_SIZE;
          ndbrequire(tableDescriptor[index].tabDescr == size);
        }
        { Uint32 index = desc + ZTD_FL_PREV;
          ndbrequire(tableDescriptor[index].tabDescr == desc2);
        }
        for (uint j = 0; j < size; j++) {
          ndbrequire(wt[desc + j].fl == -1);
          wt[desc + j].fl = i;
        }
        desc2 = desc;
        desc = tableDescriptor[desc + ZTD_FL_NEXT].tabDescr;
        free_frags++;
      }
    }
  }
  // tables
  {
    for (uint i = 0; i < cnoOfTablerec; i++) {
      TablerecPtr ptr;
      ptr.i = i;
      ptrAss(ptr, tablerec);
      if (ptr.p->tableStatus == DEFINED) {
        Uint32 offset[10];
        const Uint32 alloc = getTabDescrOffsets(ptr.p, offset);
        const Uint32 desc = ptr.p->readKeyArray - offset[3];
        Uint32 size = alloc;
        if (size % ZTD_FREE_SIZE != 0)
          size += ZTD_FREE_SIZE - size % ZTD_FREE_SIZE;
        ndbrequire(desc + size <= cnoOfTabDescrRec);
        { Uint32 index = desc + ZTD_FL_HEADER;
          ndbrequire(tableDescriptor[index].tabDescr == ZTD_TYPE_NORMAL);
        }
        { Uint32 index = desc + ZTD_FL_SIZE;
          ndbrequire(tableDescriptor[index].tabDescr == size);
        }
        { Uint32 index = desc + size - ZTD_TR_TYPE;
          ndbrequire(tableDescriptor[index].tabDescr == ZTD_TYPE_NORMAL);
        }
        { Uint32 index = desc + size - ZTD_TR_SIZE;
          ndbrequire(tableDescriptor[index].tabDescr == size);
        }
        for (uint j = 0; j < size; j++) {
          ndbrequire(wt[desc + j].ti == -1);
          wt[desc + j].ti = i;
        }
      }
    }
  }
  // all words
  {
    for (uint i = 0; i < cnoOfTabDescrRec; i++) {
      bool is_fl = wt[i].fl != -1;
      bool is_ti = wt[i].ti != -1;
      ndbrequire(is_fl != is_ti);
    }
  }
  delete [] wt;
  ndbout << "verifytabdes: frags=" << free_frags << endl;
}
#endif
