RES - Automatically Resizing Contiguous Memory for OCaml


What is RES?

This OCaml-library consists of a set of modules which implement automatically resizing (= reallocating) data structures that consume a contiguous part of memory. This allows appending and removing of elements to/from arrays (both boxed and unboxed), strings (buffers), bit strings and weak arrays while still maintaining fast constant-time access to elements.

There are also functors that allow the generation of similar modules which use different reallocation strategies.

Features

Usage

The API is fully documented and can be built as HTML using make doc. It is also available online.

The preparameterized modules (default strategy) and the functors for mapping strategy-implementations to this kind of modules are contained and documented in file lib/res.mli.

For examples of how to use the functors to implement new strategies and/or low-level representations, take a look at the implementation in lib/res.ml.

Their function interface, however, is documented in files lib/pres_intf.ml (for parameterized "low-level" types like e.g. normal arrays) and in lib/nopres_intf.ml (for non-parameterized "low-level" types like e.g. float arrays, strings (buffers), etc.).

Convenience

It should be noted that it is possible to use the standard notation for accessing elements (e.g. ar.(42)) with resizable arrays (and even with Buffer, Bits, etc...). This requires a short explanation of how OCaml treats such syntactic sugar:

All that OCaml does is that it replaces such syntax with an appropriate Array.get or Array.set. This may be any module that happens to be bound to this name in the current scope. The same principle is true for the String-module and the .[]-operator.

Thus, the following works:

module Array = Res.Bits
module String = Res.Buffer

let () =
  let ar = Array.empty () in
  Array.add_one ar true;
  print_endline (string_of_bool ar.(0));
  let str = String.empty () in
  String.add_one str 'x';
  print_char str.[0];
  print_newline ()

Do not forget that it is even possible to bind modules locally. Example:

let () =
  let module Array = Res.Array in
  Printf.printf "%d\n" (Array.init 10 (fun x -> x * x)).(7)

If you want to change one of your files to make use of resizable arrays instead of standard ones without much trouble, please read the following:

You may want to "save" the standard Array-module and its type for later access:

module StdArray = Array
type 'a std_array = 'a array

Make the resizable implementation (includes the index operators!) available:

open Res

Or more explicitly:

module Array = Res.Array

Or if you want to use a specific Array-implementation:

module Array = Res.Bits

Then set the type:

type 'a array = 'a Array.t

If you create standard arrays with the built-in syntax, change lines like:

let ar = [| 1; 2; 3; 4 |] in

to:

let ar = Array.of_array [| 1; 2; 3; 4 |] in

This should allow all of your sources to compile out-of-the-box with the additional functionality. In places where you still need the standard implementation you should have no problems to use the rebound module and type to do so.

This trick works similarly for the old and the new Buffer-module. You might also want to replace the String-module in this fashion. The latter one, however, supports a number of functions like e.g. escape, which are not available then.


Contact Information and Contributing

In the case of bugs, feature requests, contributions and similar, you can contact me here: markus.mottl@gmail.com

Up-to-date information should be available at: http://mmottl.github.io/res

Enjoy!

Markus Mottl on July 10, 2012