605b22b7627769b8c3df8d52bbb5eec9875f7003
[pspp-builds.git] / src / data / casewindow.c
1 /* PSPP - computes sample statistics.
2    Copyright (C) 2007 Free Software Foundation, Inc.
3
4    This program is free software; you can redistribute it and/or
5    modify it under the terms of the GNU General Public License as
6    published by the Free Software Foundation; either version 2 of the
7    License, or (at your option) any later version.
8
9    This program is distributed in the hope that it will be useful, but
10    WITHOUT ANY WARRANTY; without even the implied warranty of
11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12    General Public License for more details.
13
14    You should have received a copy of the GNU General Public License
15    along with this program; if not, write to the Free Software
16    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
17    02110-1301, USA. */
18
19 /* This casewindow implementation in terms of an class interface
20    is undoubtedly a form of over-abstraction.  However, it works
21    and the extra abstraction seems to be harmless. */
22
23 #include <config.h>
24
25 #include <data/casewindow.h>
26
27 #include <stdlib.h>
28
29 #include <data/case-tmpfile.h>
30 #include <libpspp/assertion.h>
31 #include <libpspp/compiler.h>
32 #include <libpspp/deque.h>
33 #include <libpspp/taint.h>
34
35 #include "xalloc.h"
36
37 /* A queue of cases. */
38 struct casewindow
39   {
40     /* Common data. */
41     size_t value_cnt;             /* Number of values per case. */
42     casenumber max_in_core_cases; /* Max cases before dumping to disk. */
43     struct taint *taint;          /* Taint status. */
44
45     /* Implementation data. */
46     const struct casewindow_class *class;
47     void *aux;
48   };
49
50 /* Implementation of a casewindow. */
51 struct casewindow_class
52   {
53     void *(*create) (struct taint *, size_t value_cnt);
54     void (*destroy) (void *aux);
55     void (*push_head) (void *aux, struct ccase *);
56     void (*pop_tail) (void *aux, casenumber cnt);
57     bool (*get_case) (void *aux, casenumber ofs, struct ccase *);
58     casenumber (*get_case_cnt) (const void *aux);
59   };
60
61 /* Classes. */
62 static const struct casewindow_class casewindow_memory_class;
63 static const struct casewindow_class casewindow_file_class;
64
65 /* Creates and returns a new casewindow using the given
66    parameters. */
67 static struct casewindow *
68 do_casewindow_create (struct taint *taint,
69                       size_t value_cnt, casenumber max_in_core_cases)
70 {
71   struct casewindow *cw = xmalloc (sizeof *cw);
72   cw->class = (max_in_core_cases
73               ? &casewindow_memory_class
74               : &casewindow_file_class);
75   cw->aux = cw->class->create (taint, value_cnt);
76   cw->value_cnt = value_cnt;
77   cw->max_in_core_cases = max_in_core_cases;
78   cw->taint = taint;
79   return cw;
80 }
81
82 /* Creates and returns a new casewindow for cases with VALUE_CNT
83    values each.  If the casewindow holds more than
84    MAX_IN_CORE_CASES cases at any time, its cases will be dumped
85    to disk; otherwise, its cases will be held in memory. */
86 struct casewindow *
87 casewindow_create (size_t value_cnt, casenumber max_in_core_cases)
88 {
89   return do_casewindow_create (taint_create (), value_cnt, max_in_core_cases);
90 }
91
92 /* Destroys casewindow CW.
93    Returns true if CW was tainted, which is caused by an I/O
94    error or by taint propagation to the casewindow. */
95 bool
96 casewindow_destroy (struct casewindow *cw)
97 {
98   bool ok = true;
99   if (cw != NULL)
100     {
101       cw->class->destroy (cw->aux);
102       ok = taint_destroy (cw->taint);
103       free (cw);
104     }
105   return ok;
106 }
107
108 /* Swaps the contents of casewindows A and B. */
109 static void
110 casewindow_swap (struct casewindow *a, struct casewindow *b)
111 {
112   struct casewindow tmp = *a;
113   *a = *b;
114   *b = tmp;
115 }
116
117 /* Dumps the contents of casewindow OLD to disk. */
118 static void
119 casewindow_to_disk (struct casewindow *old)
120 {
121   struct casewindow *new;
122   new = do_casewindow_create (taint_clone (old->taint), old->value_cnt, 0);
123   while (casewindow_get_case_cnt (old) > 0 && !casewindow_error (new))
124     {
125       struct ccase c;
126       if (!casewindow_get_case (old, 0, &c))
127         break;
128       casewindow_pop_tail (old, 1);
129       casewindow_push_head (new, &c);
130     }
131   casewindow_swap (old, new);
132   casewindow_destroy (new);
133 }
134
135 /* Pushes case C at the head of casewindow CW.
136    Case C becomes owned by the casewindow. */
137 void
138 casewindow_push_head (struct casewindow *cw, struct ccase *c)
139 {
140   if (!casewindow_error (cw))
141     {
142       cw->class->push_head (cw->aux, c);
143       if (!casewindow_error (cw))
144         {
145           casenumber case_cnt = cw->class->get_case_cnt (cw->aux);
146           if (case_cnt > cw->max_in_core_cases
147               && cw->class == &casewindow_memory_class)
148             casewindow_to_disk (cw);
149         }
150     }
151   else
152     case_destroy (c);
153 }
154
155 /* Deletes CASE_CNT cases at the tail of casewindow CW. */
156 void
157 casewindow_pop_tail (struct casewindow *cw, casenumber case_cnt)
158 {
159   if (!casewindow_error (cw))
160     cw->class->pop_tail (cw->aux, case_cnt);
161 }
162
163 /* Copies the case that is CASE_IDX cases away from CW's tail
164    into C.  Returns true if successful, false on an I/O error or
165    if CW is otherwise tainted.  On failure, nullifies case C. */
166 bool
167 casewindow_get_case (const struct casewindow *cw_, casenumber case_idx,
168                      struct ccase *c)
169 {
170   struct casewindow *cw = (struct casewindow *) cw_;
171
172   assert (case_idx >= 0 && case_idx < casewindow_get_case_cnt (cw));
173   if (!casewindow_error (cw))
174     return cw->class->get_case (cw->aux, case_idx, c);
175   else
176     {
177       case_nullify (c);
178       return false;
179     }
180 }
181
182 /* Returns the number of cases in casewindow CW. */
183 casenumber
184 casewindow_get_case_cnt (const struct casewindow *cw)
185 {
186   return cw->class->get_case_cnt (cw->aux);
187 }
188
189 /* Returns the number of values per case in casewindow CW. */
190 size_t
191 casewindow_get_value_cnt (const struct casewindow *cw)
192 {
193   return cw->value_cnt;
194 }
195
196 /* Returns true if casewindow CW is tainted.
197    A casewindow is tainted by an I/O error or by taint
198    propagation to the casewindow. */
199 bool
200 casewindow_error (const struct casewindow *cw)
201 {
202   return taint_is_tainted (cw->taint);
203 }
204
205 /* Marks casewindow CW tainted. */
206 void
207 casewindow_force_error (struct casewindow *cw)
208 {
209   taint_set_taint (cw->taint);
210 }
211
212 /* Returns casewindow CW's taint object. */
213 const struct taint *
214 casewindow_get_taint (const struct casewindow *cw)
215 {
216   return cw->taint;
217 }
218 \f
219 /* In-memory casewindow data. */
220 struct casewindow_memory
221   {
222     struct deque deque;
223     struct ccase *cases;
224   };
225
226 static void *
227 casewindow_memory_create (struct taint *taint UNUSED, size_t value_cnt UNUSED)
228 {
229   struct casewindow_memory *cwm = xmalloc (sizeof *cwm);
230   cwm->cases = deque_init (&cwm->deque, 4, sizeof *cwm->cases);
231   return cwm;
232 }
233
234 static void
235 casewindow_memory_destroy (void *cwm_)
236 {
237   struct casewindow_memory *cwm = cwm_;
238   while (!deque_is_empty (&cwm->deque))
239     case_destroy (&cwm->cases[deque_pop_front (&cwm->deque)]);
240   free (cwm->cases);
241   free (cwm);
242 }
243
244 static void
245 casewindow_memory_push_head (void *cwm_, struct ccase *c)
246 {
247   struct casewindow_memory *cwm = cwm_;
248   if (deque_is_full (&cwm->deque))
249     cwm->cases = deque_expand (&cwm->deque, cwm->cases, sizeof *cwm->cases);
250   case_move (&cwm->cases[deque_push_back (&cwm->deque)], c);
251 }
252
253 static void
254 casewindow_memory_pop_tail (void *cwm_, casenumber case_cnt)
255 {
256   struct casewindow_memory *cwm = cwm_;
257   assert (deque_count (&cwm->deque) >= case_cnt);
258   while (case_cnt-- > 0)
259     case_destroy (&cwm->cases[deque_pop_front (&cwm->deque)]);
260 }
261
262 static bool
263 casewindow_memory_get_case (void *cwm_, casenumber ofs, struct ccase *c)
264 {
265   struct casewindow_memory *cwm = cwm_;
266   case_clone (c, &cwm->cases[deque_front (&cwm->deque, ofs)]);
267   return true;
268 }
269
270 static casenumber
271 casewindow_memory_get_case_cnt (const void *cwm_)
272 {
273   const struct casewindow_memory *cwm = cwm_;
274   return deque_count (&cwm->deque);
275 }
276
277 static const struct casewindow_class casewindow_memory_class =
278   {
279     casewindow_memory_create,
280     casewindow_memory_destroy,
281     casewindow_memory_push_head,
282     casewindow_memory_pop_tail,
283     casewindow_memory_get_case,
284     casewindow_memory_get_case_cnt,
285   };
286 \f
287 /* On-disk casewindow data. */
288 struct casewindow_file
289   {
290     struct case_tmpfile *file;
291     casenumber head, tail;
292   };
293
294 static void *
295 casewindow_file_create (struct taint *taint, size_t value_cnt)
296 {
297   struct casewindow_file *cwf = xmalloc (sizeof *cwf);
298   cwf->file = case_tmpfile_create (value_cnt);
299   cwf->head = cwf->tail = 0;
300   taint_propagate (case_tmpfile_get_taint (cwf->file), taint);
301   return cwf;
302 }
303
304 static void
305 casewindow_file_destroy (void *cwf_)
306 {
307   struct casewindow_file *cwf = cwf_;
308   case_tmpfile_destroy (cwf->file);
309   free (cwf);
310 }
311
312 static void
313 casewindow_file_push_head (void *cwf_, struct ccase *c)
314 {
315   struct casewindow_file *cwf = cwf_;
316   if (case_tmpfile_put_case (cwf->file, cwf->head, c))
317     cwf->head++;
318 }
319
320 static void
321 casewindow_file_pop_tail (void *cwf_, casenumber cnt)
322 {
323   struct casewindow_file *cwf = cwf_;
324   assert (cnt <= cwf->head - cwf->tail);
325   cwf->tail += cnt;
326   if (cwf->head == cwf->tail)
327     cwf->head = cwf->tail = 0;
328 }
329
330 static bool
331 casewindow_file_get_case (void *cwf_, casenumber ofs, struct ccase *c)
332 {
333   struct casewindow_file *cwf = cwf_;
334   return case_tmpfile_get_case (cwf->file, cwf->tail + ofs, c);
335 }
336
337 static casenumber
338 casewindow_file_get_case_cnt (const void *cwf_)
339 {
340   const struct casewindow_file *cwf = cwf_;
341   return cwf->head - cwf->tail;
342 }
343
344 static const struct casewindow_class casewindow_file_class =
345   {
346     casewindow_file_create,
347     casewindow_file_destroy,
348     casewindow_file_push_head,
349     casewindow_file_pop_tail,
350     casewindow_file_get_case,
351     casewindow_file_get_case_cnt,
352   };