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