I asked ChatGPT to “Write pascal code to manage a sorted symbol table using two tables the main table and a secondary table, when the secondary table becomes more then 10% of the main table do a merge sort into the main table”
This is something I wrote back in the late eighties, and aside from a few syntax errors which ChatGPT corrected when asked it compiled and ran perfectly
Update, C++ edition, ChatGPT continues to improve
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <string_view>
#include <cstring>
#include <algorithm>
#include <fcntl.h>
#include <unistd.h>
#include <sys/mman.h>
#include <sys/stat.h>
constexpr const char* FILE_NAME = "symbols.mmap";
constexpr size_t MAX_SYMBOLS = 1'000'000;
constexpr size_t KEY_SIZE = 30;
constexpr size_t VALUE_SIZE = 100;
#pragma pack(push, 1)
struct Symbol {
char key[KEY_SIZE + 1]{};
char value[VALUE_SIZE + 1]{};
bool deleted{false};
std::string_view get_key() const { return std::string_view(key, strnlen(key, KEY_SIZE)); }
std::string_view get_value() const { return std::string_view(value, strnlen(value, VALUE_SIZE)); }
bool operator<(const Symbol& other) const {
return get_key() < other.get_key();
}
};
struct SymbolHeader {
int64_t main_count = 0;
int64_t secondary_count = 0;
};
#pragma pack(pop)
struct MMapSymbolTable {
int fd = -1;
size_t map_size = 0;
void* file_ptr = nullptr;
SymbolHeader* header = nullptr;
Symbol* records = nullptr;
void ensure_file_size(const char* filename, size_t size) {
std::fstream file(filename, std::ios::in | std::ios::out | std::ios::binary);
if (!file) {
file.open(filename, std::ios::out | std::ios::binary);
file.close();
file.open(filename, std::ios::in | std::ios::out | std::ios::binary);
}
file.seekp(size - 1);
file.write("", 1);
file.close();
}
void open() {
map_size = sizeof(SymbolHeader) + sizeof(Symbol) * MAX_SYMBOLS;
ensure_file_size(FILE_NAME, map_size);
fd = ::open(FILE_NAME, O_RDWR);
if (fd == -1) throw std::runtime_error("Failed to open file");
file_ptr = mmap(nullptr, map_size, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
if (file_ptr == MAP_FAILED) throw std::runtime_error("mmap failed");
header = static_cast<SymbolHeader*>(file_ptr);
records = reinterpret_cast<Symbol*>(static_cast<char*>(file_ptr) + sizeof(SymbolHeader));
if (header->main_count == 0 && header->secondary_count == 0) {
header->main_count = 0;
header->secondary_count = 0;
}
}
void close() {
munmap(file_ptr, map_size);
::close(fd);
}
void insert_sorted_secondary(std::string_view key, std::string_view value) {
int64_t total = header->main_count + header->secondary_count;
if (total >= MAX_SYMBOLS) {
std::cerr << "Table full\n";
return;
}
Symbol new_sym{};
std::strncpy(new_sym.key, key.data(), KEY_SIZE);
std::strncpy(new_sym.value, value.data(), VALUE_SIZE);
new_sym.deleted = false;
int64_t sec_start = header->main_count;
int64_t sec_end = sec_start + header->secondary_count;
int64_t insert_pos = sec_end;
for (int64_t i = sec_start; i < sec_end; ++i) {
if (std::string_view(records[i].key) > key) {
insert_pos = i;
break;
}
}
for (int64_t i = sec_end - 1; i >= insert_pos; --i)
records[i + 1] = records[i];
records[insert_pos] = new_sym;
++header->secondary_count;
if (header->secondary_count > 1000 &&
header->main_count > 0 &&
header->secondary_count * 100 > header->main_count * 5) {
std::cout << "Auto-merging: secondary is greater than 1000 and more than 5% of main\n";
merge();
}
}
void print() const {
std::cout << "--- Main Region (Sorted) ---\n";
for (int64_t i = 0; i < header->main_count; ++i)
if (!records[i].deleted)
std::cout << i << ": " << records[i].get_key() << " -> " << records[i].get_value() << '\n';
std::cout << "--- Secondary Region (Sorted) ---\n";
for (int64_t i = header->main_count; i < header->main_count + header->secondary_count; ++i)
if (!records[i].deleted)
std::cout << i << ": " << records[i].get_key() << " -> " << records[i].get_value() << '\n';
}
void merge() {
std::vector<Symbol> all;
for (int64_t i = 0; i < header->main_count + header->secondary_count; ++i)
if (!records[i].deleted)
all.push_back(records[i]);
std::ranges::sort(all);
for (size_t i = 0; i < all.size(); ++i)
records[i] = all[i];
for (int64_t i = all.size(); i < header->main_count + header->secondary_count; ++i)
records[i].deleted = true;
header->main_count = all.size();
header->secondary_count = 0;
std::cout << "Merge complete. MainCount = " << header->main_count << '\n';
}
void delete_symbol(std::string_view key) {
int64_t total = header->main_count + header->secondary_count;
for (int64_t i = 0; i < total; ++i) {
if (!records[i].deleted && key == records[i].get_key()) {
records[i].deleted = true;
std::cout << "Deleted: " << key << '\n';
return;
}
}
std::cout << "Not found: " << key << '\n';
}
void search_symbol(std::string_view key) const {
auto binary_search_region = [&](int64_t start, int64_t end, const char* label) {
int64_t L = start, R = end - 1;
while (L <= R) {
int64_t M = (L + R) / 2;
if (records[M].deleted) {
--R;
continue;
}
std::string_view k = records[M].get_key();
if (k == key) {
std::cout << "[" << label << "] Found: " << k << " -> " << records[M].get_value() << '\n';
return true;
} else if (k < key) {
L = M + 1;
} else {
R = M - 1;
}
}
return false;
};
if (!binary_search_region(0, header->main_count, "MAIN"))
if (!binary_search_region(header->main_count, header->main_count + header->secondary_count, "SECONDARY"))
std::cout << "Not found: " << key << '\n';
}
void demo() {
insert_sorted_secondary("KeyM", "ValueM");
insert_sorted_secondary("KeyB", "ValueB");
insert_sorted_secondary("KeyD", "ValueD");
insert_sorted_secondary("KeyE", "ValueE");
insert_sorted_secondary("KeyF", "ValueF");
insert_sorted_secondary("KeyG", "ValueG");
insert_sorted_secondary("KeyH", "ValueH");
insert_sorted_secondary("KeyI", "ValueI");
insert_sorted_secondary("KeyJ", "ValueJ");
insert_sorted_secondary("KeyK", "ValueK");
insert_sorted_secondary("KeyA", "ValueA");
insert_sorted_secondary("KeyZ", "ValueZ");
insert_sorted_secondary("KeyC", "ValueC");
std::cout << '\n';
print();
std::cout << '\n';
merge();
print();
std::cout << '\n';
search_symbol("KeyM");
delete_symbol("KeyM");
std::cout << '\n';
print();
}
};
int main() {
try {
MMapSymbolTable table;
table.open();
table.demo();
table.close();
} catch (const std::exception& ex) {
std::cerr << "Fatal error: " << ex.what() << '\n';
return 1;
}
}
Update, now in a Modula-3 version (assumes external MMAP interface, coded in C)
MODULE MMapSymbolTable;
IMPORT IO, Text, Fmt, MMapC, Ctypes, Process;
CONST
FileName = "symbols.mmap";
MaxSymbols = 1000000;
TYPE
Symbol = RECORD
key: ARRAY [0..29] OF CHAR;
value: ARRAY [0..99] OF CHAR;
deleted: BOOLEAN;
END;
SymbolHeader = RECORD
mainCount: INTEGER;
secondaryCount: INTEGER;
END;
VAR
fd: INTEGER;
mapPtr: Ctypes.void_star;
mapSize: INTEGER;
header: UNTRACED REF SymbolHeader;
records: UNTRACED REF ARRAY OF Symbol;
PROCEDURE CString(s: TEXT): ARRAY OF CHAR =
VAR a: ARRAY [0..255] OF CHAR; i := 0;
BEGIN
WHILE i < Text.Length(s) AND i < NUMBER(a) - 1 DO
a[i] := Text.GetChar(s, i);
INC(i);
END;
a[i] := '\000';
RETURN a;
END CString;
PROCEDURE ToText(ch: ARRAY OF CHAR): TEXT =
VAR len := 0;
BEGIN
WHILE len < NUMBER(ch) AND ch[len] # '\000' DO
INC(len);
END;
RETURN Text.FromChars(SUBARRAY(ch, 0, len));
END ToText;
PROCEDURE CopyTo(dest: ARRAY OF CHAR; src: TEXT) =
VAR i := 0;
BEGIN
WHILE i < Text.Length(src) AND i < NUMBER(dest) - 1 DO
dest[i] := Text.GetChar(src, i);
INC(i);
END;
dest[i] := '\000';
END CopyTo;
PROCEDURE MMapFile =
VAR cfilename := CString(FileName);
BEGIN
mapSize := BYTESIZE(SymbolHeader) + MaxSymbols * BYTESIZE(Symbol);
fd := MMapC.open(ADR(cfilename[0]), 2 (* O_RDWR *), 0);
IF fd < 0 THEN
IO.Put("Failed to open file\n");
Process.Exit(1);
END;
mapPtr := MMapC.mmap(NIL, mapSize, MMapC.PROT_READ + MMapC.PROT_WRITE,
MMapC.MAP_SHARED, fd, 0);
IF mapPtr = NIL THEN
IO.Put("mmap failed\n");
Process.Exit(2);
END;
header := LOOPHOLE(mapPtr, UNTRACED REF SymbolHeader);
records := LOOPHOLE(LOOPHOLE(mapPtr, ADDRESS) + BYTESIZE(SymbolHeader),
UNTRACED REF ARRAY OF Symbol);
IF header.mainCount = 0 AND header.secondaryCount = 0 THEN
header.mainCount := 0;
header.secondaryCount := 0;
END;
END MMapFile;
PROCEDURE UnmapAndClose =
BEGIN
MMapC.munmap(mapPtr, mapSize);
MMapC.close(fd);
END UnmapAndClose;
PROCEDURE InsertSortedIntoSecondary(key, value: TEXT) =
VAR i, insertPos, secStart, secEnd, totalCount: INTEGER;
newSym: Symbol;
BEGIN
totalCount := header.mainCount + header.secondaryCount;
IF totalCount >= MaxSymbols THEN
IO.Put("Table full\n");
RETURN;
END;
CopyTo(newSym.key, key);
CopyTo(newSym.value, value);
newSym.deleted := FALSE;
secStart := header.mainCount;
secEnd := secStart + header.secondaryCount;
insertPos := secEnd;
FOR i := secStart TO secEnd - 1 DO
IF Text.Compare(ToText(records[i].key), key) > 0 THEN
insertPos := i;
EXIT;
END;
END;
FOR i := secEnd - 1 TO insertPos BY -1 DO
records[i + 1] := records[i];
END;
records[insertPos] := newSym;
INC(header.secondaryCount);
IF (header.secondaryCount > 1000) AND (header.mainCount > 0)
AND (header.secondaryCount * 100 > header.mainCount * 5) THEN
IO.Put("Auto-merging: secondary > 1000 and > 5% of main\n");
Merge;
END;
END InsertSortedIntoSecondary;
PROCEDURE PrintTable =
VAR i: INTEGER;
BEGIN
IO.Put("\n--- Main Region (Sorted) ---\n");
FOR i := 0 TO header.mainCount - 1 DO
IF NOT records[i].deleted THEN
IO.Put(Fmt.Int(i) & ": " & ToText(records[i].key) & " -> " & ToText(records[i].value) & "\n");
END;
END;
IO.Put("--- Secondary Region (Sorted) ---\n");
FOR i := header.mainCount TO header.mainCount + header.secondaryCount - 1 DO
IF NOT records[i].deleted THEN
IO.Put(Fmt.Int(i) & ": " & ToText(records[i].key) & " -> " & ToText(records[i].value) & "\n");
END;
END;
END PrintTable;
PROCEDURE Merge =
VAR
temp: Symbol;
all: REF ARRAY OF Symbol;
i, j, count := 0;
BEGIN
NEW(all, header.mainCount + header.secondaryCount);
FOR i := 0 TO header.mainCount + header.secondaryCount - 1 DO
IF NOT records[i].deleted THEN
all[count] := records[i];
INC(count);
END;
END;
FOR i := 1 TO count - 1 DO
temp := all[i];
j := i - 1;
WHILE j >= 0 AND Text.Compare(ToText(all[j].key), ToText(temp.key)) > 0 DO
all[j + 1] := all[j];
DEC(j);
END;
all[j + 1] := temp;
END;
FOR i := 0 TO count - 1 DO
records[i] := all[i];
END;
FOR i := count TO header.mainCount + header.secondaryCount - 1 DO
records[i].deleted := TRUE;
records[i].key[0] := '\000';
records[i].value[0] := '\000';
END;
header.mainCount := count;
header.secondaryCount := 0;
IO.Put("Merge complete. MainCount = " & Fmt.Int(header.mainCount) & "\n");
END Merge;
PROCEDURE DeleteSymbol(key: TEXT) =
VAR i, total: INTEGER;
BEGIN
total := header.mainCount + header.secondaryCount;
FOR i := 0 TO total - 1 DO
IF (NOT records[i].deleted) AND Text.Equal(ToText(records[i].key), key) THEN
records[i].deleted := TRUE;
IO.Put("Deleted: " & key & "\n");
RETURN;
END;
END;
IO.Put("Not found: " & key & "\n");
END DeleteSymbol;
PROCEDURE SearchSymbol(key: TEXT) =
VAR L, R, M: INTEGER;
BEGIN
L := 0;
R := header.mainCount - 1;
WHILE L <= R DO
M := (L + R) DIV 2;
IF records[M].deleted THEN
R := M - 1;
ELSIF Text.Equal(ToText(records[M].key), key) THEN
IO.Put("[MAIN] Found: " & ToText(records[M].key) & " -> " & ToText(records[M].value) & "\n");
RETURN;
ELSIF Text.Compare(ToText(records[M].key), key) < 0 THEN
L := M + 1;
ELSE
R := M - 1;
END;
END;
L := header.mainCount;
R := header.mainCount + header.secondaryCount - 1;
WHILE L <= R DO
M := (L + R) DIV 2;
IF records[M].deleted THEN
R := M - 1;
ELSIF Text.Equal(ToText(records[M].key), key) THEN
IO.Put("[SECONDARY] Found: " & ToText(records[M].key) & " -> " & ToText(records[M].value) & "\n");
RETURN;
ELSIF Text.Compare(ToText(records[M].key), key) < 0 THEN
L := M + 1;
ELSE
R := M - 1;
END;
END;
IO.Put("Not found: " & key & "\n");
END SearchSymbol;
PROCEDURE Demo =
BEGIN
InsertSortedIntoSecondary("KeyM", "ValueM");
InsertSortedIntoSecondary("KeyB", "ValueB");
InsertSortedIntoSecondary("KeyD", "ValueD");
InsertSortedIntoSecondary("KeyE", "ValueE");
InsertSortedIntoSecondary("KeyF", "ValueF");
InsertSortedIntoSecondary("KeyG", "ValueG");
InsertSortedIntoSecondary("KeyH", "ValueH");
InsertSortedIntoSecondary("KeyI", "ValueI");
InsertSortedIntoSecondary("KeyJ", "ValueJ");
InsertSortedIntoSecondary("KeyK", "ValueK");
InsertSortedIntoSecondary("KeyA", "ValueA");
InsertSortedIntoSecondary("KeyZ", "ValueZ");
InsertSortedIntoSecondary("KeyC", "ValueC");
PrintTable;
Merge;
PrintTable;
SearchSymbol("KeyM");
DeleteSymbol("KeyM");
PrintTable;
END Demo;
BEGIN
MMapFile;
Demo;
UnmapAndClose;
END MMapSymbolTable.
program SymbolTableManager;
uses
SysUtils;
const
MaxSize = 1000;
type
Symbol = record
Key: string[30];
Value: string[100];
end;
SymbolTable = record
Data: array[1..MaxSize] of Symbol;
Count: Integer;
end;
var
MainTable, SecondaryTable: SymbolTable;
procedure InitTable(var Table: SymbolTable);
begin
Table.Count := 0;
end;
function CompareSymbols(const A, B: Symbol): Integer;
begin
if A.Key < B.Key then
CompareSymbols := -1
else if A.Key > B.Key then
CompareSymbols := 1
else
CompareSymbols := 0;
end;
procedure AddToSecondaryTableSorted(Key, Value: string);
var
i, pos: Integer;
NewSymbol: Symbol;
begin
if SecondaryTable.Count >= MaxSize then
begin
writeln('Secondary Table is full!');
Exit;
end;
// Create the new symbol
NewSymbol.Key := Key;
NewSymbol.Value := Value;
// Find insertion position
pos := SecondaryTable.Count + 1;
for i := SecondaryTable.Count downto 1 do
begin
if CompareSymbols(SecondaryTable.Data[i], NewSymbol) > 0 then
begin
SecondaryTable.Data[i + 1] := SecondaryTable.Data[i]; // shift right
pos := i;
end
else
Break;
end;
// Insert the new symbol
SecondaryTable.Data[pos] := NewSymbol;
Inc(SecondaryTable.Count);
end;
procedure MergeTables;
var
TempTable: SymbolTable;
i, j, k: Integer;
begin
writeln('Merging tables...');
i := 1;
j := 1;
k := 0;
while (i <= MainTable.Count) and (j <= SecondaryTable.Count) do
begin
if CompareSymbols(MainTable.Data[i], SecondaryTable.Data[j]) <= 0 then
begin
Inc(k);
TempTable.Data[k] := MainTable.Data[i];
Inc(i);
end
else
begin
Inc(k);
TempTable.Data[k] := SecondaryTable.Data[j];
Inc(j);
end;
end;
while i <= MainTable.Count do
begin
Inc(k);
TempTable.Data[k] := MainTable.Data[i];
Inc(i);
end;
while j <= SecondaryTable.Count do
begin
Inc(k);
TempTable.Data[k] := SecondaryTable.Data[j];
Inc(j);
end;
TempTable.Count := k;
MainTable := TempTable;
InitTable(SecondaryTable);
end;
procedure InsertSymbol(Key, Value: string);
begin
AddToSecondaryTableSorted(Key, Value);
if MainTable.Count = 0 then
Exit;
if SecondaryTable.Count > (MainTable.Count div 10) then
MergeTables;
end;
procedure PrintTable(const Table: SymbolTable; const LabelText: string);
var
i: Integer;
begin
writeln(LabelText);
for i := 1 to Table.Count do
writeln(i:3, ': ', Table.Data[i].Key, ' -> ', Table.Data[i].Value);
end;
procedure QuickSort(var A: array of Symbol; L, R: Integer);
var
i, j: Integer;
pivot, tmp: Symbol;
begin
i := L;
j := R;
pivot := A[(L + R) div 2];
repeat
while CompareSymbols(A[i], pivot) < 0 do Inc(i);
while CompareSymbols(A[j], pivot) > 0 do Dec(j);
if i <= j then
begin
tmp := A[i];
A[i] := A[j];
A[j] := tmp;
Inc(i);
Dec(j);
end;
until i > j;
if L < j then QuickSort(A, L, j);
if i < R then QuickSort(A, i, R);
end;
procedure PreloadMainTable;
var
i: Integer;
begin
for i := 1 to 20 do
begin
Inc(MainTable.Count);
with MainTable.Data[MainTable.Count] do
begin
Key := 'Key' + Chr(64 + i); // KeyA, KeyB, ...
Value := 'Value' + IntToStr(i);
end;
end;
QuickSort(MainTable.Data, 1, MainTable.Count);
end;
begin
InitTable(MainTable);
InitTable(SecondaryTable);
PreloadMainTable;
writeln('Initial Main Table:');
PrintTable(MainTable, 'Main Table:');
// Insert symbols to Secondary Table
InsertSymbol('KeyM', 'ExtraM');
InsertSymbol('KeyZ', 'ExtraZ');
InsertSymbol('KeyA', 'ExtraA');
InsertSymbol('KeyC', 'ExtraC');
InsertSymbol('KeyY', 'ExtraY');
InsertSymbol('KeyG', 'ExtraG');
InsertSymbol('KeyX', 'ExtraX');
InsertSymbol('KeyH', 'ExtraH');
InsertSymbol('KeyW', 'ExtraW');
InsertSymbol('KeyE', 'ExtraE');
InsertSymbol('KeyT', 'ExtraT'); // Should trigger merge
writeln;
PrintTable(MainTable, 'Main Table After Merge:');
end.
After some more prompting we have a program that uses a memory mapped file and supports up to 1 million records in the symbol table.
program MMapSymbolTable;
uses
BaseUnix, SysUtils;
const
FileName = 'symbols.mmap';
MaxSymbols = 1000000;
type
Symbol = packed record
Key: string[30];
Value: string[100];
Deleted: Boolean;
end;
PSymbol = ^Symbol;
SymbolHeader = packed record
MainCount: Int64;
SecondaryCount: Int64;
end;
PSymbolHeader = ^SymbolHeader;
procedure Merge; forward;
var
fd: cint;
MapSize: cint;
FilePtr: Pointer;
Header: PSymbolHeader;
Records: PSymbol;
procedure EnsureFileSize(Filename: string; Size: cint);
var
f: file;
Dummy: Byte = 0;
begin
Assign(f, Filename);
{$I-} Reset(f, 1); {$I+}
if IOResult <> 0 then Rewrite(f, 1);
Seek(f, Size - 1);
BlockWrite(f, Dummy, 1);
Close(f);
end;
procedure MMapFile;
begin
MapSize := SizeOf(SymbolHeader) + SizeOf(Symbol) * MaxSymbols;
EnsureFileSize(FileName, MapSize);
fd := fpopen(FileName, O_RDWR);
if fd = -1 then
begin writeln('Failed to open file'); Halt(1); end;
FilePtr := fpmmap(nil, MapSize, PROT_READ or PROT_WRITE, MAP_SHARED, fd, 0);
if PtrUInt(FilePtr) = PtrUInt(MAP_FAILED) then
begin writeln('mmap failed'); Halt(2); end;
Header := PSymbolHeader(FilePtr);
Records := PSymbol(Pointer(PChar(FilePtr) + SizeOf(SymbolHeader)));
if (Header^.MainCount = 0) and (Header^.SecondaryCount = 0) then
begin
Header^.MainCount := 0;
Header^.SecondaryCount := 0;
end;
end;
procedure UnmapAndClose;
begin
fpmunmap(FilePtr, MapSize);
fpclose(fd);
end;
procedure InsertSortedIntoSecondary(Key, Value: string);
var
i, insertPos, secStart, secEnd: Int64;
totalCount: Int64;
NewSym: Symbol;
begin
totalCount := Header^.MainCount + Header^.SecondaryCount;
if totalCount >= MaxSymbols then
begin writeln('Table full'); Exit; end;
NewSym.Key := Key;
NewSym.Value := Value;
NewSym.Deleted := False;
secStart := Header^.MainCount;
secEnd := secStart + Header^.SecondaryCount;
// Find insert position in secondary
insertPos := secEnd;
for i := secStart to secEnd - 1 do
begin
if Records[i].Key > Key then
begin
insertPos := i;
Break;
end;
end;
// Shift everything from insertPos to end of secondary forward
for i := secEnd - 1 downto insertPos do
Records[i + 1] := Records[i];
// Insert new record
Records[insertPos] := NewSym;
Inc(Header^.SecondaryCount);
// Auto-merge if secondary > 5% of main
if (Header^.SecondaryCount > 1000) and (Header^.MainCount > 0) and (Header^.SecondaryCount * 100 > Header^.MainCount * 5) then
begin
writeln('Auto-merging: secondary is greater than 1000 and more than 5% of main');
Merge;
Merge;
end;
end;
procedure PrintTable;
var
i: Integer;
begin
writeln('--- Main Region (Sorted) ---');
for i := 0 to Header^.MainCount - 1 do
if not Records[i].Deleted then
writeln(i:3, ': ', Records[i].Key, ' -> ', Records[i].Value);
writeln('--- Secondary Region (Sorted) ---');
for i := Header^.MainCount to Header^.MainCount + Header^.SecondaryCount - 1 do
if not Records[i].Deleted then
writeln(i:3, ': ', Records[i].Key, ' -> ', Records[i].Value);
end;
procedure Merge;
var
All: array of Symbol;
Count, i, j: NativeInt;
temp: Symbol;
begin
Count := 0;
SetLength(All, 0);
for i := 0 to Header^.MainCount + Header^.SecondaryCount - 1 do
if not Records[i].Deleted then
begin
SetLength(All, Length(All) + 1);
All[High(All)] := Records[i];
end;
Count := Length(All);
SetLength(All, Count);
for i := 1 to Count - 1 do
begin
temp := All[i];
j := i - 1;
while (j >= 0) and (All[j].Key > temp.Key) do
begin
All[j + 1] := All[j];
Dec(j);
end;
All[j + 1] := temp;
end;
for i := 0 to Count - 1 do
Records[i] := All[i];
for i := Count to Header^.MainCount + Header^.SecondaryCount - 1 do
begin
Records[i].Key := '';
Records[i].Value := '';
Records[i].Deleted := True;
end;
Header^.MainCount := Count;
Header^.SecondaryCount := 0;
writeln('Merge complete. MainCount = ', Header^.MainCount);
end;
procedure DeleteSymbol(Key: string);
var
i, total: Int64;
begin
total := Header^.MainCount + Header^.SecondaryCount;
for i := 0 to total - 1 do
if (Records[i].Key = Key) and (not Records[i].Deleted) then
begin
Records[i].Deleted := True;
writeln('Deleted: ', Key);
Exit;
end;
writeln('Not found: ', Key);
end;
procedure SearchSymbol(Key: string);
var
L, R, M: Int64;
begin
// Search Main Region
L := 0;
R := Header^.MainCount - 1;
while L <= R do
begin
M := (L + R) div 2;
if Records[M].Deleted then begin R := M - 1; Continue; end;
if Records[M].Key = Key then
begin writeln('[MAIN] Found: ', Records[M].Key, ' -> ', Records[M].Value); Exit; end
else if Records[M].Key < Key then
L := M + 1
else
R := M - 1;
end;
// Search Secondary Region
L := Header^.MainCount;
R := Header^.MainCount + Header^.SecondaryCount - 1;
while L <= R do
begin
M := (L + R) div 2;
if Records[M].Deleted then begin R := M - 1; Continue; end;
if Records[M].Key = Key then
begin writeln('[SECONDARY] Found: ', Records[M].Key, ' -> ', Records[M].Value); Exit; end
else if Records[M].Key < Key then
L := M + 1
else
R := M - 1;
end;
writeln('Not found: ', Key);
end;
procedure Demo;
begin
InsertSortedIntoSecondary('KeyM', 'ValueM');
InsertSortedIntoSecondary('KeyB', 'ValueB');
InsertSortedIntoSecondary('KeyD', 'ValueD');
InsertSortedIntoSecondary('KeyE', 'ValueE');
InsertSortedIntoSecondary('KeyF', 'ValueF');
InsertSortedIntoSecondary('KeyG', 'ValueG');
InsertSortedIntoSecondary('KeyH', 'ValueH');
InsertSortedIntoSecondary('KeyI', 'ValueI');
InsertSortedIntoSecondary('KeyJ', 'ValueJ');
InsertSortedIntoSecondary('KeyK', 'ValueK');
InsertSortedIntoSecondary('KeyA', 'ValueA');
InsertSortedIntoSecondary('KeyZ', 'ValueZ');
InsertSortedIntoSecondary('KeyC', 'ValueC');
writeln;
PrintTable;
writeln;
Merge;
PrintTable;
writeln;
SearchSymbol('KeyM');
DeleteSymbol('KeyM');
writeln;
PrintTable;
end;
begin
MMapFile;
Demo;
UnmapAndClose;
end.