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