Case Study 2: Designing a Reusable Library

Overview

In this case study, we design and build a reusable Pascal library from scratch — a Collections library providing generic-style data structures (a dynamic list, a stack, a queue, and a dictionary) that can be used across multiple projects. The focus is on API design, documentation, initialization/finalization, and the decisions that make a library genuinely reusable rather than merely extracted from a single project.

The Goal

We want a library that provides:

1. TDynList — A dynamic list of pointers with automatic resizing, iteration, sorting, and searching
2. TDynStack — A LIFO stack built on TDynList
3. TDynQueue — A FIFO queue with a circular buffer implementation
4. TSimpleDict — A string-to-pointer dictionary using a hash table

The library should be usable by any Pascal program with a single uses Collections; statement.

Design Decisions

Decision 1: One Unit or Many?

We could put everything in a single Collections unit or split into CollectionList, CollectionStack, CollectionQueue, CollectionDict.

We choose one unit for this library because: - The data structures are closely related (high cohesion) - Users typically want several of them together - Four tiny units would add friction without much benefit - The total code is under 800 lines — well within the manageable range for a single unit

If the library grew beyond ~1,500 lines or if users frequently needed only one data structure, splitting would become the better choice.

Decision 2: Interface Granularity

We export only the types and their methods. Internal helpers (hash functions, buffer management) stay in the implementation. The goal: a user should be able to read the interface section and know everything they need to use the library.

Decision 3: Error Handling Strategy

The library raises exceptions for programmer errors (popping an empty stack, accessing an invalid index) and returns sentinel values for "not found" conditions (dictionary lookup returns nil if the key does not exist). This is consistent with Free Pascal's standard library conventions.

Decision 4: Memory Ownership

The library manages the memory for its own data structures (internal arrays, hash buckets). The user is responsible for managing the memory of the items stored in the collections (the pointers). The library never frees user data unless explicitly asked to.

The Interface

unit Collections;

{$mode objfpc}{$H+}

interface

uses
  Classes, SysUtils;

type
  TCompareFunc = function(A, B: Pointer): Integer;

  { === Dynamic List === }
  TDynList = class
  private
    FItems: array of Pointer;
    FCount: Integer;
    FCapacity: Integer;
    procedure Grow;
  public
    constructor Create(InitialCapacity: Integer = 16);
    destructor Destroy; override;
    procedure Add(Item: Pointer);
    procedure Insert(Index: Integer; Item: Pointer);
    procedure Delete(Index: Integer);
    procedure Clear;
    function Get(Index: Integer): Pointer;
    function IndexOf(Item: Pointer): Integer;
    function Contains(Item: Pointer): Boolean;
    procedure Sort(CompareFunc: TCompareFunc);
    property Count: Integer read FCount;
    property Items[Index: Integer]: Pointer read Get; default;
  end;

  { === Stack (LIFO) === }
  TDynStack = class
  private
    FList: TDynList;
  public
    constructor Create;
    destructor Destroy; override;
    procedure Push(Item: Pointer);
    function Pop: Pointer;
    function Peek: Pointer;
    function IsEmpty: Boolean;
    property Count: Integer read FList.FCount;
  end;

  { === Queue (FIFO) === }
  TDynQueue = class
  private
    FBuffer: array of Pointer;
    FHead: Integer;
    FTail: Integer;
    FCount: Integer;
    FCapacity: Integer;
    procedure Grow;
  public
    constructor Create(InitialCapacity: Integer = 16);
    destructor Destroy; override;
    procedure Enqueue(Item: Pointer);
    function Dequeue: Pointer;
    function Peek: Pointer;
    function IsEmpty: Boolean;
    property Count: Integer read FCount;
  end;

  { === Dictionary (string -> pointer) === }
  TDictEntry = record
    Key: string;
    Value: Pointer;
    Used: Boolean;
  end;

  TSimpleDict = class
  private
    FBuckets: array of TDictEntry;
    FCount: Integer;
    FCapacity: Integer;
    function HashKey(const Key: string): Cardinal;
    function FindSlot(const Key: string): Integer;
    procedure Rehash;
  public
    constructor Create(InitialCapacity: Integer = 64);
    destructor Destroy; override;
    procedure Put(const Key: string; Value: Pointer);
    function Get(const Key: string): Pointer;
    function ContainsKey(const Key: string): Boolean;
    procedure Remove(const Key: string);
    procedure Clear;
    property Count: Integer read FCount;
  end;

var
  CollectionsVersion: string;

implementation

Notice how the interface tells the complete story: what each class does, what methods it offers, what parameters each method takes. A user reading this interface knows everything needed to use the library without reading a single line of implementation code.

Implementation Highlights

Dynamic List Growth Strategy

The list uses a doubling strategy for resizing — when the array is full, we allocate twice the current capacity:

procedure TDynList.Grow;
begin
  if FCapacity = 0 then
    FCapacity := 16
  else
    FCapacity := FCapacity * 2;
  SetLength(FItems, FCapacity);
end;

procedure TDynList.Add(Item: Pointer);
begin
  if FCount >= FCapacity then
    Grow;
  FItems[FCount] := Item;
  Inc(FCount);
end;

This gives amortized O(1) insertion — most additions are a simple array write, and the occasional resize (which copies the array) is rare enough that the average cost stays constant.

Dictionary Hash Function

We use the djb2 hash function — simple, fast, and well-distributed for string keys:

function TSimpleDict.HashKey(const Key: string): Cardinal;
var
  I: Integer;
begin
  Result := 5381;
  for I := 1 to Length(Key) do
    Result := ((Result shl 5) + Result) + Ord(Key[I]);
end;

Collision resolution uses linear probing: if a slot is occupied, try the next one. When the load factor exceeds 70%, we rehash into a larger table.

Initialization Section

initialization
  CollectionsVersion := '1.0.0';

finalization
  { Nothing to clean up — instances are managed by their owners }
end.

The initialization is minimal — just setting the version string. This follows our principle: keep initialization light.

Using the Library

program TestCollections;

{$mode objfpc}{$H+}

uses
  SysUtils, Collections;

type
  PStudent = ^TStudent;
  TStudent = record
    Name: string;
    GPA: Real;
  end;

function CompareByGPA(A, B: Pointer): Integer;
begin
  if PStudent(A)^.GPA < PStudent(B)^.GPA then Result := -1
  else if PStudent(A)^.GPA > PStudent(B)^.GPA then Result := 1
  else Result := 0;
end;

var
  Students: TDynList;
  Lookup: TSimpleDict;
  S: PStudent;
  I: Integer;
begin
  Students := TDynList.Create;
  Lookup := TSimpleDict.Create;
  try
    { Add students }
    New(S); S^.Name := 'Alice'; S^.GPA := 3.8;
    Students.Add(S); Lookup.Put('A001', S);

    New(S); S^.Name := 'Bob'; S^.GPA := 3.2;
    Students.Add(S); Lookup.Put('A002', S);

    New(S); S^.Name := 'Carol'; S^.GPA := 3.9;
    Students.Add(S); Lookup.Put('A003', S);

    { Sort by GPA }
    Students.Sort(@CompareByGPA);

    { Display sorted list }
    for I := 0 to Students.Count - 1 do
    begin
      S := PStudent(Students[I]);
      WriteLn(S^.Name:15, S^.GPA:6:2);
    end;

    { Lookup by ID }
    S := PStudent(Lookup.Get('A002'));
    if S <> nil then
      WriteLn('Found: ', S^.Name);

    { Cleanup — free user data }
    for I := 0 to Students.Count - 1 do
      Dispose(PStudent(Students[I]));
  finally
    Students.Free;
    Lookup.Free;
  end;
end.

Design Review Checklist

Before releasing a library, verify:

Lessons Learned

1. Design the interface first. Write the interface section before any implementation. If the interface is clear and minimal, the implementation will follow naturally.

2. Document ownership rules. Who allocates? Who frees? These questions must have clear, consistent answers. Ambiguous ownership is the number-one source of memory leaks and use-after-free bugs.

3. Keep external dependencies minimal. Every dependency is a burden on users of your library. The fewer dependencies, the easier it is to adopt.

4. Version your library. Even a simple version string helps users know what they have and report issues accurately.

5. Test with realistic usage. Writing the test program often reveals interface awkwardness that you would not notice by reading the implementation alone.