src/data/dictionary.c

   1 /* PSPP - computes sample statistics.
   2    Copyright (C) 1997-9, 2000, 2006 Free Software Foundation, Inc.
   3
   4    This program is free software; you can redistribute it and/or
   5    modify it under the terms of the GNU General Public License as
   6    published by the Free Software Foundation; either version 2 of the
   7    License, or (at your option) any later version.
   8
   9    This program is distributed in the hope that it will be useful, but
  10    WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12    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, write to the Free Software
  16    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  17    02110-1301, USA. */
  18
  19 #include <config.h>
  20
  21 #include "dictionary.h"
  22
  23 #include <stdlib.h>
  24 #include <ctype.h>
  25
  26 #include "case.h"
  27 #include "cat-routines.h"
  28 #include "category.h"
  29 #include "settings.h"
  30 #include "value-labels.h"
  31 #include "vardict.h"
  32 #include "variable.h"
  33 #include "vector.h"
  34 #include <libpspp/alloc.h>
  35 #include <libpspp/array.h>
  36 #include <libpspp/compiler.h>
  37 #include <libpspp/hash.h>
  38 #include <libpspp/message.h>
  39 #include <libpspp/misc.h>
  40 #include <libpspp/pool.h>
  41 #include <libpspp/str.h>
  42
  43 #include "minmax.h"
  44
  45 #include "gettext.h"
  46 #define _(msgid) gettext (msgid)
  47
  48 /* A dictionary. */
  49 struct dictionary
  50   {
  51     struct variable **var;      /* Variables. */
  52     size_t var_cnt, var_cap;    /* Number of variables, capacity. */
  53     struct hsh_table *name_tab; /* Variable index by name. */
  54     int next_value_idx;         /* Index of next `union value' to allocate. */
  55     struct variable **split;    /* SPLIT FILE vars. */
  56     size_t split_cnt;           /* SPLIT FILE count. */
  57     struct variable *weight;    /* WEIGHT variable. */
  58     struct variable *filter;    /* FILTER variable. */
  59     size_t case_limit;          /* Current case limit (N command). */
  60     char *label;                /* File label. */
  61     char *documents;            /* Documents, as a string. */
  62     struct vector **vector;     /* Vectors of variables. */
  63     size_t vector_cnt;          /* Number of vectors. */
  64   };
  65
  66 /* Creates and returns a new dictionary. */
  67 struct dictionary *
  68 dict_create (void)
  69 {
  70   struct dictionary *d = xmalloc (sizeof *d);
  71
  72   d->var = NULL;
  73   d->var_cnt = d->var_cap = 0;
  74   d->name_tab = hsh_create (8, compare_vars_by_name, hash_var_by_name,
  75                             NULL, NULL);
  76   d->next_value_idx = 0;
  77   d->split = NULL;
  78   d->split_cnt = 0;
  79   d->weight = NULL;
  80   d->filter = NULL;
  81   d->case_limit = 0;
  82   d->label = NULL;
  83   d->documents = NULL;
  84   d->vector = NULL;
  85   d->vector_cnt = 0;
  86
  87   return d;
  88 }
  89
  90 /* Creates and returns a (deep) copy of an existing
  91    dictionary. */
  92 struct dictionary *
  93 dict_clone (const struct dictionary *s)
  94 {
  95   struct dictionary *d;
  96   size_t i;
  97
  98   assert (s != NULL);
  99
 100   d = dict_create ();
 101
 102   for (i = 0; i < s->var_cnt; i++)
 103     {
 104       struct variable *sv = s->var[i];
 105       struct variable *dv = dict_clone_var_assert (d, sv, var_get_name (sv));
 106       var_set_short_name (dv, var_get_short_name (sv));
 107     }
 108
 109   d->next_value_idx = s->next_value_idx;
 110
 111   d->split_cnt = s->split_cnt;
 112   if (d->split_cnt > 0)
 113     {
 114       d->split = xnmalloc (d->split_cnt, sizeof *d->split);
 115       for (i = 0; i < d->split_cnt; i++)
 116         d->split[i] = dict_lookup_var_assert (d, var_get_name (s->split[i]));
 117     }
 118
 119   if (s->weight != NULL)
 120     d->weight = dict_lookup_var_assert (d, var_get_name (s->weight));
 121
 122   if (s->filter != NULL)
 123     d->filter = dict_lookup_var_assert (d, var_get_name (s->filter));
 124
 125   d->case_limit = s->case_limit;
 126   dict_set_label (d, dict_get_label (s));
 127   dict_set_documents (d, dict_get_documents (s));
 128
 129   d->vector_cnt = s->vector_cnt;
 130   d->vector = xnmalloc (d->vector_cnt, sizeof *d->vector);
 131   for (i = 0; i < s->vector_cnt; i++)
 132     d->vector[i] = vector_clone (s->vector[i], s, d);
 133
 134   return d;
 135 }
 136
 137 /* Clears the contents from a dictionary without destroying the
 138    dictionary itself. */
 139 void
 140 dict_clear (struct dictionary *d)
 141 {
 142   /* FIXME?  Should we really clear case_limit, label, documents?
 143      Others are necessarily cleared by deleting all the variables.*/
 144   int i;
 145
 146   assert (d != NULL);
 147
 148   for (i = 0; i < d->var_cnt; i++)
 149     {
 150       var_clear_vardict (d->var[i]);
 151       var_destroy (d->var[i]);
 152     }
 153   free (d->var);
 154   d->var = NULL;
 155   d->var_cnt = d->var_cap = 0;
 156   hsh_clear (d->name_tab);
 157   d->next_value_idx = 0;
 158   free (d->split);
 159   d->split = NULL;
 160   d->split_cnt = 0;
 161   d->weight = NULL;
 162   d->filter = NULL;
 163   d->case_limit = 0;
 164   free (d->label);
 165   d->label = NULL;
 166   free (d->documents);
 167   d->documents = NULL;
 168   dict_clear_vectors (d);
 169 }
 170
 171 /* Destroys the aux data for every variable in D, by calling
 172    var_clear_aux() for each variable. */
 173 void
 174 dict_clear_aux (struct dictionary *d)
 175 {
 176   int i;
 177
 178   assert (d != NULL);
 179
 180   for (i = 0; i < d->var_cnt; i++)
 181     var_clear_aux (d->var[i]);
 182 }
 183
 184 /* Clears a dictionary and destroys it. */
 185 void
 186 dict_destroy (struct dictionary *d)
 187 {
 188   if (d != NULL)
 189     {
 190       dict_clear (d);
 191       hsh_destroy (d->name_tab);
 192       free (d);
 193     }
 194 }
 195
 196 /* Returns the number of variables in D. */
 197 size_t
 198 dict_get_var_cnt (const struct dictionary *d)
 199 {
 200   assert (d != NULL);
 201
 202   return d->var_cnt;
 203 }
 204
 205 /* Returns the variable in D with dictionary index IDX, which
 206    must be between 0 and the count returned by
 207    dict_get_var_cnt(), exclusive. */
 208 struct variable *
 209 dict_get_var (const struct dictionary *d, size_t idx)
 210 {
 211   assert (d != NULL);
 212   assert (idx < d->var_cnt);
 213
 214   return d->var[idx];
 215 }
 216
 217 /* Sets *VARS to an array of pointers to variables in D and *CNT
 218    to the number of variables in *D.  All variables are returned
 219    if EXCLUDE_CLASSES is 0, or it may contain one or more of (1u
 220    << DC_ORDINARY), (1u << DC_SYSTEM), or (1u << DC_SCRATCH) to
 221    exclude the corresponding type of variable. */
 222 void
 223 dict_get_vars (const struct dictionary *d, struct variable ***vars,
 224                size_t *cnt, unsigned exclude_classes)
 225 {
 226   size_t count;
 227   size_t i;
 228
 229   assert (d != NULL);
 230   assert (vars != NULL);
 231   assert (cnt != NULL);
 232   assert ((exclude_classes & ~((1u << DC_ORDINARY)
 233                                | (1u << DC_SYSTEM)
 234                                | (1u << DC_SCRATCH))) == 0);
 235
 236   count = 0;
 237   for (i = 0; i < d->var_cnt; i++)
 238     {
 239       enum dict_class class = dict_class_from_id (var_get_name (d->var[i]));
 240       if (!(exclude_classes & (1u << class)))
 241         count++;
 242     }
 243
 244   *vars = xnmalloc (count, sizeof **vars);
 245   *cnt = 0;
 246   for (i = 0; i < d->var_cnt; i++)
 247     {
 248       enum dict_class class = dict_class_from_id (var_get_name (d->var[i]));
 249       if (!(exclude_classes & (1u << class)))
 250         (*vars)[(*cnt)++] = d->var[i];
 251     }
 252   assert (*cnt == count);
 253 }
 254
 255 static struct variable *
 256 add_var (struct dictionary *d, struct variable *v)
 257 {
 258   /* Add dictionary info to variable. */
 259   struct vardict_info vdi;
 260   vdi.case_index = d->next_value_idx;
 261   vdi.dict_index = d->var_cnt;
 262   var_set_vardict (v, &vdi);
 263
 264   /* Update dictionary. */
 265   if (d->var_cnt >= d->var_cap)
 266     {
 267       d->var_cap = 8 + 2 * d->var_cap;
 268       d->var = xnrealloc (d->var, d->var_cap, sizeof *d->var);
 269     }
 270   d->var[d->var_cnt++] = v;
 271   hsh_force_insert (d->name_tab, v);
 272
 273   d->next_value_idx += var_get_value_cnt (v);
 274
 275   return v;
 276 }
 277
 278 /* Creates and returns a new variable in D with the given NAME
 279    and WIDTH.  Returns a null pointer if the given NAME would
 280    duplicate that of an existing variable in the dictionary. */
 281 struct variable *
 282 dict_create_var (struct dictionary *d, const char *name, int width)
 283 {
 284   return (dict_lookup_var (d, name) == NULL
 285           ? dict_create_var_assert (d, name, width)
 286           : NULL);
 287 }
 288
 289 /* Creates and returns a new variable in D with the given NAME
 290    and WIDTH.  Assert-fails if the given NAME would duplicate
 291    that of an existing variable in the dictionary. */
 292 struct variable *
 293 dict_create_var_assert (struct dictionary *d, const char *name, int width)
 294 {
 295   assert (dict_lookup_var (d, name) == NULL);
 296   return add_var (d, var_create (name, width));
 297 }
 298
 299 /* Creates and returns a new variable in D with name NAME, as a
 300    copy of existing variable OLD_VAR, which need not be in D or
 301    in any dictionary.  Returns a null pointer if the given NAME
 302    would duplicate that of an existing variable in the
 303    dictionary. */
 304 struct variable *
 305 dict_clone_var (struct dictionary *d, const struct variable *old_var,
 306                 const char *name)
 307 {
 308   return (dict_lookup_var (d, name) == NULL
 309           ? dict_clone_var_assert (d, old_var, name)
 310           : NULL);
 311 }
 312
 313 /* Creates and returns a new variable in D with name NAME, as a
 314    copy of existing variable OLD_VAR, which need not be in D or
 315    in any dictionary.  Assert-fails if the given NAME would
 316    duplicate that of an existing variable in the dictionary. */
 317 struct variable *
 318 dict_clone_var_assert (struct dictionary *d, const struct variable *old_var,
 319                        const char *name)
 320 {
 321   struct variable *new_var = var_clone (old_var);
 322   assert (dict_lookup_var (d, name) == NULL);
 323   var_set_name (new_var, name);
 324   return add_var (d, new_var);
 325 }
 326
 327 /* Returns the variable named NAME in D, or a null pointer if no
 328    variable has that name. */
 329 struct variable *
 330 dict_lookup_var (const struct dictionary *d, const char *name)
 331 {
 332   struct variable *target = var_create (name, 0);
 333   struct variable *result = hsh_find (d->name_tab, target);
 334   var_destroy (target);
 335   return result;
 336 }
 337
 338 /* Returns the variable named NAME in D.  Assert-fails if no
 339    variable has that name. */
 340 struct variable *
 341 dict_lookup_var_assert (const struct dictionary *d, const char *name)
 342 {
 343   struct variable *v = dict_lookup_var (d, name);
 344   assert (v != NULL);
 345   return v;
 346 }
 347
 348 /* Returns true if variable V is in dictionary D,
 349    false otherwise. */
 350 bool
 351 dict_contains_var (const struct dictionary *d, const struct variable *v)
 352 {
 353   if (var_has_vardict (v))
 354     {
 355       const struct vardict_info *vdi = var_get_vardict (v);
 356       return (vdi->dict_index >= 0
 357               && vdi->dict_index < d->var_cnt
 358               && d->var[vdi->dict_index] == v);
 359     }
 360   else
 361     return false;
 362 }
 363
 364 /* Compares two double pointers to variables, which should point
 365    to elements of a struct dictionary's `var' member array. */
 366 static int
 367 compare_var_ptrs (const void *a_, const void *b_, const void *aux UNUSED)
 368 {
 369   struct variable *const *a = a_;
 370   struct variable *const *b = b_;
 371
 372   return *a < *b ? -1 : *a > *b;
 373 }
 374
 375 /* Sets the dict_index in V's vardict to DICT_INDEX. */
 376 static void
 377 set_var_dict_index (struct variable *v, int dict_index)
 378 {
 379   struct vardict_info vdi = *var_get_vardict (v);
 380   vdi.dict_index = dict_index;
 381   var_set_vardict (v, &vdi);
 382 }
 383
 384 /* Sets the case_index in V's vardict to DICT_INDEX. */
 385 static void
 386 set_var_case_index (struct variable *v, int case_index)
 387 {
 388   struct vardict_info vdi = *var_get_vardict (v);
 389   vdi.case_index = case_index;
 390   var_set_vardict (v, &vdi);
 391 }
 392
 393 /* Re-sets the dict_index in the dictionary variables with
 394    indexes from FROM to TO (exclusive). */
 395 static void
 396 reindex_vars (struct dictionary *d, size_t from, size_t to)
 397 {
 398   size_t i;
 399
 400   for (i = from; i < to; i++)
 401     set_var_dict_index (d->var[i], i);
 402 }
 403
 404 /* Deletes variable V from dictionary D and frees V.
 405
 406    This is a very bad idea if there might be any pointers to V
 407    from outside D.  In general, no variable in should be deleted when
 408    any transformations are active on the dictionary's dataset, because
 409    those transformations might reference the deleted variable.
 410    The safest time to delete a variable is just after a procedure
 411    has been executed, as done by MODIFY VARS.
 412
 413    Pointers to V within D are not a problem, because
 414    dict_delete_var() knows to remove V from split variables,
 415    weights, filters, etc. */
 416 void
 417 dict_delete_var (struct dictionary *d, struct variable *v)
 418 {
 419   int dict_index = var_get_dict_index (v);
 420
 421   assert (dict_contains_var (d, v));
 422
 423   /* Delete aux data. */
 424   var_clear_aux (v);
 425
 426   /* Remove V from splits, weight, filter variables. */
 427   d->split_cnt = remove_equal (d->split, d->split_cnt, sizeof *d->split,
 428                                &v, compare_var_ptrs, NULL);
 429   if (d->weight == v)
 430     d->weight = NULL;
 431   if (d->filter == v)
 432     d->filter = NULL;
 433   dict_clear_vectors (d);
 434
 435   /* Remove V from var array. */
 436   remove_element (d->var, d->var_cnt, sizeof *d->var, dict_index);
 437   d->var_cnt--;
 438
 439   /* Update dict_index for each affected variable. */
 440   reindex_vars (d, dict_index, d->var_cnt);
 441
 442   /* Update name hash. */
 443   hsh_force_delete (d->name_tab, v);
 444
 445   /* Free memory. */
 446   var_clear_vardict (v);
 447   var_destroy (v);
 448 }
 449
 450 /* Deletes the COUNT variables listed in VARS from D.  This is
 451    unsafe; see the comment on dict_delete_var() for details. */
 452 void
 453 dict_delete_vars (struct dictionary *d,
 454                   struct variable *const *vars, size_t count)
 455 {
 456   /* FIXME: this can be done in O(count) time, but this algorithm
 457      is O(count**2). */
 458   assert (d != NULL);
 459   assert (count == 0 || vars != NULL);
 460
 461   while (count-- > 0)
 462     dict_delete_var (d, *vars++);
 463 }
 464
 465 /* Deletes the COUNT variables in D starting at index IDX.  This
 466    is unsafe; see the comment on dict_delete_var() for
 467    details. */
 468 void
 469 dict_delete_consecutive_vars (struct dictionary *d, size_t idx, size_t count)
 470 {
 471   /* FIXME: this can be done in O(count) time, but this algorithm
 472      is O(count**2). */
 473   assert (idx + count <= d->var_cnt);
 474
 475   while (count-- > 0)
 476     dict_delete_var (d, d->var[idx]);
 477 }
 478
 479 /* Deletes scratch variables from dictionary D. */
 480 void
 481 dict_delete_scratch_vars (struct dictionary *d)
 482 {
 483   int i;
 484
 485   /* FIXME: this can be done in O(count) time, but this algorithm
 486      is O(count**2). */
 487   assert (d != NULL);
 488
 489   for (i = 0; i < d->var_cnt; )
 490     if (dict_class_from_id (var_get_name (d->var[i])) == DC_SCRATCH)
 491       dict_delete_var (d, d->var[i]);
 492     else
 493       i++;
 494 }
 495
 496 /* Moves V to 0-based position IDX in D.  Other variables in D,
 497    if any, retain their relative positions.  Runs in time linear
 498    in the distance moved. */
 499 void
 500 dict_reorder_var (struct dictionary *d, struct variable *v, size_t new_index)
 501 {
 502   size_t old_index = var_get_dict_index (v);
 503
 504   assert (new_index < d->var_cnt);
 505   move_element (d->var, d->var_cnt, sizeof *d->var, old_index, new_index);
 506   reindex_vars (d, MIN (old_index, new_index), MAX (old_index, new_index) + 1);
 507 }
 508
 509 /* Reorders the variables in D, placing the COUNT variables
 510    listed in ORDER in that order at the beginning of D.  The
 511    other variables in D, if any, retain their relative
 512    positions. */
 513 void
 514 dict_reorder_vars (struct dictionary *d,
 515                    struct variable *const *order, size_t count)
 516 {
 517   struct variable **new_var;
 518   size_t i;
 519
 520   assert (d != NULL);
 521   assert (count == 0 || order != NULL);
 522   assert (count <= d->var_cnt);
 523
 524   new_var = xnmalloc (d->var_cnt, sizeof *new_var);
 525   memcpy (new_var, order, count * sizeof *new_var);
 526   for (i = 0; i < count; i++)
 527     {
 528       size_t index = var_get_dict_index (order[i]);
 529       assert (d->var[index] == order[i]);
 530       d->var[index] = NULL;
 531       set_var_dict_index (order[i], i);
 532     }
 533   for (i = 0; i < d->var_cnt; i++)
 534     if (d->var[i] != NULL)
 535       {
 536         assert (count < d->var_cnt);
 537         new_var[count] = d->var[i];
 538         set_var_dict_index (new_var[count], count);
 539         count++;
 540       }
 541   free (d->var);
 542   d->var = new_var;
 543 }
 544
 545 /* Changes the name of variable V in dictionary D to NEW_NAME. */
 546 static void
 547 rename_var (struct dictionary *d, struct variable *v, const char *new_name)
 548 {
 549   struct vardict_info vdi;
 550
 551   assert (dict_contains_var (d, v));
 552
 553   vdi = *var_get_vardict (v);
 554   var_clear_vardict (v);
 555   var_set_name (v, new_name);
 556   var_set_vardict (v, &vdi);
 557 }
 558
 559 /* Changes the name of V in D to name NEW_NAME.  Assert-fails if
 560    a variable named NEW_NAME is already in D, except that
 561    NEW_NAME may be the same as V's existing name. */
 562 void
 563 dict_rename_var (struct dictionary *d, struct variable *v,
 564                  const char *new_name)
 565 {
 566   assert (!strcasecmp (var_get_name (v), new_name)
 567           || dict_lookup_var (d, new_name) == NULL);
 568
 569   hsh_force_delete (d->name_tab, v);
 570   rename_var (d, v, new_name);
 571   hsh_force_insert (d->name_tab, v);
 572
 573   if (get_algorithm () == ENHANCED)
 574     var_clear_short_name (v);
 575 }
 576
 577 /* Renames COUNT variables specified in VARS to the names given
 578    in NEW_NAMES within dictionary D.  If the renaming would
 579    result in a duplicate variable name, returns false and stores a
 580    name that would be duplicated into *ERR_NAME (if ERR_NAME is
 581    non-null).  Otherwise, the renaming is successful, and true
 582    is returned. */
 583 bool
 584 dict_rename_vars (struct dictionary *d,
 585                   struct variable **vars, char **new_names, size_t count,
 586                   char **err_name)
 587 {
 588   struct pool *pool;
 589   char **old_names;
 590   size_t i;
 591
 592   assert (count == 0 || vars != NULL);
 593   assert (count == 0 || new_names != NULL);
 594
 595   /* Save the names of the variables to be renamed. */
 596   pool = pool_create ();
 597   old_names = pool_nalloc (pool, count, sizeof *old_names);
 598   for (i = 0; i < count; i++)
 599     old_names[i] = pool_strdup (pool, var_get_name (vars[i]));
 600
 601   /* Remove the variables to be renamed from the name hash,
 602      and rename them. */
 603   for (i = 0; i < count; i++)
 604     {
 605       hsh_force_delete (d->name_tab, vars[i]);
 606       rename_var (d, vars[i], new_names[i]);
 607     }
 608
 609   /* Add the renamed variables back into the name hash,
 610      checking for conflicts. */
 611   for (i = 0; i < count; i++)
 612     if (hsh_insert (d->name_tab, vars[i]) != NULL)
 613       {
 614         /* There is a name conflict.
 615            Back out all the name changes that have already
 616            taken place, and indicate failure. */
 617         size_t fail_idx = i;
 618         if (err_name != NULL)
 619           *err_name = new_names[i];
 620
 621         for (i = 0; i < fail_idx; i++)
 622           hsh_force_delete (d->name_tab, vars[i]);
 623
 624         for (i = 0; i < count; i++)
 625           {
 626             rename_var (d, vars[i], old_names[i]);
 627             hsh_force_insert (d->name_tab, vars[i]);
 628           }
 629
 630         pool_destroy (pool);
 631         return false;
 632       }
 633
 634   /* Clear short names. */
 635   if (get_algorithm () == ENHANCED)
 636     for (i = 0; i < count; i++)
 637       var_clear_short_name (vars[i]);
 638
 639   pool_destroy (pool);
 640   return true;
 641 }
 642
 643 /* Returns the weighting variable in dictionary D, or a null
 644    pointer if the dictionary is unweighted. */
 645 struct variable *
 646 dict_get_weight (const struct dictionary *d)
 647 {
 648   assert (d != NULL);
 649   assert (d->weight == NULL || dict_contains_var (d, d->weight));
 650
 651   return d->weight;
 652 }
 653
 654 /* Returns the value of D's weighting variable in case C, except that a
 655    negative weight is returned as 0.  Returns 1 if the dictionary is
 656    unweighted. Will warn about missing, negative, or zero values if
 657    warn_on_invalid is true. The function will set warn_on_invalid to false
 658    if an invalid weight is found. */
 659 double
 660 dict_get_case_weight (const struct dictionary *d, const struct ccase *c,
 661                       bool *warn_on_invalid)
 662 {
 663   assert (d != NULL);
 664   assert (c != NULL);
 665
 666   if (d->weight == NULL)
 667     return 1.0;
 668   else
 669     {
 670       double w = case_num (c, d->weight);
 671       if (w < 0.0 || var_is_num_missing (d->weight, w))
 672         w = 0.0;
 673       if ( w == 0.0 && *warn_on_invalid ) {
 674           *warn_on_invalid = false;
 675           msg (SW, _("At least one case in the data file had a weight value "
 676                      "that was user-missing, system-missing, zero, or "
 677                      "negative.  These case(s) were ignored."));
 678       }
 679       return w;
 680     }
 681 }
 682
 683 /* Sets the weighting variable of D to V, or turning off
 684    weighting if V is a null pointer. */
 685 void
 686 dict_set_weight (struct dictionary *d, struct variable *v)
 687 {
 688   assert (d != NULL);
 689   assert (v == NULL || dict_contains_var (d, v));
 690   assert (v == NULL || var_is_numeric (v));
 691
 692   d->weight = v;
 693 }
 694
 695 /* Returns the filter variable in dictionary D (see cmd_filter())
 696    or a null pointer if the dictionary is unfiltered. */
 697 struct variable *
 698 dict_get_filter (const struct dictionary *d)
 699 {
 700   assert (d != NULL);
 701   assert (d->filter == NULL || dict_contains_var (d, d->filter));
 702
 703   return d->filter;
 704 }
 705
 706 /* Sets V as the filter variable for dictionary D.  Passing a
 707    null pointer for V turn off filtering. */
 708 void
 709 dict_set_filter (struct dictionary *d, struct variable *v)
 710 {
 711   assert (d != NULL);
 712   assert (v == NULL || dict_contains_var (d, v));
 713
 714   d->filter = v;
 715 }
 716
 717 /* Returns the case limit for dictionary D, or zero if the number
 718    of cases is unlimited. */
 719 size_t
 720 dict_get_case_limit (const struct dictionary *d)
 721 {
 722   assert (d != NULL);
 723
 724   return d->case_limit;
 725 }
 726
 727 /* Sets CASE_LIMIT as the case limit for dictionary D.  Use
 728    0 for CASE_LIMIT to indicate no limit. */
 729 void
 730 dict_set_case_limit (struct dictionary *d, size_t case_limit)
 731 {
 732   assert (d != NULL);
 733
 734   d->case_limit = case_limit;
 735 }
 736
 737 /* Returns the case index of the next value to be added to D.
 738    This value is the number of `union value's that need to be
 739    allocated to store a case for dictionary D. */
 740 int
 741 dict_get_next_value_idx (const struct dictionary *d)
 742 {
 743   assert (d != NULL);
 744
 745   return d->next_value_idx;
 746 }
 747
 748 /* Returns the number of bytes needed to store a case for
 749    dictionary D. */
 750 size_t
 751 dict_get_case_size (const struct dictionary *d)
 752 {
 753   assert (d != NULL);
 754
 755   return sizeof (union value) * dict_get_next_value_idx (d);
 756 }
 757
 758 /* Deletes scratch variables in dictionary D and reassigns values
 759    so that fragmentation is eliminated. */
 760 void
 761 dict_compact_values (struct dictionary *d)
 762 {
 763   size_t i;
 764
 765   d->next_value_idx = 0;
 766   for (i = 0; i < d->var_cnt; )
 767     {
 768       struct variable *v = d->var[i];
 769
 770       if (dict_class_from_id (var_get_name (v)) != DC_SCRATCH)
 771         {
 772           set_var_case_index (v, d->next_value_idx);
 773           d->next_value_idx += var_get_value_cnt (v);
 774           i++;
 775         }
 776       else
 777         dict_delete_var (d, v);
 778     }
 779 }
 780
 781 /* Returns the number of values that would be used by a case if
 782    dict_compact_values() were called. */
 783 size_t
 784 dict_get_compacted_value_cnt (const struct dictionary *d)
 785 {
 786   size_t i;
 787   size_t cnt;
 788
 789   cnt = 0;
 790   for (i = 0; i < d->var_cnt; i++)
 791     if (dict_class_from_id (var_get_name (d->var[i])) != DC_SCRATCH)
 792       cnt += var_get_value_cnt (d->var[i]);
 793   return cnt;
 794 }
 795
 796 /* Creates and returns an array mapping from a dictionary index
 797    to the case index that the corresponding variable will have
 798    after calling dict_compact_values().  Scratch variables
 799    receive -1 for case index because dict_compact_values() will
 800    delete them. */
 801 int *
 802 dict_get_compacted_dict_index_to_case_index (const struct dictionary *d)
 803 {
 804   size_t i;
 805   size_t next_value_idx;
 806   int *map;
 807
 808   map = xnmalloc (d->var_cnt, sizeof *map);
 809   next_value_idx = 0;
 810   for (i = 0; i < d->var_cnt; i++)
 811     {
 812       struct variable *v = d->var[i];
 813
 814       if (dict_class_from_id (var_get_name (v)) != DC_SCRATCH)
 815         {
 816           map[i] = next_value_idx;
 817           next_value_idx += var_get_value_cnt (v);
 818         }
 819       else
 820         map[i] = -1;
 821     }
 822   return map;
 823 }
 824
 825 /* Returns true if a case for dictionary D would be smaller after
 826    compacting, false otherwise.  Compacting a case eliminates
 827    "holes" between values and after the last value.  Holes are
 828    created by deleting variables (or by scratch variables).
 829
 830    The return value may differ from whether compacting a case
 831    from dictionary D would *change* the case: compacting could
 832    rearrange values even if it didn't reduce space
 833    requirements. */
 834 bool
 835 dict_compacting_would_shrink (const struct dictionary *d)
 836 {
 837   return dict_get_compacted_value_cnt (d) < dict_get_next_value_idx (d);
 838 }
 839
 840 /* Returns true if a case for dictionary D would change after
 841    compacting, false otherwise.  Compacting a case eliminates
 842    "holes" between values and after the last value.  Holes are
 843    created by deleting variables (or by scratch variables).
 844
 845    The return value may differ from whether compacting a case
 846    from dictionary D would *shrink* the case: compacting could
 847    rearrange values without reducing space requirements. */
 848 bool
 849 dict_compacting_would_change (const struct dictionary *d)
 850 {
 851   size_t case_idx;
 852   size_t i;
 853
 854   case_idx = 0;
 855   for (i = 0; i < dict_get_var_cnt (d); i++)
 856     {
 857       struct variable *v = dict_get_var (d, i);
 858       if (var_get_case_index (v) != case_idx)
 859         return true;
 860       case_idx += var_get_value_cnt (v);
 861     }
 862   return false;
 863 }
 864 \f
 865 /* How to copy a contiguous range of values between cases. */
 866 struct copy_map
 867   {
 868     size_t src_idx;             /* Starting value index in source case. */
 869     size_t dst_idx;             /* Starting value index in target case. */
 870     size_t cnt;                 /* Number of values. */
 871   };
 872
 873 /* How to compact a case. */
 874 struct dict_compactor
 875   {
 876     struct copy_map *maps;      /* Array of mappings. */
 877     size_t map_cnt;             /* Number of mappings. */
 878   };
 879
 880 /* Creates and returns a dict_compactor that can be used to
 881    compact cases for dictionary D.
 882
 883    Compacting a case eliminates "holes" between values and after
 884    the last value.  Holes are created by deleting variables (or
 885    by scratch variables). */
 886 struct dict_compactor *
 887 dict_make_compactor (const struct dictionary *d)
 888 {
 889   struct dict_compactor *compactor;
 890   struct copy_map *map;
 891   size_t map_allocated;
 892   size_t value_idx;
 893   size_t i;
 894
 895   compactor = xmalloc (sizeof *compactor);
 896   compactor->maps = NULL;
 897   compactor->map_cnt = 0;
 898   map_allocated = 0;
 899
 900   value_idx = 0;
 901   map = NULL;
 902   for (i = 0; i < d->var_cnt; i++)
 903     {
 904       struct variable *v = d->var[i];
 905
 906       if (dict_class_from_id (var_get_name (v)) == DC_SCRATCH)
 907         continue;
 908       if (map != NULL && map->src_idx + map->cnt == var_get_case_index (v))
 909         map->cnt += var_get_value_cnt (v);
 910       else
 911         {
 912           if (compactor->map_cnt == map_allocated)
 913             compactor->maps = x2nrealloc (compactor->maps, &map_allocated,
 914                                           sizeof *compactor->maps);
 915           map = &compactor->maps[compactor->map_cnt++];
 916           map->src_idx = var_get_case_index (v);
 917           map->dst_idx = value_idx;
 918           map->cnt = var_get_value_cnt (v);
 919         }
 920       value_idx += var_get_value_cnt (v);
 921     }
 922
 923   return compactor;
 924 }
 925
 926 /* Compacts SRC by copying it to DST according to the scheme in
 927    COMPACTOR.
 928
 929    Compacting a case eliminates "holes" between values and after
 930    the last value.  Holes are created by deleting variables (or
 931    by scratch variables). */
 932 void
 933 dict_compactor_compact (const struct dict_compactor *compactor,
 934                         struct ccase *dst, const struct ccase *src)
 935 {
 936   size_t i;
 937
 938   for (i = 0; i < compactor->map_cnt; i++)
 939     {
 940       const struct copy_map *map = &compactor->maps[i];
 941       case_copy (dst, map->dst_idx, src, map->src_idx, map->cnt);
 942     }
 943 }
 944
 945 /* Destroys COMPACTOR. */
 946 void
 947 dict_compactor_destroy (struct dict_compactor *compactor)
 948 {
 949   if (compactor != NULL)
 950     {
 951       free (compactor->maps);
 952       free (compactor);
 953     }
 954 }
 955
 956 /* Returns the SPLIT FILE vars (see cmd_split_file()).  Call
 957    dict_get_split_cnt() to determine how many SPLIT FILE vars
 958    there are.  Returns a null pointer if and only if there are no
 959    SPLIT FILE vars. */
 960 struct variable *const *
 961 dict_get_split_vars (const struct dictionary *d)
 962 {
 963   assert (d != NULL);
 964
 965   return d->split;
 966 }
 967
 968 /* Returns the number of SPLIT FILE vars. */
 969 size_t
 970 dict_get_split_cnt (const struct dictionary *d)
 971 {
 972   assert (d != NULL);
 973
 974   return d->split_cnt;
 975 }
 976
 977 /* Sets CNT split vars SPLIT in dictionary D. */
 978 void
 979 dict_set_split_vars (struct dictionary *d,
 980                      struct variable *const *split, size_t cnt)
 981 {
 982   assert (d != NULL);
 983   assert (cnt == 0 || split != NULL);
 984
 985   d->split_cnt = cnt;
 986   d->split = xnrealloc (d->split, cnt, sizeof *d->split);
 987   memcpy (d->split, split, cnt * sizeof *d->split);
 988 }
 989
 990 /* Returns the file label for D, or a null pointer if D is
 991    unlabeled (see cmd_file_label()). */
 992 const char *
 993 dict_get_label (const struct dictionary *d)
 994 {
 995   assert (d != NULL);
 996
 997   return d->label;
 998 }
 999
1000 /* Sets D's file label to LABEL, truncating it to a maximum of 60
1001    characters. */
1002 void
1003 dict_set_label (struct dictionary *d, const char *label)
1004 {
1005   assert (d != NULL);
1006
1007   free (d->label);
1008   if (label == NULL)
1009     d->label = NULL;
1010   else if (strlen (label) < 60)
1011     d->label = xstrdup (label);
1012   else
1013     {
1014       d->label = xmalloc (61);
1015       memcpy (d->label, label, 60);
1016       d->label[60] = '\0';
1017     }
1018 }
1019
1020 /* Returns the documents for D, or a null pointer if D has no
1021    documents (see cmd_document()).. */
1022 const char *
1023 dict_get_documents (const struct dictionary *d)
1024 {
1025   assert (d != NULL);
1026
1027   return d->documents;
1028 }
1029
1030 /* Sets the documents for D to DOCUMENTS, or removes D's
1031    documents if DOCUMENT is a null pointer. */
1032 void
1033 dict_set_documents (struct dictionary *d, const char *documents)
1034 {
1035   assert (d != NULL);
1036
1037   free (d->documents);
1038   if (documents == NULL)
1039     d->documents = NULL;
1040   else
1041     d->documents = xstrdup (documents);
1042 }
1043
1044 /* Creates in D a vector named NAME that contains the CNT
1045    variables in VAR.  Returns true if successful, or false if a
1046    vector named NAME already exists in D. */
1047 bool
1048 dict_create_vector (struct dictionary *d,
1049                     const char *name,
1050                     struct variable **var, size_t cnt)
1051 {
1052   size_t i;
1053
1054   assert (var != NULL);
1055   assert (cnt > 0);
1056   for (i = 0; i < cnt; i++)
1057     assert (dict_contains_var (d, var[i]));
1058
1059   if (dict_lookup_vector (d, name) == NULL)
1060     {
1061       d->vector = xnrealloc (d->vector, d->vector_cnt + 1, sizeof *d->vector);
1062       d->vector[d->vector_cnt++] = vector_create (name, var, cnt);
1063       return true;
1064     }
1065   else
1066     return false;
1067 }
1068
1069 /* Returns the vector in D with index IDX, which must be less
1070    than dict_get_vector_cnt (D). */
1071 const struct vector *
1072 dict_get_vector (const struct dictionary *d, size_t idx)
1073 {
1074   assert (d != NULL);
1075   assert (idx < d->vector_cnt);
1076
1077   return d->vector[idx];
1078 }
1079
1080 /* Returns the number of vectors in D. */
1081 size_t
1082 dict_get_vector_cnt (const struct dictionary *d)
1083 {
1084   assert (d != NULL);
1085
1086   return d->vector_cnt;
1087 }
1088
1089 /* Looks up and returns the vector within D with the given
1090    NAME. */
1091 const struct vector *
1092 dict_lookup_vector (const struct dictionary *d, const char *name)
1093 {
1094   size_t i;
1095   for (i = 0; i < d->vector_cnt; i++)
1096     if (!strcasecmp (vector_get_name (d->vector[i]), name))
1097       return d->vector[i];
1098   return NULL;
1099 }
1100
1101 /* Deletes all vectors from D. */
1102 void
1103 dict_clear_vectors (struct dictionary *d)
1104 {
1105   size_t i;
1106
1107   for (i = 0; i < d->vector_cnt; i++)
1108     vector_destroy (d->vector[i]);
1109   free (d->vector);
1110
1111   d->vector = NULL;
1112   d->vector_cnt = 0;
1113 }
1114
1115 /* Compares two strings. */
1116 static int
1117 compare_strings (const void *a, const void *b, const void *aux UNUSED)
1118 {
1119   return strcmp (a, b);
1120 }
1121
1122 /* Hashes a string. */
1123 static unsigned
1124 hash_string (const void *s, const void *aux UNUSED)
1125 {
1126   return hsh_hash_string (s);
1127 }
1128
1129
1130 /* Sets V's short name to BASE, followed by a suffix of the form
1131    _A, _B, _C, ..., _AA, _AB, etc. according to the value of
1132    SUFFIX_NUMBER.  Truncates BASE as necessary to fit. */
1133 static void
1134 set_var_short_name_suffix (struct variable *v, const char *base,
1135                            int suffix_number)
1136 {
1137   char suffix[SHORT_NAME_LEN + 1];
1138   char short_name[SHORT_NAME_LEN + 1];
1139   char *start, *end;
1140   int len, ofs;
1141
1142   assert (v != NULL);
1143   assert (suffix_number >= 0);
1144
1145   /* Set base name. */
1146   var_set_short_name (v, base);
1147
1148   /* Compose suffix. */
1149   start = end = suffix + sizeof suffix - 1;
1150   *end = '\0';
1151   do
1152     {
1153       *--start = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"[suffix_number % 26];
1154       if (start <= suffix + 1)
1155         msg (SE, _("Variable suffix too large."));
1156       suffix_number /= 26;
1157     }
1158   while (suffix_number > 0);
1159   *--start = '_';
1160
1161   /* Append suffix to V's short name. */
1162   str_copy_trunc (short_name, sizeof short_name, base);
1163   len = end - start;
1164   if (len + strlen (short_name) > SHORT_NAME_LEN)
1165     ofs = SHORT_NAME_LEN - len;
1166   else
1167     ofs = strlen (short_name);
1168   strcpy (short_name + ofs, start);
1169
1170   /* Set name. */
1171   var_set_short_name (v, short_name);
1172 }
1173
1174 /* Assigns a valid, unique short_name[] to each variable in D.
1175    Each variable whose actual name is short has highest priority
1176    for that short name.  Otherwise, variables with an existing
1177    short_name[] have the next highest priority for a given short
1178    name; if it is already taken, then the variable is treated as
1179    if short_name[] had been empty.  Otherwise, long names are
1180    truncated to form short names.  If that causes conflicts,
1181    variables are renamed as PREFIX_A, PREFIX_B, and so on. */
1182 void
1183 dict_assign_short_names (struct dictionary *d)
1184 {
1185   struct hsh_table *short_names;
1186   size_t i;
1187
1188   /* Give variables whose names are short the corresponding short
1189      names, and clear short_names[] that conflict with a variable
1190      name. */
1191   for (i = 0; i < d->var_cnt; i++)
1192     {
1193       struct variable *v = d->var[i];
1194       const char *short_name = var_get_short_name (v);
1195       if (strlen (var_get_name (v)) <= SHORT_NAME_LEN)
1196         var_set_short_name (v, var_get_name (v));
1197       else if (short_name != NULL && dict_lookup_var (d, short_name) != NULL)
1198         var_clear_short_name (v);
1199     }
1200
1201   /* Each variable with an assigned short_name[] now gets it
1202      unless there is a conflict. */
1203   short_names = hsh_create (d->var_cnt, compare_strings, hash_string,
1204                             NULL, NULL);
1205   for (i = 0; i < d->var_cnt; i++)
1206     {
1207       struct variable *v = d->var[i];
1208       const char *name = var_get_short_name (v);
1209       if (name != NULL && hsh_insert (short_names, (char *) name) != NULL)
1210         var_clear_short_name (v);
1211     }
1212
1213   /* Now assign short names to remaining variables. */
1214   for (i = 0; i < d->var_cnt; i++)
1215     {
1216       struct variable *v = d->var[i];
1217       const char *name = var_get_short_name (v);
1218       if (name == NULL)
1219         {
1220           /* Form initial short_name from the variable name, then
1221              try _A, _B, ... _AA, _AB, etc., if needed.*/
1222           int trial = 0;
1223           do
1224             {
1225               if (trial == 0)
1226                 var_set_short_name (v, var_get_name (v));
1227               else
1228                 set_var_short_name_suffix (v, var_get_name (v), trial - 1);
1229
1230               trial++;
1231             }
1232           while (hsh_insert (short_names, (char *) var_get_short_name (v))
1233                  != NULL);
1234         }
1235     }
1236
1237   /* Get rid of hash table. */
1238   hsh_destroy (short_names);
1239 }