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   };