Buffer Gap Data Structure Explained

0
#
(ツ) Guest
28
24.11.2025
#87

1. Overview: What is a Buffer Gap?

The Buffer Gap is a data structure used in text editors to efficiently manage text insertion and deletion.

  • The Problem: In a standard array, inserting a character at the beginning requires shifting every subsequent character one step to the right (O(N)).

  • The Solution: A "gap" (a block of unused memory) is maintained at the current cursor position.

    • Typing: You simply fill the gap (O(1)).

    • Moving Cursor: You move the gap to the new location (O(N), but generally fast for short distances).

2. The TText Structure Analysis

The code uses a specific memory layout defined as an rstruct (Reverse Structure).

Visual Memory Layout:
The pointer pText provided to functions points to Index 0 of the text area. The metadata is stored at negative offsets. 


Memory Address:  Low <-----------------------------------------> High
                 [Metadata] | [Text Part 1] [ GAP ] [Text Part 2]
                            ^
                            |__ pText points here (Zero Offset)

Fields:

  • .Length: Total allocated size of the buffer (Text + Gap).

  • .GapBegin: The offset (relative to pText) where the gap starts. This is effectively the Cursor Position.

  • .GapEnd: The offset where the gap ends.

  • .struc_size: Size of the header metadata (used for memory allocation).

3. Key Functions Breakdown

A. Life Cycle

  • TextCreate: Allocates memory using GetMem. It creates a buffer consisting entirely of a gap.

  • TextFree: Calculates the start of the memory block (pointer - header size) and frees it.

B. Navigation (Moving the Gap)

  • TextMoveGap: This is the engine's core. It moves the gap to a target logical position.

    • If the new position is after the current gap, it copies text from after the gap to before the gap (moving the gap right).

    • If the new position is before the current gap, it copies text from before the gap to the end of the gap (moving the gap left).

C. Modification

  • TextSetGapSize: Checks if the gap is large enough for a pending insertion. If not, it calls ResizeMem to expand the buffer.

  • TextAddChar / TextAddString: Writes data into the memory at .GapBegin and increments .GapBegin (shrinking the gap from the left).

  • TextDelChar: "Deletes" a character by simply moving .GapEnd forward (expanding the gap to swallow the character).

D. Coordinate Systems

The library distinguishes between:

1. Offset: Physical byte offset in memory.
2. Position: Logical byte index (ignoring the gap).
3. Index: Character count (accounting for multi-byte UTF-8 characters).

4. Step-by-Step Example Usage

Below is a conceptual trace of how you would use this library in an assembly program, showing the state of the buffer at every step.

Scenario: We want to write "Hello", then move the cursor back to insert a comma to make it "Hel,lo".

Step 1: Initialization

Call TextCreate to initialize the object. 

stdcall TextCreate, 0  ; Create text with 0 extra header size
; Returns pText in EAX. Let's assume EAX = 0x1000
mov [pText], eax

Internal State:

  • Buffer: [ _ _ _ _ _ _ ... ] (All Gap)

  • GapBegin: 0

  • GapEnd: 4096 (Default size)

Step 2: Insert "Hello"

We use TextAddString (or TextAddChar loop). The cursor is at 0. 


; Insert string at position 0
stdcall TextAddString, [pText], 0, "Hello"

  • The function ensures the gap is at 0 (it is).

  • It copies "H", "e", "l", "l", "o" into the gap.

  • It increments GapBegin by 5.

    Internal State:

  • Buffer: H e l l o [ _ _ _ ... ]

  • GapBegin: 5 (Cursor is after 'o')

  • GapEnd: 4096

Step 3: Move Cursor (The "Buffer Gap" Magic)

We want to insert a comma after the first 'l' (index 3). 


; Move gap to logical position 3
stdcall TextMoveGap, [pText], 3

  • Current Gap: Start 5, End 4096.

  • Target: 3.

  • Action: The text between target (3) and current gap start (5)—which is "lo"—must be moved to the end of the gap.

    Internal State:

  • Physical Memory: H e l [ _ _ ... _ l o ]

  • GapBegin: 3

  • GapEnd: 4094 (4096 - 2 bytes moved)

  • Note how "lo" physically moved to the far end of the buffer.

Step 4: Insert Comma

Now we insert ',' at the current gap position. 


stdcall TextAddChar, [pText], ','

  • Write ',' at GapBegin (3).

  • Increment GapBegin.

    Internal State:

  • Physical Memory: H e l , [ _ _ ... _ l o ]

  • GapBegin: 4

  • GapEnd: 4094

Step 5: Reading the Text

If you want to read the text linearly, you cannot just read the memory sequentially because of the gap. You use TextCompact to push the gap to the very end. 


stdcall TextCompact, [pText]

  • This calls TextMoveGap with position -1 (end of text).

  • It moves the "lo" chunk back to the left.

    Internal State:

  • Physical Memory: H e l , l o [ _ _ _ ... ]

  • GapBegin: 6

  • GapEnd: 4096

  • Now the memory at pText is a contiguous string "Hel,lo".

5. Code Example (Pseudo-FASM)

Here is how you would write the assembly code to utilize this library. 


; Assume FreshLib macros and standard definitions are available

proc Main
    locals
        pText dd ?
        strHello db 'Hello', 0
    endl

    ; 1. Create the text buffer
    stdcall TextCreate, 0
    jc      .error          ; Jump if allocation failed
    mov     [pText], eax

    ; 2. Add "Hello" at the beginning (Position 0)
    stdcall TextAddString, [pText], 0, strHello

    ; 3. Move cursor to index 3 (Between 'l' and 'l')
    stdcall TextMoveGap, [pText], 3

    ; 4. Insert a comma
    stdcall TextAddChar, [pText], ','

    ; 5. Delete the character AFTER the comma (The second 'l')
    ; Note: The gap is currently at pos 4 (after the comma).
    ; The character immediately following the gap is 'l'.
    stdcall TextDelChar, [pText]

    ; 6. Finalize (Compact) so we can print it
    stdcall TextCompact, [pText]
    ; EAX now contains the length, [pText] points to "Hel,o" (zero terminated by Compact)

    ; Print the result (Standard FreshLib output)
    stdcall FileWriteString, [STDOUT], [pText]

    ; 7. Clean up
    stdcall TextFree, [pText]

    return

.error:
    ; Handle allocation error
    return
endp

Summary of Important Constraints

1. UTF-8 Awareness:
TextIndexToPos calculates character length. If you are using pure ASCII, Index == Position. If using special characters, Index (char count) = Position (byte count).

2. Pointer Validity:
Because TextSetGapSize might reallocate memory (calling ResizeMem), the pText pointer can change! Always update your pointer from the EDX return value after adding text.

3. Negative Offsets:
Remember that if you manually access structure members, [pText] points to the data, not the struct start. You must use [pText + TText.Length] (where TText.Length is a negative constant) to access metadata.

Buffer Gap Data Structure Explained

0
#