Some std for you

1 files changed, 182 insertions, 0 deletions

diff --git a/std/map.zc b/std/map.zc
new file mode 100644
index 0000000..cd54f3d
--- /dev/null
+++ b/std/map.zc
@@ -0,0 +1,182 @@
+
+import "./core.zc"
+import "./option.zc"
+
+raw {
+    size_t _map_hash_str(const char* str) {
+        size_t hash = 14695981039346656037UL;
+        while (*str) {
+            hash ^= (unsigned char)*str++;
+            hash *= 1099511628211UL;
+        }
+        return hash;
+    }
+}
+
+struct Map<V> {
+    keys: char**;
+    vals: V*;
+    occupied: bool*;  
+    deleted: bool*;
+    len: usize;
+    cap: usize;
+}
+
+impl Map<V> {
+    fn new() -> Map<V> {
+        return Map<V> { keys: 0, vals: 0, occupied: 0, deleted: 0, len: 0, cap: 0 };
+    }
+
+    fn _resize(self, new_cap: usize) {
+        var old_keys = self.keys;
+        var old_vals = self.vals;
+        var old_occupied = self.occupied;
+        var old_deleted = self.deleted;
+        var old_cap = self.cap;
+
+        self.cap = new_cap;
+        self.keys = calloc(new_cap, sizeof(char*));
+        self.vals = calloc(new_cap, sizeof(V));
+        self.occupied = calloc(new_cap, sizeof(bool));
+        self.deleted = calloc(new_cap, sizeof(bool));
+        self.len = 0;
+
+        for (var i: usize = 0; i < old_cap; i = i + 1) {
+            if (old_occupied[i] && !old_deleted[i]) {
+                self.put(old_keys[i], old_vals[i]);
+            }
+        }
+        
+        // Free old arrays (use explicit braces to avoid parser bug)
+        if (old_keys != NULL) { free(old_keys); }
+        if (old_vals != NULL) { free(old_vals); }
+        if (old_occupied != NULL) { free(old_occupied); }
+        if (old_deleted != NULL) { free(old_deleted); }
+    }
+
+    fn put(self, key: char*, val: V) {
+        if (self.len >= self.cap * 0.75) {
+            var new_cap = self.cap * 2;
+            if (new_cap < 8) new_cap = 8;
+            self._resize(new_cap);
+        }
+
+        var hash = _map_hash_str(key);
+        var idx = hash % self.cap;
+
+        while (true) {
+            if (!self.occupied[idx] || (self.occupied[idx] && !self.deleted[idx] && strcmp(self.keys[idx], key) == 0)) {
+                if (!self.occupied[idx]) self.len = self.len + 1;
+                
+                if (!self.occupied[idx] || self.deleted[idx]) {
+                    self.keys[idx] = strdup(key);
+                }
+                
+                self.vals[idx] = val;
+                self.occupied[idx] = true;
+                self.deleted[idx] = false;
+                return;
+            }
+            
+            idx = (idx + 1) % self.cap;
+        }
+    }
+
+    fn get(self, key: char*) -> Option<V> {
+        if (self.cap == 0) {
+            return Option<V>::None();
+        }
+
+        var hash = _map_hash_str(key);
+        var idx = hash % self.cap;
+        var start_idx = idx;
+
+        while (true) {
+            if (!self.occupied[idx]) {
+                return Option<V>::None();
+            }
+            
+            if (!self.deleted[idx] && strcmp(self.keys[idx], key) == 0) {
+                return Option<V>::Some(self.vals[idx]);
+            }
+
+            idx = (idx + 1) % self.cap;
+            if (idx == start_idx) {
+                return Option<V>::None();
+            }
+        }
+    }
+    
+    fn contains(self, key: char*) -> bool {
+        var opt: Option<V> = self.get(key);
+        return opt.is_some();
+    }
+    
+    fn remove(self, key: char*) {
+        if (self.cap == 0) return;
+        
+        var hash = _map_hash_str(key);
+        var idx = hash % self.cap;
+        
+        while (true) {
+            if (!self.occupied[idx]) return;
+            
+            if (!self.deleted[idx] && strcmp(self.keys[idx], key) == 0) {
+                 self.deleted[idx] = true;
+                 self.len = self.len - 1;
+                 free(self.keys[idx]);
+                 return;
+            }
+            
+            idx = (idx + 1) % self.cap;
+        }
+    }
+    
+    fn length(self) -> usize {
+        return self.len;
+    }
+    
+    fn is_empty(self) -> bool {
+        return self.len == 0;
+    }
+    
+    fn free(self) {
+        if (self.keys) {
+            for (var i: usize = 0; i < self.cap; i = i + 1) {
+                if (self.occupied[i] && !self.deleted[i]) {
+                    free(self.keys[i]);
+                }
+            }
+            free(self.keys);
+            free(self.vals);
+            free(self.occupied);
+            free(self.deleted);
+        }
+        self.keys = 0;
+        self.vals = 0;
+        self.occupied = 0;
+        self.deleted = 0;
+        self.len = 0;
+        self.cap = 0;
+    }
+    
+    fn capacity(self) -> usize {
+        return self.cap;
+    }
+    
+    fn is_slot_occupied(self, idx: usize) -> bool {
+        if (idx >= self.cap) return false;
+        return self.occupied[idx] && !self.deleted[idx];
+    }
+    
+    fn key_at(self, idx: usize) -> char* {
+        if (idx >= self.cap || !self.occupied[idx] || self.deleted[idx]) {
+            return NULL;
+        }
+        return self.keys[idx];
+    }
+    
+    fn val_at(self, idx: usize) -> V {
+        return self.vals[idx];
+    }
+}