One of the annoying things about OCaml arrays is that every cell has to be initialized when the array is first created.
I'm trying to implement an array in OCaml that distinguishes
size (the current number of elements in the array) from
capacity (the maximum size that the array can grow to).
At any given point in the array's lifetime, the "inhabited cells" must form a prefix of the array itself. In other words, you can't do something like:
1 2 UNINITIALIZED 3 4 UNINITIALIZED
The array also clears cell immediately once they've been popped so the application doesn't leak memory / hold references to stuff that "used to be in the array" but isn't anymore.
The array uses the last element as the size. The reason for this is three-fold: 1) creating an array only requires one call to
Array.make 2) you don't need to do any arithmetic on the indices to access the elements in the underlying array and 3) it only requires chasing one pointer, not two, to get to the elements.
This code uses
Obj.magic, but I try to confine it to places where it can be easily audited.
I'm not using
Sys.opaque_identity from the Sys Module anywhere because I'm not actually using uninitialized memory anywhere ... I'm just using
Obj.magic to subvert the type system and let me store integers in strategic places. I am curious what work is needed to
flambda-proof this code though.
Anyway, here's the interface file
type 'a t val make : int -> 'a t val size : 'a t -> int val cap : 'a t -> int val get_exn : 'a t -> int -> 'a val get_opt : 'a t -> int -> 'a option val set_exn : 'a t -> int -> 'a -> unit val append_exn : 'a t -> 'a -> unit val pop_exn : 'a t -> 'a
And the source file
type 'a t = 'a array (* set every value to the integer 0, regardless of the * type of the array. * note that the last zero is special, it is the current size * of the array. *) let make : int -> 'a t = fun cap -> Array.make (cap + 1) (Obj.magic 0) let cap : 'a . 'a t -> int = fun arr -> (-1) + Array.length arr (* get the index of the size. This is the same as the capacity *) let size_idx : 'a t -> int = cap let size : 'a . 'a t -> int = fun arr -> (Obj.magic arr.(size_idx arr)) (* NOTE: incr_size is not checked and not safe *) let incr_size : 'a . 'a t -> unit = fun arr -> let new_size : int = 1 + Obj.magic arr.(size_idx arr) in arr.(size_idx arr) <- (Obj.magic new_size) (* NOTE: decr_size is not checked and not safe *) let decr_size : 'a . 'a t -> unit = fun arr -> let new_size : int = -1 + Obj.magic arr.(size_idx arr) in arr.(size_idx arr) <- (Obj.magic new_size) let get_exn : 'a . 'a t -> int -> 'a = fun arr idx -> if idx < size arr then arr.(idx) else raise (Invalid_argument "out of bounds") let get_opt : 'a . 'a t -> int -> 'a option = fun arr idx -> if idx < size arr then Some arr.(idx) else None let set_exn : 'a . 'a t -> int -> 'a -> unit = fun arr idx v -> if idx < size arr then arr.(idx) <- v else raise (Invalid_argument "out of bounds") let append_exn : 'a . 'a t -> 'a -> unit = fun arr v -> let s = size arr in let c = cap arr in if s = c then failwith "cannot extend array! size = capacity" else (* put the new item one after the last item, increment * the size by 1 *) (arr.(s) <- v; incr_size arr) let pop_exn : 'a . 'a t -> 'a = fun arr -> let s = size arr in if size arr = 0 then failwith "cannot pop from empty array" else let item = arr.(-1 + s) in (* shrink the array, re-zero the discarded element *) (decr_size arr; arr.(-1 + s) <- (Obj.magic 0); item)