<?php
/**
 * SeekQuarry/Yioop --
 * Open Source Pure PHP Search Engine, Crawler, and Indexer
 *
 * Copyright (C) 2009 - 2026  Chris Pollett chris@pollett.org
 *
 * LICENSE:
 *
 * 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, either version 3 of the License, or
 * (at your option) any later version.
 *
 * 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, see <https://www.gnu.org/licenses/>.
 *
 * END LICENSE
 *
 * @author Chris Pollett chris@pollett.org
 * @license https://www.gnu.org/licenses/ GPL3
 * @link https://www.seekquarry.com/
 * @copyright 2009 - 2026
 * @filesource
 */
namespace seekquarry\yioop\library\data_structures;
use seekquarry\yioop\library as L;

use seekquarry\yioop\configs as C;
/**
 * This class implements the B+-tree structure over existing file system
 *
 * @author Chris Pollett
 */
class BPlusTree
{
    /**
     * The default compressor object used to compress tree nodes
     */
    const DEFAULT_COMPRESSOR = C\NS_COMPRESSORS . "NonCompressor";
    /**
     * The MAXIMUM number of keys stored in a tree node (will split if have
     * more)
     */
    const MAX_KEYS = 501;
    /**
     * Maximum size of a cache of any type used by this BPlusTree
     */
    const MAX_CACHE_SIZE = 200;
    /**
     * Default parameters to use when constructing a BPlusTree
     */
    const DEFAULT_PARAMETERS = ["NODE_COMPRESSOR" => self::DEFAULT_COMPRESSOR,
        "BLOB_COMPRESSOR" => self::DEFAULT_COMPRESSOR,
        "FORMAT" => ["PRIMARY KEY" => ["KEY", -1], "VALUE" => "BLOB"],
        "MAX_KEYS" => self::MAX_KEYS
    ];
    /**
     * Internal nodes of BPlusTree are folders, subfolders/subfiles are
     * names according to their least key except for the first subdfolder/
     * subfile of the node which is given the name of the LEAST_NODE_NAME
     * constant
     */
    const LEAST_NODE_NAME = "start";
    /**
     * Internal nodes of BPlusTree are folders. For nodes of the same
     * height in the tree NEXT_NODE_NAME is used as the name of the file
     * with the serialized name of the next folder of the same height in
     * the tree.
     */
    const NEXT_NODE_NAME = "next";
    /**
     * Name of temporary file used when splitting a BPlusTree node.
     */
    const TEMP_NODE_NAME = "tmp_node";
    /**
     * Leaf node archive file (used for blob and serial record columns) name
     * prefix
     */
    const ARCHIVE_PREFIX = "a";
    /**
     * Leaf node index record file name prefix
     */
    const NODE_PREFIX = "i";
    /**
     * File name of file used to store the parameters of this
     * BPlusTree
     */
    const PARAMETERS_FILE = "bpt_parameters.txt";
    /**
     * Field variable used as a cache for the file handle, file name, and
     * time of the last archive file for a B+-tree node added to
     * @var array
     */
    public $add_archive_cache = [null, "", -1];
    /**
     * Field variable used as a cache for the file handle, file name, and
     * time of the last archive file for a B+-tree node accessed for a value
     * @var array
     */
    public $get_archive_cache = [null, "", -1];
    /**
     * Array of column names for the columns in a BPlusTree which
     * are of type BLOB or SERIAL
     * @var array
     */
    public $blob_columns;
    /**
     * The seekquarry\yioop\library\compressors\Compressor object used to
     * compress node files.
     * @var object
     */
    public $node_compressor;
    /**
     * The seekquarry\yioop\library\compressors\Compressor object used to
     * compress blob columns.
     * @var object
     */
    public $blob_compressor;
    /**
     * Folder for storing the B-Tree files
     * @var string
     */
    public $folder;
    /**
     * A cache for contents of nodes that have been recently added to.
     * consists of path_to_node => node_content pairs
     * @var array
     */
    public $insert_node_cache = [];
    /**
     * Used to keep track of when this instance was created, as part of managing
     * file handles expiration (could be set/updated externally to reflect
     * some other instance using the BPlusTree)
     * @var int
     */
    public $instance_time;
    /**
     * Name of primary key column for records
     * @var string
     */
    public $key_field;
    /**
     * Last folder path of a find operation, provided this was cacheable
     * @var string
     */
    public $last_find_folder = null;
    /**
     * Last encoded key used for a find operation, provided this was cacheable
     * Used to avoid recomputing path down tree if will be the same.
     * @var string
     */
    public $last_find_key = null;
    /**
     * First key of next node after returned node for the last find operation,
     * provided this was cacheable
     * @var string
     */
    public $last_find_next_key = null;
    /**
     * File path of last inserted node
     * @var string
     */
    public $last_insert_node_path;
    /**
     * Storage for root node of the B-Tree
     * @var object
     */
    public $parameters;
    /**
     * Array of column names for the columns in a PartitionDocumentBundle which
     * are of type SERIAL
     * @var array
     */
    public $serial_columns;
    /**
     * The PackedTableTools object used to pack and unpack records in
     * BPlusTree
     * @var object
     */
    public $table_tools;
    /**
     * Cache of key-values (internal_node_path => array of subnodes) used to
     * speed up tree traversal
     * @var array
     */
    public $tree_path_cache = [];
    /**
     * Creates/Loads B+-Tree having specified folder and minimum_degree.
     *
     * @param string $folder is the folder for storing the B+-Tree files
     * @param array $format the column names, keys and types for this
     *  B+-Tree  object
     * @param int $max_keys the maximum number of keys a node is allowed to hold
     * @param object $node_compressor_type
     *  seekquarry\yioop\library\compressors\Compressor object used to
     *  compress index node files.
     * @param object $blob_compressor_type
     *  seekquarry\yioop\library\compressors\Compressor object used to
     *  compress blob columns.
     * @return null returned (leaving the instance partially initialised)
     *  on a corrupt on-disk parameters file or when the resolved
     *  format disagrees with the constructor arguments
     */
    public function __construct($folder, $format =
        self::DEFAULT_PARAMETERS["FORMAT"], $max_keys = self::MAX_KEYS,
        $node_compressor_type = self::DEFAULT_COMPRESSOR,
        $blob_compressor_type = self::DEFAULT_COMPRESSOR)
    {
        // ensure $max_keys odd
        $max_keys = ($max_keys % 2 == 1) ? $max_keys : $max_keys + 1;
        $initial_parameters = self::DEFAULT_PARAMETERS;
        $initial_parameters["MAX_KEYS"] = $max_keys;
        $initial_parameters["NODE_COMPRESSOR"] = $node_compressor_type;
        $initial_parameters["BLOB_COMPRESSOR"] = $blob_compressor_type;
        $this->node_compressor = new $node_compressor_type();
        $this->blob_compressor = new $blob_compressor_type();
        $initial_parameters["FORMAT"] = $format;
        $this->instance_time = hrtime(true);
        $this->folder = $folder;
        $changed_parameters = false;
        if (!file_exists($folder)) {
            $changed_parameters = true;
            if(!mkdir($folder)) {
                return null;
            }
            file_put_contents($folder . "/" . self::NEXT_NODE_NAME,
                serialize(null));
        }
        $this->parameters = self::getParameterInfo($folder);
        foreach (self::DEFAULT_PARAMETERS as $field => $value) {
            if (!isset($this->parameters[$field])) {
                $this->parameters[$field] = $initial_parameters[$field];
                $changed_parameters = true;
            }
        }
        $format = $this->parameters["FORMAT"];
        $packed_table_format = [];
        $this->blob_columns = [];
        $this->serial_columns = [];
        $this->key_field = null;
        foreach ($format as $field_name => $type) {
            $upper_field_name = strtoupper($field_name);
            if ($upper_field_name == "PRIMARY KEY") {
                $packed_table_format["PRIMARY KEY"] = $type;
                $this->key_field = (is_array($type)) ? $type[0] : $type;
                continue;
            }
            $type = strtoupper($type);
            if (in_array($type, ["BLOB", "SERIAL"])) {
                $this->blob_columns[] = $field_name;
                if ($type == "SERIAL") {
                    $this->serial_columns[] = $field_name;
                }
                $packed_table_format[$field_name] = "INT";
            } else if (isset(PackedTableTools::TYPE_SYNONYMS[$type])) {
                $packed_table_format[$field_name] =
                    PackedTableTools::TYPE_SYNONYMS[$type];
            } else {
                return null;
            }
        }
        if (empty($this->key_field)) {
            return null;
        }
        if (!empty($this->blob_columns)) {
            $packed_table_format["LAST_BLOB_LEN"] = "INT";
        }
        $this->table_tools = new PackedTableTools($packed_table_format,
            $node_compressor_type);
        if ($changed_parameters) {
            $this->saveParameters();
        }
    }
    /**
     * Adds an entry to the BPlusTree. Entries added might not be fully
     * on disk until flushLastPutNode is called, as this memory tries to
     * avoid disk writes.
     *
     * @param array $row associative array of filed_name => values for each
     *  column field field this BPlusTree's signature has
     * @param bool $is_encoded_key whether in $row the primary key field has
     *  already been encoded (rawurlencode) or not
     * @param int $mode says what to do in the event that an entry with the
     *  given key already exists in the BPlusTree. Possibilities are either
     *  PackedTableTools::APPEND_MODE or PackedTableTools::REPLACE_MODE
     *  The former appends as a subrecord the nonkey fields of the entry
     *  to the existing list of sub-records associated to the given key, the
     *  later replaces the key value pair.
     * @return bool success (true) or failure (false)
     */
    public function put($row, $is_encoded_key = true,
        $mode = PackedTableTools::APPEND_MODE)
    {
        $key = $row[$this->key_field] ?? false;
        if ($key === false) {
            return false;
        }
        $encode_key = ($is_encoded_key) ? $key : rawurlencode($key);
        $insert_node_path = $this->find($encode_key, true);
        if(empty($insert_node_path)) {
            return false;
        }
        $table_tools = $this->table_tools;
        $this->flushLastPutNode($insert_node_path);
        if (!isset($this->insert_node_cache[$insert_node_path])) {
            $this->insert_node_cache[$insert_node_path] =
                $table_tools->load($insert_node_path, $mode) ?? [];
        }
        $insert_node = $this->insert_node_cache[$insert_node_path];
        $archive_filename = (empty($this->blob_columns)) ? "" :
            $this->archiveFilenameFromNodeFilename($insert_node_path);
        $this->putNode($row, $insert_node, $archive_filename, $is_encoded_key,
            $mode);
        if (count($insert_node) > $this->parameters["MAX_KEYS"]) {
            $this->flushLastPutNode();
            $this->splitRecordsInLeaf($insert_node_path, $insert_node);
            $this->insert_node_cache = [];
            $this->tree_path_cache = [];
            $parent_path = $this->getParentFolder($insert_node_path);
            $this->updateNodePath($parent_path);
            return true;
        }
        if (count($this->insert_node_cache) >= self::MAX_CACHE_SIZE) {
            $this->insert_node_cache = [];
        }
        $this->insert_node_cache[$insert_node_path] = $insert_node;
        $this->last_insert_node_path = $insert_node_path;
        return true;
    }
    /**
     * Saves the the BPlusTree $insert_node_path (if not empty) node to disk.
     * If $insert_node_path == "" then the last node put'ted to will be saved.
     *
     * @param string $insert_node_path name of node to save to disk.
     */
    public function flushLastPutNode($insert_node_path = "")
    {
        $last_insert_node_path = $this->last_insert_node_path ?? "";
        if (!empty($last_insert_node_path) &&
            $insert_node_path != $last_insert_node_path &&
            isset($this->insert_node_cache[$last_insert_node_path])) {
            $this->table_tools->save($last_insert_node_path,
                $this->insert_node_cache[$last_insert_node_path]);
            unset($this->insert_node_cache[$last_insert_node_path]);
            $this->last_insert_node_path = "";
        }
    }
    /**
     * Given an entry to add to a BPlusTree node, the index file of the node
     * (for non blob or serial fields), and the name of the archive file for
     * node (for blob or serial fields) stores the entry to the node.
     *
     * @param array $row associative array of filed_name => values for each
     *  column field field this BPlusTree's signature has
     * @param bool $is_encoded_key whether in $row the primary key field has
     *  already been encoded (rawurlencode) or not
     * @param array &$node an in-memory code of a node (will be modified by
     *  this method)
     * @param string $archive_filename the name of the archive file associated
     *  with this file used for blob or serial fields.
     * @param bool $is_encoded_key whether in $row the primary key field has
     *  already been encoded (rawurlencode) or not
     * @param int $mode says what to do in the event that an entry with the
     *  given key already exists in the BPlusTree. Possibilities are either
     *  PackedTableTools::APPEND_MODE or PackedTableTools::REPLACE_MODE
     *  The former appends as a subrecord the nonkey fields of the entry
     *  to the existing list of sub-records associated to the given key, the
     *  later replaces the key value pair.
     */
    public function putNode($row, &$node, $archive_filename,
        $is_encoded_key = true, $mode = PackedTableTools::APPEND_MODE)
    {
        $table_tools = $this->table_tools;
        $key = $row[$this->key_field] ?? false;
        $encode_key = ($is_encoded_key) ? $key : rawurlencode($key);
        $out_value = $this->writeBlobsAndPack($archive_filename, $row);
        $table_tools->add($node, $encode_key, $out_value,
            PackedTableTools::ADD_MEM_TABLE, $mode);
    }
    /**
     * For a non-leaf node checks if it needs to be split, and if so splits
     * and fixes keys up the tree to restore BPlus-Tree properties.
     *
     * @param string $folder to check if needs split
     * @return bool success (true) or failure (false)
     */
    public function updateNodePath($folder)
    {
        if (strncmp($folder, $this->folder, strlen($this->folder)) != 0) {
            return false;
        }
        $node_prefix = self::NODE_PREFIX;
        $nodes = glob("$folder/$node_prefix*");
        if (count($nodes) < $this->parameters["MAX_KEYS"]) {
            return true;
        }
        if ($folder == $this->folder) { //root case
            return $this->splitRootNode();
        }
        $len = strlen($folder);
        $num_nodes = count($nodes);
        $next_node_name = self::NEXT_NODE_NAME;
        $this->add_archive_cache = [null, "", -1];
        $this->get_archive_cache = [null, "", -1];
        $parent_folder = $this->getParentFolder($folder);
        $half_max = floor($num_nodes/2);
        $node_name = substr($nodes[$half_max], $len + 1);
        $new_node = "$parent_folder/$node_name";
        mkdir($new_node);
        $next_node = "$folder/$next_node_name";
        rename($next_node, "$new_node/$next_node_name");
        file_put_contents($next_node, serialize($node_name));
        $node = $nodes[$half_max];
        $node_name = substr($node, $len + 1);
        $archive_prefix = self::ARCHIVE_PREFIX;
        $least_node_name = self::LEAST_NODE_NAME;
        $len_node_prefix = strlen($node_prefix);
        $archive_name = $archive_prefix .
            substr($node_name, $len_node_prefix);
        rename($node, "$new_node/$least_node_name");
        $archive_filename = "$folder/$archive_name";
        if (file_exists($archive_filename)) {
            rename($archive_filename,
                "$new_node/$archive_prefix$least_node_name");
        }
        for ($i = $half_max + 1; $i < $num_nodes; $i++) {
            $node = $nodes[$i];
            $node_name = substr($node, $len + 1);
            rename($node, "$new_node/$node_name");
            $archive_name = $archive_prefix .
                substr($node_name, $len_node_prefix);
            $archive_filename = "$folder/$archive_name";
            if (file_exists($archive_filename)) {
                rename($archive_filename, "$new_node/$archive_name");
            }
        }
        return $this->updateNodePath($parent_folder);
    }
    /**
     * This method handles split the root node of a BPlusTree when it gets too
     * full. Unlike for other nodes when we can add a key in the parent, for the
     * root, we make a temporary folder and move all the root node's nodes to it
     * then rename this the the least node of the root, and call updateNodePath
     * on this to restore the BPlusTree property.
     *
     * @return bool success (true) or failure (false)
     */
    public function splitRootNode()
    {
        $this->last_find_folder = null;
        $this->last_find_key = null;
        $this->last_find_next_key = null;
        $folder = $this->folder;
        $this->add_archive_cache = [null, "", -1];
        $this->get_archive_cache = [null, "", -1];
        $len = strlen($folder);
        $node_prefix =  self::NODE_PREFIX;
        $temp_node_name = self::TEMP_NODE_NAME;
        $least_node_name = self::LEAST_NODE_NAME;
        $archive_prefix = self::ARCHIVE_PREFIX;
        $next_node_name = self::NEXT_NODE_NAME;
        $nodes = glob("$folder/$node_prefix*");
        $tmp_folder = "$folder/$temp_node_name";
        $least_node = "$folder/$least_node_name";
        $least_archive = "$folder/$archive_prefix$least_node_name";
        mkdir($tmp_folder);
        $next_node_name_path = "$folder/$next_node_name";
        if (!file_exists($next_node_name_path)) {
            file_put_contents($next_node_name_path, serialize(null));
        }
        $tmp_next_node_name_path = "$tmp_folder/$next_node_name";
        rename($next_node_name_path, $tmp_next_node_name_path);
        if (file_exists($least_node)) {
            rename($least_node, "$tmp_folder/$least_node_name");
            if (file_exists($least_archive)) {
                rename($least_archive,
                    "$tmp_folder/$archive_prefix$least_node_name");
            }
        }
        $len_node_prefix = strlen($node_prefix);
        foreach ($nodes as $node) {
            $node_name = substr($node, $len + 1);
            rename($node, "$tmp_folder/$node_name");
            $archive_name = $archive_prefix .
                substr($node_name, $len_node_prefix);
            $archive_filename = "$folder/$archive_name";
            if (file_exists($archive_filename)) {
                rename($archive_filename, "$tmp_folder/$archive_name");
            }
        }
        rename($tmp_folder, $least_node);
        return $this->updateNodePath($least_node);
    }
    /**
     * Splits BPlusTree leaf $node with path $node_path into two nodes each
     * with an equal number of keys.
     *
     * @param string $node_path path to file used to store a BPlusTree node
     *  Used to name files after split.
     * @param array $node BPlusTree node (associative array of pairs key =>
     *  record for key stored according to BPlusTree signature using
     *  PackedTableTools)
     */
    public function splitRecordsInLeaf($node_path, $node)
    {
        $this->last_find_folder = null;
        $this->last_find_key = null;
        $this->last_find_next_key = null;
        $parent_folder = $this->getParentFolder($node_path);
        $archive_prefix = self::ARCHIVE_PREFIX;
        $temp_node_name = self::TEMP_NODE_NAME;
        $node_prefix = self::NODE_PREFIX;
        $tmp_filename = "$parent_folder/$temp_node_name";
        $tmp_archive_filename = "$parent_folder/$archive_prefix$temp_node_name";
        $archive_filename = (empty($this->blob_columns)) ? "" :
            $this->archiveFilenameFromNodeFilename($node_path);
        $num_keys = count($node);
        $half_num = ceil($num_keys/2);
        $keys = array_keys($node);
        sort($keys);
        $half_key = $keys[$half_num];
        /* the str_replaces are because I was getting hard to trace crashes
           concerning nulls in file name.
         */
        $new_leaf_filename = str_replace("\x00", "0",
            "$parent_folder/$node_prefix$half_key");
        $new_archive_filename = str_replace("\x00", "0",
            "$parent_folder/$archive_prefix$half_key");
        $table_tools = $this->table_tools;
        $out_archive_filename = $tmp_archive_filename;
        $out_node = [];
        $flag = false;
        for ($i = 0; $i < $half_num; $i++) {
            $values = $this->getFromNode($keys[$i], $node, $archive_filename);
            if ($values) {
                foreach ($values as $value) {
                    $this->putNode($value, $out_node, $out_archive_filename);
                }
            }
        }
        $table_tools->save($tmp_filename, $out_node);
        $out_node = [];
        $out_archive_filename = $new_archive_filename;
        for ($i = $half_num; $i < $num_keys; $i++) {
            $values = $this->getFromNode($keys[$i], $node, $archive_filename);
            if ($values) {
                foreach ($values as $value) {
                    $this->putNode($value, $out_node, $out_archive_filename);
                }
            }
        }
        $table_tools->save($new_leaf_filename, $out_node);
        $this->add_archive_cache = [null, "", -1];
        $this->get_archive_cache = [null, "", -1];
        rename($tmp_filename, $node_path);
        if (!empty($this->blob_columns)) {
            rename($tmp_archive_filename, $archive_filename);
        }
    }
    /**
     * Returns the record associated with a $key as stored in the BPlusTree.
     * If $key is not present in tree then returns null
     *
     * @param string $key to look up in current BPlusTree
     * @param bool $is_encoded_key whether $key has been rawurlencode'd or not
     * @param bool $use_string_node rather than load in a node and split
     *   into keys for use of all keys, read in node as a string and uncompress
     *   but do not perform further decoding (faster if only doing reads).
     * @param bool $decode whether or not to unpack record
     * @param bool $look_up_blobs whether to leave in the record the
     *      offset and length for blob items or to look up the blob item
     * @param int $offset starting record item associated with this key
     *      to return
     * @param int $limit maximum number of record items associated with this
     *      key to return
     * @return array of items associated with this key in the BPlusTree
     *      if $look_up_blobs == false, then returns a pair
     *      ["ARCHIVE_FILE" => [filename where blob columns stored,
     *     array of items associated with this key]]
     */
    public function get($key, $is_encoded_key = true, $use_string_node = false,
        $decode = true, $look_up_blobs = true, $offset = 0, $limit = -1)
    {
        $table_tools = $this->table_tools;
        $key_node_filename = $this->find($key, $is_encoded_key);
        if (!$key_node_filename) {
            return null;
        }
        $archive_filename = (empty($this->blob_columns)) ? "" :
            $this->archiveFilenameFromNodeFilename($key_node_filename);
        if ($use_string_node) {
            $key_node = $table_tools->load($key_node_filename,
                $table_tools::AS_STRING_MODE, true);
        } else {
            $key_node = $table_tools->load($key_node_filename);
        }
        $rows = $this->getFromNode($key, $key_node, $archive_filename,
            $is_encoded_key, $use_string_node, $decode, $look_up_blobs, $offset,
            $limit);
        if (!$look_up_blobs) {
            return ["ARCHIVE_FILE" => $archive_filename, "ROWS" => $rows];
        }
        return $rows;
    }
    /**
     * Returns records associated with $key in $key_node and the file
     * associated with $archive_filename (for blob and serial column values)
     * if it exists.
     *
     * @param string $key the key to look up
     * @param array $key_node the BPlusTree index node in which to look up the
     *  key
     * @param string $archive_filename file name of archive data (blob and
     *  serial columns) associated with $key_node
     * @param bool $is_encoded_key whether the key is rawurlencoded or not
     * @param bool $is_string_node when true, $key_node is a serialized
     *  string-format leaf and is searched via findRowFromKeyTableString
     *  instead of the in-memory associative-array find()
     * @param bool $decode  whether to $decode the records or leave them packed
     * @param bool $look_up_blobs whether to look up blob and serial columns
     * @param int $offset index of the first record associated with $key to
     *  return
     * @param int $limit maximum number of records associated with key to return
     * @return array of value records associated with $key
     */
    public function getFromNode($key, $key_node, $archive_filename,
        $is_encoded_key = true, $is_string_node = false, $decode = true,
        $look_up_blobs = true, $offset = 0, $limit = -1)
    {
        $table_tools = $this->table_tools;
        $encode_key = ($is_encoded_key) ? $key : rawurlencode($key);
        if ($is_string_node) {
            $values = $table_tools->findRowFromKeyTableString($key_node,
                 $encode_key);
        } else {
            $values = $table_tools->find($key_node, $encode_key);
        }
        if (!$values) {
            return null;
        }
        if (!$decode) {
            return $values;
        }
        $values = $table_tools->unpack($values, $offset, $limit);
        if (!is_array($values)) {
            L\crawlLog("Unpack BPlusTree error!!! (Key,offset,limit) was: ".
                "($key, $offset, $limit) ..");
            $value_message = (is_string($values)) ? L\toHexString($values) :
                serialize($values);
            L\crawlLog(".. value was:" . $value_message);
            return null;
        }
        $num_unpacked = count($values);
        if (!$look_up_blobs) {
            return $values;
        }
        $num_blob_columns = count($this->blob_columns);
        for ($k = 0; $k < $num_unpacked; $k++) {
            if ($num_blob_columns > 0) {
                $blob_offset = intval($values[$k][$this->blob_columns[0]]);
                for ($i = 0; $i < $num_blob_columns; $i++) {
                    $column_name = $this->blob_columns[$i];
                    $len = ($i + 1 < $num_blob_columns) ?
                        intval($values[$k][$this->blob_columns[$i + 1]]) :
                        $values[$k]["LAST_BLOB_LEN"];
                    $values[$k][$column_name] = ($len == 0) ? "" :
                        $this->getArchive($archive_filename, $blob_offset,
                        $len);
                    $blob_offset += $len;
                }
                unset($values[$k]["LAST_BLOB_LEN"]);
                foreach ($this->serial_columns as $field_name) {
                    $values[$k][$field_name] = unserialize(
                        $values[$k][$field_name]);
                }
            }
            $values[$k][$this->key_field] = ($is_encoded_key) ?
                $key : rawurldecode($encode_key);
        }
        return $values;
    }
    /**
     * Returns the file path to the file that may or may not contain $key
     * in the BPlusTree
     *
     * @param string $key to look up in BPlusTree
     * @param bool $is_encoded_key whether $key has been rawurlencode'd or not
     * @return string file path to node in BPlusTree that may or may not contain
     *      this key
     */
    public function find($key, $is_encoded_key = false)
    {
        $encode_key = ($is_encoded_key) ? $key : rawurlencode($key);
        if (!empty($this->last_find_folder) && !empty($this->last_find_key) &&
            $this->last_find_key <= $encode_key
            && !empty($this->last_find_next_key) &&
            $encode_key < $this->last_find_next_key) {
                return $this->last_find_folder;
        }
        $current_folder = $this->folder;
        $cache = & $this->tree_path_cache;
        $node_prefix = self::NODE_PREFIX;
        $least_node_name = self::LEAST_NODE_NAME;
        $node_prefix_and_key = self::NODE_PREFIX . $encode_key;
        while (isset($cache[$current_folder]) || is_dir($current_folder)) {
            $current_prefix = "$current_folder/$node_prefix";
            $len_current_prefix = strlen($current_prefix);
            if (!isset($cache[$current_folder])) {
                $cache[$current_folder] = glob("$current_prefix*");
            }
            $nodes = $cache[$current_folder];
            if (empty($nodes)) {
                return "$current_folder/$least_node_name";
            }
            if ($nodes == $current_folder) {
                break;
            }
            $exact_node = "$current_folder/$node_prefix_and_key";
            $least_node = "$current_folder/$least_node_name";
            $first_index = 0;
            $last_index = count($nodes) - 1;
            $this->last_find_folder = null;
            $this->last_find_key = null;
            $this->last_find_next_key = null;
            if ($exact_node < $nodes[$first_index]) {
                $this->last_find_folder = $least_node;
                $this->last_find_key = $encode_key;
                $this->last_find_next_key = substr($nodes[$first_index],
                    $len_current_prefix);
                $current_folder = $least_node;
            } else if ($exact_node == $nodes[$first_index]) {
                if (!empty($nodes[$first_index + 1])) {
                    $this->last_find_folder = $nodes[$first_index];
                    $this->last_find_key = $encode_key;
                    $this->last_find_next_key = substr($nodes[$first_index + 1],
                        $len_current_prefix);
                }
                $current_folder = $nodes[$first_index];
            } else if ($nodes[$last_index] <= $exact_node) {
                $current_folder = $nodes[$last_index];
            } else {
                while ($first_index < $last_index) {
                    $mid_index = ceil(($first_index + $last_index)/2);
                    if ($nodes[$mid_index] > $exact_node) {
                        $last_index = $mid_index - 1;
                    } else {
                        $first_index = $mid_index;
                    }
                }
                if (!empty($nodes[$first_index + 1])) {
                    $this->last_find_folder = $nodes[$first_index];
                    $this->last_find_key = $encode_key;
                    $this->last_find_next_key = substr($nodes[$first_index + 1],
                        $len_current_prefix);
                }
                $current_folder = $nodes[$first_index];
            }
        }
        $return_folder =  null;
        if ($nodes == $current_folder) {
            $return_folder =  $current_folder;
        } else if (file_exists($current_folder)) {
            if (count($cache) >= self::MAX_CACHE_SIZE) {
                $this->tree_path_cache = [];
            }
            $cache[$current_folder] = $current_folder;
            $return_folder =  $current_folder;
        } else {
            $this->last_find_folder = null;
            $this->last_find_key = null;
            $this->last_find_next_key = null;
        }
        return $return_folder;
    }
    /**
     * Given the path to an index node file in the BPlusTree compute the
     * path to the corresponding archive node file.
     *
     * @param string $node_filename of index node path
     * @return string associated archive node path
     */
    public function archiveFilenameFromNodeFilename($node_filename)
    {
        $parent_folder = $this->getParentFolder($node_filename);
        $len = strlen($parent_folder);
        $node_name = substr($node_filename, $len + 1);
        if ($node_name == self::LEAST_NODE_NAME) {
             return $parent_folder. "/" . self::ARCHIVE_PREFIX .
                self::LEAST_NODE_NAME;
        }
        return $parent_folder . "/" . self::ARCHIVE_PREFIX .
            substr($node_name, strlen(self::NODE_PREFIX));
    }
    /**
     * Cuts a blob length taken from this tree's index down to something
     * it is safe to read: no further than the end of the archive file,
     * and no larger than MAX_BLOB_READ_LEN. fread() asks PHP for the
     * whole length before it reads a byte, so a corrupted length asks
     * for that much memory however small the file is, which is enough
     * to end a long-running server. A length past the maximum is logged
     * with its file and offset and the read is skipped.
     *
     * @param string $archive_filename path to the archive node file the
     *  blob is being read from
     * @param int $offset byte offset into that file where the blob starts
     * @param int $len length of the blob as the index gives it
     * @return int number of bytes it is safe to read, possibly zero
     */
    public function lengthWorthReading($archive_filename, $offset, $len)
    {
        if ($len > C\MAX_BLOB_READ_LEN) {
            L\crawlLog("BPlusTree::getArchive: blob length $len at offset " .
                "$offset in $archive_filename exceeds " .
                C\MAX_BLOB_READ_LEN . "; treating the entry as corrupt " .
                "and skipping the read");
            return 0;
        }
        $size = @filesize($archive_filename);
        if ($size === false) {
            return $len;
        }
        $room = $size - $offset;
        if ($room <= 0) {
            return 0;
        }
        return min($len, $room);
    }
    /**
     * Return the blob item from $archive_filename at $offset of length $len,
     * uncompress the result
     *
     * @param string $archive_filename path to an archive node file for this
     *  BPlusTree
     * @param int $offset byte offset into archive node file file
     * @param int $len length of blob item
     * @return string uncompressed blob item from $archive_filename
     */
    public function getArchive($archive_filename, $offset, $len)
    {
        list($fh, $previous_archive_filename, $previous_instance_time) =
            $this->get_archive_cache;
        $blob_compressor = $this->blob_compressor;
        if (!$fh || $previous_archive_filename != $archive_filename ||
            $previous_instance_time != $this->instance_time) {
            if ($fh) {
                fclose($fh);
            }
            $fh = fopen($archive_filename , "r");
            $previous_archive_filename = $archive_filename;
            $previous_instance_time = $this->instance_time;
        }
        if (empty($blob_compressor)) {
            $blob_compress_type = $this->parameters["BLOB_COMPRESSOR"];
            $blob_compressor = new $blob_compress_type();
        }
        $value = false;
        if ($fh && fseek($fh, $offset) == 0 && $len > 0) {
            $len = self::lengthWorthReading($archive_filename, $offset,
                $len);
        }
        if ($fh && $len > 0) {
            $compressed_file = fread($fh, $len);
            $value = $blob_compressor->uncompress($compressed_file);
        }
        $this->get_archive_cache = [$fh, $previous_archive_filename,
            $previous_instance_time];
        return $value;
    }
    /**
     * Given a encoded hash_key to be used as the name of in the name of
     * an archive file for a BPlusTree node and a folder where that
     * node should be stored, return the path name for an archive file for
     * a node
     * @param string $current_folder to store archive file in
     * @param string $encode_key encode key value to be used in the file
     *  name of a BPlusTree node archive file
     * @return string archive file path
     */
    protected function getArchiveName($current_folder, $encode_key)
    {
        $archive_filename = $current_folder . "/" . self::ARCHIVE_PREFIX .
            $encode_key;
        return $archive_filename;
    }
    /**
     * Write the blob and serial columns from a row to insert into BPlusTree
     * and then pack the rest of the row as a string
     *
     * @param string $archive_filename name of archive file for a BPlusTree node
     * @param array $row BPlusTree row to pack Blob columns for
     * @return string packed row
     */
    protected function writeBlobsAndPack($archive_filename, $row)
    {
        $blob_columns = $this->blob_columns ?? [];
        $serial_columns = $this->serial_columns ?? [];
        $format = $this->parameters["FORMAT"];
        unset($format['PRIMARY KEY']);
        $format_keys = array_keys($format);
        $out_value = [];
        foreach ($format_keys as $format_key) {
            $out_value[$format_key] = $row[$format_key] ?? null;
        }
        if (!empty($blob_columns)) {
            $old_offset = 0;
            foreach ($blob_columns as $blob_column) {
                $blob = $out_value[$blob_column] ?? "";
                if (empty($blob)) {
                    $offset = $old_offset;
                    $len = 0;
                } else {
                    if (in_array($blob_column, $serial_columns)) {
                        $blob = serialize($blob);
                    }
                    if (($add_info = $this->addArchive($archive_filename,
                        $blob)) === false) {
                        return false;
                    }
                    list($offset, $len) = $add_info;
                }
                $out_value[$blob_column] = $offset - $old_offset;
                $old_offset = $offset;
            }
            $out_value["LAST_BLOB_LEN"] = $len;
        }
        $out_value = $this->table_tools->pack($out_value);
        return $out_value;
    }
    /**
     * Add a value to an archive file $archive_filename of a B+-tree node
     * @param string $archive_filename name of archive file
     * @param string $value value to add
     * @return array [offset into archive, length data saved]
     */
    protected function addArchive($archive_filename, $value)
    {
        list($fh, $previous_archive_filename,
            $previous_instance_time) =  $this->add_archive_cache;
        if (!$fh || $previous_archive_filename != $archive_filename ||
            $previous_instance_time != $this->instance_time) {
            if ($fh) {
                fclose($fh);
            }
            $fh = fopen($archive_filename , "c+");
            $previous_archive_filename = $archive_filename;
            $previous_instance_time = $this->instance_time;
        }
        $blob_compress_type = $this->parameters["BLOB_COMPRESSOR"];
        $blob_compressor = new $blob_compress_type();
        fseek($fh, 0, SEEK_END);
        $offset = ftell($fh);
        $compressed_value = $blob_compressor->compress($value);
        $len = strlen($compressed_value);
        $success = (fwrite($fh, $compressed_value, $len) !== false) ? true :
            false;
        $this->add_archive_cache = [$fh, $previous_archive_filename,
            $previous_instance_time];
        if (!$success) {
            return false;
        }
        return [$offset, $len];
    }
    /**
     * Returns the file path of the parent node of the current internal node
     *
     * @param string $folder path to internal BPlusTree node folder.
     *  (Internal nodes are folders, leaves are files)
     * @return string file_path to parent or false, if no parent.
     */
    public function getParentFolder($folder)
    {
        if (!($last_pos = strrpos($folder, "/"))) {
            return false;
        }
        return substr($folder, 0, $last_pos);
    }
    /**
     * Save the operating parameters of this BPlusTree
     */
    public function saveParameters()
    {
        $parameter_path = $this->folder . "/" . self::PARAMETERS_FILE;
        file_put_contents($parameter_path, serialize($this->parameters),
            LOCK_EX);
    }
    /**
     * Returns the parameters (such as its signature, max keys per nodes, etc)
     * used to configure the BPlusTree stored at $folder
     *
     * @param string $folder file path to a stored BPlusTree
     * @return array configuration info about the BPlusTree
     */
    public static function getParameterInfo($folder)
    {
        $parameter_path = $folder . "/" . self::PARAMETERS_FILE;
        if(file_exists($parameter_path)) {
            $parameters = unserialize(file_get_contents($parameter_path)) ?? [];
            if (!empty($parameters["COMPRESSOR"])) {
                //original format didn't distinguish between compressor use
                $parameters["NODE_COMPRESSOR"] ??= $parameters["COMPRESSOR"];
                $parameters["BLOB_COMPRESSOR"] ??= $parameters["COMPRESSOR"];
            }
            return $parameters;
        } else {
            return [];
        }
    }
}
