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   struct dictionary *d = vdi.dict;
 404   vdi.dict_index = dict_index;
 405   var_set_vardict (v, &vdi);
 406
 407   if ( d->callbacks && d->callbacks->var_changed )
 408     d->callbacks->var_changed (d, dict_index, d->cb_data);
 409 }
 410
 411 /* Sets the case_index in V's vardict to DICT_INDEX. */
 412 static void
 413 set_var_case_index (struct variable *v, int case_index)
 414 {
 415   struct vardict_info vdi = *var_get_vardict (v);
 416   vdi.case_index = case_index;
 417   var_set_vardict (v, &vdi);
 418 }
 419
 420 /* Re-sets the dict_index in the dictionary variables with
 421    indexes from FROM to TO (exclusive). */
 422 static void
 423 reindex_vars (struct dictionary *d, size_t from, size_t to)
 424 {
 425   size_t i;
 426
 427   for (i = from; i < to; i++)
 428     set_var_dict_index (d->var[i], i);
 429 }
 430
 431 /* Deletes variable V from dictionary D and frees V.
 432
 433    This is a very bad idea if there might be any pointers to V
 434    from outside D.  In general, no variable in should be deleted when
 435    any transformations are active on the dictionary's dataset, because
 436    those transformations might reference the deleted variable.
 437    The safest time to delete a variable is just after a procedure
 438    has been executed, as done by MODIFY VARS.
 439
 440    Pointers to V within D are not a problem, because
 441    dict_delete_var() knows to remove V from split variables,
 442    weights, filters, etc. */
 443 void
 444 dict_delete_var (struct dictionary *d, struct variable *v)
 445 {
 446   int dict_index = var_get_dict_index (v);
 447
 448   assert (dict_contains_var (d, v));
 449
 450   /* Delete aux data. */
 451   var_clear_aux (v);
 452
 453   /* Remove V from splits, weight, filter variables. */
 454   d->split_cnt = remove_equal (d->split, d->split_cnt, sizeof *d->split,
 455                                &v, compare_var_ptrs, NULL);
 456   if (d->weight == v)
 457     d->weight = NULL;
 458   if (d->filter == v)
 459     d->filter = NULL;
 460   dict_clear_vectors (d);
 461
 462   /* Remove V from var array. */
 463   remove_element (d->var, d->var_cnt, sizeof *d->var, dict_index);
 464   d->var_cnt--;
 465
 466   /* Update dict_index for each affected variable. */
 467   reindex_vars (d, dict_index, d->var_cnt);
 468
 469   /* Update name hash. */
 470   hsh_force_delete (d->name_tab, v);
 471
 472
 473   /* Free memory. */
 474   var_clear_vardict (v);
 475   var_destroy (v);
 476
 477   if (d->callbacks && d->callbacks->var_deleted )
 478     d->callbacks->var_deleted (d, dict_index, d->cb_data);
 479 }
 480
 481 /* Deletes the COUNT variables listed in VARS from D.  This is
 482    unsafe; see the comment on dict_delete_var() for details. */
 483 void
 484 dict_delete_vars (struct dictionary *d,
 485                   struct variable *const *vars, size_t count)
 486 {
 487   /* FIXME: this can be done in O(count) time, but this algorithm
 488      is O(count**2). */
 489   assert (d != NULL);
 490   assert (count == 0 || vars != NULL);
 491
 492   while (count-- > 0)
 493     dict_delete_var (d, *vars++);
 494 }
 495
 496 /* Deletes the COUNT variables in D starting at index IDX.  This
 497    is unsafe; see the comment on dict_delete_var() for
 498    details. */
 499 void
 500 dict_delete_consecutive_vars (struct dictionary *d, size_t idx, size_t count)
 501 {
 502   /* FIXME: this can be done in O(count) time, but this algorithm
 503      is O(count**2). */
 504   assert (idx + count <= d->var_cnt);
 505
 506   while (count-- > 0)
 507     dict_delete_var (d, d->var[idx]);
 508 }
 509
 510 /* Deletes scratch variables from dictionary D. */
 511 void
 512 dict_delete_scratch_vars (struct dictionary *d)
 513 {
 514   int i;
 515
 516   /* FIXME: this can be done in O(count) time, but this algorithm
 517      is O(count**2). */
 518   assert (d != NULL);
 519
 520   for (i = 0; i < d->var_cnt; )
 521     if (dict_class_from_id (var_get_name (d->var[i])) == DC_SCRATCH)
 522       dict_delete_var (d, d->var[i]);
 523     else
 524       i++;
 525 }
 526
 527 /* Moves V to 0-based position IDX in D.  Other variables in D,
 528    if any, retain their relative positions.  Runs in time linear
 529    in the distance moved. */
 530 void
 531 dict_reorder_var (struct dictionary *d, struct variable *v, size_t new_index)
 532 {
 533   size_t old_index = var_get_dict_index (v);
 534
 535   assert (new_index < d->var_cnt);
 536   move_element (d->var, d->var_cnt, sizeof *d->var, old_index, new_index);
 537   reindex_vars (d, MIN (old_index, new_index), MAX (old_index, new_index) + 1);
 538 }
 539
 540 /* Reorders the variables in D, placing the COUNT variables
 541    listed in ORDER in that order at the beginning of D.  The
 542    other variables in D, if any, retain their relative
 543    positions. */
 544 void
 545 dict_reorder_vars (struct dictionary *d,
 546                    struct variable *const *order, size_t count)
 547 {
 548   struct variable **new_var;
 549   size_t i;
 550
 551   assert (d != NULL);
 552   assert (count == 0 || order != NULL);
 553   assert (count <= d->var_cnt);
 554
 555   new_var = xnmalloc (d->var_cnt, sizeof *new_var);
 556   memcpy (new_var, order, count * sizeof *new_var);
 557   for (i = 0; i < count; i++)
 558     {
 559       size_t index = var_get_dict_index (order[i]);
 560       assert (d->var[index] == order[i]);
 561       d->var[index] = NULL;
 562       set_var_dict_index (order[i], i);
 563     }
 564   for (i = 0; i < d->var_cnt; i++)
 565     if (d->var[i] != NULL)
 566       {
 567         assert (count < d->var_cnt);
 568         new_var[count] = d->var[i];
 569         set_var_dict_index (new_var[count], count);
 570         count++;
 571       }
 572   free (d->var);
 573   d->var = new_var;
 574 }
 575
 576 /* Changes the name of variable V in dictionary D to NEW_NAME. */
 577 static void
 578 rename_var (struct dictionary *d, struct variable *v, const char *new_name)
 579 {
 580   struct vardict_info vdi;
 581
 582   assert (dict_contains_var (d, v));
 583
 584   vdi = *var_get_vardict (v);
 585   var_clear_vardict (v);
 586   var_set_name (v, new_name);
 587   var_set_vardict (v, &vdi);
 588 }
 589
 590 /* Changes the name of V in D to name NEW_NAME.  Assert-fails if
 591    a variable named NEW_NAME is already in D, except that
 592    NEW_NAME may be the same as V's existing name. */
 593 void
 594 dict_rename_var (struct dictionary *d, struct variable *v,
 595                  const char *new_name)
 596 {
 597   assert (!strcasecmp (var_get_name (v), new_name)
 598           || dict_lookup_var (d, new_name) == NULL);
 599
 600   hsh_force_delete (d->name_tab, v);
 601   rename_var (d, v, new_name);
 602   hsh_force_insert (d->name_tab, v);
 603
 604   if (get_algorithm () == ENHANCED)
 605     var_clear_short_name (v);
 606
 607   if ( d->callbacks && d->callbacks->var_changed )
 608     d->callbacks->var_changed (d, var_get_dict_index (v), d->cb_data);
 609 }
 610
 611 /* Renames COUNT variables specified in VARS to the names given
 612    in NEW_NAMES within dictionary D.  If the renaming would
 613    result in a duplicate variable name, returns false and stores a
 614    name that would be duplicated into *ERR_NAME (if ERR_NAME is
 615    non-null).  Otherwise, the renaming is successful, and true
 616    is returned. */
 617 bool
 618 dict_rename_vars (struct dictionary *d,
 619                   struct variable **vars, char **new_names, size_t count,
 620                   char **err_name)
 621 {
 622   struct pool *pool;
 623   char **old_names;
 624   size_t i;
 625
 626   assert (count == 0 || vars != NULL);
 627   assert (count == 0 || new_names != NULL);
 628
 629   /* Save the names of the variables to be renamed. */
 630   pool = pool_create ();
 631   old_names = pool_nalloc (pool, count, sizeof *old_names);
 632   for (i = 0; i < count; i++)
 633     old_names[i] = pool_strdup (pool, var_get_name (vars[i]));
 634
 635   /* Remove the variables to be renamed from the name hash,
 636      and rename them. */
 637   for (i = 0; i < count; i++)
 638     {
 639       hsh_force_delete (d->name_tab, vars[i]);
 640       rename_var (d, vars[i], new_names[i]);
 641     }
 642
 643   /* Add the renamed variables back into the name hash,
 644      checking for conflicts. */
 645   for (i = 0; i < count; i++)
 646     if (hsh_insert (d->name_tab, vars[i]) != NULL)
 647       {
 648         /* There is a name conflict.
 649            Back out all the name changes that have already
 650            taken place, and indicate failure. */
 651         size_t fail_idx = i;
 652         if (err_name != NULL)
 653           *err_name = new_names[i];
 654
 655         for (i = 0; i < fail_idx; i++)
 656           hsh_force_delete (d->name_tab, vars[i]);
 657
 658         for (i = 0; i < count; i++)
 659           {
 660             rename_var (d, vars[i], old_names[i]);
 661             hsh_force_insert (d->name_tab, vars[i]);
 662           }
 663
 664         pool_destroy (pool);
 665         return false;
 666       }
 667
 668   /* Clear short names. */
 669   if (get_algorithm () == ENHANCED)
 670     for (i = 0; i < count; i++)
 671       var_clear_short_name (vars[i]);
 672
 673   pool_destroy (pool);
 674   return true;
 675 }
 676
 677 /* Returns the weighting variable in dictionary D, or a null
 678    pointer if the dictionary is unweighted. */
 679 struct variable *
 680 dict_get_weight (const struct dictionary *d)
 681 {
 682   assert (d != NULL);
 683   assert (d->weight == NULL || dict_contains_var (d, d->weight));
 684
 685   return d->weight;
 686 }
 687
 688 /* Returns the value of D's weighting variable in case C, except that a
 689    negative weight is returned as 0.  Returns 1 if the dictionary is
 690    unweighted. Will warn about missing, negative, or zero values if
 691    warn_on_invalid is true. The function will set warn_on_invalid to false
 692    if an invalid weight is found. */
 693 double
 694 dict_get_case_weight (const struct dictionary *d, const struct ccase *c,
 695                       bool *warn_on_invalid)
 696 {
 697   assert (d != NULL);
 698   assert (c != NULL);
 699
 700   if (d->weight == NULL)
 701     return 1.0;
 702   else
 703     {
 704       double w = case_num (c, d->weight);
 705       if (w < 0.0 || var_is_num_missing (d->weight, w, MV_ANY))
 706         w = 0.0;
 707       if ( w == 0.0 && *warn_on_invalid ) {
 708           *warn_on_invalid = false;
 709           msg (SW, _("At least one case in the data file had a weight value "
 710                      "that was user-missing, system-missing, zero, or "
 711                      "negative.  These case(s) were ignored."));
 712       }
 713       return w;
 714     }
 715 }
 716
 717 /* Sets the weighting variable of D to V, or turning off
 718    weighting if V is a null pointer. */
 719 void
 720 dict_set_weight (struct dictionary *d, struct variable *v)
 721 {
 722   assert (d != NULL);
 723   assert (v == NULL || dict_contains_var (d, v));
 724   assert (v == NULL || var_is_numeric (v));
 725
 726   d->weight = v;
 727 }
 728
 729 /* Returns the filter variable in dictionary D (see cmd_filter())
 730    or a null pointer if the dictionary is unfiltered. */
 731 struct variable *
 732 dict_get_filter (const struct dictionary *d)
 733 {
 734   assert (d != NULL);
 735   assert (d->filter == NULL || dict_contains_var (d, d->filter));
 736
 737   return d->filter;
 738 }
 739
 740 /* Sets V as the filter variable for dictionary D.  Passing a
 741    null pointer for V turn off filtering. */
 742 void
 743 dict_set_filter (struct dictionary *d, struct variable *v)
 744 {
 745   assert (d != NULL);
 746   assert (v == NULL || dict_contains_var (d, v));
 747
 748   d->filter = v;
 749 }
 750
 751 /* Returns the case limit for dictionary D, or zero if the number
 752    of cases is unlimited. */
 753 size_t
 754 dict_get_case_limit (const struct dictionary *d)
 755 {
 756   assert (d != NULL);
 757
 758   return d->case_limit;
 759 }
 760
 761 /* Sets CASE_LIMIT as the case limit for dictionary D.  Use
 762    0 for CASE_LIMIT to indicate no limit. */
 763 void
 764 dict_set_case_limit (struct dictionary *d, size_t case_limit)
 765 {
 766   assert (d != NULL);
 767
 768   d->case_limit = case_limit;
 769 }
 770
 771 /* Returns the case index of the next value to be added to D.
 772    This value is the number of `union value's that need to be
 773    allocated to store a case for dictionary D. */
 774 int
 775 dict_get_next_value_idx (const struct dictionary *d)
 776 {
 777   assert (d != NULL);
 778
 779   return d->next_value_idx;
 780 }
 781
 782 /* Returns the number of bytes needed to store a case for
 783    dictionary D. */
 784 size_t
 785 dict_get_case_size (const struct dictionary *d)
 786 {
 787   assert (d != NULL);
 788
 789   return sizeof (union value) * dict_get_next_value_idx (d);
 790 }
 791
 792 /* Deletes scratch variables in dictionary D and reassigns values
 793    so that fragmentation is eliminated. */
 794 void
 795 dict_compact_values (struct dictionary *d)
 796 {
 797   size_t i;
 798
 799   d->next_value_idx = 0;
 800   for (i = 0; i < d->var_cnt; )
 801     {
 802       struct variable *v = d->var[i];
 803
 804       if (dict_class_from_id (var_get_name (v)) != DC_SCRATCH)
 805         {
 806           set_var_case_index (v, d->next_value_idx);
 807           d->next_value_idx += var_get_value_cnt (v);
 808           i++;
 809         }
 810       else
 811         dict_delete_var (d, v);
 812     }
 813 }
 814
 815 /* Returns the number of values that would be used by a case if
 816    dict_compact_values() were called. */
 817 size_t
 818 dict_get_compacted_value_cnt (const struct dictionary *d)
 819 {
 820   size_t i;
 821   size_t cnt;
 822
 823   cnt = 0;
 824   for (i = 0; i < d->var_cnt; i++)
 825     if (dict_class_from_id (var_get_name (d->var[i])) != DC_SCRATCH)
 826       cnt += var_get_value_cnt (d->var[i]);
 827   return cnt;
 828 }
 829
 830 /* Creates and returns an array mapping from a dictionary index
 831    to the case index that the corresponding variable will have
 832    after calling dict_compact_values().  Scratch variables
 833    receive -1 for case index because dict_compact_values() will
 834    delete them. */
 835 int *
 836 dict_get_compacted_dict_index_to_case_index (const struct dictionary *d)
 837 {
 838   size_t i;
 839   size_t next_value_idx;
 840   int *map;
 841
 842   map = xnmalloc (d->var_cnt, sizeof *map);
 843   next_value_idx = 0;
 844   for (i = 0; i < d->var_cnt; i++)
 845     {
 846       struct variable *v = d->var[i];
 847
 848       if (dict_class_from_id (var_get_name (v)) != DC_SCRATCH)
 849         {
 850           map[i] = next_value_idx;
 851           next_value_idx += var_get_value_cnt (v);
 852         }
 853       else
 854         map[i] = -1;
 855     }
 856   return map;
 857 }
 858
 859 /* Returns true if a case for dictionary D would be smaller after
 860    compacting, false otherwise.  Compacting a case eliminates
 861    "holes" between values and after the last value.  Holes are
 862    created by deleting variables (or by scratch variables).
 863
 864    The return value may differ from whether compacting a case
 865    from dictionary D would *change* the case: compacting could
 866    rearrange values even if it didn't reduce space
 867    requirements. */
 868 bool
 869 dict_compacting_would_shrink (const struct dictionary *d)
 870 {
 871   return dict_get_compacted_value_cnt (d) < dict_get_next_value_idx (d);
 872 }
 873
 874 /* Returns true if a case for dictionary D would change after
 875    compacting, false otherwise.  Compacting a case eliminates
 876    "holes" between values and after the last value.  Holes are
 877    created by deleting variables (or by scratch variables).
 878
 879    The return value may differ from whether compacting a case
 880    from dictionary D would *shrink* the case: compacting could
 881    rearrange values without reducing space requirements. */
 882 bool
 883 dict_compacting_would_change (const struct dictionary *d)
 884 {
 885   size_t case_idx;
 886   size_t i;
 887
 888   case_idx = 0;
 889   for (i = 0; i < dict_get_var_cnt (d); i++)
 890     {
 891       struct variable *v = dict_get_var (d, i);
 892       if (var_get_case_index (v) != case_idx)
 893         return true;
 894       case_idx += var_get_value_cnt (v);
 895     }
 896   return false;
 897 }
 898 \f
 899 /* How to copy a contiguous range of values between cases. */
 900 struct copy_map
 901   {
 902     size_t src_idx;             /* Starting value index in source case. */
 903     size_t dst_idx;             /* Starting value index in target case. */
 904     size_t cnt;                 /* Number of values. */
 905   };
 906
 907 /* How to compact a case. */
 908 struct dict_compactor
 909   {
 910     struct copy_map *maps;      /* Array of mappings. */
 911     size_t map_cnt;             /* Number of mappings. */
 912   };
 913
 914 /* Creates and returns a dict_compactor that can be used to
 915    compact cases for dictionary D.
 916
 917    Compacting a case eliminates "holes" between values and after
 918    the last value.  Holes are created by deleting variables (or
 919    by scratch variables). */
 920 struct dict_compactor *
 921 dict_make_compactor (const struct dictionary *d)
 922 {
 923   struct dict_compactor *compactor;
 924   struct copy_map *map;
 925   size_t map_allocated;
 926   size_t value_idx;
 927   size_t i;
 928
 929   compactor = xmalloc (sizeof *compactor);
 930   compactor->maps = NULL;
 931   compactor->map_cnt = 0;
 932   map_allocated = 0;
 933
 934   value_idx = 0;
 935   map = NULL;
 936   for (i = 0; i < d->var_cnt; i++)
 937     {
 938       struct variable *v = d->var[i];
 939
 940       if (dict_class_from_id (var_get_name (v)) == DC_SCRATCH)
 941         continue;
 942       if (map != NULL && map->src_idx + map->cnt == var_get_case_index (v))
 943         map->cnt += var_get_value_cnt (v);
 944       else
 945         {
 946           if (compactor->map_cnt == map_allocated)
 947             compactor->maps = x2nrealloc (compactor->maps, &map_allocated,
 948                                           sizeof *compactor->maps);
 949           map = &compactor->maps[compactor->map_cnt++];
 950           map->src_idx = var_get_case_index (v);
 951           map->dst_idx = value_idx;
 952           map->cnt = var_get_value_cnt (v);
 953         }
 954       value_idx += var_get_value_cnt (v);
 955     }
 956
 957   return compactor;
 958 }
 959
 960 /* Compacts SRC by copying it to DST according to the scheme in
 961    COMPACTOR.
 962
 963    Compacting a case eliminates "holes" between values and after
 964    the last value.  Holes are created by deleting variables (or
 965    by scratch variables). */
 966 void
 967 dict_compactor_compact (const struct dict_compactor *compactor,
 968                         struct ccase *dst, const struct ccase *src)
 969 {
 970   size_t i;
 971
 972   for (i = 0; i < compactor->map_cnt; i++)
 973     {
 974       const struct copy_map *map = &compactor->maps[i];
 975       case_copy (dst, map->dst_idx, src, map->src_idx, map->cnt);
 976     }
 977 }
 978
 979 /* Destroys COMPACTOR. */
 980 void
 981 dict_compactor_destroy (struct dict_compactor *compactor)
 982 {
 983   if (compactor != NULL)
 984     {
 985       free (compactor->maps);
 986       free (compactor);
 987     }
 988 }
 989
 990 /* Returns the SPLIT FILE vars (see cmd_split_file()).  Call
 991    dict_get_split_cnt() to determine how many SPLIT FILE vars
 992    there are.  Returns a null pointer if and only if there are no
 993    SPLIT FILE vars. */
 994 struct variable *const *
 995 dict_get_split_vars (const struct dictionary *d)
 996 {
 997   assert (d != NULL);
 998
 999   return d->split;
1000 }
1001
1002 /* Returns the number of SPLIT FILE vars. */
1003 size_t
1004 dict_get_split_cnt (const struct dictionary *d)
1005 {
1006   assert (d != NULL);
1007
1008   return d->split_cnt;
1009 }
1010
1011 /* Sets CNT split vars SPLIT in dictionary D. */
1012 void
1013 dict_set_split_vars (struct dictionary *d,
1014                      struct variable *const *split, size_t cnt)
1015 {
1016   assert (d != NULL);
1017   assert (cnt == 0 || split != NULL);
1018
1019   d->split_cnt = cnt;
1020   d->split = xnrealloc (d->split, cnt, sizeof *d->split);
1021   memcpy (d->split, split, cnt * sizeof *d->split);
1022 }
1023
1024 /* Returns the file label for D, or a null pointer if D is
1025    unlabeled (see cmd_file_label()). */
1026 const char *
1027 dict_get_label (const struct dictionary *d)
1028 {
1029   assert (d != NULL);
1030
1031   return d->label;
1032 }
1033
1034 /* Sets D's file label to LABEL, truncating it to a maximum of 60
1035    characters. */
1036 void
1037 dict_set_label (struct dictionary *d, const char *label)
1038 {
1039   assert (d != NULL);
1040
1041   free (d->label);
1042   if (label == NULL)
1043     d->label = NULL;
1044   else if (strlen (label) < 60)
1045     d->label = xstrdup (label);
1046   else
1047     {
1048       d->label = xmalloc (61);
1049       memcpy (d->label, label, 60);
1050       d->label[60] = '\0';
1051     }
1052 }
1053
1054 /* Returns the documents for D, or a null pointer if D has no
1055    documents (see cmd_document()).. */
1056 const char *
1057 dict_get_documents (const struct dictionary *d)
1058 {
1059   assert (d != NULL);
1060
1061   return d->documents;
1062 }
1063
1064 /* Sets the documents for D to DOCUMENTS, or removes D's
1065    documents if DOCUMENT is a null pointer. */
1066 void
1067 dict_set_documents (struct dictionary *d, const char *documents)
1068 {
1069   assert (d != NULL);
1070
1071   free (d->documents);
1072   if (documents == NULL)
1073     d->documents = NULL;
1074   else
1075     d->documents = xstrdup (documents);
1076 }
1077
1078 /* Creates in D a vector named NAME that contains the CNT
1079    variables in VAR.  Returns true if successful, or false if a
1080    vector named NAME already exists in D. */
1081 bool
1082 dict_create_vector (struct dictionary *d,
1083                     const char *name,
1084                     struct variable **var, size_t cnt)
1085 {
1086   size_t i;
1087
1088   assert (var != NULL);
1089   assert (cnt > 0);
1090   for (i = 0; i < cnt; i++)
1091     assert (dict_contains_var (d, var[i]));
1092
1093   if (dict_lookup_vector (d, name) == NULL)
1094     {
1095       d->vector = xnrealloc (d->vector, d->vector_cnt + 1, sizeof *d->vector);
1096       d->vector[d->vector_cnt++] = vector_create (name, var, cnt);
1097       return true;
1098     }
1099   else
1100     return false;
1101 }
1102
1103 /* Returns the vector in D with index IDX, which must be less
1104    than dict_get_vector_cnt (D). */
1105 const struct vector *
1106 dict_get_vector (const struct dictionary *d, size_t idx)
1107 {
1108   assert (d != NULL);
1109   assert (idx < d->vector_cnt);
1110
1111   return d->vector[idx];
1112 }
1113
1114 /* Returns the number of vectors in D. */
1115 size_t
1116 dict_get_vector_cnt (const struct dictionary *d)
1117 {
1118   assert (d != NULL);
1119
1120   return d->vector_cnt;
1121 }
1122
1123 /* Looks up and returns the vector within D with the given
1124    NAME. */
1125 const struct vector *
1126 dict_lookup_vector (const struct dictionary *d, const char *name)
1127 {
1128   size_t i;
1129   for (i = 0; i < d->vector_cnt; i++)
1130     if (!strcasecmp (vector_get_name (d->vector[i]), name))
1131       return d->vector[i];
1132   return NULL;
1133 }
1134
1135 /* Deletes all vectors from D. */
1136 void
1137 dict_clear_vectors (struct dictionary *d)
1138 {
1139   size_t i;
1140
1141   for (i = 0; i < d->vector_cnt; i++)
1142     vector_destroy (d->vector[i]);
1143   free (d->vector);
1144
1145   d->vector = NULL;
1146   d->vector_cnt = 0;
1147 }
1148
1149 /* Compares two strings. */
1150 static int
1151 compare_strings (const void *a, const void *b, const void *aux UNUSED)
1152 {
1153   return strcmp (a, b);
1154 }
1155
1156 /* Hashes a string. */
1157 static unsigned
1158 hash_string (const void *s, const void *aux UNUSED)
1159 {
1160   return hsh_hash_string (s);
1161 }
1162
1163
1164 /* Sets V's short name to BASE, followed by a suffix of the form
1165    _A, _B, _C, ..., _AA, _AB, etc. according to the value of
1166    SUFFIX_NUMBER.  Truncates BASE as necessary to fit. */
1167 static void
1168 set_var_short_name_suffix (struct variable *v, const char *base,
1169                            int suffix_number)
1170 {
1171   char suffix[SHORT_NAME_LEN + 1];
1172   char short_name[SHORT_NAME_LEN + 1];
1173   char *start, *end;
1174   int len, ofs;
1175
1176   assert (v != NULL);
1177   assert (suffix_number >= 0);
1178
1179   /* Set base name. */
1180   var_set_short_name (v, base);
1181
1182   /* Compose suffix. */
1183   start = end = suffix + sizeof suffix - 1;
1184   *end = '\0';
1185   do
1186     {
1187       *--start = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"[suffix_number % 26];
1188       if (start <= suffix + 1)
1189         msg (SE, _("Variable suffix too large."));
1190       suffix_number /= 26;
1191     }
1192   while (suffix_number > 0);
1193   *--start = '_';
1194
1195   /* Append suffix to V's short name. */
1196   str_copy_trunc (short_name, sizeof short_name, base);
1197   len = end - start;
1198   if (len + strlen (short_name) > SHORT_NAME_LEN)
1199     ofs = SHORT_NAME_LEN - len;
1200   else
1201     ofs = strlen (short_name);
1202   strcpy (short_name + ofs, start);
1203
1204   /* Set name. */
1205   var_set_short_name (v, short_name);
1206 }
1207
1208 /* Assigns a valid, unique short_name[] to each variable in D.
1209    Each variable whose actual name is short has highest priority
1210    for that short name.  Otherwise, variables with an existing
1211    short_name[] have the next highest priority for a given short
1212    name; if it is already taken, then the variable is treated as
1213    if short_name[] had been empty.  Otherwise, long names are
1214    truncated to form short names.  If that causes conflicts,
1215    variables are renamed as PREFIX_A, PREFIX_B, and so on. */
1216 void
1217 dict_assign_short_names (struct dictionary *d)
1218 {
1219   struct hsh_table *short_names;
1220   size_t i;
1221
1222   /* Give variables whose names are short the corresponding short
1223      names, and clear short_names[] that conflict with a variable
1224      name. */
1225   for (i = 0; i < d->var_cnt; i++)
1226     {
1227       struct variable *v = d->var[i];
1228       const char *short_name = var_get_short_name (v);
1229       if (strlen (var_get_name (v)) <= SHORT_NAME_LEN)
1230         var_set_short_name (v, var_get_name (v));
1231       else if (short_name != NULL && dict_lookup_var (d, short_name) != NULL)
1232         var_clear_short_name (v);
1233     }
1234
1235   /* Each variable with an assigned short_name[] now gets it
1236      unless there is a conflict. */
1237   short_names = hsh_create (d->var_cnt, compare_strings, hash_string,
1238                             NULL, NULL);
1239   for (i = 0; i < d->var_cnt; i++)
1240     {
1241       struct variable *v = d->var[i];
1242       const char *name = var_get_short_name (v);
1243       if (name != NULL && hsh_insert (short_names, (char *) name) != NULL)
1244         var_clear_short_name (v);
1245     }
1246
1247   /* Now assign short names to remaining variables. */
1248   for (i = 0; i < d->var_cnt; i++)
1249     {
1250       struct variable *v = d->var[i];
1251       const char *name = var_get_short_name (v);
1252       if (name == NULL)
1253         {
1254           /* Form initial short_name from the variable name, then
1255              try _A, _B, ... _AA, _AB, etc., if needed.*/
1256           int trial = 0;
1257           do
1258             {
1259               if (trial == 0)
1260                 var_set_short_name (v, var_get_name (v));
1261               else
1262                 set_var_short_name_suffix (v, var_get_name (v), trial - 1);
1263
1264               trial++;
1265             }
1266           while (hsh_insert (short_names, (char *) var_get_short_name (v))
1267                  != NULL);
1268         }
1269     }
1270
1271   /* Get rid of hash table. */
1272   hsh_destroy (short_names);
1273 }
1274
1275
1276 /* Called from variable.c to notify the dictionary that some property of
1277    the variable has changed */
1278 void
1279 dict_var_changed (const struct variable *v)
1280 {
1281   if ( var_has_vardict (v))
1282     {
1283       const struct vardict_info *vdi = var_get_vardict (v);
1284       struct dictionary *d;
1285
1286       d = vdi->dict;
1287
1288       if ( d->callbacks && d->callbacks->var_changed )
1289         d->callbacks->var_changed (d, var_get_dict_index (v), d->cb_data);
1290     }
1291 }