Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-xml

Source of release 0.3.0

0.3.0 / src / xml / buffers.lucb

#==============================================================================================
#
#   xml/buffers - Growable lists, byte strings, a text arena and a name table
#
#   DESCRIPTION:
#       The reader keeps its records in `List`s, heap arrays that double as they fill,
#       addressed by index so nothing points into them. `Bytes` builds text (and is an
#       `io.Writer`, so error messages are formatted into one). Text that must outlive
#       the input it was made from (decoded documents, entity replacement texts,
#       namespace URIs) is kept in an `Arena`, whose blocks never move. A `Table` maps
#       names to indices by open addressing, so entity and attribute lookups stay
#       constant time however large a DTD is.
#
#==============================================================================================

# mark: Lists =================================================================================

## A growable heap array of `T`; `used` of `items` are in use.
struct List[T]:
    var items: T[]
    var used: usize = 0

    ## Append `value`.
    func push(value: T) -> !:
        if self.used >= self.items.length:
            let size = 8 if self.items.length == 0 else self.items.length * 2
            let larger = try new T[size] --- in memory.heap
            memory.copy(larger, self.items, self.used)
            if self.items.length > 0:
                free(self.items) in memory.heap
            self.items = larger
        self.items[self.used] = value
        self.used += 1

    ## The items in use, as a span.
    func view() -> T[]:
        return self.items[..<self.used]

    ## Free the items; the list is empty afterwards.
    func release():
        if self.items.length > 0:
            free(self.items) in memory.heap
        var empty: T[]
        self.items = empty
        self.used = 0

# mark: Byte strings ==========================================================================

## Text built a piece at a time.
struct Bytes: io.Writer:
    var items: u8[]
    var used: usize = 0

    ## Room for `more` bytes past those in use.
    func reserve(more: usize) -> !:
        let needed = self.used + more
        if needed <= self.items.length:
            return
        var size = 64 if self.items.length == 0 else self.items.length * 2
        if size < needed:
            size = needed
        let larger = try new u8[size] --- in memory.heap
        memory.copy(larger, self.items, self.used)
        if self.items.length > 0:
            free(self.items) in memory.heap
        self.items = larger

    func add(byte: u8) -> !:
        if self.used >= self.items.length:
            try self.reserve(1)
        self.items[self.used] = byte
        self.used += 1

    func add_all(data: const u8[]) -> !:
        try self.reserve(data.length)
        memory.copy(self.items[self.used..], data, data.length)
        self.used += data.length

    ## Append `scalar` as UTF-8.
    func add_scalar(scalar: u32) -> !:
        try self.reserve(4)
        self.used += encode_utf8(scalar, self.items[self.used..])

    pub func write(data: const u8[]) -> usize!:
        try self.add_all(data)
        return data.length

    ## The bytes so far, as text; valid until the next change.
    func view() -> str:
        return (str)self.items[..<self.used]

    func clear():
        self.used = 0

    func release():
        if self.items.length > 0:
            free(self.items) in memory.heap
        var empty: u8[]
        self.items = empty
        self.used = 0

# mark: The text arena ========================================================================

## Bytes for text that outlives what it was made from, in blocks that never move.
struct Arena:
    var blocks: List[u8[]] = List[u8[]]()
    var block_used: usize = 0

    ## A copy of `data` in the arena.
    func store(data: const u8[]) -> str!:
        let target = try self.reserve(data.length)
        memory.copy(target, data, data.length)
        return (str)target

    ## `length` bytes of fresh arena storage, for the caller to fill.
    func reserve(length: usize) -> u8[]!:
        if length == 0:
            var empty: u8[]
            return empty
        var room: usize = 0
        if self.blocks.used > 0:
            room = self.blocks.items[self.blocks.used - 1].length - self.block_used
        if room < length:
            let size = length if length > 16384 else 16384
            try self.blocks.push(try new u8[size] --- in memory.heap)
            self.block_used = 0
        let block = self.blocks.items[self.blocks.used - 1]
        let start = self.block_used
        self.block_used += length
        return block[start..<start + length]

    ## Free every block; every `str` the arena gave out is invalid afterwards.
    func release():
        for block in self.blocks.view():
            free(block) in memory.heap
        self.blocks.release()
        self.block_used = 0

# mark: The name table ========================================================================

## One slot of a `Table`: `value` is 0 when the slot is empty, else the stored value + 1.
struct Slot:
    var key: str
    var value: u32

## A map from names to `u32` values, by open addressing with linear probing.
struct Table:
    var slots: Slot[]
    var count: usize = 0

    ## The value stored for `key`.
    func find(key: str) -> u32?:
        if self.count == 0:
            return none
        let mask = self.slots.length - 1
        var index = (usize)(fnv(key) & (u64)mask)
        while self.slots[index].value != 0:
            if self.slots[index].key == key:
                return self.slots[index].value - 1
            index = (index + 1) & mask
        return none

    ## Store `value` for `key`, which must not be in the table yet.
    func insert(key: str, value: u32) -> !:
        if (self.count + 1) * 2 > self.slots.length:
            try self.grow()
        let mask = self.slots.length - 1
        var index = (usize)(fnv(key) & (u64)mask)
        while self.slots[index].value != 0:
            index = (index + 1) & mask
        self.slots[index] = Slot(key = key, value = value + 1)
        self.count += 1

    ## Store `value` for `key`, replacing the value it had.
    func set(key: str, value: u32) -> !:
        if self.count > 0:
            let mask = self.slots.length - 1
            var index = (usize)(fnv(key) & (u64)mask)
            while self.slots[index].value != 0:
                if self.slots[index].key == key:
                    self.slots[index].value = value + 1
                    return
                index = (index + 1) & mask
        try self.insert(key, value)

    func grow() -> !:
        let old = self.slots
        let size = 16 if old.length == 0 else old.length * 2
        self.slots = try new Slot[size] in memory.heap
        self.count = 0
        for slot in old:
            if slot.value != 0:
                try self.insert(slot.key, slot.value - 1)
        if old.length > 0:
            free(old) in memory.heap

    func clear():
        for index in 0..<self.slots.length:
            self.slots[index] = Slot()
        self.count = 0

    func release():
        if self.slots.length > 0:
            free(self.slots) in memory.heap
        var empty: Slot[]
        self.slots = empty
        self.count = 0

## The FNV-1a hash of `key`.
func fnv(key: str) -> u64:
    var value: u64 = 0xcbf29ce484222325
    for byte in key.bytes:
        value = (value ^ (u64)byte) *% 0x100000001b3
    return value