dsa_rust/sequences/
dyn_array.rs

1/*!
2
3# About
4
5# Design
6
7# Example
8*/
9
10use std::alloc::{self, Layout};
11use std::ops::{Index, IndexMut};
12use std::ptr::{self, NonNull};
13
14#[derive(Debug)]
15/// A dynamically sized, contiguous storage buffer with positive
16/// (forward) indexing, where elements are stored sequentially in memory.
17pub struct DynArray<T> {
18    ptr: NonNull<T>, // Pointer to the start of the contiguous region
19    len: usize,      // Number of elements currently initialized
20    cap: usize,      // Total number of elements the region can hold
21}
22#[allow(clippy::new_without_default)]
23impl<T> DynArray<T> {
24    pub fn new() -> Self {
25        // Start with zero capacity and a "dangling" pointer to avoid
26        // an immediate syscall for an empty array
27        Self {
28            ptr: NonNull::dangling(),
29            len: 0,
30            cap: 0,
31        }
32    }
33
34    /// Pre-allocate for quicker operations
35    pub fn new_with_capacity(cap: usize) -> Self {
36        // Will panic on attempts to allocate beyond isize::MAX
37        let new_layout = Layout::array::<T>(cap).unwrap();
38        // SAFETY:
39        let ptr = unsafe { alloc::alloc(new_layout) };
40        Self {
41            ptr: NonNull::new(ptr as *mut T).expect("Out of memory"),
42            len: 0,
43            cap,
44        }
45    }
46
47    fn grow(&mut self) {
48        // Double the capacity (or start at 4)
49        let new_cap = if self.cap == 0 { 4 } else { self.cap * 2 };
50        let new_layout = Layout::array::<T>(new_cap).unwrap();
51
52        // SAFETY:
53        unsafe {
54            let new_ptr = if self.cap == 0 {
55                // First time allocating: ask the retailer for a fresh block
56                alloc::alloc(new_layout)
57            } else {
58                // Already have memory: ask to resize (might move to a new page)
59                let old_layout = Layout::array::<T>(self.cap).unwrap();
60                alloc::realloc(self.ptr.as_ptr() as *mut u8, old_layout, new_layout.size())
61            };
62
63            self.ptr = NonNull::new(new_ptr as *mut T).expect("Out of memory");
64            self.cap = new_cap;
65        }
66    }
67
68    pub fn add(&mut self, val: T) {
69        if self.len == self.cap {
70            self.grow();
71        }
72
73        // SAFETY:
74        unsafe {
75            // Calculate the offset and write the value into the uninitialized slot
76            let offset_ptr = self.ptr.as_ptr().add(self.len);
77            ptr::write(offset_ptr, val);
78            self.len += 1;
79        }
80    }
81}
82impl<T> Index<usize> for DynArray<T> {
83    type Output = T;
84
85    fn index(&self, index: usize) -> &Self::Output {
86        if index >= self.len {
87            panic!(
88                "Index out of bounds: the len is {} but the index is {}",
89                self.len, index
90            );
91        }
92        // Uses pointer arithmetic to retireve the [index]th element
93        // add takes usize, for negative indexing like in Python's
94        // list type, use offset
95        // SAFETY:
96        unsafe { &*self.ptr.as_ptr().add(index) }
97    }
98}
99impl<T> IndexMut<usize> for DynArray<T> {
100    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
101        if index >= self.len {
102            panic!(
103                "Index out of bounds: the len is {} but the index is {}",
104                self.len, index
105            );
106        }
107        // SAFETY:
108        unsafe { &mut *self.ptr.as_ptr().add(index) }
109    }
110}
111impl<T> Drop for DynArray<T> {
112    fn drop(&mut self) {
113        if self.cap != 0 {
114            // SAFETY:
115            unsafe {
116                // 1. Drop the actual items in the array
117                ptr::drop_in_place(ptr::slice_from_raw_parts_mut(self.ptr.as_ptr(), self.len));
118
119                // 2. Tell the allocator to release the virtual memory region
120                let layout = Layout::array::<T>(self.cap).unwrap();
121                alloc::dealloc(self.ptr.as_ptr() as *mut u8, layout);
122            }
123        }
124    }
125}
126
127#[test]
128fn test_0() {
129    let mut a = DynArray::<&str>::new();
130    a.add("Hello");
131    a.add("world");
132
133    assert_eq!(a.len, 2);
134    assert_eq!(a.cap, 4);
135
136    // Accesses the array with index operator
137    assert_eq!(a[0], "Hello");
138    assert_eq!(a[1], "world");
139
140    a.add("Alpha");
141    a.add("Bravo");
142    assert_eq!(a.len, 4);
143    assert_eq!(a.cap, 4);
144
145    // Grows the array, doubling its capacity
146    a.add("Charlie");
147    assert_eq!(a.len, 5);
148    assert_eq!(a.cap, 8);
149
150    // Illustrates the same logic with a pre-allocated slab
151    // which avoids O(n) reallocation with the internal grow()
152    let mut a = DynArray::<String>::new_with_capacity(4);
153    a.add("Papa".to_string());
154    a.add("Echo".to_string());
155    a.add("Tango".to_string());
156    a.add("Echo".to_string());
157    a.add("Romeo".to_string());
158    assert_eq!(a.cap, 8);
159    assert_eq!(a.len, 5);
160}
161
162#[test]
163#[should_panic]
164fn test_1() {
165    let mut a = DynArray::<&str>::new();
166    a.add("Hello");
167    a.add("world");
168
169    assert_ne!(a[5], "Hello"); // Illegal index
170}
171
172#[test]
173fn test_2() {
174    let mut a = DynArray::<String>::new_with_capacity(4);
175    a.add("Papa".to_string());
176    a.add("Echo".to_string());
177    a.add("Tango".to_string());
178    a.add("Echo".to_string());
179    a.add("Romeo".to_string());
180    assert_eq!(a.cap, 8);
181    assert_eq!(a.len, 5);
182
183    //assert!(balance("([][]{([]{()})})")); // Balanced
184    //assert!(balance("([][]{[]{()}}()")); // Missing closing symbol
185    //assert!(balance("[][]{[]{()}}())")); // Missing opening symbol
186}
dsa_rust/sequences/dyn_array.rs

dsa_rust/sequences/
dyn_array.rs
