On Fri, Apr 22, 2016 at 9:52 AM, Jed Brown <[email protected]> wrote:

Matthew Knepley <[email protected]> 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