<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Fri, Apr 22, 2016 at 9:52 AM, Jed Brown <span dir="ltr"><<a href="mailto:jed@jedbrown.org" target="_blank">jed@jedbrown.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><span class="">Matthew Knepley <<a href="mailto:knepley@gmail.com">knepley@gmail.com</a>> writes:<br>
> You are wrong in this case. The HashIJ is not trivial, and cannot be done<br>
> easily inline. What is the problem here?<br>
<br>
</span>$ git grep -l 'PetscHashIJ[^K]'<br>
src/sys/examples/tests/ex26.c<br>
src/sys/utils/hash.h<br>
<br>
$ git grep -l 'PetscHashJK'<br>
src/dm/impls/plex/plexfem.c<br>
src/mat/impls/preallocator/matpreallocator.c<br>
src/sys/utils/hash.h<br>
<br>
But matpreallocator.c doesn't actually use the linked list aspects of<br>
PetscHashJK, so it's memory overhead (two unused pointers plus padding<br>
per entry) for nothing.<br>
<br>
$ git grep -l 'PetscHashIJKL'<br>
src/dm/impls/plex/plexinterpolate.c<br>
src/sys/utils/hash.h<br>
<br>
This is actually used, but I think the implementation (below) accurately<br>
fits my description of wrapping khash primitives with imaginary error<br>
checking. Lawrence, do you just want a general-purpose hash table or do<br>
you specifically want Matt's hash/linked-list structure?<br></blockquote><div><br></div><div>I assume you would just stick this stuff in source files?</div><div><br></div><div><div>/* Linked list of values in a bucket. */</div><div>struct _IJKLNode {</div><div> PetscInt k;</div><div> struct _IJKLNode *next;</div><div>};</div><div>typedef struct _IJKLNode IJKLNode;</div><div><br></div><div>/* Value (holds a linked list of nodes) in the bucket. */</div><div>struct _IJKLVal {</div><div> PetscInt n;</div><div> IJKLNode *head, *tail;</div><div>};</div><div>typedef struct _IJKLVal IJKLVal;</div><div><br></div><div>/* Key (a quartet of integers). */</div><div>struct _PetscHashIJKLKey {</div><div> PetscInt i, j, k, l;</div><div>};</div><div>typedef struct _PetscHashIJKLKey PetscHashIJKLKey;</div><div><br></div><div>/* Hash function: mix two integers into one.</div><div> 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.</div><div> We should shift by (8/4)*sizeof(PetscInt): sizeof(PetscInt) is the number of bytes in PetscInt, with 8 bits per byte.</div><div> */</div><div>#define IJKLKeyHash(key) ( (((key).i) << (4*sizeof(PetscInt)))^((key).j)^(((key).k) << (2*sizeof(PetscInt)))^(((key).l) << (6*sizeof(PetscInt))) )</div><div><br></div><div>/* Compare two keys (integer pairs). */</div><div>#define IJKLKeyEqual(k1,k2) (((k1).i==(k2).i) ? ((k1).j==(k2).j) ? ((k1).k==(k2).k) ? ((k1).l==(k2).l) : 0 : 0 : 0)</div><div><br></div><div>KHASH_INIT(HASHIJKL,PetscHashIJKLKey,IJKLVal,1,IJKLKeyHash,IJKLKeyEqual)</div><div><br></div><div>struct _PetscHashIJKL {</div><div> khash_t(HASHIJKL) *ht;</div><div>};</div><div><br></div><div>typedef struct _PetscHashIJKL *PetscHashIJKL;</div><div><br></div><div>typedef khiter_t PetscHashIJKLIter;</div><div><br></div><div>typedef IJKLNode *PetscHashIJKLValIter;</div></div><div><br></div><div>This is a silly argument. It is argument for the sake of arguing rather than to improve what we are doing.</div><div><br></div><div> Matt</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
#undef __FUNCT__<br>
#define __FUNCT__ "PetscHashIJKLCreate"<br>
PETSC_STATIC_INLINE PetscErrorCode PetscHashIJKLCreate(PetscHashIJKL *h)<br>
{<br>
PetscErrorCode ierr;<br>
<br>
PetscFunctionBegin;<br>
PetscValidPointer(h, 1);<br>
ierr = PetscNew((h));CHKERRQ(ierr);<br>
(*h)->ht = kh_init(HASHIJKL);<br>
PetscFunctionReturn(0);<br>
}<br>
<br>
#undef __FUNCT__<br>
#define __FUNCT__ "PetscHashIJKLResize"<br>
PETSC_STATIC_INLINE PetscErrorCode PetscHashIJKLResize(PetscHashIJKL h, PetscInt n)<br>
{<br>
PetscFunctionBegin;<br>
(kh_resize(HASHIJKL, (h)->ht, (n)));<br>
PetscFunctionReturn(0);<br>
}<br>
<br>
#undef __FUNCT__<br>
#define __FUNCT__ "PetscHashIJKLKeySize"<br>
PETSC_STATIC_INLINE PetscErrorCode PetscHashIJKLKeySize(PetscHashIJKL h, PetscInt *n)<br>
{<br>
PetscFunctionBegin;<br>
((*n) = kh_size((h)->ht));<br>
PetscFunctionReturn(0);<br>
}<br>
<br>
#undef __FUNCT__<br>
#define __FUNCT__ "PetscHashIJKLPut"<br>
/*<br>
PetscHashIJKLPut - Insert key in the hash table<br>
<br>
Input Parameters:<br>
+ h - The hash table<br>
- key - The key to insert<br>
<br>
Output Parameter:<br>
+ 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<br>
- iter - Iterator into table<br>
<br>
Level: developer<br>
<br>
.seealso: PetscHashIJKLCreate(), PetscHashIJKLSet()<br>
*/<br>
PETSC_STATIC_INLINE PetscErrorCode PetscHashIJKLPut(PetscHashIJKL h, PetscHashIJKLKey key, PetscHashIJKLIter *missing, PetscHashIJKLIter *iter)<br>
{<br>
PetscFunctionBeginHot;<br>
*iter = kh_put(HASHIJKL, (h)->ht, (key), missing);<br>
PetscFunctionReturn(0);<br>
}<br>
<br>
#undef __FUNCT__<br>
#define __FUNCT__ "PetscHashIJKLSet"<br>
/*<br>
PetscHashIJKLSet - Set the value for an iterator in the hash table<br>
<br>
Input Parameters:<br>
+ h - The hash table<br>
. iter - An iterator into the table<br>
- value - The value to set<br>
<br>
Level: developer<br>
<br>
.seealso: PetscHashIJKLCreate(), PetscHashIJKLPut(), PetscHashIJKLGet()<br>
*/<br>
PETSC_STATIC_INLINE PetscErrorCode PetscHashIJKLSet(PetscHashIJKL h, PetscHashIJKLIter iter, PetscInt value)<br>
{<br>
PetscFunctionBeginHot;<br>
kh_val((h)->ht, iter).n = value;<br>
PetscFunctionReturn(0);<br>
}<br>
<br>
#undef __FUNCT__<br>
#define __FUNCT__ "PetscHashIJKLGet"<br>
/*<br>
PetscHashIJKLGet - Get the value for an iterator in the hash table<br>
<br>
Input Parameters:<br>
+ h - The hash table<br>
. iter - An iterator into the table<br>
<br>
Output Parameters:<br>
. value - The value to get<br>
<br>
Level: developer<br>
<br>
.seealso: PetscHashIJKLCreate(), PetscHashIJKLPut(), PetscHashIJKLSet()<br>
*/<br>
PETSC_STATIC_INLINE PetscErrorCode PetscHashIJKLGet(PetscHashIJKL h, PetscHashIJKLIter iter, PetscInt *value)<br>
{<br>
PetscFunctionBeginHot;<br>
*value = kh_val((h)->ht, iter).n;<br>
PetscFunctionReturn(0);<br>
}<br>
<br>
#undef __FUNCT__<br>
#define __FUNCT__ "PetscHashIJKLClear"<br>
PETSC_STATIC_INLINE PetscErrorCode PetscHashIJKLClear(PetscHashIJKL h)<br>
{<br>
PetscFunctionBegin;<br>
kh_clear(HASHIJKL, (h)->ht);<br>
PetscFunctionReturn(0);<br>
}<br>
<br>
#undef __FUNCT__<br>
#define __FUNCT__ "PetscHashIJKLDestroy"<br>
PETSC_STATIC_INLINE PetscErrorCode PetscHashIJKLDestroy(PetscHashIJKL *h)<br>
{<br>
PetscFunctionBegin;<br>
PetscValidPointer(h, 1);<br>
if ((*h)) {<br>
PetscErrorCode ierr;<br>
<br>
if ((*h)->ht) {<br>
kh_destroy(HASHIJKL, (*h)->ht);<br>
(*h)->ht = NULL;<br>
}<br>
ierr = PetscFree((*h));CHKERRQ(ierr);<br>
}<br>
PetscFunctionReturn(0);<br>
}<br>
</blockquote></div><br><br clear="all"><div><br></div>-- <br><div class="gmail_signature">What most experimenters take for granted before they begin their experiments is infinitely more interesting than any results to which their experiments lead.<br>-- Norbert Wiener</div>
</div></div>