Skip to content

FSEntry Table

Jump to bottom
Levente Santha edited this page May 15, 2026 · 1 revision

FSEntry Table

Per-directory data structure that maps filesystem entry names and IDs to FSEntry objects, with lazy loading, case sensitivity support, and free-slot management.

Overview

FSEntryTable (org.jnode.fs.spi.FSEntryTable) is the core data structure used by JNode's filesystem SPI to represent the contents of a single directory. It maintains three parallel data structures to support name-based lookup, ID-based lookup, and ordered iteration:

  • entries — HashMap<String, FSEntry> for name-based lookup (key = normalized name)
  • entriesById — HashMap<String, FSEntry> for ID-based lookup (key = FSEntry.getId())
  • entryNames — ArrayList<String> preserving disk-order with null slots representing deleted/free entries

The table is used by the SPI base class AbstractFSDirectory and directly by HfsPlusDirectory. Filesystem implementations that do not use FSEntryTable (FAT, NTFS, ISO9660, ExFAT) implement their own directory data structures.

FSEntryTable extends AbstractFSObject, inheriting dirty tracking and filesystem association. Each FSEntry holds a back-reference to its parent table, enabling rename operations to update the table's maps atomically.

Key Components

Class / File Role
fs/src/fs/org/jnode/fs/spi/FSEntryTable.java Base table class with case-sensitive name lookup
fs/src/fs/org/jnode/fs/FSEntryTableIgnoreCase.java Subclass that uppercases names for case-insensitive matching (unused)
fs/src/fs/org/jnode/fs/spi/AbstractFSDirectory.java SPI directory base class that owns and lazily loads FSEntryTable
fs/src/fs/org/jnode/fs/spi/AbstractFSEntry.java SPI entry base class holding back-reference to parent FSEntryTable
fs/src/fs/org/jnode/fs/FSEntry.java Interface for filesystem entries (name, ID, parent, file/directory access)
fs/src/fs/org/jnode/fs/ext2/Ext2Directory.java ext2/ext3 directory implementation using FSEntryTable via AbstractFSDirectory
fs/src/fs/org/jnode/fs/hfsplus/HfsPlusDirectory.java HFS+ directory implementation using FSEntryTable directly (not via SPI)

How It Works

Three-Structure Design

FSEntryTable maintains three parallel data structures for a single directory's entries:

FSEntryTable:
  entries:       HashMap<String, FSEntry>    // name → entry (normalized key)
  entriesById:   HashMap<String, FSEntry>    // id → entry
  entryNames:    ArrayList<String>           // ordered names with null = free slot

The entryNames list preserves disk order — the index corresponds to the on-disk position of the directory record. null entries represent deleted/free slots, which is crucial for filesystems like FAT and ext2 that use fixed-size directory records with deletion markers.

Lazy Loading with EMPTY_TABLE Sentinel

Both AbstractFSDirectory and HfsPlusDirectory use the same lazy-loading idiom:

// Field declaration — starts as empty sentinel
private FSEntryTable entries = FSEntryTable.EMPTY_TABLE;

// On first access
private void checkEntriesLoaded() throws IOException {
    if (entries == FSEntryTable.EMPTY_TABLE) {  // identity check
        entries = readEntries();  // reads from block device
    }
}

// On failure, fall back to EMPTY_TABLE (retryable)
entries = FSEntryTable.EMPTY_TABLE;

EMPTY_TABLE uses Collections.emptyMap() and Collections.emptyList() internally, making it lightweight and safe for the identity-check pattern (== rather than .equals()).

Case Sensitivity Strategy

The normalizeName() method is a Template Method hook:

  • Base class (FSEntryTable): returns name unchanged — case-sensitive, used by ext2 and HFS+
  • Subclass (FSEntryTableIgnoreCase): returns name.toUpperCase() — case-insensitive, intended for FAT/ISO9660

Filesystem Driver Usage

Filesystem Extends AbstractFSDirectory? Uses FSEntryTable? Directory Implementation
ext2/ext3 Yes (Ext2Directory) Yes readEntries() reads from disk, writeEntries() is a no-op
HFS+ No (custom HfsPlusDirectory) Yes (directly) Duplicates the lazy-loading pattern from AbstractFSDirectory
FAT No (AbstractDirectory) No Uses Vector<FatBasicDirEntry> with equalsIgnoreCase()
NTFS No (NTFSDirectory) No Uses DirectoryEntryIterator over MFT records
ISO9660 No (ISO9660Directory) No Custom iteration over ISO directory records
ExFAT No No Custom implementation

Entry Operations

Adding an entry — addEntry(FSEntry) grows the table, finds a free slot (or appends), and updates all three data structures:

protected int addEntry(FSEntry entry) {
    final String name = normalizeName(entry.getName());
    entries.put(name, entry);
    entriesById.put(entry.getId(), entry);
    entryNames.add(name);
    setDirty();
    return entryNames.size() - 1;
}

Removing an entry — remove(String name) marks the entry as null in all three structures (free slot), preserving the disk-order index:

public int remove(String name) {
    final String normalizedName = normalizeName(name);
    final int index = entryNames.indexOf(normalizedName);
    if (index >= 0) {
        entries.remove(normalizedName);
        entriesById.remove(entries.get(normalizedName).getId());
        entries.put(null, null);  // free slot
        entryNames.set(index, null);
        setDirty();
    }
    return index;
}

Renaming an entry — rename(String oldName, String newName) updates both maps and the name list atomically:

public int rename(String oldName, String newName) {
    final String oldNormal = normalizeName(oldName);
    final String newNormal = normalizeName(newName);
    final FSEntry entry = entries.remove(oldNormal);
    if (entry != null) {
        entries.put(newNormal, entry);
        final int index = entryNames.indexOf(oldNormal);
        entryNames.set(index, newNormal);
        setDirty();
    }
    return index;
}

Dirty Tracking (Cascading)

FSEntryTable.isDirty() implements cascading dirty checking:

  1. Checks if the table itself is dirty (via AbstractFSObject.isDirty())
  2. Iterates all entries in the entries map, checking entry.isDirty() for each non-null entry
  3. Returns true if any child entry is dirty

This ensures that when a single entry is modified (e.g., setName()), the entire table is marked dirty and will be flushed to disk.

Entry Back-Reference Pattern

AbstractFSEntry holds a back-reference to its parent FSEntryTable:

private FSEntryTable table;  // null for root entries

This is used for rename operations: setName() calls table.rename(oldName, newName) to keep the table's maps in sync.

Relationship to FSEntry Cache

The FSEntryCache (documented in FSEntry-Cache) sits above the FSEntryTable layer:

  • FSEntryCache is a VFS-level LRU cache (100 entries max) keyed by absolute path
  • FSEntryTable is the per-directory data structure used by filesystem drivers internally
  • When the VFS cache misses, it falls through to FSDirectory.getEntry(name), which delegates to FSEntryTable.get(name)

Gotchas & Non-Obvious Behavior

  • EMPTY_TABLE is technically mutable: The comment at line 50 says // FIXME ... actually it CAN be modified!! — the private constructor uses Collections.emptyMap() / emptyList() which throw UnsupportedOperationException on mutation, but inherited methods like setDirty() are still callable on the sentinel.
  • FSEntryTableIgnoreCase is dead code: It exists but is never instantiated anywhere in the codebase. FAT handles case-insensitivity through its own getFatEntry() method with equalsIgnoreCase().
  • HfsPlusDirectory duplicates AbstractFSDirectory: The HFS+ directory re-implements the EMPTY_TABLE lazy-loading pattern, checkEntriesLoaded(), setFreeEntry(), and flush() instead of extending AbstractFSDirectory. This appears to be because HFS+ implements FSDirectory directly rather than extending the SPI base class.
  • Duplicate ID detection only logs: In the constructor, duplicate IDs are logged as errors but not prevented — entriesById.put() silently overwrites the old entry.
  • HashMap permits null keys: The constructor puts null as a key in the entries map when an entry is null (free slot), which works with HashMap but could cause subtle bugs with get(null).
  • writeEntries is a no-op for ext2: Ext2Directory.writeEntries() does nothing — writes are done incrementally by createFileEntry() and createDirectoryEntry(). The table is used for in-memory representation only.

Related Pages

Home | index

Architecture

Subsystems

Development

Reference

Clone this wiki locally