src/data/caseproto.c

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