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

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