hashpointer.c File Reference

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <limits.h>
#include "linear_assert.h"
#include "boolean.h"

Include dependency graph for hashpointer.c:

Go to the source code of this file.

Data Structures
struct	paire
struct	linear_hashtable_st
	hidden structure to store the hashtable. More...

Macros
#define	debug_assert(a)
	expected headers: the internal structure does not need to be available! struct linear_hashtable_st; typedef struct linear_hashtable_st * linear_hashtable_pt; More...
#define	debug_assert_coherent(h)   debug_assert(linear_hashtable_coherent_p(h))
#define	FREE_CHUNK   ((void *) 0)
#define	EMPTIED_CHUNK   ((void *) -1)
#define	HASHTABLE_INITIAL_SIZE   (17)
	size of internal table. More...

Typedefs
typedef struct linear_hashtable_st *	linear_hashtable_pt
	hidden structure to store the hashtable. More...

Functions
static uintptr_t	key_location (linear_hashtable_pt h, void *k, bool toget)
	returns the location to put or get k in h. More...
static void	linear_hashtable_print (FILE *file, linear_hashtable_pt h)
void	linear_hashtable_dump (linear_hashtable_pt h)
	convenient function to be called from gdb. More...
bool	linear_hashtable_coherent_p (linear_hashtable_pt h)
	check hashtable coherency More...
linear_hashtable_pt	linear_hashtable_make (void)
	constructor. More...
void	linear_hashtable_free (linear_hashtable_pt h)
	destructor More...
static void	linear_hashtable_extend (linear_hashtable_pt h)
static void	linear_hashtable_internal_put (linear_hashtable_pt h, void *k, void *v, bool once)
void	linear_hashtable_put (linear_hashtable_pt h, void *k, void *v)
void	linear_hashtable_put_once (linear_hashtable_pt h, void *k, void *v)
bool	linear_hashtable_isin (linear_hashtable_pt h, void *k)
bool	linear_hashtable_remove (linear_hashtable_pt h, void *k)
void *	linear_hashtable_get (linear_hashtable_pt h, void *k)
int	linear_hashtable_nitems (linear_hashtable_pt h)

Macro Definition Documentation

debug_assert

#define debug_assert

(

a

)

expected headers: the internal structure does not need to be available! struct linear_hashtable_st; typedef struct linear_hashtable_st * linear_hashtable_pt;

#define LINEAR_HASHTABLE_DEBUG 1

Definition at line 50 of file hashpointer.c.

debug_assert_coherent

#define debug_assert_coherent

(

h

)

debug_assert(linear_hashtable_coherent_p(h))

Definition at line 53 of file hashpointer.c.

EMPTIED_CHUNK

#define EMPTIED_CHUNK   ((void *) -1)

Definition at line 56 of file hashpointer.c.

FREE_CHUNK

#define FREE_CHUNK   ((void *) 0)

Definition at line 55 of file hashpointer.c.

HASHTABLE_INITIAL_SIZE

#define HASHTABLE_INITIAL_SIZE   (17)

size of internal table.

should be a not too big odd number.

Definition at line 160 of file hashpointer.c.

Typedef Documentation

linear_hashtable_pt

typedef struct linear_hashtable_st * linear_hashtable_pt

hidden structure to store the hashtable.

Function Documentation

key_location()

static uintptr_t key_location ( linear_hashtable_pt  h, void *  k, bool  toget  )

static

returns the location to put or get k in h.

should not loop to put!

if !loop and toget, the initial index is returned. it is checked against the expected key before returning the value.

Definition at line 75 of file hashpointer.c.

{
  uintptr_t index = ((((uintptr_t) k)
                      & ~(((uintptr_t)1) << ((sizeof(uintptr_t)*CHAR_BIT) - 1)))
                     % (h->size));
  uintptr_t loop = h->size;
 
  while (loop-- && !(h->contents[index].key==FREE_CHUNK ||
                   h->contents[index].key==k ||
                   (toget && h->contents[index].key==EMPTIED_CHUNK)))
    index = (index+1) % h->size;
 
  assert(!(!loop && !toget)); /* should not loop to put! */
 
  /* if !loop and toget, the initial index is returned.
   * it is checked against the expected key before returning the value.
   */
  debug_assert(index>=0 && index<h->size &&
               (h->contents[index].key==FREE_CHUNK ||
                h->contents[index].key==EMPTIED_CHUNK ||
                (h->contents[index].key==k || (!loop && toget))));
 
  return index;
}

References assert, linear_hashtable_st::contents, debug_assert, EMPTIED_CHUNK, FREE_CHUNK, paire::key, linear_hashtable_st::size, and uintptr_t.

Referenced by linear_hashtable_coherent_p(), linear_hashtable_extend(), linear_hashtable_get(), linear_hashtable_internal_put(), linear_hashtable_isin(), linear_hashtable_print(), and linear_hashtable_remove().

Here is the caller graph for this function:

linear_hashtable_coherent_p()

bool linear_hashtable_coherent_p

(

linear_hashtable_pt

h

)

check hashtable coherency

coherent size/nitems.

check number of item stored.

check key index

Definition at line 128 of file hashpointer.c.

{
  uintptr_t i, n;
 
  /* coherent size/nitems. */
  if (h->nitems >= h->size) 
    return false;
 
  /* check number of item stored. */
  for(i=0, n=0; i<h->size; i++)
  {
    void * k = h->contents[i].key;
    if (k!=FREE_CHUNK && k!=EMPTIED_CHUNK)
    {
      /* check key index */
      uintptr_t index = key_location(h, k, true);
      if (index!=i) return false;
      n++;
    }
  }
 
  if (n!=h->nitems)
    return false;
 
  return true;
}

References linear_hashtable_st::contents, EMPTIED_CHUNK, FREE_CHUNK, paire::key, key_location(), linear_hashtable_st::nitems, linear_hashtable_st::size, and uintptr_t.

Here is the call graph for this function:

linear_hashtable_dump()

void linear_hashtable_dump

(

linear_hashtable_pt

h

)

convenient function to be called from gdb.

hashpointer.c

Definition at line 122 of file hashpointer.c.

{
  linear_hashtable_print(stderr, h);
}

References linear_hashtable_print().

Here is the call graph for this function:

linear_hashtable_extend()

static void linear_hashtable_extend ( linear_hashtable_pt  h )

static

check malloc

the expected number of items was moved.

Definition at line 197 of file hashpointer.c.

{
  paire * oldcontents;
  uintptr_t i, oldsize, moved_nitems;
 
  debug_assert_coherent(h);
 
  moved_nitems = h->nitems;
  oldcontents = h->contents;
  oldsize = h->size;
 
  h->size = 2*oldsize + 1;
  h->contents = (paire*) malloc(sizeof(paire)*h->size);
  assert(h->contents); /* check malloc */
 
  for (i=0; i<h->size; i++)
    h->contents[i].key = FREE_CHUNK,
      h->contents[i].val = FREE_CHUNK;
 
  for (i=0; i<oldsize; i++)
  {
    register void * k = oldcontents[i].key;
    if (k!=FREE_CHUNK && k!=EMPTIED_CHUNK)
    {
      register int index = key_location(h, k, false);
      h->contents[index].key = k;
      h->contents[index].val = oldcontents[i].val;
      moved_nitems--;
    }
  }
 
  assert(moved_nitems==0); /* the expected number of items was moved. */
  free(oldcontents);
 
  debug_assert_coherent(h);
}

References assert, linear_hashtable_st::contents, debug_assert_coherent, EMPTIED_CHUNK, free(), FREE_CHUNK, paire::key, key_location(), malloc(), linear_hashtable_st::nitems, linear_hashtable_st::size, uintptr_t, and paire::val.

Referenced by linear_hashtable_internal_put().

Here is the call graph for this function:

Here is the caller graph for this function:

linear_hashtable_free()

void linear_hashtable_free

(

linear_hashtable_pt

h

)

destructor

Definition at line 189 of file hashpointer.c.

{
  debug_assert_coherent(h);
  
  free(h->contents);
  free(h);
}

References linear_hashtable_st::contents, debug_assert_coherent, and free().

Referenced by base_append(), base_included_p(), base_union(), fortran_data_to_prec_for_variables(), sc_to_minimal_basis(), transitive_closure_from_two_bases(), and vect_check().

Here is the call graph for this function:

Here is the caller graph for this function:

linear_hashtable_get()

void* linear_hashtable_get	(	linear_hashtable_pt	h,
		void *	k
	)

Definition at line 293 of file hashpointer.c.

{
  register int index = key_location(h, k, true);
  return h->contents[index].key==k ? h->contents[index].val: FREE_CHUNK;
}

References linear_hashtable_st::contents, FREE_CHUNK, paire::key, key_location(), and paire::val.

Here is the call graph for this function:

linear_hashtable_internal_put()

static void linear_hashtable_internal_put ( linear_hashtable_pt  h, void *  k, void *  v, bool  once  )

static

no special values!

50% limit to extend

is it already in?

no

where should it be put?

if it is in, the once option must not be set

update number of stored items

Definition at line 236 of file hashpointer.c.

{
  register int index;
 
  assert(k!=FREE_CHUNK && k!=EMPTIED_CHUNK); /* no special values! */
  debug_assert_coherent(h);
 
  if ((h->nitems*2) > h->size) { /* 50% limit to extend */
    linear_hashtable_extend(h);
  }
 
  index = key_location(h, k, true); /* is it already in? */
  if (h->contents[index].key!=k) /* no */
    index = key_location(h, k, false); /* where should it be put? */
  else 
    assert(!once); /* if it is in, the once option must not be set */
 
  if (h->contents[index].key!=k) /* update number of stored items */
    h->nitems++;
 
  h->contents[index].key = k;
  h->contents[index].val = v;
 
  debug_assert_coherent(h);
}

References assert, linear_hashtable_st::contents, debug_assert_coherent, EMPTIED_CHUNK, FREE_CHUNK, paire::key, key_location(), linear_hashtable_extend(), linear_hashtable_st::nitems, linear_hashtable_st::size, and paire::val.

Referenced by linear_hashtable_put(), and linear_hashtable_put_once().

Here is the call graph for this function:

Here is the caller graph for this function:

linear_hashtable_isin()

bool linear_hashtable_isin	(	linear_hashtable_pt	h,
		void *	k
	)

Definition at line 273 of file hashpointer.c.

{
  return h->contents[key_location(h, k, true)].key==k;
}

References linear_hashtable_st::contents, paire::key, and key_location().

Referenced by base_append(), base_included_p(), base_to_set(), base_union(), contains_variables(), fortran_data_to_prec_for_variables(), sc_to_minimal_basis(), and vect_check().

Here is the call graph for this function:

Here is the caller graph for this function:

linear_hashtable_make()

linear_hashtable_pt linear_hashtable_make

(

void

)

constructor.

returns a newly allocated hashtable.

check malloc

check malloc

Definition at line 165 of file hashpointer.c.

{
  linear_hashtable_pt h;
  register int i, size = HASHTABLE_INITIAL_SIZE;
 
  h = (linear_hashtable_pt) malloc(sizeof(struct linear_hashtable_st));
  assert(h); /* check malloc */
 
  h->size = size;
  h->nitems = 0;
  h->contents = (paire*) malloc(sizeof(paire)*size);
 
  assert(h->contents); /* check malloc */
 
  for (i=0; i<size; i++)
    h->contents[i].key = FREE_CHUNK, 
      h->contents[i].val = FREE_CHUNK;
 
  debug_assert_coherent(h);
 
  return h;
}

References assert, linear_hashtable_st::contents, debug_assert_coherent, FREE_CHUNK, HASHTABLE_INITIAL_SIZE, paire::key, malloc(), linear_hashtable_st::nitems, linear_hashtable_st::size, and paire::val.

Referenced by base_append(), base_included_p(), base_union(), fortran_data_to_prec_for_variables(), sc_to_minimal_basis(), transitive_closure_from_two_bases(), and vect_check().

Here is the call graph for this function:

Here is the caller graph for this function:

linear_hashtable_nitems()

int linear_hashtable_nitems

(

linear_hashtable_pt

h

)

Definition at line 299 of file hashpointer.c.

{
  return h->nitems;
}

References linear_hashtable_st::nitems.

linear_hashtable_print()

static void linear_hashtable_print ( FILE *  file, linear_hashtable_pt  h  )

static

Definition at line 102 of file hashpointer.c.

{
  uintptr_t i;
 
  fprintf(file, "[linear_hashtable_dump] hash=%p size=%zd nitems=%zd\n",
          h, h->size, h->nitems);
  
  for (i=0; i<h->size; i++)
  {
    void * k = h->contents[i].key;
    fprintf(file, "%zd (%td): 0x%p -> 0x%p\n", 
            i, 
            (k!=FREE_CHUNK && k!=EMPTIED_CHUNK)? key_location(h, k, true): ~(uintptr_t)0,
            k, h->contents[i].val);
  }
 
  fprintf(file, "[linear_hashtable_dump] done.\n");
}

References linear_hashtable_st::contents, EMPTIED_CHUNK, fprintf(), FREE_CHUNK, paire::key, key_location(), linear_hashtable_st::nitems, linear_hashtable_st::size, uintptr_t, and paire::val.

Referenced by linear_hashtable_dump().

Here is the call graph for this function:

Here is the caller graph for this function:

linear_hashtable_put()

void linear_hashtable_put	(	linear_hashtable_pt	h,
		void *	k,
		void *	v
	)

Definition at line 263 of file hashpointer.c.

{
  linear_hashtable_internal_put(h, k, v, false);
}

References linear_hashtable_internal_put().

Referenced by base_to_set(), and vect_check().

Here is the call graph for this function:

Here is the caller graph for this function:

linear_hashtable_put_once()

void linear_hashtable_put_once	(	linear_hashtable_pt	h,
		void *	k,
		void *	v
	)

Definition at line 268 of file hashpointer.c.

{
  linear_hashtable_internal_put(h, k, v, true);
}

References linear_hashtable_internal_put().

Referenced by base_append(), base_included_p(), base_union(), fortran_data_to_prec_for_variables(), and sc_to_minimal_basis().

Here is the call graph for this function:

Here is the caller graph for this function:

linear_hashtable_remove()

bool linear_hashtable_remove	(	linear_hashtable_pt	h,
		void *	k
	)

Definition at line 278 of file hashpointer.c.

{
  register int index = key_location(h, k, true);
 
  if (h->contents[index].key==k) 
  {
    h->contents[index].key = EMPTIED_CHUNK;
    h->contents[index].val = FREE_CHUNK;
    h->nitems--;
    return true;
  }
 
  return false;
}

References linear_hashtable_st::contents, EMPTIED_CHUNK, FREE_CHUNK, paire::key, key_location(), linear_hashtable_st::nitems, and paire::val.

Here is the call graph for this function: