diff options
Diffstat (limited to 'cil/ocamlutil/clist.mli')
| -rw-r--r-- | cil/ocamlutil/clist.mli | 97 |
1 files changed, 97 insertions, 0 deletions
diff --git a/cil/ocamlutil/clist.mli b/cil/ocamlutil/clist.mli new file mode 100644 index 0000000..c0378a6 --- /dev/null +++ b/cil/ocamlutil/clist.mli @@ -0,0 +1,97 @@ +(* + * + * Copyright (c) 2001-2002, + * George C. Necula <necula@cs.berkeley.edu> + * Scott McPeak <smcpeak@cs.berkeley.edu> + * Wes Weimer <weimer@cs.berkeley.edu> + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * 3. The names of the contributors may not be used to endorse or promote + * products derived from this software without specific prior written + * permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS + * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED + * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A + * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER + * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * + *) + +(** Utilities for managing "concatenable lists" (clists). We often need to + concatenate sequences, and using lists for this purpose is expensive. This + module provides routines to manage such lists more efficiently. In this + model, we never do cons or append explicitly. Instead we maintain + the elements of the list in a special data structure. Routines are provided + to convert to/from ordinary lists, and carry out common list operations.*) + +(** The clist datatype. A clist can be an ordinary list, or a clist preceded + or followed by an element, or two clists implicitly appended together*) +type 'a clist = + | CList of 'a list (** The only representation for the empty + list. Try to use sparingly. *) + | CConsL of 'a * 'a clist (** Do not use this a lot because scanning + * it is not tail recursive *) + | CConsR of 'a clist * 'a + | CSeq of 'a clist * 'a clist (** We concatenate only two of them at this + time. Neither is the empty clist. To be + sure always use append to make these *) + + +(** Convert a clist to an ordinary list *) +val toList: 'a clist -> 'a list + +(** Convert an ordinary list to a clist *) +val fromList: 'a list -> 'a clist + +(** Create a clist containing one element *) +val single: 'a -> 'a clist + +(** The empty clist *) +val empty: 'a clist + + +(** Append two clists *) +val append: 'a clist -> 'a clist -> 'a clist + +(** A useful check to assert before an append. It checks that the two lists + * are not identically the same (Except if they are both empty) *) +val checkBeforeAppend: 'a clist -> 'a clist -> bool + +(** Find the length of a clist *) +val length: 'a clist -> int + +(** Map a function over a clist. Returns another clist *) +val map: ('a -> 'b) -> 'a clist -> 'b clist + + +(** A version of fold_left that works on clists *) +val fold_left: ('acc -> 'a -> 'acc) -> 'acc -> 'a clist -> 'acc + +(** A version of iter that works on clists *) +val iter: ('a -> unit) -> 'a clist -> unit + +(** Reverse a clist. The first function reverses an element. *) +val rev: ('a -> 'a) -> 'a clist -> 'a clist + +(** A document for printing a clist (similar to [docList]) *) +val docCList: + Pretty.doc -> ('a -> Pretty.doc) -> unit -> 'a clist -> Pretty.doc + |