src/libpspp/sparse-xarray.c

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2007, 2009, 2010, 2011, 2012 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       RANGE_SET_FOR_EACH (node, old->disk_rows)
 109         {
 110           unsigned long int start = range_set_node_get_start (node);
 111           unsigned long int end = range_set_node_get_end (node);
 112           unsigned long int idx;
 113
 114           for (idx = start; idx < end; idx++)
 115             {
 116               off_t offset = (off_t) idx * old->n_bytes;
 117               if (!ext_array_read (old->disk, offset, old->n_bytes, tmp)
 118                   || !ext_array_write (new->disk, offset, old->n_bytes, tmp))
 119                 {
 120                   free (tmp);
 121                   sparse_xarray_destroy (new);
 122                   return NULL;
 123                 }
 124             }
 125         }
 126       free (tmp);
 127     }
 128   else
 129     {
 130       new->disk = NULL;
 131       new->disk_rows = NULL;
 132     }
 133
 134   return new;
 135 }
 136
 137 static void
 138 free_memory_rows (struct sparse_xarray *sx)
 139 {
 140   if (sx->memory != NULL)
 141     {
 142       unsigned long int idx;
 143       uint8_t **row;
 144       for (row = sparse_array_first (sx->memory, &idx); row != NULL;
 145            row = sparse_array_next (sx->memory, idx, &idx))
 146         free (*row);
 147       sparse_array_destroy (sx->memory);
 148       sx->memory = NULL;
 149     }
 150 }
 151
 152 /* Destroys sparse array of rows SX. */
 153 void
 154 sparse_xarray_destroy (struct sparse_xarray *sx)
 155 {
 156   if (sx != NULL)
 157     {
 158       free (sx->default_row);
 159       free_memory_rows (sx);
 160       ext_array_destroy (sx->disk);
 161       range_set_destroy (sx->disk_rows);
 162       free (sx);
 163     }
 164 }
 165
 166 /* Returns the number of bytes in each row in SX. */
 167 size_t
 168 sparse_xarray_get_n_columns (const struct sparse_xarray *sx)
 169 {
 170   return sx->n_bytes;
 171 }
 172
 173 /* Returns the number of rows in SX. */
 174 size_t
 175 sparse_xarray_get_n_rows (const struct sparse_xarray *sx)
 176 {
 177   if (sx->memory)
 178     {
 179       unsigned long int idx;
 180       return sparse_array_last (sx->memory, &idx) != NULL ? idx + 1 : 0;
 181     }
 182   else
 183     {
 184       const struct range_set_node *last = range_set_last (sx->disk_rows);
 185       return last != NULL ? range_set_node_get_end (last) : 0;
 186     }
 187 }
 188
 189 /* Dumps the rows in SX, which must currently be stored in
 190    memory, to disk.  Returns true if successful, false on I/O
 191    error. */
 192 static bool
 193 dump_sparse_xarray_to_disk (struct sparse_xarray *sx)
 194 {
 195   unsigned long int idx;
 196   uint8_t **row;
 197
 198   assert (sx->memory != NULL);
 199   assert (sx->disk == NULL);
 200
 201   sx->disk = ext_array_create ();
 202   sx->disk_rows = range_set_create ();
 203
 204   for (row = sparse_array_first (sx->memory, &idx); row != NULL;
 205        row = sparse_array_next (sx->memory, idx, &idx))
 206     {
 207       if (!ext_array_write (sx->disk, (off_t) idx * sx->n_bytes, sx->n_bytes,
 208                           *row))
 209         {
 210           ext_array_destroy (sx->disk);
 211           sx->disk = NULL;
 212           range_set_destroy (sx->disk_rows);
 213           sx->disk_rows = NULL;
 214           return false;
 215         }
 216       range_set_set1 (sx->disk_rows, idx, 1);
 217     }
 218   free_memory_rows (sx);
 219   return true;
 220 }
 221
 222 /* Returns true if any data has ever been written to ROW in SX,
 223    false otherwise. */
 224 bool
 225 sparse_xarray_contains_row (const struct sparse_xarray *sx,
 226                             unsigned long int row)
 227 {
 228   return (sx->memory != NULL
 229           ? sparse_array_get (sx->memory, row) != NULL
 230           : range_set_contains (sx->disk_rows, row));
 231 }
 232
 233 /* Reads columns COLUMNS...(COLUMNS + VALUE_CNT), exclusive, in
 234    the given ROW in SX, into the VALUE_CNT values in VALUES.
 235    Returns true if successful, false on I/O error. */
 236 bool
 237 sparse_xarray_read (const struct sparse_xarray *sx, unsigned long int row,
 238                     size_t start, size_t n, void *data)
 239 {
 240   assert (range_is_valid (sx, start, n));
 241
 242   if (sx->memory != NULL)
 243     {
 244       uint8_t **p = sparse_array_get (sx->memory, row);
 245       if (p != NULL)
 246         {
 247           memcpy (data, *p + start, n);
 248           return true;
 249         }
 250     }
 251   else
 252     {
 253       if (range_set_contains (sx->disk_rows, row))
 254         return ext_array_read (sx->disk, (off_t) row * sx->n_bytes + start,
 255                                n, data);
 256     }
 257
 258   memcpy (data, sx->default_row + start, n);
 259   return true;
 260 }
 261
 262 /* Implements sparse_xarray_write for an on-disk sparse_xarray. */
 263 static bool
 264 write_disk_row (struct sparse_xarray *sx, unsigned long int row,
 265                 size_t start, size_t n, const void *data)
 266 {
 267   off_t ofs = (off_t) row * sx->n_bytes;
 268   if (range_set_contains (sx->disk_rows, row))
 269     return ext_array_write (sx->disk, ofs + start, n, data);
 270   else
 271     {
 272       range_set_set1 (sx->disk_rows, row, 1);
 273       return (ext_array_write (sx->disk, ofs, start, sx->default_row)
 274               && ext_array_write (sx->disk, ofs + start, n, data)
 275               && ext_array_write (sx->disk, ofs + start + n,
 276                                   sx->n_bytes - start - n,
 277                                   sx->default_row + start + n));
 278     }
 279 }
 280
 281 /* Writes the VALUE_CNT values in VALUES into columns
 282    COLUMNS...(COLUMNS + VALUE_CNT), exclusive, in the given ROW
 283    in SX.
 284    Returns true if successful, false on I/O error. */
 285 bool
 286 sparse_xarray_write (struct sparse_xarray *sx, unsigned long int row,
 287                      size_t start, size_t n, const void *data)
 288 {
 289   assert (range_is_valid (sx, start, n));
 290   if (sx->memory != NULL)
 291     {
 292       uint8_t **p = sparse_array_get (sx->memory, row);
 293       if (p == NULL)
 294         {
 295           if (sparse_array_count (sx->memory) < sx->max_memory_rows)
 296             {
 297               p = sparse_array_insert (sx->memory, row);
 298               *p = xmemdup (sx->default_row, sx->n_bytes);
 299             }
 300           else
 301             {
 302               if (!dump_sparse_xarray_to_disk (sx))
 303                 return false;
 304               return write_disk_row (sx, row, start, n, data);
 305             }
 306         }
 307       memcpy (*p + start, data, n);
 308       return true;
 309     }
 310   else
 311     return write_disk_row (sx, row, start, n, data);
 312 }
 313
 314 /* Writes the VALUE_CNT values in VALUES to columns
 315    START_COLUMN...(START_COLUMN + VALUE_CNT), exclusive, in every
 316    row in SX, even those rows that have not yet been written.
 317    Returns true if successful, false on I/O error.
 318
 319    The runtime of this function is linear in the number of rows
 320    in SX that have already been written. */
 321 bool
 322 sparse_xarray_write_columns (struct sparse_xarray *sx, size_t start,
 323                              size_t n, const void *data)
 324 {
 325   assert (range_is_valid (sx, start, n));
 326
 327   /* Set defaults. */
 328   memcpy (sx->default_row + start, data, n);
 329
 330   /* Set individual rows. */
 331   if (sx->memory != NULL)
 332     {
 333       unsigned long int idx;
 334       uint8_t **p;
 335
 336       for (p = sparse_array_first (sx->memory, &idx); p != NULL;
 337            p = sparse_array_next (sx->memory, idx, &idx))
 338         memcpy (*p + start, data, n);
 339     }
 340   else
 341     {
 342       const struct range_set_node *node;
 343
 344       RANGE_SET_FOR_EACH (node, sx->disk_rows)
 345         {
 346           unsigned long int start_row = range_set_node_get_start (node);
 347           unsigned long int end_row = range_set_node_get_end (node);
 348           unsigned long int row;
 349
 350           for (row = start_row; row < end_row; row++)
 351             {
 352               off_t offset = (off_t) row * sx->n_bytes;
 353               if (!ext_array_write (sx->disk, offset + start, n, data))
 354                 break;
 355             }
 356         }
 357
 358       if (ext_array_error (sx->disk))
 359         return false;
 360     }
 361   return true;
 362 }
 363
 364 static unsigned long int
 365 scan_first (const struct sparse_xarray *sx)
 366 {
 367   if (sx->memory)
 368     {
 369       unsigned long int idx;
 370       return sparse_array_first (sx->memory, &idx) ? idx : ULONG_MAX;
 371     }
 372   else
 373     return range_set_scan (sx->disk_rows, 0);
 374 }
 375
 376 static unsigned long int
 377 scan_next (const struct sparse_xarray *sx, unsigned long int start)
 378 {
 379   if (sx->memory)
 380     {
 381       unsigned long int idx;
 382       return sparse_array_next (sx->memory, start, &idx) ? idx : ULONG_MAX;
 383     }
 384   else
 385     return range_set_scan (sx->disk_rows, start + 1);
 386 }
 387
 388 /* Only works for rows for which sparse_xarray_contains_row()
 389    would return true. */
 390 static uint8_t *
 391 get_row (const struct sparse_xarray *sx, unsigned long int idx,
 392          uint8_t *buffer)
 393 {
 394   if (sx->memory)
 395     {
 396       uint8_t **p = sparse_array_get (sx->memory, idx);
 397       return *p;
 398     }
 399   else if (ext_array_read (sx->disk, (off_t) idx * sx->n_bytes,
 400                            sx->n_bytes, buffer))
 401     return buffer;
 402   else
 403     return NULL;
 404 }
 405
 406 /* Iterates over all the rows in SX and DX, passing each pair of
 407    rows with equal indexes to CB.  CB's modifications, if any, to
 408    destination rows are written back to DX.
 409
 410    All rows that are actually in use in SX or in DX or both are
 411    passed to CB.  If a row is in use in SX but not in DX, or vice
 412    versa, then the "default" row (as set by
 413    sparse_xarray_write_columns) is passed as the contents of the
 414    other row.
 415
 416    CB is also called once with the default row from SX and the
 417    default row from DX.  Modifying the data passed as the default
 418    row from DX will change DX's default row.
 419
 420    Returns true if successful, false if I/O on SX or DX fails or
 421    if CB returns false.  On failure, the contents of DX are
 422    undefined. */
 423 bool
 424 sparse_xarray_copy (const struct sparse_xarray *sx, struct sparse_xarray *dx,
 425                     bool (*cb) (const void *src, void *dst, void *aux),
 426                     void *aux)
 427 {
 428   bool success = true;
 429
 430   if (!cb (sx->default_row, dx->default_row, aux))
 431     return false;
 432
 433   if (sx == dx)
 434     {
 435       if (sx->memory)
 436         {
 437           unsigned long int idx;
 438           uint8_t **row;
 439
 440           for (row = sparse_array_first (sx->memory, &idx); row != NULL;
 441                row = sparse_array_next (sx->memory, idx, &idx))
 442             {
 443               success = cb (*row, *row, aux);
 444               if (!success)
 445                 break;
 446             }
 447         }
 448       else if (sx->disk)
 449         {
 450           const struct range_set_node *node;
 451           void *tmp = xmalloc (sx->n_bytes);
 452
 453           RANGE_SET_FOR_EACH (node, sx->disk_rows)
 454             {
 455               unsigned long int start = range_set_node_get_start (node);
 456               unsigned long int end = range_set_node_get_end (node);
 457               unsigned long int row;
 458
 459               for (row = start; row < end; row++)
 460                 {
 461                   off_t offset = (off_t) row * sx->n_bytes;
 462                   success = (ext_array_read (sx->disk, offset, sx->n_bytes,
 463                                              tmp)
 464                              && cb (tmp, tmp, aux)
 465                              && ext_array_write (dx->disk, offset,
 466                                                  dx->n_bytes, tmp));
 467                   if (!success)
 468                     break;
 469                 }
 470             }
 471
 472           free (tmp);
 473         }
 474     }
 475   else
 476     {
 477       unsigned long int src_idx = scan_first (sx);
 478       unsigned long int dst_idx = scan_first (dx);
 479
 480       uint8_t *tmp_src_row = xmalloc (sx->n_bytes);
 481       uint8_t *tmp_dst_row = xmalloc (dx->n_bytes);
 482
 483       for (;;)
 484         {
 485           unsigned long int idx;
 486           const uint8_t *src_row;
 487           uint8_t *dst_row;
 488
 489           /* Determine the index of the row to process.  If
 490              src_idx == dst_idx, then the row has been written in
 491              both SX and DX.  Otherwise, it has been written in
 492              only the sparse_xarray corresponding to the smaller
 493              index, and has the default contents in the other. */
 494           idx = MIN (src_idx, dst_idx);
 495           if (idx == ULONG_MAX)
 496             break;
 497
 498           /* Obtain a copy of the source row as src_row. */
 499           if (idx == src_idx)
 500             src_row = get_row (sx, idx, tmp_src_row);
 501           else
 502             src_row = sx->default_row;
 503
 504           /* Obtain the destination row as dst_row. */
 505           if (idx == dst_idx)
 506             dst_row = get_row (dx, idx, tmp_dst_row);
 507           else if (dx->memory
 508                    && sparse_array_count (dx->memory) < dx->max_memory_rows)
 509             {
 510               uint8_t **p = sparse_array_insert (dx->memory, idx);
 511               dst_row = *p = xmemdup (dx->default_row, dx->n_bytes);
 512             }
 513           else
 514             {
 515               memcpy (tmp_dst_row, dx->default_row, dx->n_bytes);
 516               dst_row = tmp_dst_row;
 517             }
 518
 519           /* Run the callback. */
 520           success = cb (src_row, dst_row, aux);
 521           if (!success)
 522             break;
 523
 524           /* Write back the destination row, if necessary. */
 525           if (dst_row == tmp_dst_row)
 526             {
 527               success = sparse_xarray_write (dx, idx, 0, dx->n_bytes, dst_row);
 528               if (!success)
 529                 break;
 530             }
 531           else
 532             {
 533               /* Nothing to do: we modified the destination row in-place. */
 534             }
 535
 536           /* Advance to the next row. */
 537           if (src_idx == idx)
 538             src_idx = scan_next (sx, src_idx);
 539           if (dst_idx == idx)
 540             dst_idx = scan_next (dx, dst_idx);
 541         }
 542
 543       free (tmp_src_row);
 544       free (tmp_dst_row);
 545     }
 546
 547   return success;
 548 }
 549
 550 /* Returns a hash value for SX suitable for use with the model
 551    checker.  The value in BASIS is folded into the hash.
 552
 553    The returned hash value is *not* suitable for storage and
 554    retrieval of sparse_xarrays that have identical contents,
 555    because it will return different hash values for
 556    sparse_xarrays that have the same contents (and it's slow).
 557
 558    We use MD4 because it is much faster than MD5 or SHA-1 but its
 559    collision resistance is just as good. */
 560 unsigned int
 561 sparse_xarray_model_checker_hash (const struct sparse_xarray *sx,
 562                                   unsigned int basis)
 563 {
 564   unsigned int hash[DIV_RND_UP (20, sizeof (unsigned int))];
 565   struct md4_ctx ctx;
 566
 567   md4_init_ctx (&ctx);
 568   md4_process_bytes (&basis, sizeof basis, &ctx);
 569   md4_process_bytes (&sx->n_bytes, sizeof sx->n_bytes, &ctx);
 570   md4_process_bytes (sx->default_row, sx->n_bytes, &ctx);
 571
 572   if (sx->memory)
 573     {
 574       unsigned long int idx;
 575       uint8_t **row;
 576
 577       md4_process_bytes ("m", 1, &ctx);
 578       md4_process_bytes (&sx->max_memory_rows, sizeof sx->max_memory_rows,
 579                          &ctx);
 580       for (row = sparse_array_first (sx->memory, &idx); row != NULL;
 581            row = sparse_array_next (sx->memory, idx, &idx))
 582         {
 583           md4_process_bytes (&idx, sizeof idx, &ctx);
 584           md4_process_bytes (*row, sx->n_bytes, &ctx);
 585         }
 586     }
 587   else
 588     {
 589       const struct range_set_node *node;
 590       void *tmp = xmalloc (sx->n_bytes);
 591
 592       md4_process_bytes ("d", 1, &ctx);
 593       RANGE_SET_FOR_EACH (node, sx->disk_rows)
 594         {
 595           unsigned long int start = range_set_node_get_start (node);
 596           unsigned long int end = range_set_node_get_end (node);
 597           unsigned long int idx;
 598
 599           for (idx = start; idx < end; idx++)
 600             {
 601               off_t offset = (off_t) idx * sx->n_bytes;
 602               if (!ext_array_read (sx->disk, offset, sx->n_bytes, tmp))
 603                 NOT_REACHED ();
 604               md4_process_bytes (&idx, sizeof idx, &ctx);
 605               md4_process_bytes (tmp, sx->n_bytes, &ctx);
 606             }
 607         }
 608       free (tmp);
 609     }
 610   md4_finish_ctx (&ctx, hash);
 611   return hash[0];
 612 }