diff options
| -rw-r--r-- | README.md | 1 | ||||
| -rw-r--r-- | docs/std/README.md | 1 | ||||
| -rw-r--r-- | docs/std/queue.md | 74 | ||||
| -rw-r--r-- | docs/std/string.md | 2 | ||||
| -rw-r--r-- | std/io.zc | 22 | ||||
| -rw-r--r-- | std/queue.zc | 93 | ||||
| -rw-r--r-- | std/string.zc | 72 | ||||
| -rw-r--r-- | tests/std/test_queue.zc | 52 | ||||
| -rw-r--r-- | tests/std/test_string_utils.zc | 46 |
9 files changed, 329 insertions, 34 deletions
@@ -834,6 +834,7 @@ Zen C includes a standard library (`std`) covering essential functionality. | :--- | :--- | :--- | | **`std/vec.zc`** | Growable dynamic array `Vec<T>`. | [Docs](docs/std/vec.md) | | **`std/string.zc`** | Heap-allocated `String` type with UTF-8 support. | [Docs](docs/std/string.md) | +| **`std/queue.zc`** | FIFO queue. | [Docs](docs/std/queue.md) | | **`std/map.zc`** | Generic Hash Map `Map<V>`. | [Docs](docs/std/map.md) | | **`std/fs.zc`** | File system operations. | [Docs](docs/std/fs.md) | | **`std/option.zc`** | Optional values (`Some`/`None`). | [Docs](docs/std/option.md) | diff --git a/docs/std/README.md b/docs/std/README.md index 988440d..f15b67a 100644 --- a/docs/std/README.md +++ b/docs/std/README.md @@ -6,5 +6,6 @@ - [Option](./option.md) - Optional values (Some/None). - [Path](./path.md) - File path manipulation. - [Result](./result.md) - Error handling (Ok/Err). +- [Queue](./queue.md) - FIFO queue (Ring Buffer). - [String](./string.md) - Growable, heap-allocated string type. - [Vector (Vec)](./vec.md) - A growable dynamic array. diff --git a/docs/std/queue.md b/docs/std/queue.md new file mode 100644 index 0000000..d463f15 --- /dev/null +++ b/docs/std/queue.md @@ -0,0 +1,74 @@ +# Standard Library: Queue (`std/queue.zc`) + +`Queue<T>` is a generic First-In-First-Out (FIFO) queue implemented as a **Ring Buffer (Circular Buffer)**. + +## Usage + +```zc +import "std/queue.zc" + +fn main() { + var q = Queue<int>::new(); + + q.push(1); + q.push(2); + q.push(3); + + // Pop returns an Option<T> + if (q.pop().is_some()) { + println "Popped: {q.pop().unwrap()}"; // 1 + } +} +``` + +## Implementation Details + +- **Ring Buffer**: Uses a circular buffer with `head` and `tail` indices. +- **Performance**: + - `push`: **Amortized O(1)** (resizes when full). + - `pop`: **O(1)** (advances head index). + - `clone`: **O(N)**. +- **Safety**: Safe handling of memory wrapping and resizing. + +## Structure + +```zc +struct Queue<T> { + data: T*; + cap: usize; + head: usize; + tail: usize; + count: usize; +} +``` + +## Methods + +### Construction + +| Method | Signature | Description | +| :--- | :--- | :--- | +| **new** | `Queue<T>::new() -> Queue<T>` | Creates a new, empty queue. | +| **clone** | `clone(self) -> Queue<T>` | Creates a deep copy of the queue. | + +### Modification + +| Method | Signature | Description | +| :--- | :--- | :--- | +| **push** | `push(self, value: T)` | Adds an element to the back of the queue. | +| **pop** | `pop(self) -> Option<T>` | Removes and returns the element at the front. Returns `None` if empty. | +| **clear** | `clear(self)` | Removes all items from the queue. | + +### Access / Query + +| Method | Signature | Description | +| :--- | :--- | :--- | +| **length** | `length(self) -> usize` | Returns the number of items. | +| **is_empty** | `is_empty(self) -> bool` | Returns `true` if the queue is empty. | + +### Memory Management + +| Method | Signature | Description | +| :--- | :--- | :--- | +| **free** | `free(self)` | Frees the internal buffer. | +| **Trait** | `impl Drop for Queue` | Automatically calls `free()` when out of scope. | diff --git a/docs/std/string.md b/docs/std/string.md index b83ee80..252b737 100644 --- a/docs/std/string.md +++ b/docs/std/string.md @@ -72,6 +72,8 @@ These methods handle UTF-8 character boundaries correctly, contrasting with the | Method | Signature | Description | | :--- | :--- | :--- | | **split** | `split(self, delim: char) -> Vec<String>` | Splits the string into a vector of substrings separated by `delim`. | +| **trim** | `trim(self) -> String` | Returns a new string with leading and trailing whitespace removed. | +| **replace** | `replace(self, target: char*, replacement: char*) -> String` | Returns a new string with all occurrences of `target` replaced by `replacement`. | ### Comparison @@ -1,5 +1,6 @@ import "./core.zc" +import "./string.zc" raw { char* format(const char* fmt, ...) { @@ -34,8 +35,29 @@ raw { { return fgetc((FILE*)stream); } + + char* _z_format_alloc(const char* fmt, va_list args) { + int len = vsnprintf(NULL, 0, fmt, args); + if (len < 0) return NULL; + char* buffer = malloc(len + 1); + if (!buffer) return NULL; + vsnprintf(buffer, len + 1, fmt, args); + return buffer; + } + + char* format_s_raw(char* fmt, ...) { + va_list args; + va_start(args, fmt); + char* ret = _z_format_alloc(fmt, args); + va_end(args); + return ret; + } } +extern fn format_s_raw(fmt: char*, ...) -> char*; + +// TODO: add format function. We will need to do a few updates... +// like adding support for varargs in Zen C functions. fn readln() -> char* { diff --git a/std/queue.zc b/std/queue.zc index 3e99eba..0b00ee2 100644 --- a/std/queue.zc +++ b/std/queue.zc @@ -3,13 +3,15 @@ import "./mem.zc" struct Queue<T> { data: T*; - len: usize; cap: usize; + head: usize; + tail: usize; + count: usize; } impl Queue<T> { fn new() -> Queue<T> { - return Queue<T>{data: NULL, len: 0, cap: 0}; + return Queue<T>{data: NULL, cap: 0, head: 0, tail: 0, count: 0}; } fn free(self) { @@ -17,54 +19,91 @@ impl Queue<T> { free(self.data); self.data = NULL; } - self.len = 0; + self.cap = 0; + self.head = 0; + self.tail = 0; + self.count = 0; + } + + fn _grow(self) { + var new_cap = (self.cap == 0) ? 8 : self.cap * 2; + var new_data = malloc(sizeof(T) * new_cap); + + if (self.count > 0) { + if (self.tail > self.head) { + memcpy(new_data, self.data + self.head, sizeof(T) * self.count); + } else { + var first_part = self.cap - self.head; + var second_part = self.tail; + memcpy(new_data, self.data + self.head, sizeof(T) * first_part); + memcpy(new_data + first_part, self.data, sizeof(T) * second_part); + } + } + + if (self.data) free(self.data); + self.data = new_data; + self.cap = new_cap; + self.head = 0; + self.tail = self.count; } fn clone(self) -> Queue<T> { var new_queue = Queue<T>::new(); - new_queue.len = self.len; + new_queue.data = malloc(sizeof(T) * self.cap); new_queue.cap = self.cap; - new_queue.data = malloc(sizeof(T) * new_queue.cap); - memcpy(new_queue.data, self.data, sizeof(T) * new_queue.len); + new_queue.head = 0; + new_queue.tail = self.count; + new_queue.count = self.count; + + if (self.count > 0) { + if (self.tail > self.head) { + memcpy(new_queue.data, self.data + self.head, sizeof(T) * self.count); + } + else { + var first_part = self.cap - self.head; + var second_part = self.tail; + memcpy(new_queue.data, self.data + self.head, sizeof(T) * first_part); + memcpy(new_queue.data + first_part, self.data, sizeof(T) * second_part); + } + } + return new_queue; } fn push(self, value: T) { - if (!self.data) { - self.cap = 8; - self.data = malloc(sizeof(T) * self.cap); + if (self.count == self.cap) { + self._grow(); } - if (self.len == self.cap) { - self.cap = self.cap * 2; - self.data = realloc(self.data, sizeof(T) * self.cap); - } - self.data[self.len] = value; - self.len = self.len + 1; + + self.data[self.tail] = value; + self.tail = (self.tail + 1) % self.cap; + self.count = self.count + 1; } fn pop(self) -> Option<T> { - if (self.len > 0) { - var value = self.data[0]; - self.len = self.len - 1; - - // Shifts the data in the queue "forward" - memcpy(self.data, self.data + 1, sizeof(T) * self.len); - - return Option<T>::Some(value); + if (self.count == 0) { + return Option<T>::None(); } - return Option<T>::None(); + + var value = self.data[self.head]; + self.head = (self.head + 1) % self.cap; + self.count = self.count - 1; + + return Option<T>::Some(value); } fn length(self) -> usize { - return self.len; + return self.count; } fn clear(self) { - self.len = 0; + self.head = 0; + self.tail = 0; + self.count = 0; } fn is_empty(self) -> bool { - return self.len == 0; + return self.count == 0; } } diff --git a/std/string.zc b/std/string.zc index 3f96053..a7dd6ce 100644 --- a/std/string.zc +++ b/std/string.zc @@ -31,7 +31,6 @@ impl String { return String::new(s); } - // Fixed: 'self' implies pointer in generated C fn c_str(self) -> char* { return self.vec.data; } @@ -245,4 +244,75 @@ impl String { return parts; } + + fn trim(self) -> String { + var start: usize = 0; + var len = self.length(); + var end = len; + + // Find start + while (start < len) { + var c = self.vec.get(start); + if (c != ' ' && c != '\t' && c != '\n' && c != '\r') { + break; + } + start = start + 1; + } + + if (start == len) { + return String::new(""); + } + + // Find end + while (end > start) { + var c = self.vec.get(end - 1); + if (c != ' ' && c != '\t' && c != '\n' && c != '\r') { + break; + } + end = end - 1; + } + + return self.substring(start, end - start); + } + + fn replace(self, target: char*, replacement: char*) -> String { + var t_len = strlen(target); + if (t_len == 0) return self.substring(0, self.length()); // clone + + + var s_len = self.length(); + var result = String::new(""); + + var i: usize = 0; + while (i < s_len) { + // Check if match + if (i + t_len <= s_len) { + var is_match = true; + // Manual strncmp against vec data + for (var k: usize = 0; k < t_len; k = k + 1) { + if (self.vec.get(i + k) != target[k]) { + is_match = false; + break; + } + } + + if (is_match) { + var r_str = String::new(replacement); + result.append(&r_str); + i = i + t_len; + continue; + } + } + + // Append single char + var v = Vec<char>::new(); + v.push(self.vec.get(i)); + v.push(0); + var ch_s = String::new(v.data); + result.append(&ch_s); + v.free(); + i = i + 1; + } + return result; + } }
\ No newline at end of file diff --git a/tests/std/test_queue.zc b/tests/std/test_queue.zc index 131eb05..d8895b8 100644 --- a/tests/std/test_queue.zc +++ b/tests/std/test_queue.zc @@ -1,15 +1,15 @@ import "std/queue.zc" test "Queue Push/Pop" { - print "Testing Queue Push/Pop"; + println "Testing Queue Push/Pop"; var queue = Queue<i32>::new(); defer queue.free(); - print "Popping on an empty queue without pushing anything prior" + println "Popping on an empty queue without pushing anything prior" var v = queue.pop(); assert(v.is_none(), "v should not have a valid value"); - print "Pushing in three values..." + println "Pushing in three values..." queue.push(123); queue.push(456); queue.push(789); @@ -23,13 +23,13 @@ test "Queue Push/Pop" { v = queue.pop(); assert(v.is_some() && v.unwrap() == 789, "v's value should be 789"); - print "Popping on an empty queue after pushing and popping three values" + println "Popping on an empty queue after pushing and popping three values" v = queue.pop(); assert(v.is_none(), "v should not have a valid value"); } test "Queue Length and Clear" { - print "Testing Queue clear"; + println "Testing Queue clear"; var queue = Queue<i32>::new(); defer queue.free(); @@ -43,7 +43,7 @@ test "Queue Length and Clear" { } test "Queue Clone" { - print "Testing Queue Cloning"; + println "Testing Queue Cloning"; var queue = Queue<i32>::new(); defer queue.free(); queue.push(123); @@ -60,3 +60,43 @@ test "Queue Clone" { v = queue.pop(); assert(v.is_none(), "v should not have a valid value"); } + +test "Queue Ring Buffer (Advanced)" { + var q = Queue<int>::new(); + + println "Fill slightly" + q.push(1); + q.push(2); + q.push(3); + assert(*q.pop().unwrap_ref() == 1); + + println "Pushing until capacity (assume 8)" + q.push(4); q.push(5); q.push(6); q.push(7); q.push(8); q.push(9); + + println "Popping some to advance head" + assert(*q.pop().unwrap_ref() == 2); + assert(*q.pop().unwrap_ref() == 3); + + println "Pushing to wrap tail" + q.push(10); + q.push(11); + + while (!q.is_empty()) { + q.pop(); + } + + println "Testing clear" + q.push(100); + q.clear(); + assert(q.is_empty()); + + println "Large scale test" + for (var i = 0; i < 100; i=i+1) { + q.push(i); + } + for (var i = 0; i < 100; i=i+1) { + assert(*q.pop().unwrap_ref() == i); + } + + q.free(); +} diff --git a/tests/std/test_string_utils.zc b/tests/std/test_string_utils.zc new file mode 100644 index 0000000..212bac1 --- /dev/null +++ b/tests/std/test_string_utils.zc @@ -0,0 +1,46 @@ +import "std/string.zc" + +test "string trim" { + var s1 = String::from(" hello "); + var t1 = s1.trim(); + var e1 = String::from("hello"); + assert(t1.eq(&e1)); + t1.free(); s1.free(); e1.free(); + + var s2 = String::from("\n\t world \r "); + var t2 = s2.trim(); + var e2 = String::from("world"); + assert(t2.eq(&e2)); + t2.free(); s2.free(); e2.free(); + + var s3 = String::from("no_trim"); + var t3 = s3.trim(); + var e3 = String::from("no_trim"); + assert(t3.eq(&e3)); + t3.free(); s3.free(); e3.free(); + + var s4 = String::from(" "); + var t4 = s4.trim(); + assert(t4.is_empty()); + t4.free(); s4.free(); +} + +test "string replace" { + var s1 = String::from("foo bar foo"); + var r1 = s1.replace("foo", "baz"); + var e1 = String::from("baz bar baz"); + assert(r1.eq(&e1)); + r1.free(); s1.free(); e1.free(); + + var s2 = String::from("hello world"); + var r2 = s2.replace("world", "ZenC"); + var e2 = String::from("hello ZenC"); + assert(r2.eq(&e2)); + r2.free(); s2.free(); e2.free(); + + var s3 = String::from("aaaa"); + var r3 = s3.replace("aa", "b"); + var e3 = String::from("bb"); + assert(r3.eq(&e3)); + r3.free(); s3.free(); e3.free(); +} |