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