Re: [PATCH] Add procedures to convert alists into hash tables

[David Thompson]

Thank you for taking the time to give some really useful feedback, Mark 
Weaver. I appreciate it.

On 10/21/2013 01:00 PM, Mark H Weaver wrote:
> Hi David,
>
> >  From 46b7905727ad2efed2dc1d1aca4d4ad00d8f48c5 Mon Sep 17 00:00:00 2001
> > From: David Thompson <address@hidden>
> > Date: Sat, 19 Oct 2013 22:43:37 -0400
> > Subject: [PATCH] Add procedures to convert alists into hash tables.
> >
> > * libguile/hashtab.c (scm_alist_to_hash_table, scm_alist_to_hashq_table,
> >    scm_alist_to_hashv_table, scm_alist_to_hashx_table): Add the
> >    equivalent of SRFI-69's alist->hash-table procedure for the native
> >    hash table implementation.
>
> In general, commit logs shouldn't describe what the new procedures do,
> nor should they provide rationale.  Those things belong in code
> comments.  Here, it is sufficient to write "New procedures."
>
> You should also mention the new macro SCM_ALIST_TO_HASH_TABLE, as well
> as the new prototypes in hashtab.h.
>
> > * test-suite/tests/hash.test ("alist->hash-table"): Add tests.
> >
> > * doc/ref/api-compound.texi (alist->hash-table): Add docs.
>
> For .texi files, the part in parentheses here should be the node name
> where the changes were made.  To find it, I usually search backwards for
> "@node".  In this case, the node name is "Hash Table Reference".

Good to know. Still trying to get used to this commit format.

> > ---
> >   doc/ref/api-compound.texi  | 18 ++++++++++++++
> >   libguile/hashtab.c         | 61 ++++++++++++++++++++++++++++++++++++++++++++++
> >   libguile/hashtab.h         |  6 +++++
> >   test-suite/tests/hash.test | 27 ++++++++++++++++++++
> >   4 files changed, 112 insertions(+)
> >
> > diff --git a/doc/ref/api-compound.texi b/doc/ref/api-compound.texi
> > index 94e0145..06115be 100644
> > --- a/doc/ref/api-compound.texi
> > +++ b/doc/ref/api-compound.texi
> > @@ -3829,6 +3829,24 @@ then it can use @var{size} to avoid rehashing when 
> > initial entries are
> >   added.
> >   @end deffn
> >
> > address@hidden {Scheme Procedure} alist->hash-table alist [size]
> > address@hidden {Scheme Procedure} alist->hashq-table alist [size]
> > address@hidden {Scheme Procedure} alist->hashv-table alist [size]
> > address@hidden {Scheme Procedure} alist->hashx-table hash assoc alist [size]
> > address@hidden {C Function} scm_alist_to_hash_table (alist, size)
> > address@hidden {C Function} scm_alist_to_hashq_table (alist, size)
> > address@hidden {C Function} scm_alist_to_hashv_table (alist, size)
> > address@hidden {C Function} scm_alist_to_hashx_table (hash, assoc, alist, size)
> > +Convert @var{alist} into a hash table with minimum number of buckets
> > address@hidden When keys are repeated in @var{alist}, the leftmost
> > +association takes precedence.
>
> A few thoughts:
>
> * Are you sure that the leftmost association takes precedence?  From
>    looking at the code, I'd expect the _rightmost_ association to take
>    precedence.  In either case, since it's mentioned explicitly in the
>    docs, it would be good if the test suite checked this.

You are right. I have changed the code such that the leftmost 
association actually takes precedence and the tests check for this.
> * For 'alist->hashx-table' (and 'scm_alist_to_hashx_table') the 'hash'
>    and 'assoc' arguments should probably be mentioned, and it would be
>    good to include an example of its use.
>
> * I'm not sure the 'size' argument is worth keeping here.  It seems to
>    me that it will rarely be used.  It might be better to instead compute
>    the size automatically from the alist.  What do you think?
>
>    If you did this, you should use the internal 'scm_ilength' function,
>    which is robust against improper lists and even circular lists, in
>    which case it returns -1.  (In fact, SCM_VALIDATE_LIST works by simply
>    calling scm_ilength and checking that the result is non-negative.)

'size' argument is gone in favor of using 'scm_ilength'.

> > address@hidden
> > +(alist->hash-table '((foo . 1) (bar . 2)))
> > address@hidden example
> > +
> > address@hidden deffn
> > +
> >   @deffn {Scheme Procedure} hash-table? obj
> >   @deffnx {C Function} scm_hash_table_p (obj)
> >   Return @code{#t} if @var{obj} is a abstract hash table object.
> > diff --git a/libguile/hashtab.c b/libguile/hashtab.c
> > index 88cb199..c215269 100644
> > --- a/libguile/hashtab.c
> > +++ b/libguile/hashtab.c
> > @@ -423,6 +423,67 @@ SCM_DEFINE (scm_make_hash_table, "make-hash-table", 0, 1, 
> > 0,
> >   }
> >   #undef FUNC_NAME
> >
> > +#define SCM_ALIST_TO_HASH_TABLE(alist, n, hash_set_fn) \
> > +  SCM hash_table; \
> > +  SCM_VALIDATE_LIST (1, alist); \
> > +  hash_table = scm_make_hash_table (n); \
> > +  while (!scm_is_null (alist)) { \
> > +    SCM pair = SCM_CAR (alist); \
> > +    hash_set_fn (hash_table, scm_car (pair), scm_cdr (pair));   \
> > +    alist = SCM_CDR (alist); \
> > +  } \
> > +  return hash_table;
>
> This is a nitpick, but according to our usual style, the backslashes
> should be lined up in a single column.

Much prettier.

> > +
> > +SCM_DEFINE (scm_alist_to_hash_table, "alist->hash-table", 1, 1, 0,
> > +           (SCM alist, SCM n),
>
> More nitpicking: there's a tab in the line above, which messes up the
> indentation.

When kill/yank goes wrong. Fixed.

> > +            "Convert @var{alist} into a hash table with minimum number of "
> > +            "buckets @var{n}.")
> > +#define FUNC_NAME s_scm_alist_to_hash_table
> > +{
> > +  SCM_ALIST_TO_HASH_TABLE (alist, n, scm_hash_set_x);
> > +}
> > +#undef FUNC_NAME
> > +
> > +SCM_DEFINE (scm_alist_to_hashq_table, "alist->hashq-table", 1, 1, 0,
> > +           (SCM alist, SCM n),
>
> Ditto ^^
>
> > +            "Convert @var{alist} into a hash table with minimum number of "
> > +            "buckets @var{n}.")
> > +#define FUNC_NAME s_scm_alist_to_hashq_table
> > +{
> > +  SCM_ALIST_TO_HASH_TABLE (alist, n, scm_hashq_set_x);
> > +}
> > +#undef FUNC_NAME
> > +
> > +SCM_DEFINE (scm_alist_to_hashv_table, "alist->hashv-table", 1, 1, 0,
> > +           (SCM alist, SCM n),
>
> Ditto ^^
>
> > +            "Convert @var{alist} into a hash table with minimum number of "
> > +            "buckets @var{n}.")
> > +#define FUNC_NAME s_scm_alist_to_hashv_table
> > +{
> > +  SCM_ALIST_TO_HASH_TABLE (alist, n, scm_hashv_set_x);
> > +}
> > +#undef FUNC_NAME
> > +
> > +SCM_DEFINE (scm_alist_to_hashx_table, "alist->hashx-table", 3, 1, 0,
> > +           (SCM hash, SCM assoc, SCM alist, SCM n),
>
> Ditto ^^
>
> > +            "Convert @var{alist} into a hash table with minimum number of "
> > +            "buckets @var{n}.")
>
> Please mention the 'hash' and 'assoc' arguments in the docstring.

Mentioned.

> > +#define FUNC_NAME s_scm_alist_to_hashx_table
> > +{
> > +  SCM hash_table;
> > +  SCM_VALIDATE_LIST (3, alist);
> > +  hash_table = scm_make_hash_table (n);
> > +
> > +  while (!scm_is_null (alist)) {
> > +    SCM pair = SCM_CAR (alist);
> > +    scm_hashx_set_x (hash, assoc, hash_table, scm_car (pair), scm_cdr (pair));
> > +    alist = SCM_CDR (alist);
> > +  }
> > +
> > +  return hash_table;
> > +}
> > +#undef FUNC_NAME
> > +
> >   /* The before-gc C hook only runs if GC_set_start_callback is available,
> >      so if not, fall back on a finalizer-based implementation.  */
> >   static int
> > diff --git a/libguile/hashtab.h b/libguile/hashtab.h
> > index dcebcb8..da4f28c 100644
> > --- a/libguile/hashtab.h
> > +++ b/libguile/hashtab.h
> > @@ -101,6 +101,12 @@ SCM_API SCM scm_make_weak_key_hash_table (SCM k);
> >   SCM_API SCM scm_make_weak_value_hash_table (SCM k);
> >   SCM_API SCM scm_make_doubly_weak_hash_table (SCM k);
> >
> > +SCM_API SCM scm_alist_to_hash_table (SCM alist, SCM n);
> > +SCM_API SCM scm_alist_to_hashq_table (SCM alist, SCM n);
> > +SCM_API SCM scm_alist_to_hashv_table (SCM alist, SCM n);
> > +SCM_API SCM scm_alist_to_hashx_table (SCM hash, SCM assoc,
> > +                                      SCM alist, SCM n);
> > +
> >   SCM_API SCM scm_hash_table_p (SCM h);
> >   SCM_API SCM scm_weak_key_hash_table_p (SCM h);
> >   SCM_API SCM scm_weak_value_hash_table_p (SCM h);
> > diff --git a/test-suite/tests/hash.test b/test-suite/tests/hash.test
> > index 3bd4004..b09c0b8 100644
> > --- a/test-suite/tests/hash.test
> > +++ b/test-suite/tests/hash.test
> > @@ -81,6 +81,33 @@
> >                                 (write (make-hash-table 100)))))))
> >
> >   ;;;
> > +;;; alist->hash-table
> > +;;;
> > +
> > +(with-test-prefix
> > +  "alist->hash-table"
> > +
> > +  ;; equal? hash table
> > +  (pass-if (let ((table (alist->hash-table '(("foo" . 1) ("bar" . 2)))))
> > +             (and (= (hash-ref table "foo") 1)
> > +                  (= (hash-ref table "bar") 2))))
> > +
> > +  ;; eq? hash table
> > +  (pass-if (let ((table (alist->hashq-table '((foo . 1) (bar . 2)))))
> > +             (and (= (hashq-ref table 'foo) 1)
> > +                  (= (hashq-ref table 'bar) 2))))
> > +
> > +  ;; eqv? hash table
> > +  (pass-if (let ((table (alist->hashv-table '((1 . 1) (2 . 2)))))
> > +             (and (= (hashv-ref table 1) 1)
> > +                  (= (hashv-ref table 2) 2))))
> > +
> > +  ;; custom hash table
> > +  (pass-if (let ((table (alist->hashx-table hash assoc '((foo . 1) (bar . 
> > 2)))))
> > +             (and (= (hashx-ref hash assoc table 'foo) 1)
> > +                  (= (hashx-ref hash assoc table 'bar) 2)))))
> > +
> > +;;;
> >   ;;; usual set and reference
> >   ;;;

Updated patch attached.

- Dave

0001-Add-procedures-to-convert-alists-into-hash-tables.patch
Description: Text Data