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.
Anywhere, 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 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 t -> int = fun arr -> (Obj.magic arr.(size_idx arr)) (* NOTE: incr_size is not checked and not safe *) let incr_size : '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 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 t -> int -> 'a = fun arr idx -> if idx < size arr then arr.(idx) else raise (Invalid_argument "out of bounds") let get_opt : 'a t -> int -> 'a option = fun arr idx -> if idx < size arr then Some arr.(idx) else None let set_exn : '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 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 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)
✓ Extra quality
ExtraProxies brings the best proxy quality for you with our private and reliable proxies
✓ Extra anonymity
Top level of anonymity and 100% safe proxies – this is what you get with every proxy package
✓ Extra speed
1,ooo mb/s proxy servers speed – we are way better than others – just enjoy our proxies!
USA proxy location
We offer premium quality USA private proxies – the most essential proxies you can ever want from USA
Our proxies have TOP level of anonymity + Elite quality, so you are always safe and secure with your proxies
Use your proxies as much as you want – we have no limits for data transfer and bandwidth, unlimited usage!
Superb fast proxy servers with 1,000 mb/s speed – sit back and enjoy your lightning fast private proxies!
99,9% servers uptime
Alive and working proxies all the time – we are taking care of our servers so you can use them without any problems
No usage restrictions
You have freedom to use your proxies with every software, browser or website you want without restrictions
Perfect for SEO
We are 100% friendly with all SEO tasks as well as internet marketing – feel the power with our proxies
Buy more proxies and get better price – we offer various proxy packages with great deals and discounts
We are working 24/7 to bring the best proxy experience for you – we are glad to help and assist you!