--------------------------------------------------------------------------- Distribution of RES Automatically Resizing Contiguous Memory for OCaml --------------------------------------------------------------------------- Prerequisites YOU WILL NEED GNU-MAKE TO COMPILE THE SYSTEM WITH THE DISTRIBUTED MAKEFILES --------------------------------------------------------------------------- Contents of this distribution Changes - History of code changes. INSTALL - Short notes on compiling and installing the library LICENSE - A copy of the "GNU LESSER GENERAL PUBLIC LICENSE" Makefile - Top Makefile OcamlMakefile - Makefile for easy handling of compilation of not so easy OCaml-projects. It generates dependencies of Ocaml-files automatically, is able to handle "ocamllex"-, "ocamlyacc"-, IDL- and C-files and generates native- or byte-code, as executable or as library - with thread-support if you want! README - this file examples/ lib/ - Implementation of the RES-library. --------------------------------------------------------------------------- What is it? This OCaml-library consists of a set of modules which implement automatically resizing (= reallocating) datastructures 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. --------------------------------------------------------------------------- Why should you use it? For several reasons: * Fast constant-time access to indexed elements (e.g. in arrays and strings) is often a prerequisite for short execution times of programs. Still, operations like adding and/or removing elements to/from the end of such datastructures are often needed. Unfortunately, having both properties at the same time sometimes requires reallocating this contiguous part of memory. This module does not eliminate this problem, but hides the process of reallocation from the user, i.e. it happens automatically. Thus, the user is liberated from this bug-attracting (e.g. index errors) task. * This library allows the user to parameterize allocation strategies at runtime. This is a very important feature, because it is impossible for any allocation algorithm to perform optimally without having knowledge about the user program. For example, the programmer might know that a consecutive series of operations will alternately add and remove large amounts of elements. In such a case it would be wise to keep a high reserve of available slots in the datastructure, because otherwise it will resize very often during this procedure which requires a significant amount of time. By raising a corresponding threshold in appropriate places at runtime, the programmer can fine-tune the behaviour of e.g. his buffers for optimal performance and set this parameter back later to save memory. * Because reallocation strategies themselves may be quite complicated, it was also a design goal to have the user supply his own ones (if required). By using functors the user can parameterize these datastructures with his own reallocation strategies, giving him even more control over how and when reallocations are triggered. * It is possible that the user wants to add support for additional low-level implementations that require reallocations. Even in this case it is fairly easy to create new modules by using functors. * The library implements a large interface of functions, all of which are completely independent of the reallocation strategy and the low-level implementation. All the interfaces of the corresponding low-level implementations of datastructures (e.g. array, string) are fully supported and have been extended with further functionality. There is even a new buffer module which can be used in every context of the standard one. * OCaml makes a distinction between unboxed and boxed arrays. If the type of an array is "float", the representation will be unboxed in cases in which the array is not used in a polymorphic context (native code only). To benefit from these much faster representations there are specialized versions of automatically resizing arrays in the distribution. --------------------------------------------------------------------------- Documentation of Functions 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 of "res.ml". Their function interface, however, is documented in files "lib/pres_intf.mli" (for parameterized "low-level" types like e.g. normal arrays) and in "lib/nopres_intf.mli" (for non-parameterized "low-level" types like e.g. int arrays, strings (buffers), ...). This was done so as not do confuse people with too large an interface description in one file. It is advisable to keep all of these files at some specific location at hand for quick information. --------------------------------------------------------------------------- Hints for Convenient Use 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 each such structure to 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 open 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, you should read the following: You should "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 explicitely: 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 builtin 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. --------------------------------------------------------------------------- Up-to-date information (newest release of distribution) can always be found at: http://www.ocaml.info/home/ocaml_sources.html --------------------------------------------------------------------------- Enjoy! Vienna, 2002-09-11 Markus Mottl e-mail: markus.mottl@gmail.com WWW: http://www.ocaml.info