<?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
*
* This file contains unit tests of the LinearHashTable class
*
* @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\tests;
use seekquarry\yioop\configs as C;
use seekquarry\yioop\library as L;
use seekquarry\yioop\models\Model;
use seekquarry\yioop\library\UnitTest;
use seekquarry\yioop\library\data_structures as LDS;
/**
* Used to test that the LinearHashTable class properly stores key value pairs,
* handles insert, deletes, retrievals okay.
*
* @author Chris Pollett
*/
class LinearHashTableTest extends UnitTest
{
/**
* Prefix of folders for linear hashing test
*/
const TEST_DIR = '/test_files/linear_test';
/**
* Maintains all linear hash tables created for testing
* @var array
*/
public $table_dirs;
/**
* Sets up an array to keep track of what linear hash tables we've made
* so that we can delete them when done a test.
*/
public function setUp()
{
$this->table_dirs = [];
}
/**
* Used to create a single hash table in the folder
* TEST_DIR . $max_items_per_file which allows at most
* $max_items_per_file to be stored in a bucket
*
* @param int $max_items_per_file number of items allowed to be stored in a
* bucket
* @param array $format column definitions for the table; defaults to a
* string primary key and a BLOB value column
* @return LDS\LinearHashTable freshly-constructed table
* backed by the
* per-test directory
*/
public function createTable($max_items_per_file, $format =
["PRIMARY KEY" => "KEY", "VALUE" => "BLOB"])
{
$table_dir = __DIR__ . self::TEST_DIR . $max_items_per_file;
$this->table_dirs[] = $table_dir;
return new LDS\LinearHashTable(
$table_dir, $format, $max_items_per_file);
}
/**
* Deletes all the Linear Hash tables in $this->table_dirs
*/
public function tearDown()
{
$model = new Model();
foreach ($this->table_dirs as $table_dir) {
$model->db->unlinkRecursive($table_dir);
}
$this->table_dirs = [];
}
/**
* manyKeysReadEachBucketOnceTestCase puts sixty urls into a table of
* four records a bucket whose INDEX_CACHE_SIZE is four, so their
* records lie in about fifteen buckets, more than INDEX_CACHE_SIZE
* keeps. Looked up one at a time in the order they were put, the urls
* read bucket indexes from disk many times over; getMany, which orders
* them by bucket, reads each bucket's index at most once, and finds the
* same records.
*/
public function manyKeysReadEachBucketOnceTestCase()
{
$table_dir = __DIR__ . self::TEST_DIR . "many";
$this->table_dirs[] = $table_dir;
$hash_table = new class($table_dir, ["PRIMARY KEY" => "URL",
"ETAG" => "TEXT", "EXPIRES" => "INT"], 4) extends
LDS\LinearHashTable {
/**
* INDEX_CACHE_SIZE is the number of bucket indexes this table
* keeps in index_buffer, made small so a few urls fill it
*/
const INDEX_CACHE_SIZE = 4;
/**
* $index_reads counts the bucket indexes read from disk
* @var int
*/
public $index_reads = 0;
/**
* getIndexInfo counts a bucket index not already kept in
* index_buffer, then finds it as LinearHashTable does.
*
* @param string $hash_key hash of the key whose bucket is wanted
* @param int $count number of records the table is taken to hold
* @return array the bucket's path and its index
*/
protected function getIndexInfo($hash_key, $count = -1)
{
if ($hash_key != self::ACTIVE_INDEX) {
$path = $this->getHashPath($hash_key, ($count == -1) ?
$this->parameters['COUNT'] : $count);
if (empty($this->index_buffer[$path])) {
$this->index_reads++;
}
}
return parent::getIndexInfo($hash_key, $count);
}
};
$urls = [];
for ($i = 0; $i < 60; $i++) {
$urls[] = "https://www.site$i.com/";
$hash_table->put(["URL" => $urls[$i], "ETAG" => "tag$i",
"EXPIRES" => $i]);
}
$hash_table->index_buffer = [];
$hash_table->index_reads = 0;
$one_at_a_time = [];
foreach ($urls as $url) {
$one_at_a_time[$url] = $hash_table->get($url, ["ETAG"]);
}
$reads_one_at_a_time = $hash_table->index_reads;
$hash_table->index_buffer = [];
$hash_table->index_reads = 0;
$together = $hash_table->getMany($urls, ["ETAG"]);
$num_buckets = count(array_unique(array_map(fn($url) =>
$hash_table->getHashPath($hash_table->hashKey($url),
$hash_table->parameters['COUNT']), $urls)));
$this->assertTrue($hash_table->index_reads <= $num_buckets,
"getMany reads each of $num_buckets bucket indexes at most once");
$this->assertTrue($reads_one_at_a_time > $hash_table->index_reads,
"one at a time read $reads_one_at_a_time bucket indexes");
$same = 0;
foreach ($urls as $url) {
if (($together[$url]["ETAG"] ?? null) ==
($one_at_a_time[$url]["ETAG"] ?? false)) {
$same++;
}
}
$this->assertEqual($same, count($urls),
"getMany finds the same etag for every url");
}
/**
* getManySearchesBucketFilesTestCase checks that getMany finds records
* by searching each bucket index file as a string. It puts thirty
* urls, then looks up those and thirty urls never put. getMany
* must give the same records as get, leave out the urls never put, and
* leave index_buffer empty, since it searches bucket files as strings
* and does not keep them as arrays. It also checks that a record
* changed while its bucket is in
* index_buffer is found with its new value.
*/
public function getManySearchesBucketFilesTestCase()
{
$hash_table = $this->createTable(4, ["PRIMARY KEY" => "URL",
"ETAG" => "TEXT", "EXPIRES" => "INT"]);
$urls = [];
$missing = [];
for ($i = 0; $i < 30; $i++) {
$urls[] = "https://www.put$i.com/";
$missing[] = "https://www.never$i.com/";
$hash_table->put(["URL" => $urls[$i], "ETAG" => "tag$i",
"EXPIRES" => $i]);
}
$hash_table->index_buffer = [];
$found = $hash_table->getMany(array_merge($urls, $missing),
["ETAG", "EXPIRES"]);
$this->assertEqual(count($hash_table->index_buffer), 0,
"getMany turns no bucket index into an array");
$this->assertEqual(count($found), count($urls),
"getMany finds the urls put and none of the others");
$same = 0;
foreach ($urls as $url) {
if (($found[$url] ?? null) == $hash_table->get($url,
["ETAG", "EXPIRES"])) {
$same++;
}
}
$this->assertEqual($same, count($urls),
"getMany gives the same record as get for every url");
$hash_table->put(["URL" => $urls[7], "ETAG" => "changed",
"EXPIRES" => 7]);
$again = $hash_table->getMany([$urls[7]], ["ETAG"]);
$this->assertEqual($again[$urls[7]]["ETAG"] ?? "", "changed",
"getMany finds a record changed after the last lookup");
$hash_table->index_buffer = [];
$again = $hash_table->getMany([$urls[7]], ["ETAG"]);
$this->assertEqual($again[$urls[7]]["ETAG"] ?? "", "changed",
"the changed record is found in its bucket file too");
}
/**
* This tests that packed records can be successfully unpacked
* after being put into the linear hash table and retrieved.
* This tests the LinearHashTable use-case for storing ETag data
*/
public function packUnpackFormatTestCase()
{
$hash_table = $this->createTable(2,
["PRIMARY KEY" => "ID", "FNAME" => "TEXT",
"LNAME" => "TEXT", "BDATE" => "INT",
"META" => "SERIAL", "META2" => "BLOB"]);
$rows = [
["ID" => 10, "FNAME" => "Bob", "LNAME"=> "Smith",
"BDATE" => 5, "META" => "yo", "META2" => "no"],
["ID" => 20, "FNAME" => "Sally", "LNAME"=> "Salad",
"BDATE" => 4, "META" => "old", "META2" => "glow"],
["ID" => 30, "FNAME" => "Jojo", "LNAME"=> "yolo",
"BDATE" => 400, "META" => "dgdfld", "META2" => "low"]
];
foreach ($rows as $row) {
$hash_table->put($row);
}
$i = 0;
foreach ($rows as $row) {
$found_row = $hash_table->get($row['ID']);
foreach ($row as $field => $value) {
$found_value = $found_row[$field] ?? false;
$this->assertEqual($value, $found_value,
"row $i field $field test");
}
$i++;
}
$hash_table = $this->createTable(3, ["PRIMARY KEY" => "URL",
"ETAG" => "TEXT", "EXPIRES" => "INT"]);
$rows = [
["URL" => "https://somewhere.com/",
"ETAG" => "33a64df551425fcc55e4d42a148795d9f25f89d4",
"EXPIRES"=> time()],
["URL" => "https://nowhere.com/", "ETAG" => "686897696a7c876b7e",
"EXPIRES"=> time()+50],
];
foreach ($rows as $row) {
$hash_table->put($row);
}
foreach ($rows as $row) {
$found_row = $hash_table->get($row['URL']);
foreach ($row as $field => $value) {
$found_value = $found_row[$field] ?? false;
$this->assertEqual($value, $found_value,
"row $i field $field test");
}
$i++;
}
$row = ["URL" => "https://nowhere.com/",
"ETAG" => "e686897696a7c876b7", "EXPIRES"=> time()+60];
$hash_table->put($row);
$found_row = $hash_table->get($row['URL']);
foreach ($row as $field => $value) {
$found_value = $found_row[$field] ?? false;
$this->assertEqual($value, $found_value,
"insert_same_key row field $field test");
}
}
/**
* Tests whether key value pairs inserted into the linear hash table
* can subsequently be retrieved. This tests the hashed key case. It
* puts eighteen rows into tables of one, two, four, eight and sixteen
* records a bucket, so rows are moved from the active index into
* buckets that split, and, for sixteen, two rows stay in the active
* index.
*/
public function insertHashKeyLookupTestCase()
{
for ($i = 1; $i <= 16; $i *= 2) {
$hash_table = $this->createTable($i);
$insert_rows = [];
for ($j = 0; $j < 18; $j++) {
$insert_rows[] = ["KEY" => pack("J2", $j, 0),
"VALUE" => "test$i-$j"];
}
$hash_table->put($insert_rows, true);
for ($j = 0; $j < 18; $j++) {
$result = $hash_table->get(pack("J2", $j, 0), [], true);
$this->assertEqual("test$i-$j", $result["VALUE"],
"epoch $i put $j get $j test");
}
}
}
/**
* Tests whether key value pairs inserted into the linear hash table
* can subsequently be retrieved. This tests the non-hashed key case
* with forty rows in a table of four records a bucket.
*/
public function insertKeyLookupTestCase()
{
$hash_table = $this->createTable(4);
$insert_rows = [];
for ($j = 0; $j < 40; $j++) {
$insert_rows[] = ["KEY" => $j, "VALUE" =>"test-$j"];
}
$hash_table->put($insert_rows);
for ($j = 0; $j < 40; $j++) {
$result = $hash_table->get($j);
$this->assertEqual("test-$j", $result["VALUE"],
"put $j get $j test");
}
}
/**
* deleteHashKeyTestCase checks that key value pairs can be deleted
* from the linear hash table without destroying the data not deleted,
* for keys hashed beforehand. It puts twenty rows into tables of one,
* two, four, eight and sixteen records a bucket and deletes the middle
* ten, so rows are deleted from buckets that merge and, for sixteen,
* from the active index.
*/
public function deleteHashKeyTestCase()
{
for ($i = 1; $i <= 16; $i *= 2) {
$hash_table = $this->createTable($i);
$insert_rows = [];
for ($j = 0; $j < 20; $j++) {
$insert_rows[] = ["KEY" => pack("J2", $j, 0),
"VALUE" => "test$i-$j"];
}
$hash_table->put($insert_rows, true);
for ($j = 5; $j < 15; $j++) {
$hash_table->delete(pack("J2", $j, 0), true);
}
for ($j = 0; $j < 20; $j++) {
$result = $hash_table->get(pack("J2", $j, 0), [], true);
$value = $result["VALUE"] ?? false;
if ($j < 5 || $j >= 15) {
$this->assertEqual("test$i-$j", $value,
"epoch $i put $j get $j test");
} else {
$this->assertEqual(false, $value,
"epoch $i delete $j get false test");
}
}
}
}
/**
* deleteKeyTestCase checks that key value pairs can be deleted from
* the linear hash table without destroying the data not deleted, for
* keys that are not hashed beforehand. It puts forty rows into a table
* of four records a bucket and deletes the middle twenty.
*/
public function deleteKeyTestCase()
{
$hash_file = $this->createTable(4);
$insert_rows = [];
for ($j = 0; $j < 40; $j++) {
$insert_rows[] = ["KEY" => $j, "VALUE" => "test-$j"];
}
$hash_file->put($insert_rows);
$deletes = [];
for ($j = 10; $j < 30; $j++) {
$deletes[] = $j;
}
$hash_file->delete($deletes);
for ($j = 0; $j < 40; $j++) {
$result = $hash_file->get($j);
$value = $result["VALUE"] ?? false;
if ($j < 10 || $j >= 30) {
$this->assertEqual("test-$j", $value, "put $j get $j test");
} else {
$this->assertEqual(false, $value, "delete $j get false test");
}
}
}
}
- Yioop Repo - Seekquarry