pintos-os.org Git - pspp/blob - src/data/case-map.c

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 1997-9, 2000, 2006, 2007, 2009, 2011, 2013 Free Software Foundation, Inc.
   3
   4    This program is free software: you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation, either version 3 of the License, or
   7    (at your option) any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program.  If not, see <http://www.gnu.org/licenses/>. */
  16
  17 #include <config.h>
  18
  19 #include "data/case-map.h"
  20
  21 #include <stdio.h>
  22 #include <stdlib.h>
  23
  24 #include "data/casereader.h"
  25 #include "data/casewriter.h"
  26 #include "data/dictionary.h"
  27 #include "data/variable.h"
  28 #include "data/case.h"
  29 #include "libpspp/assertion.h"
  30 #include "libpspp/hash-functions.h"
  31 #include "libpspp/hmap.h"
  32
  33 #include "gl/xalloc.h"
  34
  35 /* A case map. */
  36 struct case_map
  37   {
  38     struct caseproto *proto;   /* Prototype for output cases. */
  39     int *map;                  /* For each destination index, the
  40                                   corresponding source index. */
  41   };
  42
  43 static struct ccase *translate_case (struct ccase *, void *map_);
  44 static bool destroy_case_map (void *map_);
  45
  46 /* Creates and returns an empty map that outputs cases matching
  47    PROTO. */
  48 static struct case_map *
  49 create_case_map (const struct caseproto *proto)
  50 {
  51   size_t n_values = caseproto_get_n_widths (proto);
  52   struct case_map *map;
  53   size_t i;
  54
  55   map = xmalloc (sizeof *map);
  56   map->proto = caseproto_ref (proto);
  57   map->map = xnmalloc (n_values, sizeof *map->map);
  58   for (i = 0; i < n_values; i++)
  59     map->map[i] = -1;
  60
  61   return map;
  62 }
  63
  64 /* Inserts into MAP a mapping of the value at index FROM in the
  65    source case to the value at index TO in the destination
  66    case. */
  67 static void
  68 insert_mapping (struct case_map *map, size_t from, size_t to)
  69 {
  70   assert (to < caseproto_get_n_widths (map->proto));
  71   assert (map->map[to] == -1);
  72   map->map[to] = from;
  73 }
  74
  75 /* Destroys case map MAP. */
  76 void
  77 case_map_destroy (struct case_map *map)
  78 {
  79   if (map != NULL)
  80     {
  81       caseproto_unref (map->proto);
  82       free (map->map);
  83       free (map);
  84     }
  85 }
  86
  87 /* If MAP is nonnull, returns a new case that is the result of
  88    applying case map MAP to SRC, and unrefs SRC.
  89
  90    If MAP is null, returns SRC unchanged. */
  91 struct ccase *
  92 case_map_execute (const struct case_map *map, struct ccase *src)
  93 {
  94   if (map != NULL)
  95     {
  96       size_t n_values = caseproto_get_n_widths (map->proto);
  97       struct ccase *dst;
  98       size_t dst_idx;
  99
 100       dst = case_create (map->proto);
 101       for (dst_idx = 0; dst_idx < n_values; dst_idx++)
 102         {
 103           int src_idx = map->map[dst_idx];
 104           if (src_idx != -1)
 105             value_copy (case_data_rw_idx (dst, dst_idx), case_data_idx (src, src_idx), caseproto_get_width (map->proto, dst_idx));
 106         }
 107       case_unref (src);
 108       return dst;
 109     }
 110   else
 111     return src;
 112 }
 113
 114 /* Returns the prototype for output cases created by MAP.  The
 115    caller must not unref the returned case prototype. */
 116 const struct caseproto *
 117 case_map_get_proto (const struct case_map *map)
 118 {
 119   return map->proto;
 120 }
 121
 122 /* Creates and returns a new casereader whose cases are produced
 123    by reading from SUBREADER and executing the actions of MAP.
 124    The casereader will have as many `union value's as MAP.  When
 125    the new casereader is destroyed, MAP will be destroyed too.
 126
 127    After this function is called, SUBREADER must not ever again
 128    be referenced directly.  It will be destroyed automatically
 129    when the returned casereader is destroyed. */
 130 struct casereader *
 131 case_map_create_input_translator (struct case_map *map,
 132                                   struct casereader *subreader)
 133 {
 134     return casereader_create_translator (subreader,
 135                                          case_map_get_proto (map),
 136                                          translate_case,
 137                                          destroy_case_map,
 138                                          map);
 139 }
 140
 141 /* Creates and returns a new casewriter.  Cases written to the
 142    new casewriter will be passed through MAP and written to
 143    SUBWRITER.  The casewriter will have as many `union value's as
 144    MAP.  When the new casewriter is destroyed, MAP will be
 145    destroyed too.
 146
 147    After this function is called, SUBWRITER must not ever again
 148    be referenced directly.  It will be destroyed automatically
 149    when the returned casewriter is destroyed. */
 150 struct casewriter *
 151 case_map_create_output_translator (struct case_map *map,
 152                                    struct casewriter *subwriter)
 153 {
 154     return casewriter_create_translator (subwriter,
 155                                          case_map_get_proto (map),
 156                                          translate_case,
 157                                          destroy_case_map,
 158                                          map);
 159 }
 160
 161 /* Casereader/casewriter translation callback. */
 162 static struct ccase *
 163 translate_case (struct ccase *input, void *map_)
 164 {
 165   struct case_map *map = map_;
 166   return case_map_execute (map, input);
 167 }
 168
 169 /* Casereader/casewriter destruction callback. */
 170 static bool
 171 destroy_case_map (void *map_)
 172 {
 173   struct case_map *map = map_;
 174   case_map_destroy (map);
 175   return true;
 176 }
 177
 178 /* Creates and returns a case_map that can be used to compact
 179    cases for dictionary D.
 180
 181    Compacting a case eliminates "holes" between values and after
 182    the last value.  (Holes are created by deleting variables.)
 183
 184    All variables are compacted if EXCLUDE_CLASSES is 0, or it may
 185    contain one or more of (1u << DC_ORDINARY), (1u << DC_SYSTEM),
 186    or (1u << DC_SCRATCH) to cause the corresponding type of
 187    variable to be deleted during compaction. */
 188 struct case_map *
 189 case_map_to_compact_dict (const struct dictionary *d,
 190                           unsigned int exclude_classes)
 191 {
 192   size_t n_vars = dict_get_var_cnt (d);
 193   struct caseproto *proto;
 194   struct case_map *map;
 195   size_t n_values;
 196   size_t i;
 197
 198   /* Create the case mapping. */
 199   proto = dict_get_compacted_proto (d, exclude_classes);
 200   map = create_case_map (proto);
 201   caseproto_unref (proto);
 202
 203   /* Add the values to the case mapping. */
 204   n_values = 0;
 205   for (i = 0; i < n_vars; i++)
 206     {
 207       struct variable *v = dict_get_var (d, i);
 208       if (!(exclude_classes & (1u << var_get_dict_class (v))))
 209         insert_mapping (map, var_get_case_index (v), n_values++);
 210     }
 211
 212   return map;
 213 }
 214 \f
 215 struct stage_var
 216   {
 217     struct hmap_node hmap_node; /* In struct case_map_stage's 'stage_vars'. */
 218     const struct variable *var;
 219     int case_index;
 220   };
 221
 222 struct case_map_stage
 223   {
 224     const struct dictionary *dict;
 225     struct hmap stage_vars;
 226   };
 227
 228 /* Prepares and returns a "struct case_map_stage" for producing a case map for
 229    DICT.  Afterward, the caller may delete, reorder, or rename variables within
 230    DICT at will before using case_map_stage_get_case_map() to produce the case
 231    map.
 232
 233    The caller must *not* add new variables to DICT. */
 234 struct case_map_stage *
 235 case_map_stage_create (const struct dictionary *dict)
 236 {
 237   size_t n_vars = dict_get_var_cnt (dict);
 238   struct case_map_stage *stage;
 239   size_t i;
 240
 241   stage = xmalloc (sizeof *stage);
 242   stage->dict = dict;
 243   hmap_init (&stage->stage_vars);
 244
 245   for (i = 0; i < n_vars; i++)
 246     {
 247       const struct variable *var = dict_get_var (dict, i);
 248       struct stage_var *stage_var;
 249
 250       stage_var = xmalloc (sizeof *stage_var);
 251       stage_var->var = var;
 252       stage_var->case_index = var_get_case_index (var);
 253       hmap_insert (&stage->stage_vars, &stage_var->hmap_node,
 254                    hash_pointer (var, 0));
 255     }
 256
 257   return stage;
 258 }
 259
 260 /* Destroys STAGE, which was created by case_map_stage_create(). */
 261 void
 262 case_map_stage_destroy (struct case_map_stage *stage)
 263 {
 264   if (stage != NULL)
 265     {
 266       struct stage_var *stage_var, *next_stage_var;
 267
 268       HMAP_FOR_EACH_SAFE (stage_var, next_stage_var,
 269                           struct stage_var, hmap_node, &stage->stage_vars)
 270         {
 271           hmap_delete (&stage->stage_vars, &stage_var->hmap_node);
 272           free (stage_var);
 273         }
 274       hmap_destroy (&stage->stage_vars);
 275       free (stage);
 276     }
 277 }
 278
 279 static const struct stage_var *
 280 case_map_stage_find_var (const struct case_map_stage *stage,
 281                          const struct variable *var)
 282 {
 283   const struct stage_var *stage_var;
 284
 285   HMAP_FOR_EACH_IN_BUCKET (stage_var, struct stage_var, hmap_node,
 286                            hash_pointer (var, 0), &stage->stage_vars)
 287     if (stage_var->var == var)
 288       return stage_var;
 289
 290   /* If the following assertion is reached, it indicates a bug in the
 291      case_map_stage client: the client allowed a new variable to be added to
 292      the dictionary.  This is not allowed, because of the risk that the new
 293      varaible might have the same address as an old variable that has been
 294      deleted. */
 295   NOT_REACHED ();
 296 }
 297
 298 /* Produces a case map from STAGE, which must have been previously created with
 299    case_map_stage_create().  The case map maps from the original case index of
 300    the variables in STAGE's dictionary to their current case indexes.
 301
 302    Returns the new case map, or a null pointer if no mapping is required (that
 303    is, no data has changed position). */
 304 struct case_map *
 305 case_map_stage_get_case_map (const struct case_map_stage *stage)
 306 {
 307   struct case_map *map;
 308   size_t n_vars = dict_get_var_cnt (stage->dict);
 309   size_t n_values;
 310   size_t i;
 311   bool identity_map = true;
 312
 313   map = create_case_map (dict_get_proto (stage->dict));
 314   for (i = 0; i < n_vars; i++)
 315     {
 316       const struct variable *var = dict_get_var (stage->dict, i);
 317       const struct stage_var *stage_var = case_map_stage_find_var (stage, var);
 318
 319       if (var_get_case_index (var) != stage_var->case_index)
 320         identity_map = false;
 321
 322       insert_mapping (map, stage_var->case_index, var_get_case_index (var));
 323     }
 324
 325   if (identity_map)
 326     {
 327       case_map_destroy (map);
 328       return NULL;
 329     }
 330
 331   n_values = caseproto_get_n_widths (map->proto);
 332   while (n_values > 0 && caseproto_get_width (map->proto, n_values - 1) == -1)
 333     map->proto = caseproto_remove_widths (map->proto, --n_values, 1);
 334
 335   return map;
 336 }
 337
 338 /* Creates and returns a case map for mapping variables in OLD to
 339    variables in NEW based on their name.  For every variable in
 340    NEW, there must be a variable in OLD with the same name, type,
 341    and width. */
 342 struct case_map *
 343 case_map_by_name (const struct dictionary *old,
 344                   const struct dictionary *new)
 345 {
 346   struct case_map *map;
 347   size_t var_cnt = dict_get_var_cnt (new);
 348   size_t i;
 349
 350   map = create_case_map (dict_get_proto (new));
 351   for (i = 0; i < var_cnt; i++)
 352     {
 353       struct variable *nv = dict_get_var (new, i);
 354       struct variable *ov = dict_lookup_var_assert (old, var_get_name (nv));
 355       assert (var_get_width (nv) == var_get_width (ov));
 356       insert_mapping (map, var_get_case_index (ov), var_get_case_index (nv));
 357     }
 358   return map;
 359 }
 360
 361 /* Prints the mapping represented by case map CM to stdout, for
 362    debugging purposes. */
 363 void
 364 case_map_dump (const struct case_map *cm)
 365 {
 366   int i;
 367   for (i = 0 ; i < caseproto_get_n_widths (cm->proto); ++i )
 368     printf ("%d -> %d\n", i, cm->map[i]);
 369 }