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
