On Fri, Apr 22, 2016 at 9:52 AM, Jed Brown <jed@jedbrown.org> wrote:
Matthew Knepley <knepley@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