Can someone review for me? I made my own Array

I made my own Array for practising using C APIs and pointers
Please help me improve it.
Thanks.

struct MyArray<T> {

    final class Ref {
        private var bufferPtr: UnsafeMutableRawPointer

        init(defaultSize: UInt) {
            let defaultSize = Int(defaultSize)
            let totalSize = MemoryLayout<T>.size * defaultSize
            bufferPtr = malloc(totalSize)
            bufferPtr.initializeMemory(as: UInt8.self, repeating: 0, count: totalSize)
        }

        deinit {
            free(bufferPtr)
        }

        func callAsFunction() -> UnsafeMutableRawPointer {
            bufferPtr
        }
    }

    private var bufferRef: Ref
    private var avaliableSize: UInt
    private(set) var count: UInt = 0

    init(size: UInt = 100) {
        bufferRef = Ref(defaultSize: size)
        avaliableSize = size
    }

    private func getPtr(index: UInt) -> UnsafeMutablePointer<T> {
            let targetPtr = bufferRef().advanced(by: Int(index) * MemoryLayout<T>.size)
            return targetPtr.bindMemory(to: T.self, capacity: 1)
    }

    mutating func remove(at index: UInt) {
        guard index < count else {
            fatalError("out of bounds")
        }
        let destPtr = bufferRef().advanced(by: Int(index) * MemoryLayout<T>.size)
        let sourcePtr = bufferRef().advanced(by: Int(index + 1) * MemoryLayout<T>.size)
        memmove(destPtr, sourcePtr, Int(count - index - 1) * MemoryLayout<T>.size)

        let lastElmPtr = bufferRef().advanced(by: Int(count - 1) * MemoryLayout<T>.size)
        let arrPtr = lastElmPtr.bindMemory(to: UInt8.self, capacity: MemoryLayout<T>.size)

        (0..<MemoryLayout<T>.size).forEach { (arrPtr + $0).pointee = 0 }
        count -= 1
    }

    mutating func append(_ addValue: T) {
        if count == avaliableSize {
            reallocate()
        }

        getPtr(index: count).pointee = addValue
        self.count += 1
    }  

    mutating func insert(_ element: T, at index: UInt) {
        guard index <= count else {
            fatalError("out of bounds")
        }

        if count + 1 > avaliableSize {
            reallocate()
        }

        let sourcePtr = bufferRef().advanced(by: Int(index) * MemoryLayout<T>.size)
        let destPtr = bufferRef().advanced(by: Int(index + 1) * MemoryLayout<T>.size)
        memmove(destPtr, sourcePtr, Int(count - index) * MemoryLayout<T>.size)
        getPtr(index: index).pointee = element
        count += 1
    }  

    mutating func append(_ anotheSequence: some Sequence<T>) {
        let sequenceCount = anotheSequence.reduce(0) { sum, _ in sum + 1 }
        append(total: sequenceCount, anotheSequence: anotheSequence)
    }

    private mutating func append(total: Int, anotheSequence: some Sequence<T>) {
        let remainSize = Int(avaliableSize - count) - total

        if remainSize <= 0 {
            reallocate(addSize: avaliableSize + UInt(total))
        }

        anotheSequence.forEach {
            append($0)
        }
    }

    private mutating func reallocate(addSize: UInt? = nil) {
        let newTotalSize = avaliableSize + (addSize ?? avaliableSize)
        let newBuff = Ref(defaultSize: newTotalSize)
        memcpy(newBuff(), bufferRef(), Int(count) * MemoryLayout<T>.size)
        bufferRef = newBuff
        avaliableSize = newTotalSize
    }
}

extension MyArray: Collection {
    func index(after i: UInt) -> UInt {
        i + 1
    }

    var startIndex: UInt {
        0
    }

    var endIndex: UInt {
        count
    }

    private func checkBoundary(index: UInt) {
        guard index < count else {
            fatalError("out of bounds")
        }
    }

    subscript(index: UInt) -> T {
        _read { 
            checkBoundary(index: index)
            yield getPtr(index: index).pointee
        }
        _modify {
            checkBoundary(index: index)   
            yield &getPtr(index: index).pointee
        }
    }
}
1 Like

So, you're using a raw pointer, lots of manual offset calculations, and C functions such as memmove and memcpy. You also bind that memory to different types.

Firstly, the offsets should be MemoryLayout<T>.stride, not .size:

stride

The number of bytes from the start of one instance of T to the start of the next when stored in contiguous memory or in an Array<T>.

But really, you shouldn't be doing these calculations manually anyway - you should use a typed pointer. I see that your getPtr() function returns a typed pointer, but really you should store the typed pointer and use it everywhere instead of storing a raw pointer and binding it ad-hoc (also, I would go for the buffer variant - UnsafeMutableBufferPointer<T>).

I guess the core thing to keep in mind is that when this buffer is allocated, it is entirely uninitialised. That's fine. Don't try to bind it to UInt8 and zero it. Instead, the thing that an Array needs to do is manage that memory by initialising and deinitialising the elements within it, and bounds-check to ensure it never reads from an uninitialised location.

And instead of using C to manage the elements in the buffer, you should use the functions provided on UMBP, such as initialize(fromContentsOf:), moveInitialize(fromContentsOf:), deinitializeElement(at:), etc.

In your append method, you have:

getPtr(index: count).pointee = addValue

This is undefined behaviour if T is a non-trivial type (such as a class). The .pointee property setter is an update operation which requires its memory location to already hold a valid initialised value (and that value will be released when it is replaced). In this case, the memory location does not hold a reference to a class instance, so you should use one of the initialize methods instead.

Since you zero the memory it's possible that it won't actually crash (perhaps the runtime is lenient towards releasing null pointers), but you shouldn't rely on that.

And in your remove method, you have:

(0..<MemoryLayout<T>.size).forEach { (arrPtr + $0).pointee = 0 }

Again, if T is a class, just zeroing its bytes will not release it, so its deinitialiser will not run and you will leak the element.

And in your insert method, you have:

memmove(destPtr, sourcePtr, Int(count - index) * MemoryLayout<T>.size)

I think Swift has types which are non-trivially moveable (e.g. structs containing Obj-C weak references, I think?), so this could also be undefined behaviour.

In short: don't use raw pointers and C functions, use typed pointers and the Swift functions they expose.

I hope that helps get you started! Here are some more resources you might find useful:

17 Likes