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