[petsc-dev] Make PetscHash publicly accessible

[Matthew Knepley]

On Fri, Apr 22, 2016 at 9:52 AM, Jed Brown <jed at jedbrown.org> wrote:

> Matthew Knepley <knepley at gmail.com> writes:
> > You are wrong in this case. The HashIJ is not trivial, and cannot be done
> > easily inline. What is the problem here?
>
> $ git grep -l 'PetscHashIJ[^K]'
> src/sys/examples/tests/ex26.c
> src/sys/utils/hash.h
>
> $ git grep -l 'PetscHashJK'
> src/dm/impls/plex/plexfem.c
> src/mat/impls/preallocator/matpreallocator.c
> src/sys/utils/hash.h
>
> But matpreallocator.c doesn't actually use the linked list aspects of
> PetscHashJK, so it's memory overhead (two unused pointers plus padding
> per entry) for nothing.
>
> $ git grep -l 'PetscHashIJKL'
> src/dm/impls/plex/plexinterpolate.c
> src/sys/utils/hash.h
>
> This is actually used, but I think the implementation (below) accurately
> fits my description of wrapping khash primitives with imaginary error
> checking.  Lawrence, do you just want a general-purpose hash table or do
> you specifically want Matt's hash/linked-list structure?
>

I assume you would just stick this stuff in source files?

/* Linked list of values in a bucket. */
struct _IJKLNode {
  PetscInt       k;
  struct _IJKLNode *next;
};
typedef struct _IJKLNode IJKLNode;

/* Value (holds a linked list of nodes) in the bucket. */
struct _IJKLVal {
  PetscInt n;
  IJKLNode   *head, *tail;
};
typedef struct _IJKLVal IJKLVal;

/* Key (a quartet of integers). */
struct _PetscHashIJKLKey {
  PetscInt i, j, k, l;
};
typedef struct _PetscHashIJKLKey PetscHashIJKLKey;

/* Hash function: mix two integers into one.
   Shift by a quarter the number of bits in PetscInt to the left and then
XOR.  If the indices fit into the lowest quarter part of PetscInt, this is
a bijection.
   We should shift by (8/4)*sizeof(PetscInt): sizeof(PetscInt) is the
number of bytes in PetscInt, with 8 bits per byte.
 */
#define IJKLKeyHash(key) ( (((key).i) <<
(4*sizeof(PetscInt)))^((key).j)^(((key).k) <<
(2*sizeof(PetscInt)))^(((key).l) << (6*sizeof(PetscInt))) )

/* Compare two keys (integer pairs). */
#define IJKLKeyEqual(k1,k2) (((k1).i==(k2).i) ? ((k1).j==(k2).j) ?
((k1).k==(k2).k) ? ((k1).l==(k2).l) : 0 : 0 : 0)

KHASH_INIT(HASHIJKL,PetscHashIJKLKey,IJKLVal,1,IJKLKeyHash,IJKLKeyEqual)

struct _PetscHashIJKL {
  khash_t(HASHIJKL) *ht;
};

typedef struct _PetscHashIJKL *PetscHashIJKL;

typedef khiter_t               PetscHashIJKLIter;

typedef IJKLNode              *PetscHashIJKLValIter;

This is a silly argument. It is argument for the sake of arguing rather
than to improve what we are doing.

   Matt


> #undef  __FUNCT__
> #define __FUNCT__ "PetscHashIJKLCreate"
> PETSC_STATIC_INLINE PetscErrorCode PetscHashIJKLCreate(PetscHashIJKL *h)
> {
>   PetscErrorCode ierr;
>
>   PetscFunctionBegin;
>   PetscValidPointer(h, 1);
>   ierr = PetscNew((h));CHKERRQ(ierr);
>   (*h)->ht = kh_init(HASHIJKL);
>   PetscFunctionReturn(0);
> }
>
> #undef  __FUNCT__
> #define __FUNCT__ "PetscHashIJKLResize"
> PETSC_STATIC_INLINE PetscErrorCode PetscHashIJKLResize(PetscHashIJKL h,
> PetscInt n)
> {
>   PetscFunctionBegin;
>   (kh_resize(HASHIJKL, (h)->ht, (n)));
>   PetscFunctionReturn(0);
> }
>
> #undef  __FUNCT__
> #define __FUNCT__ "PetscHashIJKLKeySize"
> PETSC_STATIC_INLINE PetscErrorCode PetscHashIJKLKeySize(PetscHashIJKL h,
> PetscInt *n)
> {
>   PetscFunctionBegin;
>   ((*n) = kh_size((h)->ht));
>   PetscFunctionReturn(0);
> }
>
> #undef  __FUNCT__
> #define __FUNCT__ "PetscHashIJKLPut"
> /*
>   PetscHashIJKLPut - Insert key in the hash table
>
>   Input Parameters:
> + h - The hash table
> - key - The key to insert
>
>   Output Parameter:
> + missing - 0 if the key is present in the hash table, 1 if the bucket is
> empty (never used), 2 if the element in the bucket has been deleted
> - iter - Iterator into table
>
>   Level: developer
>
> .seealso: PetscHashIJKLCreate(), PetscHashIJKLSet()
> */
> PETSC_STATIC_INLINE PetscErrorCode PetscHashIJKLPut(PetscHashIJKL h,
> PetscHashIJKLKey key, PetscHashIJKLIter *missing, PetscHashIJKLIter *iter)
> {
>   PetscFunctionBeginHot;
>   *iter = kh_put(HASHIJKL, (h)->ht, (key), missing);
>   PetscFunctionReturn(0);
> }
>
> #undef  __FUNCT__
> #define __FUNCT__ "PetscHashIJKLSet"
> /*
>   PetscHashIJKLSet - Set the value for an iterator in the hash table
>
>   Input Parameters:
> + h - The hash table
> . iter - An iterator into the table
> - value - The value to set
>
>   Level: developer
>
> .seealso: PetscHashIJKLCreate(), PetscHashIJKLPut(), PetscHashIJKLGet()
> */
> PETSC_STATIC_INLINE PetscErrorCode PetscHashIJKLSet(PetscHashIJKL h,
> PetscHashIJKLIter iter, PetscInt value)
> {
>   PetscFunctionBeginHot;
>   kh_val((h)->ht, iter).n = value;
>   PetscFunctionReturn(0);
> }
>
> #undef  __FUNCT__
> #define __FUNCT__ "PetscHashIJKLGet"
> /*
>   PetscHashIJKLGet - Get the value for an iterator in the hash table
>
>   Input Parameters:
> + h - The hash table
> . iter - An iterator into the table
>
>   Output Parameters:
> . value - The value to get
>
>   Level: developer
>
> .seealso: PetscHashIJKLCreate(), PetscHashIJKLPut(), PetscHashIJKLSet()
> */
> PETSC_STATIC_INLINE PetscErrorCode PetscHashIJKLGet(PetscHashIJKL h,
> PetscHashIJKLIter iter, PetscInt *value)
> {
>   PetscFunctionBeginHot;
>   *value = kh_val((h)->ht, iter).n;
>   PetscFunctionReturn(0);
> }
>
> #undef  __FUNCT__
> #define __FUNCT__ "PetscHashIJKLClear"
> PETSC_STATIC_INLINE PetscErrorCode PetscHashIJKLClear(PetscHashIJKL h)
> {
>   PetscFunctionBegin;
>   kh_clear(HASHIJKL, (h)->ht);
>   PetscFunctionReturn(0);
> }
>
> #undef  __FUNCT__
> #define __FUNCT__ "PetscHashIJKLDestroy"
> PETSC_STATIC_INLINE PetscErrorCode PetscHashIJKLDestroy(PetscHashIJKL *h)
> {
>   PetscFunctionBegin;
>   PetscValidPointer(h, 1);
>   if ((*h)) {
>     PetscErrorCode ierr;
>
>     if ((*h)->ht) {
>       kh_destroy(HASHIJKL, (*h)->ht);
>       (*h)->ht = NULL;
>     }
>     ierr = PetscFree((*h));CHKERRQ(ierr);
>   }
>   PetscFunctionReturn(0);
> }
>



-- 
What most experimenters take for granted before they begin their
experiments is infinitely more interesting than any results to which their
experiments lead.
-- Norbert Wiener
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-dev/attachments/20160422/6b015bd8/attachment.html>