gui: Fix behavior of print preview in psppire-output-window.
[pspp] / src / libpspp / sparse-xarray.c
1 /* PSPP - a program for statistical analysis.
2    Copyright (C) 2007, 2009, 2010, 2011 Free Software Foundation, Inc.
3
4    This program is free software: you can redistribute it and/or modify
5    it under the terms of the GNU General Public License as published by
6    the Free Software Foundation, either version 3 of the License, or
7    (at your option) any later version.
8
9    This program is distributed in the hope that it will be useful,
10    but WITHOUT ANY WARRANTY; without even the implied warranty of
11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12    GNU 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, see <http://www.gnu.org/licenses/>. */
16
17 #include <config.h>
18
19 #include "libpspp/sparse-xarray.h"
20
21 #include <limits.h>
22 #include <stdint.h>
23 #include <stdlib.h>
24 #include <string.h>
25
26 #include "libpspp/assertion.h"
27 #include "libpspp/ext-array.h"
28 #include "libpspp/misc.h"
29 #include "libpspp/range-set.h"
30 #include "libpspp/sparse-array.h"
31
32 #include "gl/md4.h"
33 #include "gl/minmax.h"
34 #include "gl/xalloc.h"
35
36 /* A sparse array of arrays of bytes. */
37 struct sparse_xarray
38   {
39     size_t n_bytes;                     /* Number of bytes per row. */
40     uint8_t *default_row;               /* Defaults for unwritten rows. */
41     unsigned long int max_memory_rows;  /* Max rows before dumping to disk. */
42     struct sparse_array *memory;        /* Backing, if stored in memory. */
43     struct ext_array *disk;             /* Backing, if stored on disk. */
44     struct range_set *disk_rows;        /* Allocated rows, if on disk. */
45   };
46
47 static bool UNUSED
48 range_is_valid (const struct sparse_xarray *sx, size_t ofs, size_t n)
49 {
50   return n <= sx->n_bytes && ofs <= sx->n_bytes && ofs + n <= sx->n_bytes;
51 }
52
53 /* Creates and returns a new sparse array of arrays of bytes.
54    Each row in the sparse array will consist of N_BYTES bytes.
55    If fewer than MAX_MEMORY_ROWS rows are added to the array,
56    then it will be kept in memory; if more than that are added,
57    then it will be stored on disk. */
58 struct sparse_xarray *
59 sparse_xarray_create (size_t n_bytes, size_t max_memory_rows)
60 {
61   struct sparse_xarray *sx = xmalloc (sizeof *sx);
62   sx->n_bytes = n_bytes;
63   sx->default_row = xzalloc (n_bytes);
64   sx->max_memory_rows = max_memory_rows;
65   sx->memory = sparse_array_create (sizeof (uint8_t *));
66   sx->disk = NULL;
67   sx->disk_rows = NULL;
68   return sx;
69 }
70
71 /* Creates and returns a new sparse array of rows that contains
72    the same data as OLD.  Returns a null pointer if cloning
73    fails. */
74 struct sparse_xarray *
75 sparse_xarray_clone (const struct sparse_xarray *old)
76 {
77   struct sparse_xarray *new = xmalloc (sizeof *new);
78
79   new->n_bytes = old->n_bytes;
80
81   new->default_row = xmemdup (old->default_row, old->n_bytes);
82
83   new->max_memory_rows = old->max_memory_rows;
84
85   if (old->memory != NULL)
86     {
87       unsigned long int idx;
88       uint8_t **old_row;
89
90       new->memory = sparse_array_create (sizeof (uint8_t *));
91       for (old_row = sparse_array_first (old->memory, &idx); old_row != NULL;
92            old_row = sparse_array_next (old->memory, idx, &idx))
93         {
94           uint8_t **new_row = sparse_array_insert (new->memory, idx);
95           *new_row = xmemdup (*old_row, new->n_bytes);
96         }
97     }
98   else
99     new->memory = NULL;
100
101   if (old->disk != NULL)
102     {
103       const struct range_set_node *node;
104       void *tmp = xmalloc (old->n_bytes);
105
106       new->disk = ext_array_create ();
107       new->disk_rows = range_set_clone (old->disk_rows, NULL);
108       for (node = range_set_first (old->disk_rows); node != NULL;
109            node = range_set_next (old->disk_rows, node))
110         {
111           unsigned long int start = range_set_node_get_start (node);
112           unsigned long int end = range_set_node_get_end (node);
113           unsigned long int idx;
114
115           for (idx = start; idx < end; idx++)
116             {
117               off_t offset = (off_t) idx * old->n_bytes;
118               if (!ext_array_read (old->disk, offset, old->n_bytes, tmp)
119                   || !ext_array_write (new->disk, offset, old->n_bytes, tmp))
120                 {
121                   free (tmp);
122                   sparse_xarray_destroy (new);
123                   return NULL;
124                 }
125             }
126         }
127       free (tmp);
128     }
129   else
130     {
131       new->disk = NULL;
132       new->disk_rows = NULL;
133     }
134
135   return new;
136 }
137
138 /* Destroys sparse array of rows SX. */
139 void
140 sparse_xarray_destroy (struct sparse_xarray *sx)
141 {
142   if (sx != NULL)
143     {
144       free (sx->default_row);
145       if (sx->memory != NULL)
146         {
147           unsigned long int idx;
148           uint8_t **row;
149           for (row = sparse_array_first (sx->memory, &idx); row != NULL;
150                row = sparse_array_next (sx->memory, idx, &idx))
151             free (*row);
152           sparse_array_destroy (sx->memory);
153         }
154       ext_array_destroy (sx->disk);
155       range_set_destroy (sx->disk_rows);
156       free (sx);
157     }
158 }
159
160 /* Returns the number of bytes in each row in SX. */
161 size_t
162 sparse_xarray_get_n_columns (const struct sparse_xarray *sx)
163 {
164   return sx->n_bytes;
165 }
166
167 /* Returns the number of rows in SX. */
168 size_t
169 sparse_xarray_get_n_rows (const struct sparse_xarray *sx)
170 {
171   if (sx->memory)
172     {
173       unsigned long int idx;
174       return sparse_array_last (sx->memory, &idx) != NULL ? idx + 1 : 0;
175     }
176   else
177     {
178       const struct range_set_node *last = range_set_last (sx->disk_rows);
179       return last != NULL ? range_set_node_get_end (last) : 0;
180     }
181 }
182
183 /* Dumps the rows in SX, which must currently be stored in
184    memory, to disk.  Returns true if successful, false on I/O
185    error. */
186 static bool
187 dump_sparse_xarray_to_disk (struct sparse_xarray *sx)
188 {
189   unsigned long int idx;
190   uint8_t **row;
191
192   assert (sx->memory != NULL);
193   assert (sx->disk == NULL);
194
195   sx->disk = ext_array_create ();
196   sx->disk_rows = range_set_create ();
197
198   for (row = sparse_array_first (sx->memory, &idx); row != NULL;
199        row = sparse_array_next (sx->memory, idx, &idx))
200     {
201       if (!ext_array_write (sx->disk, (off_t) idx * sx->n_bytes, sx->n_bytes,
202                           *row))
203         {
204           ext_array_destroy (sx->disk);
205           sx->disk = NULL;
206           range_set_destroy (sx->disk_rows);
207           sx->disk_rows = NULL;
208           return false;
209         }
210       range_set_insert (sx->disk_rows, idx, 1);
211     }
212   sparse_array_destroy (sx->memory);
213   sx->memory = NULL;
214   return true;
215 }
216
217 /* Returns true if any data has ever been written to ROW in SX,
218    false otherwise. */
219 bool
220 sparse_xarray_contains_row (const struct sparse_xarray *sx,
221                             unsigned long int row)
222 {
223   return (sx->memory != NULL
224           ? sparse_array_get (sx->memory, row) != NULL
225           : range_set_contains (sx->disk_rows, row));
226 }
227
228 /* Reads columns COLUMNS...(COLUMNS + VALUE_CNT), exclusive, in
229    the given ROW in SX, into the VALUE_CNT values in VALUES.
230    Returns true if successful, false on I/O error. */
231 bool
232 sparse_xarray_read (const struct sparse_xarray *sx, unsigned long int row,
233                     size_t start, size_t n, void *data)
234 {
235   assert (range_is_valid (sx, start, n));
236
237   if (sx->memory != NULL)
238     {
239       uint8_t **p = sparse_array_get (sx->memory, row);
240       if (p != NULL)
241         {
242           memcpy (data, *p + start, n);
243           return true;
244         }
245     }
246   else
247     {
248       if (range_set_contains (sx->disk_rows, row))
249         return ext_array_read (sx->disk, (off_t) row * sx->n_bytes + start,
250                                n, data);
251     }
252
253   memcpy (data, sx->default_row + start, n);
254   return true;
255 }
256
257 /* Implements sparse_xarray_write for an on-disk sparse_xarray. */
258 static bool
259 write_disk_row (struct sparse_xarray *sx, unsigned long int row,
260                 size_t start, size_t n, const void *data)
261 {
262   off_t ofs = (off_t) row * sx->n_bytes;
263   if (range_set_contains (sx->disk_rows, row))
264     return ext_array_write (sx->disk, ofs + start, n, data);
265   else
266     {
267       range_set_insert (sx->disk_rows, row, 1);
268       return (ext_array_write (sx->disk, ofs, start, sx->default_row)
269               && ext_array_write (sx->disk, ofs + start, n, data)
270               && ext_array_write (sx->disk, ofs + start + n,
271                                   sx->n_bytes - start - n,
272                                   sx->default_row + start + n));
273     }
274 }
275
276 /* Writes the VALUE_CNT values in VALUES into columns
277    COLUMNS...(COLUMNS + VALUE_CNT), exclusive, in the given ROW
278    in SX.
279    Returns true if successful, false on I/O error. */
280 bool
281 sparse_xarray_write (struct sparse_xarray *sx, unsigned long int row,
282                      size_t start, size_t n, const void *data)
283 {
284   assert (range_is_valid (sx, start, n));
285   if (sx->memory != NULL)
286     {
287       uint8_t **p = sparse_array_get (sx->memory, row);
288       if (p == NULL)
289         {
290           if (sparse_array_count (sx->memory) < sx->max_memory_rows)
291             {
292               p = sparse_array_insert (sx->memory, row);
293               *p = xmemdup (sx->default_row, sx->n_bytes);
294             }
295           else
296             {
297               if (!dump_sparse_xarray_to_disk (sx))
298                 return false;
299               return write_disk_row (sx, row, start, n, data);
300             }
301         }
302       memcpy (*p + start, data, n);
303       return true;
304     }
305   else
306     return write_disk_row (sx, row, start, n, data);
307 }
308
309 /* Writes the VALUE_CNT values in VALUES to columns
310    START_COLUMN...(START_COLUMN + VALUE_CNT), exclusive, in every
311    row in SX, even those rows that have not yet been written.
312    Returns true if successful, false on I/O error.
313
314    The runtime of this function is linear in the number of rows
315    in SX that have already been written. */
316 bool
317 sparse_xarray_write_columns (struct sparse_xarray *sx, size_t start,
318                              size_t n, const void *data)
319 {
320   assert (range_is_valid (sx, start, n));
321
322   /* Set defaults. */
323   memcpy (sx->default_row + start, data, n);
324
325   /* Set individual rows. */
326   if (sx->memory != NULL)
327     {
328       unsigned long int idx;
329       uint8_t **p;
330
331       for (p = sparse_array_first (sx->memory, &idx); p != NULL;
332            p = sparse_array_next (sx->memory, idx, &idx))
333         memcpy (*p + start, data, n);
334     }
335   else
336     {
337       const struct range_set_node *node;
338
339       for (node = range_set_first (sx->disk_rows); node != NULL;
340            node = range_set_next (sx->disk_rows, node))
341         {
342           unsigned long int start_row = range_set_node_get_start (node);
343           unsigned long int end_row = range_set_node_get_end (node);
344           unsigned long int row;
345
346           for (row = start_row; row < end_row; row++)
347             {
348               off_t offset = (off_t) row * sx->n_bytes;
349               if (!ext_array_write (sx->disk, offset + start, n, data))
350                 break;
351             }
352         }
353
354       if (ext_array_error (sx->disk))
355         return false;
356     }
357   return true;
358 }
359
360 static unsigned long int
361 scan_first (const struct sparse_xarray *sx)
362 {
363   if (sx->memory)
364     {
365       unsigned long int idx;
366       return sparse_array_first (sx->memory, &idx) ? idx : ULONG_MAX;
367     }
368   else
369     return range_set_scan (sx->disk_rows, 0);
370 }
371
372 static unsigned long int
373 scan_next (const struct sparse_xarray *sx, unsigned long int start)
374 {
375   if (sx->memory)
376     {
377       unsigned long int idx;
378       return sparse_array_next (sx->memory, start, &idx) ? idx : ULONG_MAX;
379     }
380   else
381     return range_set_scan (sx->disk_rows, start + 1);
382 }
383
384 /* Only works for rows for which sparse_xarray_contains_row()
385    would return true. */
386 static uint8_t *
387 get_row (const struct sparse_xarray *sx, unsigned long int idx,
388          uint8_t *buffer)
389 {
390   if (sx->memory)
391     {
392       uint8_t **p = sparse_array_get (sx->memory, idx);
393       return *p;
394     }
395   else if (ext_array_read (sx->disk, (off_t) idx * sx->n_bytes,
396                            sx->n_bytes, buffer))
397     return buffer;
398   else
399     return NULL;
400 }
401
402 /* Iterates over all the rows in SX and DX, passing each pair of
403    rows with equal indexes to CB.  CB's modifications, if any, to
404    destination rows are written back to DX.
405
406    All rows that are actually in use in SX or in DX or both are
407    passed to CB.  If a row is in use in SX but not in DX, or vice
408    versa, then the "default" row (as set by
409    sparse_xarray_write_columns) is passed as the contents of the
410    other row.
411
412    CB is also called once with the default row from SX and the
413    default row from DX.  Modifying the data passed as the default
414    row from DX will change DX's default row.
415
416    Returns true if successful, false if I/O on SX or DX fails or
417    if CB returns false.  On failure, the contents of DX are
418    undefined. */
419 bool
420 sparse_xarray_copy (const struct sparse_xarray *sx, struct sparse_xarray *dx,
421                     bool (*cb) (const void *src, void *dst, void *aux),
422                     void *aux)
423 {
424   bool success = true;
425
426   if (!cb (sx->default_row, dx->default_row, aux))
427     return false;
428
429   if (sx == dx)
430     {
431       if (sx->memory)
432         {
433           unsigned long int idx;
434           uint8_t **row;
435
436           for (row = sparse_array_first (sx->memory, &idx); row != NULL;
437                row = sparse_array_next (sx->memory, idx, &idx))
438             {
439               success = cb (*row, *row, aux);
440               if (!success)
441                 break;
442             }
443         }
444       else if (sx->disk)
445         {
446           const struct range_set_node *node;
447           void *tmp = xmalloc (sx->n_bytes);
448
449           for (node = range_set_first (sx->disk_rows); node != NULL;
450                node = range_set_next (sx->disk_rows, node))
451             {
452               unsigned long int start = range_set_node_get_start (node);
453               unsigned long int end = range_set_node_get_end (node);
454               unsigned long int row;
455
456               for (row = start; row < end; row++)
457                 {
458                   off_t offset = (off_t) row * sx->n_bytes;
459                   success = (ext_array_read (sx->disk, offset, sx->n_bytes,
460                                              tmp)
461                              && cb (tmp, tmp, aux)
462                              && ext_array_write (dx->disk, offset,
463                                                  dx->n_bytes, tmp));
464                   if (!success)
465                     break;
466                 }
467             }
468
469           free (tmp);
470         }
471     }
472   else
473     {
474       unsigned long int src_idx = scan_first (sx);
475       unsigned long int dst_idx = scan_first (dx);
476
477       uint8_t *tmp_src_row = xmalloc (sx->n_bytes);
478       uint8_t *tmp_dst_row = xmalloc (dx->n_bytes);
479
480       for (;;)
481         {
482           unsigned long int idx;
483           const uint8_t *src_row;
484           uint8_t *dst_row;
485
486           /* Determine the index of the row to process.  If
487              src_idx == dst_idx, then the row has been written in
488              both SX and DX.  Otherwise, it has been written in
489              only the sparse_xarray corresponding to the smaller
490              index, and has the default contents in the other. */
491           idx = MIN (src_idx, dst_idx);
492           if (idx == ULONG_MAX)
493             break;
494
495           /* Obtain a copy of the source row as src_row. */
496           if (idx == src_idx)
497             src_row = get_row (sx, idx, tmp_src_row);
498           else
499             src_row = sx->default_row;
500
501           /* Obtain the destination row as dst_row. */
502           if (idx == dst_idx)
503             dst_row = get_row (dx, idx, tmp_dst_row);
504           else if (dx->memory
505                    && sparse_array_count (dx->memory) < dx->max_memory_rows)
506             {
507               uint8_t **p = sparse_array_insert (dx->memory, idx);
508               dst_row = *p = xmemdup (dx->default_row, dx->n_bytes);
509             }
510           else
511             {
512               memcpy (tmp_dst_row, dx->default_row, dx->n_bytes);
513               dst_row = tmp_dst_row;
514             }
515
516           /* Run the callback. */
517           success = cb (src_row, dst_row, aux);
518           if (!success)
519             break;
520
521           /* Write back the destination row, if necessary. */
522           if (dst_row == tmp_dst_row)
523             {
524               success = sparse_xarray_write (dx, idx, 0, dx->n_bytes, dst_row);
525               if (!success)
526                 break;
527             }
528           else
529             {
530               /* Nothing to do: we modified the destination row in-place. */
531             }
532
533           /* Advance to the next row. */
534           if (src_idx == idx)
535             src_idx = scan_next (sx, src_idx);
536           if (dst_idx == idx)
537             dst_idx = scan_next (dx, dst_idx);
538         }
539
540       free (tmp_src_row);
541       free (tmp_dst_row);
542     }
543
544   return success;
545 }
546
547 /* Returns a hash value for SX suitable for use with the model
548    checker.  The value in BASIS is folded into the hash.
549
550    The returned hash value is *not* suitable for storage and
551    retrieval of sparse_xarrays that have identical contents,
552    because it will return different hash values for
553    sparse_xarrays that have the same contents (and it's slow).
554
555    We use MD4 because it is much faster than MD5 or SHA-1 but its
556    collision resistance is just as good. */
557 unsigned int
558 sparse_xarray_model_checker_hash (const struct sparse_xarray *sx,
559                                   unsigned int basis)
560 {
561   unsigned int hash[DIV_RND_UP (20, sizeof (unsigned int))];
562   struct md4_ctx ctx;
563
564   md4_init_ctx (&ctx);
565   md4_process_bytes (&basis, sizeof basis, &ctx);
566   md4_process_bytes (&sx->n_bytes, sizeof sx->n_bytes, &ctx);
567   md4_process_bytes (sx->default_row, sx->n_bytes, &ctx);
568
569   if (sx->memory)
570     {
571       unsigned long int idx;
572       uint8_t **row;
573
574       md4_process_bytes ("m", 1, &ctx);
575       md4_process_bytes (&sx->max_memory_rows, sizeof sx->max_memory_rows,
576                          &ctx);
577       for (row = sparse_array_first (sx->memory, &idx); row != NULL;
578            row = sparse_array_next (sx->memory, idx, &idx))
579         {
580           md4_process_bytes (&idx, sizeof idx, &ctx);
581           md4_process_bytes (*row, sx->n_bytes, &ctx);
582         }
583     }
584   else
585     {
586       const struct range_set_node *node;
587       void *tmp = xmalloc (sx->n_bytes);
588
589       md4_process_bytes ("d", 1, &ctx);
590       for (node = range_set_first (sx->disk_rows); node != NULL;
591            node = range_set_next (sx->disk_rows, node))
592         {
593           unsigned long int start = range_set_node_get_start (node);
594           unsigned long int end = range_set_node_get_end (node);
595           unsigned long int idx;
596
597           for (idx = start; idx < end; idx++)
598             {
599               off_t offset = (off_t) idx * sx->n_bytes;
600               if (!ext_array_read (sx->disk, offset, sx->n_bytes, tmp))
601                 NOT_REACHED ();
602               md4_process_bytes (&idx, sizeof idx, &ctx);
603               md4_process_bytes (tmp, sx->n_bytes, &ctx);
604             }
605         }
606       free (tmp);
607     }
608   md4_finish_ctx (&ctx, hash);
609   return hash[0];
610 }