1
(**************************************************************************)
3
(* Copyright (C) 2001-2003, *)
4
(* George C. Necula <necula@cs.berkeley.edu> *)
5
(* Scott McPeak <smcpeak@cs.berkeley.edu> *)
6
(* Wes Weimer <weimer@cs.berkeley.edu> *)
7
(* Ben Liblit <liblit@cs.berkeley.edu> *)
8
(* All rights reserved. *)
10
(* Redistribution and use in source and binary forms, with or without *)
11
(* modification, are permitted provided that the following conditions *)
14
(* 1. Redistributions of source code must retain the above copyright *)
15
(* notice, this list of conditions and the following disclaimer. *)
17
(* 2. Redistributions in binary form must reproduce the above copyright *)
18
(* notice, this list of conditions and the following disclaimer in the *)
19
(* documentation and/or other materials provided with the distribution. *)
21
(* 3. The names of the contributors may not be used to endorse or *)
22
(* promote products derived from this software without specific prior *)
23
(* written permission. *)
25
(* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS *)
26
(* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT *)
27
(* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS *)
28
(* FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE *)
29
(* COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, *)
30
(* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, *)
31
(* BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; *)
32
(* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER *)
33
(* CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT *)
34
(* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN *)
35
(* ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE *)
36
(* POSSIBILITY OF SUCH DAMAGE. *)
38
(* File modified by CEA (Commissariat � l'�nergie Atomique). *)
39
(**************************************************************************)
43
* Copyright (c) 2001-2002,
44
* George C. Necula <necula@cs.berkeley.edu>
45
* Scott McPeak <smcpeak@cs.berkeley.edu>
46
* Wes Weimer <weimer@cs.berkeley.edu>
47
* All rights reserved.
49
* Redistribution and use in source and binary forms, with or without
50
* modification, are permitted provided that the following conditions are
53
* 1. Redistributions of source code must retain the above copyright
54
* notice, this list of conditions and the following disclaimer.
56
* 2. Redistributions in binary form must reproduce the above copyright
57
* notice, this list of conditions and the following disclaimer in the
58
* documentation and/or other materials provided with the distribution.
60
* 3. The names of the contributors may not be used to endorse or promote
61
* products derived from this software without specific prior written
64
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
65
* IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
66
* TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
67
* PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
68
* OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
69
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
70
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
71
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
72
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
73
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
74
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
78
(** Utilities for managing "concatenable lists" (clists). We often need to
79
concatenate sequences, and using lists for this purpose is expensive. This
80
module provides routines to manage such lists more efficiently. In this
81
model, we never do cons or append explicitly. Instead we maintain
82
the elements of the list in a special data structure. Routines are provided
83
to convert to/from ordinary lists, and carry out common list operations.*)
85
(** The clist datatype. A clist can be an ordinary list, or a clist preceded
86
or followed by an element, or two clists implicitly appended together*)
88
| CList of 'a list (** The only representation for the empty
89
list. Try to use sparingly. *)
90
| CConsL of 'a * 'a clist (** Do not use this a lot because scanning
91
* it is not tail recursive *)
92
| CConsR of 'a clist * 'a
93
| CSeq of 'a clist * 'a clist (** We concatenate only two of them at this
94
time. Neither is the empty clist. To be
95
sure always use append to make these *)
98
(** Convert a clist to an ordinary list *)
99
val toList: 'a clist -> 'a list
101
(** Convert an ordinary list to a clist *)
102
val fromList: 'a list -> 'a clist
104
(** Create a clist containing one element *)
105
val single: 'a -> 'a clist
107
(** The empty clist *)
111
(** Append two clists *)
112
val append: 'a clist -> 'a clist -> 'a clist
114
(** A useful check to assert before an append. It checks that the two lists
115
* are not identically the same (Except if they are both empty) *)
116
val checkBeforeAppend: 'a clist -> 'a clist -> bool
118
(** Find the length of a clist *)
119
val length: 'a clist -> int
121
(** Map a function over a clist. Returns another clist *)
122
val map: ('a -> 'b) -> 'a clist -> 'b clist
125
(** A version of fold_left that works on clists *)
126
val fold_left: ('acc -> 'a -> 'acc) -> 'acc -> 'a clist -> 'acc
128
(** A version of iter that works on clists *)
129
val iter: ('a -> unit) -> 'a clist -> unit
131
(** Reverse a clist. The first function reverses an element. *)
132
val rev: ('a -> 'a) -> 'a clist -> 'a clist
134
(** A document for printing a clist (similar to [docList]) *)
136
Pretty.doc -> ('a -> Pretty.doc) -> unit -> 'a clist -> Pretty.doc
added
removed
cil/ocamlutil/clist.mli
