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