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           assert (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   if (!map)
 135     return casereader_rename (subreader);
 136   static const struct casereader_translator_class class = {
 137     translate_case, destroy_case_map,
 138   };
 139   return casereader_translate_stateless (subreader,
 140                                          case_map_get_proto (map),
 141                                          &class, map);
 142 }
 143
 144 /* Creates and returns a new casewriter.  Cases written to the
 145    new casewriter will be passed through MAP and written to
 146    SUBWRITER.  The casewriter will have as many `union value's as
 147    MAP.  When the new casewriter is destroyed, MAP will be
 148    destroyed too.
 149
 150    After this function is called, SUBWRITER must not ever again
 151    be referenced directly.  It will be destroyed automatically
 152    when the returned casewriter is destroyed. */
 153 struct casewriter *
 154 case_map_create_output_translator (struct case_map *map,
 155                                    struct casewriter *subwriter)
 156 {
 157   if (!map)
 158     return casewriter_rename (subwriter);
 159   return casewriter_create_translator (subwriter,
 160                                        case_map_get_proto (map),
 161                                        translate_case,
 162                                        destroy_case_map,
 163                                        map);
 164 }
 165
 166 /* Casereader/casewriter translation callback. */
 167 static struct ccase *
 168 translate_case (struct ccase *input, void *map_)
 169 {
 170   struct case_map *map = map_;
 171   return case_map_execute (map, input);
 172 }
 173
 174 /* Casereader/casewriter destruction callback. */
 175 static bool
 176 destroy_case_map (void *map_)
 177 {
 178   struct case_map *map = map_;
 179   case_map_destroy (map);
 180   return true;
 181 }
 182 \f
 183 struct stage_var
 184   {
 185     struct hmap_node hmap_node; /* In struct case_map_stage's 'stage_vars'. */
 186     const struct variable *var;
 187     int case_index;
 188   };
 189
 190 struct case_map_stage
 191   {
 192     const struct dictionary *dict;
 193     struct hmap stage_vars_by_pointer;
 194
 195     struct stage_var *stage_vars;
 196     size_t n_stage_vars;
 197   };
 198
 199 /* Prepares and returns a "struct case_map_stage" for producing a case map for
 200    DICT.  Afterward, the caller may delete, reorder, or rename variables within
 201    DICT at will before using case_map_stage_to_case_map() to produce the case
 202    map.
 203
 204    The caller must *not* add new variables to DICT. */
 205 struct case_map_stage *
 206 case_map_stage_create (const struct dictionary *dict)
 207 {
 208   size_t n_vars = dict_get_n_vars (dict);
 209   struct case_map_stage *stage = xmalloc (sizeof *stage);
 210   *stage = (struct case_map_stage) {
 211     .dict = dict,
 212     .stage_vars_by_pointer = HMAP_INITIALIZER (stage->stage_vars_by_pointer),
 213     .stage_vars = xnmalloc (n_vars, sizeof *stage->stage_vars),
 214     .n_stage_vars = n_vars,
 215   };
 216
 217   for (size_t i = 0; i < n_vars; i++)
 218     {
 219       const struct variable *var = dict_get_var (dict, i);
 220       struct stage_var *stage_var = &stage->stage_vars[i];
 221       *stage_var = (struct stage_var) {
 222         .var = var,
 223         .case_index = var_get_dict_index (var),
 224       };
 225       hmap_insert (&stage->stage_vars_by_pointer, &stage_var->hmap_node,
 226                    hash_pointer (var, 0));
 227     }
 228
 229   return stage;
 230 }
 231
 232 /* Destroys STAGE, which was created by case_map_stage_create(). */
 233 void
 234 case_map_stage_destroy (struct case_map_stage *stage)
 235 {
 236   if (stage != NULL)
 237     {
 238       hmap_destroy (&stage->stage_vars_by_pointer);
 239       free (stage->stage_vars);
 240       free (stage);
 241     }
 242 }
 243
 244 static const struct stage_var *
 245 case_map_stage_find_var (const struct case_map_stage *stage,
 246                          const struct variable *var)
 247 {
 248   const struct stage_var *stage_var;
 249
 250   HMAP_FOR_EACH_IN_BUCKET (stage_var, struct stage_var, hmap_node,
 251                            hash_pointer (var, 0), &stage->stage_vars_by_pointer)
 252     if (stage_var->var == var)
 253       return stage_var;
 254
 255   /* If the following assertion is reached, it indicates a bug in the
 256      case_map_stage client: the client allowed a new variable to be added to
 257      the dictionary.  This is not allowed, because of the risk that the new
 258      varaible might have the same address as an old variable that has been
 259      deleted. */
 260   NOT_REACHED ();
 261 }
 262
 263 static struct case_map *
 264 case_map_stage_get_case_map (const struct case_map_stage *stage)
 265 {
 266   size_t n_vars = dict_get_n_vars (stage->dict);
 267   bool identity_map = n_vars == stage->n_stage_vars;
 268
 269   struct case_map *map = create_case_map (dict_get_proto (stage->dict));
 270   for (size_t i = 0; i < n_vars; i++)
 271     {
 272       const struct variable *var = dict_get_var (stage->dict, i);
 273       const struct stage_var *stage_var = case_map_stage_find_var (stage, var);
 274
 275       if (var_get_dict_index (var) != stage_var->case_index)
 276         identity_map = false;
 277
 278       insert_mapping (map, stage_var->case_index, var_get_dict_index (var));
 279     }
 280
 281   if (identity_map)
 282     {
 283       case_map_destroy (map);
 284       return NULL;
 285     }
 286
 287   return map;
 288 }
 289
 290 /* Produces a case map from STAGE, which must have been previously created with
 291    case_map_stage_create().  The case map maps from the original case index of
 292    the variables in STAGE's dictionary to their current case indexes.
 293
 294    Returns the new case map, or a null pointer if no mapping is required (that
 295    is, no variables were deleted or reordered).
 296
 297    Destroys STAGE. */
 298 struct case_map *
 299 case_map_stage_to_case_map (struct case_map_stage *stage)
 300 {
 301   struct case_map *map = case_map_stage_get_case_map (stage);
 302   case_map_stage_destroy (stage);
 303   return map;
 304 }
 305
 306 /* Creates and returns a case map for mapping variables in OLD to
 307    variables in NEW based on their name.  For every variable in
 308    NEW, there must be a variable in OLD with the same name, type,
 309    and width. */
 310 struct case_map *
 311 case_map_by_name (const struct dictionary *old,
 312                   const struct dictionary *new)
 313 {
 314   size_t n_vars = dict_get_n_vars (new);
 315   struct case_map *map = create_case_map (dict_get_proto (new));
 316   for (size_t i = 0; i < n_vars; i++)
 317     {
 318       struct variable *nv = dict_get_var (new, i);
 319       struct variable *ov = dict_lookup_var_assert (old, var_get_name (nv));
 320       assert (var_get_width (nv) == var_get_width (ov));
 321       insert_mapping (map, var_get_dict_index (ov), var_get_dict_index (nv));
 322     }
 323   return map;
 324 }
 325
 326 /* Prints the mapping represented by case map CM to stdout, for
 327    debugging purposes. */
 328 void
 329 case_map_dump (const struct case_map *cm)
 330 {
 331   int i;
 332   for (i = 0 ; i < caseproto_get_n_widths (cm->proto); ++i)
 333     printf ("%d -> %d\n", i, cm->map[i]);
 334 }