pintos-os.org Git - pspp/blob - src/data/caseproto.c

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2009, 2011, 2013 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 "data/caseproto.h"
  20
  21 #include "data/val-type.h"
  22 #include "data/value.h"
  23 #include "libpspp/array.h"
  24 #include "libpspp/assertion.h"
  25 #include "libpspp/pool.h"
  26
  27 #include "gl/minmax.h"
  28
  29 static struct caseproto *caseproto_unshare (struct caseproto *);
  30 static bool try_init_long_strings (const struct caseproto *,
  31                                    size_t first, size_t last, union value[]);
  32 static void init_long_strings (const struct caseproto *,
  33                                size_t first, size_t last, union value[]);
  34 static void destroy_long_strings (const struct caseproto *,
  35                                   size_t first, size_t last, union value[]);
  36 static size_t count_long_strings (const struct caseproto *,
  37                                   size_t idx, size_t count);
  38
  39 /* Returns the number of bytes to allocate for a struct caseproto
  40    with room for N_WIDTHS elements in its widths[] array. */
  41 static inline size_t
  42 caseproto_size (size_t n_widths)
  43 {
  44   return (offsetof (struct caseproto, widths)
  45           + n_widths * sizeof (((struct caseproto *) NULL)->widths[0]));
  46 }
  47
  48 /* Creates and returns a case prototype that initially has no
  49    widths. */
  50 struct caseproto *
  51 caseproto_create (void)
  52 {
  53   enum { N_ALLOCATE = 4 };
  54   struct caseproto *proto = xmalloc (caseproto_size (N_ALLOCATE));
  55   proto->ref_cnt = 1;
  56   proto->long_strings = NULL;
  57   proto->n_long_strings = 0;
  58   proto->n_widths = 0;
  59   proto->allocated_widths = N_ALLOCATE;
  60   return proto;
  61 }
  62
  63 static void
  64 do_unref (void *proto_)
  65 {
  66   struct caseproto *proto = proto_;
  67   caseproto_unref (proto);
  68 }
  69
  70 /* Creates and returns a new reference to PROTO.  When POOL is
  71    destroyed, the new reference will be destroyed (unrefed).  */
  72 struct caseproto *
  73 caseproto_ref_pool (const struct caseproto *proto_, struct pool *pool)
  74 {
  75   struct caseproto *proto = caseproto_ref (proto_);
  76   pool_register (pool, do_unref, proto);
  77   return proto;
  78 }
  79
  80 /* Returns a replacement for PROTO that is unshared and has
  81    enough room for at least N_WIDTHS widths before additional
  82    memory is needed.  */
  83 struct caseproto *
  84 caseproto_reserve (struct caseproto *proto, size_t n_widths)
  85 {
  86   proto = caseproto_unshare (proto);
  87   if (n_widths > proto->allocated_widths)
  88     {
  89       proto->allocated_widths *= MAX (proto->allocated_widths * 2, n_widths);
  90       proto = xrealloc (proto, caseproto_size (proto->allocated_widths));
  91     }
  92   return proto;
  93 }
  94
  95 /* Returns a replacement for PROTO with WIDTH appended.  */
  96 struct caseproto *
  97 caseproto_add_width (struct caseproto *proto, int width)
  98 {
  99   assert (width >= -1 && width <= MAX_STRING);
 100
 101   proto = caseproto_reserve (proto, proto->n_widths + 1);
 102   proto->widths[proto->n_widths++] = width;
 103   proto->n_long_strings += count_long_strings (proto, proto->n_widths - 1, 1);
 104
 105   return proto;
 106 }
 107
 108 /* Returns a replacement for PROTO with the width at index IDX
 109    replaced by WIDTH.  IDX may be greater than the current number
 110    of widths in PROTO, in which case any gap is filled in by
 111    widths of -1. */
 112 struct caseproto *
 113 caseproto_set_width (struct caseproto *proto, size_t idx, int width)
 114 {
 115   assert (width >= -1 && width <= MAX_STRING);
 116
 117   proto = caseproto_reserve (proto, idx + 1);
 118   while (idx >= proto->n_widths)
 119     proto->widths[proto->n_widths++] = -1;
 120   proto->n_long_strings -= count_long_strings (proto, idx, 1);
 121   proto->widths[idx] = width;
 122   proto->n_long_strings += count_long_strings (proto, idx, 1);
 123
 124   return proto;
 125 }
 126
 127 /* Returns a replacement for PROTO with WIDTH inserted just
 128    before index BEFORE, or just after the last element if BEFORE
 129    is the number of widths in PROTO. */
 130 struct caseproto *
 131 caseproto_insert_width (struct caseproto *proto, size_t before, int width)
 132 {
 133   assert (before <= proto->n_widths);
 134
 135   proto = caseproto_reserve (proto, proto->n_widths + 1);
 136   proto->n_long_strings += value_needs_init (width);
 137   insert_element (proto->widths, proto->n_widths, sizeof *proto->widths,
 138                   before);
 139   proto->widths[before] = width;
 140   proto->n_widths++;
 141
 142   return proto;
 143 }
 144
 145 /* Returns a replacement for PROTO with CNT widths removed
 146    starting at index IDX. */
 147 struct caseproto *
 148 caseproto_remove_widths (struct caseproto *proto, size_t idx, size_t cnt)
 149 {
 150   assert (caseproto_range_is_valid (proto, idx, cnt));
 151
 152   proto = caseproto_unshare (proto);
 153   proto->n_long_strings -= count_long_strings (proto, idx, cnt);
 154   remove_range (proto->widths, proto->n_widths, sizeof *proto->widths,
 155                 idx, cnt);
 156   proto->n_widths -= cnt;
 157   return proto;
 158 }
 159
 160 /* Returns a replacement for PROTO in which the CNT widths
 161    starting at index OLD_WIDTH now start at index NEW_WIDTH, with
 162    other widths shifting out of the way to make room. */
 163 struct caseproto *
 164 caseproto_move_widths (struct caseproto *proto,
 165                        size_t old_start, size_t new_start,
 166                        size_t cnt)
 167 {
 168   assert (caseproto_range_is_valid (proto, old_start, cnt));
 169   assert (caseproto_range_is_valid (proto, new_start, cnt));
 170
 171   proto = caseproto_unshare (proto);
 172   move_range (proto->widths, proto->n_widths, sizeof *proto->widths,
 173               old_start, new_start, cnt);
 174   return proto;
 175 }
 176
 177 /* Returns true if PROTO contains COUNT widths starting at index
 178    OFS, false if any of those widths are out of range for
 179    PROTO. */
 180 bool
 181 caseproto_range_is_valid (const struct caseproto *proto,
 182                           size_t ofs, size_t count)
 183 {
 184   return (count <= proto->n_widths
 185           && ofs <= proto->n_widths
 186           && ofs + count <= proto->n_widths);
 187 }
 188
 189 /* Returns true if A and B have the same widths along their
 190    common length.  (When this is so, a case with prototype A may
 191    be extended or truncated to have prototype B without having to
 192    change any existing values, and vice versa.) */
 193 bool
 194 caseproto_is_conformable (const struct caseproto *a, const struct caseproto *b)
 195 {
 196   size_t min;
 197   size_t i;
 198
 199   min = MIN (a->n_widths, b->n_widths);
 200   for (i = 0; i < min; i++)
 201     if (a->widths[i] != b->widths[i])
 202       return false;
 203   return true;
 204 }
 205
 206 /* Returns true if the N widths starting at A_START in A are the
 207    same as the N widths starting at B_START in B, false if any of
 208    the corresponding widths differ. */
 209 bool
 210 caseproto_equal (const struct caseproto *a, size_t a_start,
 211                  const struct caseproto *b, size_t b_start,
 212                  size_t n)
 213 {
 214   size_t i;
 215
 216   assert (caseproto_range_is_valid (a, a_start, n));
 217   assert (caseproto_range_is_valid (b, b_start, n));
 218   for (i = 0; i < n; i++)
 219     if (a->widths[a_start + i] != b->widths[b_start + i])
 220       return false;
 221   return true;
 222 }
 223
 224 struct pxd_object *
 225 caseproto_save (const struct caseproto *proto, struct pxd *pxd)
 226 {
 227   if (proto->pxd == NULL)
 228     {
 229       struct pxd_builder b;
 230       size_t i;
 231
 232       pxd_builder_init (&b, pxd);
 233
 234       pxd_builder_put_size_t (&b, proto->n_widths);
 235       for (i = 0; i < proto->n_widths; i++)
 236         pxd_builder_put_s16 (&b, proto->widths[i]);
 237
 238       CONST_CAST (struct caseproto *, proto)->pxd = pxd_builder_commit (&b);
 239     }
 240   return pxd_object_ref (proto->pxd);
 241 }
 242
 243 struct caseproto *
 244 caseproto_load (struct pxd_object *object, const struct pxd *pxd)
 245 {
 246   struct caseproto *proto;
 247   struct pxd_parser p;
 248   size_t n, i;
 249
 250   pxd_parser_init (&p, object, pxd);
 251
 252   n = pxd_parser_get_size_t (&p);
 253   proto = caseproto_reserve (caseproto_create (), n);
 254
 255   for (i = 0; i < n; i++)
 256     proto = caseproto_add_width (proto, pxd_parser_get_s16 (&p));
 257
 258   pxd_parser_destroy (&p);
 259
 260   return proto;
 261 }
 262
 263 /* Returns true if an array of values that is to be used for
 264    data of the format specified in PROTO needs to be initialized
 265    by calling caseproto_init_values, false if that step may be
 266    skipped because such an initialization would be a no-op anyhow.
 267
 268    This optimization is useful only when a large number of
 269    initializations of such arrays may be skipped as a group. */
 270 bool
 271 caseproto_needs_init_values (const struct caseproto *proto)
 272 {
 273   return proto->n_long_strings > 0;
 274 }
 275
 276 /* Initializes the values in VALUES as required by PROTO, by
 277    calling value_init() on each value for which this is required.
 278    The data in VALUES have indeterminate contents until
 279    explicitly written.
 280
 281    VALUES must have at least caseproto_get_n_widths(PROTO)
 282    elements; only that many elements of VALUES are initialized.
 283
 284    The caller retains ownership of PROTO. */
 285 void
 286 caseproto_init_values (const struct caseproto *proto, union value values[])
 287 {
 288   init_long_strings (proto, 0, proto->n_long_strings, values);
 289 }
 290
 291 /* Like caseproto_init_values, but returns false instead of
 292    terminating if memory cannot be obtained. */
 293 bool
 294 caseproto_try_init_values (const struct caseproto *proto, union value values[])
 295 {
 296   return try_init_long_strings (proto, 0, proto->n_long_strings, values);
 297 }
 298
 299 /* Initializes the data in VALUES that are in NEW but not in OLD,
 300    destroys the data in VALUES that are in OLD but not NEW, and
 301    does not modify the data in VALUES that are in both OLD and
 302    NEW.  VALUES must previously have been initialized as required
 303    by OLD using e.g. caseproto_init_values.  The data in VALUES
 304    that are in NEW but not in OLD will have indeterminate
 305    contents until explicitly written.
 306
 307    OLD and NEW must be conformable for this operation, as
 308    reported by caseproto_is_conformable.
 309
 310    The caller retains ownership of OLD and NEW. */
 311 void
 312 caseproto_reinit_values (const struct caseproto *old,
 313                          const struct caseproto *new, union value values[])
 314 {
 315   size_t old_n_long = old->n_long_strings;
 316   size_t new_n_long = new->n_long_strings;
 317
 318   expensive_assert (caseproto_is_conformable (old, new));
 319
 320   if (new_n_long > old_n_long)
 321     init_long_strings (new, old_n_long, new_n_long, values);
 322   else if (new_n_long < old_n_long)
 323     destroy_long_strings (old, new_n_long, old_n_long, values);
 324 }
 325
 326 /* Frees the values in VALUES as required by PROTO, by calling
 327    value_destroy() on each value for which this is required.  The
 328    values must previously have been initialized using
 329    e.g. caseproto_init_values.
 330
 331    The caller retains ownership of PROTO. */
 332 void
 333 caseproto_destroy_values (const struct caseproto *proto, union value values[])
 334 {
 335   destroy_long_strings (proto, 0, proto->n_long_strings, values);
 336 }
 337
 338 /* Copies COUNT values, whose widths are given by widths in PROTO
 339    starting with index IDX, from SRC to DST.  The caller must
 340    ensure that the values in SRC and DST were appropriately
 341    initialized using e.g. caseproto_init_values. */
 342 void
 343 caseproto_copy (const struct caseproto *proto, size_t idx, size_t count,
 344                 union value *dst, const union value *src)
 345 {
 346   size_t i;
 347
 348   assert (caseproto_range_is_valid (proto, idx, count));
 349   for (i = 0; i < count; i++)
 350     value_copy (&dst[idx + i], &src[idx + i], proto->widths[idx + i]);
 351 }
 352 \f
 353 void
 354 caseproto_free__ (struct caseproto *proto)
 355 {
 356   pxd_object_unref (proto->pxd);
 357   free (proto->long_strings);
 358   free (proto);
 359 }
 360
 361 void
 362 caseproto_refresh_long_string_cache__ (const struct caseproto *proto_)
 363 {
 364   struct caseproto *proto = CONST_CAST (struct caseproto *, proto_);
 365   size_t n, i;
 366
 367   assert (proto->long_strings == NULL);
 368   assert (proto->n_long_strings > 0);
 369
 370   proto->long_strings = xmalloc (proto->n_long_strings
 371                                  * sizeof *proto->long_strings);
 372   n = 0;
 373   for (i = 0; i < proto->n_widths; i++)
 374     if (proto->widths[i] > MAX_SHORT_STRING)
 375       proto->long_strings[n++] = i;
 376   assert (n == proto->n_long_strings);
 377 }
 378
 379 static struct caseproto *
 380 caseproto_unshare (struct caseproto *old)
 381 {
 382   struct caseproto *new;
 383   if (old->ref_cnt > 1)
 384     {
 385       new = xmemdup (old, caseproto_size (old->allocated_widths));
 386       new->ref_cnt = 1;
 387       --old->ref_cnt;
 388     }
 389   else
 390     {
 391       new = old;
 392       free (new->long_strings);
 393       pxd_object_unref (new->pxd);
 394       new->pxd = NULL;
 395     }
 396   new->long_strings = NULL;
 397   return new;
 398 }
 399
 400 static bool
 401 try_init_long_strings (const struct caseproto *proto,
 402                        size_t first, size_t last, union value values[])
 403 {
 404   size_t i;
 405
 406   if (last > 0 && proto->long_strings == NULL)
 407     caseproto_refresh_long_string_cache__ (proto);
 408
 409   for (i = first; i < last; i++)
 410     {
 411       size_t idx = proto->long_strings[i];
 412       if (!value_try_init (&values[idx], proto->widths[idx]))
 413         {
 414           destroy_long_strings (proto, first, i, values);
 415           return false;
 416         }
 417     }
 418   return true;
 419 }
 420
 421 static void
 422 init_long_strings (const struct caseproto *proto,
 423                    size_t first, size_t last, union value values[])
 424 {
 425   if (!try_init_long_strings (proto, first, last, values))
 426     xalloc_die ();
 427 }
 428
 429 static void
 430 destroy_long_strings (const struct caseproto *proto, size_t first, size_t last,
 431                       union value values[])
 432 {
 433   size_t i;
 434
 435   if (last > 0 && proto->long_strings == NULL)
 436     caseproto_refresh_long_string_cache__ (proto);
 437
 438   for (i = first; i < last; i++)
 439     {
 440       size_t idx = proto->long_strings[i];
 441       value_destroy (&values[idx], proto->widths[idx]);
 442     }
 443 }
 444
 445 static size_t
 446 count_long_strings (const struct caseproto *proto, size_t idx, size_t count)
 447 {
 448   size_t n, i;
 449
 450   n = 0;
 451   for (i = 0; i < count; i++)
 452     n += proto->widths[idx + i] > MAX_SHORT_STRING;
 453   return n;
 454 }