Method add

src/common/classes/tree.h:648–884

template <typename Value, typename Key, typename KeyOfValue, typename Cmp>
bool BePlusTree<Value, Key, KeyOfValue, Cmp>::add(const Value& item, Accessor* accessor)
{
	// Finish initialization of the tree if necessary
	if (!root)
		root = FB_NEW_POOL(*pool) ItemList();

	// Find leaf page for our item
	NodePtr vList = this->root;
	const Key& key = KeyOfValue::generate(nullptr, item);
	for (int lev = this->level; lev > 0; lev--)
	{
		FB_SIZE_T pos;
		if (!vList.nodes->find(key, pos))
		{
			if (pos > 0)
				pos--;
		}
		vList = (*vList.nodes)[pos];
	}

	ItemList *leaf = vList.items;

	FB_SIZE_T pos;
	if (leaf->find(key, pos))
	{
		if (accessor)
		{
			accessor->curr = leaf;
			accessor->curPos = pos;
		}
		return false;
	}

	if (leaf->getCount() < LEAF_COUNT)
	{
		leaf->insert(pos, item);
		return true;
	}

	// Page is full. Look up nearby pages for space if possible
	ItemList *temp;
	// Adding items to the next page is cheaper in most cases that
	// is why it is checked first
	if ((temp = leaf->next) && temp->getCount() < LEAF_COUNT)
	{
		// Found space on the next page
		if (pos == LEAF_COUNT)
		{
			// This would be ok if items were unique: temp->insert(0, item);
			// The same applies to all simular cases below
			temp->insert(0, item);
		}
		else
		{
			// Maybe splitting array by half would make things faster ?
			// It should do it in case of random size items.
			// It would make things slower in case of sequental items addition.
			// Let's leave it as is now.