FREQUENCIES: Use newer hmap library instead of older hsh_table library.
authorBen Pfaff <blp@cs.stanford.edu>
Wed, 17 Mar 2010 04:43:15 +0000 (21:43 -0700)
committerBen Pfaff <blp@cs.stanford.edu>
Wed, 17 Mar 2010 04:43:15 +0000 (21:43 -0700)
The FREQUENCIES procedure can use some cleanup.  Here's one step.

src/language/stats/binomial.c
src/language/stats/chisquare.c
src/language/stats/freq.c
src/language/stats/freq.h
src/language/stats/frequencies.q

index 3c8925803bfd5741623120e21c412ab8caa35d2e..b92018fdb400e9fe88d72ec93eed6d04d40d9bbe 100644 (file)
@@ -1,5 +1,5 @@
 /* PSPP - a program for statistical analysis.
-   Copyright (C) 2006, 2009 Free Software Foundation, Inc.
+   Copyright (C) 2006, 2009, 2010 Free Software Foundation, Inc.
 
    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
@@ -91,8 +91,8 @@ static bool
 do_binomial (const struct dictionary *dict,
             struct casereader *input,
             const struct binomial_test *bst,
-            struct freq_mutable *cat1,
-            struct freq_mutable *cat2,
+            struct freq *cat1,
+            struct freq *cat2,
              enum mv_class exclude
             )
 {
@@ -160,7 +160,7 @@ binomial_execute (const struct dataset *ds,
   const struct binomial_test *bst = (const struct binomial_test *) test;
   const struct one_sample_test *ost = (const struct one_sample_test*) test;
 
-  struct freq_mutable *cat[2];
+  struct freq *cat[2];
   int i;
 
   assert ((bst->category1 == SYSMIS) == (bst->category2 == SYSMIS) || bst->cutpoint != SYSMIS);
index 4a75acb879879a218ab34644054323e56508a340..6218228690526da661921ec38b82d33c63b13a78 100644 (file)
 
 #include <language/stats/chisquare.h>
 
-#include <stdlib.h>
-#include <math.h>
-
-#include <data/format.h>
-#include <data/case.h>
-#include <data/casereader.h>
-#include <data/dictionary.h>
-#include <data/procedure.h>
-#include <data/value-labels.h>
-#include <data/variable.h>
-#include <language/stats/freq.h>
-#include <language/stats/npar.h>
-#include <libpspp/assertion.h>
-#include <libpspp/cast.h>
-#include <libpspp/compiler.h>
-#include <libpspp/hash.h>
-#include <libpspp/message.h>
-#include <libpspp/taint.h>
-#include <output/tab.h>
-
 #include <gsl/gsl_cdf.h>
+#include <math.h>
+#include <stdlib.h>
 
-#include "xalloc.h"
+#include "data/format.h"
+#include "data/case.h"
+#include "data/casereader.h"
+#include "data/dictionary.h"
+#include "data/procedure.h"
+#include "data/value-labels.h"
+#include "data/variable.h"
+#include "language/stats/freq.h"
+#include "language/stats/npar.h"
+#include "libpspp/array.h"
+#include "libpspp/assertion.h"
+#include "libpspp/cast.h"
+#include "libpspp/compiler.h"
+#include "libpspp/hash-functions.h"
+#include "libpspp/message.h"
+#include "libpspp/taint.h"
+#include "output/tab.h"
+
+#include "gl/xalloc.h"
 
 #include "gettext.h"
 #define _(msgid) gettext (msgid)
 
-/* Return a hash table containing the frequency counts of each
-   value of VAR in CF .
-   It is the caller's responsibility to free the hash table when
-   no longer required.
-*/
-static struct hsh_table *
+/* Adds frequency counts of each value of VAR in INPUT between LO and HI to
+   FREQ_HASH.  LO and HI and each input value is truncated to an integer.
+   Returns true if successful, false on input error.  It is the caller's
+   responsibility to initialize FREQ_HASH and to free it when no longer
+   required, even on failure. */
+static bool
 create_freq_hash_with_range (const struct dictionary *dict,
                             struct casereader *input,
                             const struct variable *var,
-                            double lo,
-                            double hi)
+                            double lo_, double hi_,
+                             struct hmap *freq_hash)
 {
+  struct freq **entries;
   bool warn = true;
-  float i_d;
   struct ccase *c;
+  double lo, hi;
+  double i_d;
 
-  struct hsh_table *freq_hash =
-    hsh_create (4, compare_freq, hash_freq,
-               free_freq_mutable_hash,
-               (void *) var);
+  assert (var_is_numeric (var));
+  lo = trunc (lo_);
+  hi = trunc (hi_);
 
   /* Populate the hash with zero entries */
-  for (i_d = trunc (lo); i_d <= trunc (hi); i_d += 1.0 )
+  entries = xnmalloc (hi - lo + 1, sizeof *entries);
+  for (i_d = lo; i_d <= hi; i_d += 1.0 )
     {
-      struct freq_mutable *fr = xmalloc (sizeof (*fr));
-      value_init (&fr->value, 0);
-      fr->value.f = i_d;
-      fr->count = 0;
-      hsh_insert (freq_hash, fr);
+      size_t ofs = i_d - lo;
+      union value value = { i_d };
+      entries[ofs] = freq_hmap_insert (freq_hash, &value, 0,
+                                       value_hash (&value, 0, 0));
     }
 
   for (; (c = casereader_read (input)) != NULL; case_unref (c))
     {
-      struct freq_mutable fr;
-      fr.value.f = trunc (case_num (c, var));
-      if (fr.value.f >= lo && fr.value.f <= hi)
+      double x = trunc (case_num (c, var));
+      if (x >= lo && x <= hi)
         {
-          struct freq_mutable *existing_fr = hsh_force_find (freq_hash, &fr);
-          existing_fr->count += dict_get_case_weight (dict, c, &warn);
+          size_t ofs = x - lo;
+          struct freq *fr = entries[ofs];
+          fr->count += dict_get_case_weight (dict, c, &warn);
         }
     }
-  if (casereader_destroy (input))
-    return freq_hash;
-  else
-    {
-      hsh_destroy (freq_hash);
-      return NULL;
-    }
-}
 
+  return casereader_destroy (input);
+}
 
-/* Return a hash table containing the frequency counts of each
-   value of VAR in INPUT .
-   It is the caller's responsibility to free the hash table when
-   no longer required.
-*/
-static struct hsh_table *
+/* Adds frequency counts of each value of VAR in INPUT to FREQ_HASH.  LO and HI
+   and each input value is truncated to an integer.  Returns true if
+   successful, false on input error.  It is the caller's responsibility to
+   initialize FREQ_HASH and to free it when no longer required, even on
+   failure. */
+static bool
 create_freq_hash (const struct dictionary *dict,
                  struct casereader *input,
-                 const struct variable *var)
+                 const struct variable *var,
+                  struct hmap *freq_hash)
 {
   int width = var_get_width (var);
   bool warn = true;
   struct ccase *c;
 
-  struct hsh_table *freq_hash =
-    hsh_create (4, compare_freq, hash_freq,
-               free_freq_mutable_hash,
-               (void *) var);
-
   for (; (c = casereader_read (input)) != NULL; case_unref (c))
     {
-      struct freq_mutable fr;
-      void **p;
+      const union value *value = case_data (c, var);
+      size_t hash = value_hash (value, width, 0);
+      double weight = dict_get_case_weight (dict, c, &warn);
+      struct freq *f;
 
-      fr.value = *case_data (c, var);
-      fr.count = dict_get_case_weight (dict, c, &warn);
+      f = freq_hmap_search (freq_hash, value, width, hash);
+      if (f == NULL)
+        f = freq_hmap_insert (freq_hash, value, width, hash);
 
-      p = hsh_probe (freq_hash, &fr);
-      if (*p == NULL)
-        {
-          struct freq_mutable *new_fr = *p = xmalloc (sizeof *new_fr);
-          value_init (&new_fr->value, width);
-          value_copy (&new_fr->value, &fr.value, width);
-          new_fr->count = fr.count;
-        }
-      else
-        {
-          struct freq *existing_fr = *p;
-          existing_fr->count += fr.count;
-        }
-    }
-  if (casereader_destroy (input))
-    return freq_hash;
-  else
-    {
-      hsh_destroy (freq_hash);
-      return NULL;
+      f->count += weight;
     }
-}
-
 
+  return casereader_destroy (input);
+}
 
 static struct tab_table *
 create_variable_frequency_table (const struct dictionary *dict,
                                 struct casereader *input,
                                 const struct chisquare_test *test,
-                                int v,
-                                struct hsh_table **freq_hash)
+                                int v, struct hmap *freq_hash)
 
 {
   int i;
@@ -162,11 +136,14 @@ create_variable_frequency_table (const struct dictionary *dict,
   struct tab_table *table ;
   const struct variable *var =  ost->vars[v];
 
-  *freq_hash = create_freq_hash (dict, input, var);
-  if (*freq_hash == NULL)
-    return NULL;
+  hmap_init (freq_hash);
+  if (!create_freq_hash (dict, input, var, freq_hash))
+    {
+      freq_hmap_destroy (freq_hash, var_get_width (var));
+      return NULL;
+    }
 
-  n_cells = hsh_count (*freq_hash);
+  n_cells = hmap_count (freq_hash);
 
   if ( test->n_expected > 0 && n_cells != test->n_expected )
     {
@@ -175,8 +152,6 @@ create_variable_frequency_table (const struct dictionary *dict,
          test->n_expected, n_cells,
          var_get_name (var)
          );
-      hsh_destroy (*freq_hash);
-      *freq_hash = NULL;
       return NULL;
     }
 
@@ -323,11 +298,12 @@ chisquare_execute (const struct dataset *ds,
     {
       for ( v = 0 ; v < ost->n_vars ; ++v )
        {
+          const struct variable *var = ost->vars[v];
          double total_obs = 0.0;
-         struct hsh_table *freq_hash = NULL;
+         struct hmap freq_hash;
           struct casereader *reader =
             casereader_create_filter_missing (casereader_clone (input),
-                                              &ost->vars[v], 1, exclude,
+                                              &var, 1, exclude,
                                              NULL, NULL);
          struct tab_table *freq_table =
             create_variable_frequency_table(dict, reader, cst, v, &freq_hash);
@@ -336,9 +312,9 @@ chisquare_execute (const struct dataset *ds,
 
          if ( NULL == freq_table )
             continue;
-          ff = (struct freq **) hsh_sort (freq_hash);
+          ff = freq_hmap_sort (&freq_hash, var_get_width (var));
 
-         n_cells = hsh_count (freq_hash);
+         n_cells = hmap_count (&freq_hash);
 
          for ( i = 0 ; i < n_cells ; ++i )
            total_obs += ff[i]->count;
@@ -351,7 +327,7 @@ chisquare_execute (const struct dataset *ds,
              const union value *observed_value = &ff[i]->value;
 
              ds_init_empty (&str);
-             var_append_value_name (ost->vars[v], observed_value, &str);
+             var_append_value_name (var, observed_value, &str);
 
              /* The key */
              tab_text (freq_table, 0, i + 1, TAB_LEFT, ds_cstr (&str));
@@ -384,7 +360,8 @@ chisquare_execute (const struct dataset *ds,
 
          tab_submit (freq_table);
 
-         hsh_destroy (freq_hash);
+          freq_hmap_destroy (&freq_hash, var_get_width (var));
+          free (ff);
        }
     }
   else  /* ranged == true */
@@ -395,28 +372,30 @@ chisquare_execute (const struct dataset *ds,
 
       for ( v = 0 ; v < ost->n_vars ; ++v )
        {
+          const struct variable *var = ost->vars[v];
          double total_obs = 0.0;
           struct casereader *reader =
             casereader_create_filter_missing (casereader_clone (input),
-                                              &ost->vars[v], 1, exclude,
+                                              &var, 1, exclude,
                                              NULL, NULL);
-         struct hsh_table *freq_hash =
-           create_freq_hash_with_range (dict, reader,
-                                         ost->vars[v], cst->lo, cst->hi);
-
+         struct hmap freq_hash;
          struct freq **ff;
 
-          if (freq_hash == NULL)
-            continue;
+          hmap_init (&freq_hash);
+          if (!create_freq_hash_with_range (dict, reader, var,
+                                            cst->lo, cst->hi, &freq_hash))
+            {
+              freq_hmap_destroy (&freq_hash, var_get_width (var));
+              continue;
+            }
 
-          ff = (struct freq **) hsh_sort (freq_hash);
-         assert ( n_cells == hsh_count (freq_hash));
+          ff = freq_hmap_sort (&freq_hash, var_get_width (var));
 
-         for ( i = 0 ; i < hsh_count (freq_hash) ; ++i )
+         for ( i = 0 ; i < hmap_count (&freq_hash) ; ++i )
            total_obs += ff[i]->count;
 
          xsq[v] = 0.0;
-         for ( i = 0 ; i < hsh_count (freq_hash) ; ++i )
+         for ( i = 0 ; i < hmap_count (&freq_hash) ; ++i )
            {
              struct string str;
              double exp;
@@ -437,7 +416,7 @@ chisquare_execute (const struct dataset *ds,
              if ( cst->n_expected > 0 )
                exp = cst->expected[i] * total_obs / total_expected ;
              else
-               exp = total_obs / (double) hsh_count (freq_hash);
+               exp = total_obs / (double) hmap_count (&freq_hash);
 
              /* The expected N */
              tab_double (freq_table, v * 4 + 3, i + 2 , TAB_NONE,
@@ -456,7 +435,8 @@ chisquare_execute (const struct dataset *ds,
 
          df[v] = n_cells - 1.0;
 
-         hsh_destroy (freq_hash);
+         freq_hmap_destroy (&freq_hash, var_get_width (var));
+          free (ff);
        }
 
       tab_submit (freq_table);
index 1a0ecd498636561b9fb225f96baa8d9bdc82e409..6c201021abf921a16aa2b4817613c7cd62f636df 100644 (file)
@@ -1,5 +1,5 @@
 /* PSPP - a program for statistical analysis.
-   Copyright (C) 2006, 2009 Free Software Foundation, Inc.
+   Copyright (C) 2006, 2009, 2010 Free Software Foundation, Inc.
 
    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    along with this program.  If not, see <http://www.gnu.org/licenses/>. */
 
 #include <config.h>
-#include <data/variable.h>
-#include <data/value.h>
-#include <libpspp/compiler.h>
+
+#include "language/stats/freq.h"
 
 #include <stdlib.h>
 
-#include "freq.h"
+#include "data/variable.h"
+#include "data/value.h"
+#include "libpspp/array.h"
+#include "libpspp/compiler.h"
 
-int
-compare_freq ( const void *_f1, const void *_f2, const void *_var)
+void
+freq_hmap_destroy (struct hmap *hmap, int width)
 {
-  const struct freq *f1 = _f1;
-  const struct freq *f2 = _f2;
-  const struct variable *var = _var;
+  struct freq *f, *next;
 
-  return value_compare_3way (&f1->value, &f2->value, var_get_width (var));
+  HMAP_FOR_EACH_SAFE (f, next, struct freq, hmap_node, hmap)
+    {
+      value_destroy (&f->value, width);
+      hmap_delete (hmap, &f->hmap_node);
+      free (f);
+    }
+  hmap_destroy (hmap);
 }
 
-unsigned int
-hash_freq (const void *_f, const void *var)
+struct freq *
+freq_hmap_search (struct hmap *hmap,
+                  const union value *value, int width, size_t hash)
 {
-  const struct freq *f = _f;
+  struct freq *f;
+
+  HMAP_FOR_EACH_WITH_HASH (f, struct freq, hmap_node, hash, hmap)
+    if (value_equal (value, &f->value, width))
+      return f;
 
-  return value_hash (&f->value, var_get_width (var), 0);
+  return NULL;
 }
 
-/* Free function to be used on FR whose value parameter has been copied */
-void
-free_freq_mutable_hash (void *fr, const void *var_)
+struct freq *
+freq_hmap_insert (struct hmap *hmap,
+                  const union value *value, int width, size_t hash)
 {
-  const struct variable *var = var_;
-  struct freq_mutable *freq = fr;
-  value_destroy (&freq->value, var_get_width (var));
-  free (freq);
+  struct freq *f = xmalloc (sizeof *f);
+  value_clone (&f->value, value, width);
+  f->count = 0;
+  hmap_insert (hmap, &f->hmap_node, hash);
+  return f;
 }
 
-void
-free_freq_hash (void *fr, const void *var UNUSED)
+static int
+compare_freq_ptr_3way (const void *a_, const void *b_, const void *width_)
+{
+  const struct freq *const *ap = a_;
+  const struct freq *const *bp = b_;
+  const int *widthp = width_;
+
+  return value_compare_3way (&(*ap)->value, &(*bp)->value, *widthp);
+}
+
+struct freq **
+freq_hmap_sort (struct hmap *hmap, int width)
 {
-  free (fr);
+  size_t n_entries = hmap_count (hmap);
+  struct freq **entries;
+  struct freq *f;
+  size_t i;
+
+  entries = xnmalloc (n_entries, sizeof *entries);
+  i = 0;
+  HMAP_FOR_EACH (f, struct freq, hmap_node, hmap)
+    entries[i++] = f;
+  assert (i == n_entries);
+
+  sort (entries, n_entries, sizeof *entries, compare_freq_ptr_3way, &width);
+
+  return entries;
 }
+
+struct freq *
+freq_hmap_extract (struct hmap *hmap)
+{
+  struct freq *freqs, *f;
+  size_t n_freqs;
+  size_t i;
+
+  n_freqs = hmap_count (hmap);
+  freqs = xnmalloc (n_freqs, sizeof *freqs);
+  i = 0;
+  HMAP_FOR_EACH (f, struct freq, hmap_node, hmap)
+    freqs[i++] = *f;
+  assert (i == n_freqs);
+
+  return freqs;
+}
+
index b06a36f6b2fb14f5fbc47f7f9db6d6d924dab893..fd6081f4e13c465704ce2bf264b6a14d6daf9ebb 100644 (file)
@@ -1,5 +1,5 @@
 /* PSPP - a program for statistical analysis.
-   Copyright (C) 2006 Free Software Foundation, Inc.
+   Copyright (C) 2006, 2010 Free Software Foundation, Inc.
 
    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>. */
 
-#ifndef freq_h
-#define freq_h
+#ifndef LANGUAGE_STATS_FREQ_H
+#define LANGUAGE_STATS_FREQ_H 1
+
+#include "data/value.h"
+#include "libpspp/hmap.h"
 
-union value ;
 /* Frequency table entry. */
 struct freq
   {
-    const union value value;   /* The value. */
-    double count;              /* The number of occurrences of the value. */
-  };
-
-/* Non const version of frequency table entry. */
-struct freq_mutable
-  {
-    union value value;         /* The value. */
+    struct hmap_node hmap_node; /* Element in hash table. */
+    union value value;          /* The value. */
     double count;              /* The number of occurrences of the value. */
   };
 
+void freq_hmap_destroy (struct hmap *, int width);
 
-int compare_freq ( const void *_f1, const void *_f2, const void *_var);
-
-unsigned int hash_freq (const void *_f, const void *_var);
-
-/* Free function for struct freq */
-void free_freq_hash (void *fr, const void *aux);
-
-/* Free function for struct freq_mutable */
-void free_freq_mutable_hash (void *fr, const void *var);
-
+struct freq *freq_hmap_search (struct hmap *, const union value *, int width,
+                               size_t hash);
+struct freq *freq_hmap_insert (struct hmap *, const union value *, int width,
+                               size_t hash);
 
+struct freq **freq_hmap_sort (struct hmap *, int width);
+struct freq *freq_hmap_extract (struct hmap *);
 
-#endif
+#endif /* language/stats/freq.h */
index 45c969d4c00a5edaaeac0fce56ed8721a36cff1f..ef36f139d59b971403ad9d43557df81db145c5e0 100644 (file)
 #include <stdlib.h>
 #include <gsl/gsl_histogram.h>
 
-#include <data/case.h>
-#include <data/casegrouper.h>
-#include <data/casereader.h>
-#include <data/dictionary.h>
-#include <data/format.h>
-#include <data/procedure.h>
-#include <data/settings.h>
-#include <data/value-labels.h>
-#include <data/variable.h>
-#include <language/command.h>
-#include <language/dictionary/split-file.h>
-#include <language/lexer/lexer.h>
-#include <libpspp/array.h>
-#include <libpspp/bit-vector.h>
-#include <libpspp/compiler.h>
-#include <libpspp/hash.h>
-#include <libpspp/message.h>
-#include <libpspp/misc.h>
-#include <libpspp/pool.h>
-#include <libpspp/str.h>
-#include <math/histogram.h>
-#include <math/moments.h>
-#include <output/chart-item.h>
-#include <output/charts/piechart.h>
-#include <output/charts/plot-hist.h>
-#include <output/tab.h>
-
-#include "freq.h"
-
-#include "minmax.h"
-#include "xalloc.h"
+#include "data/case.h"
+#include "data/casegrouper.h"
+#include "data/casereader.h"
+#include "data/dictionary.h"
+#include "data/format.h"
+#include "data/procedure.h"
+#include "data/settings.h"
+#include "data/value-labels.h"
+#include "data/variable.h"
+#include "language/command.h"
+#include "language/dictionary/split-file.h"
+#include "language/lexer/lexer.h"
+#include "language/stats/freq.h"
+#include "libpspp/array.h"
+#include "libpspp/bit-vector.h"
+#include "libpspp/compiler.h"
+#include "libpspp/hmap.h"
+#include "libpspp/message.h"
+#include "libpspp/misc.h"
+#include "libpspp/pool.h"
+#include "libpspp/str.h"
+#include "math/histogram.h"
+#include "math/moments.h"
+#include "output/chart-item.h"
+#include "output/charts/piechart.h"
+#include "output/charts/plot-hist.h"
+#include "output/tab.h"
+
+#include "gl/minmax.h"
+#include "gl/xalloc.h"
 
 #include "gettext.h"
 #define _(msgid) gettext (msgid)
@@ -187,13 +186,12 @@ static struct pool *syntax_pool;        /* For syntax-related data. */
 /* Entire frequency table. */
 struct freq_tab
   {
-    struct hsh_table *data;    /* Undifferentiated data. */
-    struct freq_mutable *valid; /* Valid freqs. */
+    struct hmap data;           /* Hash table for accumulating counts. */
+    struct freq *valid;         /* Valid freqs. */
     int n_valid;               /* Number of total freqs. */
-    const struct dictionary *dict; /* The dict from whence entries in the table
-                                     come */
+    const struct dictionary *dict; /* Source of entries in the table. */
 
-    struct freq_mutable *missing; /* Missing freqs. */
+    struct freq *missing;       /* Missing freqs. */
     int n_missing;             /* Number of missing freqs. */
 
     /* Statistics. */
@@ -238,10 +236,10 @@ static void dump_freq_table (const struct variable *, const struct variable *);
 static void dump_statistics (const struct variable *, const struct variable *);
 static void cleanup_freq_tab (const struct variable *);
 
-static hsh_compare_func compare_value_numeric_a, compare_value_alpha_a;
-static hsh_compare_func compare_value_numeric_d, compare_value_alpha_d;
-static hsh_compare_func compare_freq_numeric_a, compare_freq_alpha_a;
-static hsh_compare_func compare_freq_numeric_d, compare_freq_alpha_d;
+static algo_compare_func compare_value_numeric_a, compare_value_alpha_a;
+static algo_compare_func compare_value_numeric_d, compare_value_alpha_d;
+static algo_compare_func compare_freq_numeric_a, compare_freq_alpha_a;
+static algo_compare_func compare_freq_numeric_d, compare_freq_alpha_d;
 
 
 static void do_piechart(const struct variable *var,
@@ -427,27 +425,20 @@ calc (const struct ccase *c, const struct dataset *ds)
 
   for (i = 0; i < n_variables; i++)
     {
-      const struct variable *v = v_variables[i];
-      const union value *val = case_data (c, v);
-      struct var_freqs *vf = get_var_freqs (v);
-      struct freq_tab *ft = &vf->tab;
+      const struct variable *var = v_variables[i];
+      int width = var_get_width (var);
 
-      struct freq_mutable target;
-      struct freq_mutable **fpp;
+      const union value *value = case_data (c, var);
+      size_t hash = value_hash (value, width, 0);
 
-      target.value = *val;
-      fpp = (struct freq_mutable **) hsh_probe (ft->data, &target);
+      struct hmap *hmap = &get_var_freqs (var)->tab.data;
+      struct freq *f;
 
-      if (*fpp != NULL)
-        (*fpp)->count += weight;
-      else
-        {
-          struct freq_mutable *fp = pool_alloc (data_pool, sizeof *fp);
-          fp->count = weight;
-          value_init_pool (data_pool, &fp->value, vf->width);
-          value_copy (&fp->value, val, vf->width);
-          *fpp = fp;
-        }
+      f = freq_hmap_search (hmap, value, width, hash);
+      if (f == NULL)
+        f = freq_hmap_insert (hmap, value, width, hash);
+
+      f->count += weight;
     }
 }
 
@@ -474,7 +465,7 @@ precalc (struct casereader *input, struct dataset *ds)
       const struct variable *v = v_variables[i];
       struct freq_tab *ft = &get_var_freqs (v)->tab;
 
-      ft->data = hsh_create (16, compare_freq, hash_freq, NULL, v);
+      hmap_init (&ft->data);
     }
 }
 
@@ -536,7 +527,7 @@ postcalc (const struct dataset *ds)
 /* Returns the comparison function that should be used for
    sorting a frequency table by FRQ_SORT using VAL_TYPE
    values. */
-static hsh_compare_func *
+static algo_compare_func *
 get_freq_comparator (int frq_sort, enum val_type val_type)
 {
   bool is_numeric = val_type == VAL_NUMERIC;
@@ -555,12 +546,12 @@ get_freq_comparator (int frq_sort, enum val_type val_type)
     }
 }
 
-/* Returns true iff the value in struct freq_mutable F is non-missing
+/* Returns true iff the value in struct freq F is non-missing
    for variable V. */
 static bool
 not_missing (const void *f_, const void *v_)
 {
-  const struct freq_mutable *f = f_;
+  const struct freq *f = f_;
   const struct variable *v = v_;
 
   return !var_is_value_missing (v, &f->value, MV_ANY);
@@ -570,27 +561,18 @@ not_missing (const void *f_, const void *v_)
 static void
 postprocess_freq_tab (const struct variable *v)
 {
-  hsh_compare_func *compare;
+  algo_compare_func *compare;
   struct freq_tab *ft;
   size_t count;
-  void *const *data;
-  struct freq_mutable *freqs, *f;
+  struct freq *freqs, *f;
   size_t i;
 
   ft = &get_var_freqs (v)->tab;
   compare = get_freq_comparator (cmd.sort, var_get_type (v));
 
   /* Extract data from hash table. */
-  count = hsh_count (ft->data);
-  data = hsh_data (ft->data);
-
-  /* Copy dereferenced data into freqs. */
-  freqs = xnmalloc (count, sizeof *freqs);
-  for (i = 0; i < count; i++)
-    {
-      struct freq_mutable *f = data[i];
-      freqs[i] = *f;
-    }
+  count = hmap_count (&ft->data);
+  freqs = freq_hmap_extract (&ft->data);
 
   /* Put data into ft. */
   ft->valid = freqs;
@@ -624,9 +606,9 @@ postprocess_freq_tab (const struct variable *v)
 static void
 cleanup_freq_tab (const struct variable *v)
 {
-  struct freq_tab *ft = &get_var_freqs (v)->tab;
-  free (ft->valid);
-  hsh_destroy (ft->data);
+  struct var_freqs *vf = get_var_freqs (v);
+  free (vf->tab.valid);
+  freq_hmap_destroy (&vf->tab.data, vf->width);
 }
 
 /* Parses the VARIABLES subcommand, adding to
@@ -796,8 +778,8 @@ add_percentile (double x, bool show)
 static int
 compare_value_numeric_a (const void *a_, const void *b_, const void *aux UNUSED)
 {
-  const struct freq_mutable *a = a_;
-  const struct freq_mutable *b = b_;
+  const struct freq *a = a_;
+  const struct freq *b = b_;
 
   if (a->value.f > b->value.f)
     return 1;
@@ -811,8 +793,8 @@ compare_value_numeric_a (const void *a_, const void *b_, const void *aux UNUSED)
 static int
 compare_value_alpha_a (const void *a_, const void *b_, const void *v_)
 {
-  const struct freq_mutable *a = a_;
-  const struct freq_mutable *b = b_;
+  const struct freq *a = a_;
+  const struct freq *b = b_;
   const struct variable *v = v_;
   struct var_freqs *vf = get_var_freqs (v);
 
@@ -838,8 +820,8 @@ compare_value_alpha_d (const void *a, const void *b, const void *v)
 static int
 compare_freq_numeric_a (const void *a_, const void *b_, const void *aux UNUSED)
 {
-  const struct freq_mutable *a = a_;
-  const struct freq_mutable *b = b_;
+  const struct freq *a = a_;
+  const struct freq *b = b_;
 
   if (a->count > b->count)
     return 1;
@@ -859,8 +841,8 @@ compare_freq_numeric_a (const void *a_, const void *b_, const void *aux UNUSED)
 static int
 compare_freq_alpha_a (const void *a_, const void *b_, const void *v_)
 {
-  const struct freq_mutable *a = a_;
-  const struct freq_mutable *b = b_;
+  const struct freq *a = a_;
+  const struct freq *b = b_;
   const struct variable *v = v_;
   struct var_freqs *vf = get_var_freqs (v);
 
@@ -877,8 +859,8 @@ compare_freq_alpha_a (const void *a_, const void *b_, const void *v_)
 static int
 compare_freq_numeric_d (const void *a_, const void *b_, const void *aux UNUSED)
 {
-  const struct freq_mutable *a = a_;
-  const struct freq_mutable *b = b_;
+  const struct freq *a = a_;
+  const struct freq *b = b_;
 
   if (a->count > b->count)
     return -1;
@@ -898,8 +880,8 @@ compare_freq_numeric_d (const void *a_, const void *b_, const void *aux UNUSED)
 static int
 compare_freq_alpha_d (const void *a_, const void *b_, const void *v_)
 {
-  const struct freq_mutable *a = a_;
-  const struct freq_mutable *b = b_;
+  const struct freq *a = a_;
+  const struct freq *b = b_;
   const struct variable *v = v_;
   struct var_freqs *vf = get_var_freqs (v);
 
@@ -921,7 +903,7 @@ dump_freq_table (const struct variable *v, const struct variable *wv)
   int n_categories;
   struct var_freqs *vf;
   struct freq_tab *ft;
-  struct freq_mutable *f;
+  struct freq *f;
   struct tab_table *t;
   int r, x;
   double cum_total = 0.0;
@@ -1009,7 +991,7 @@ calc_stats (const struct variable *v, double d[frq_n_stats])
   struct freq_tab *ft = &get_var_freqs (v)->tab;
   double W = ft->valid_cases;
   struct moments *m;
-  struct freq_mutable *f=0;
+  struct freq *f=0;
   int most_often;
   double X_mode;
 
@@ -1265,7 +1247,7 @@ freq_tab_to_hist (const struct freq_tab *ft, const struct variable *var)
   valid_freq = 0;
   for (i = 0; i < ft->n_valid; i++)
     {
-      const struct freq_mutable *frq = &ft->valid[i];
+      const struct freq *frq = &ft->valid[i];
       if (chart_includes_value (&hist, var, &frq->value))
         {
           x_min = MIN (x_min, frq->value.f);
@@ -1291,7 +1273,7 @@ freq_tab_to_hist (const struct freq_tab *ft, const struct variable *var)
   histogram = histogram_create (bins, x_min, x_max);
   for (i = 0; i < ft->n_valid; i++)
     {
-      const struct freq_mutable *frq = &ft->valid[i];
+      const struct freq *frq = &ft->valid[i];
       if (chart_includes_value (&hist, var, &frq->value))
         histogram_add (histogram, frq->value.f, frq->count);
     }
@@ -1300,7 +1282,7 @@ freq_tab_to_hist (const struct freq_tab *ft, const struct variable *var)
 }
 
 static int
-add_slice (const struct freq_mutable *freq, const struct variable *var,
+add_slice (const struct freq *freq, const struct variable *var,
            struct slice *slice)
 {
   if (chart_includes_value (&pie, var, &freq->value))