---

xhash_tmpl_c.inc

Go to the documentation of this file.

/***************************************************************************
                               xhash_tmpl_c.inc
                             -------------------
    begin                : Sat Dec 08 2001
    copyright            : (C) 2001-2002 by Christian Hoenig & Gunter Ohrner
    email                : pdepp@CustomCDROM.de
 ***************************************************************************/

/***************************************************************************
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 ***************************************************************************/

// any Table Name Prefix defined?
#ifdef XH_TABLE_NAME

#include "common.h"

#include <stdlib.h>
#include <sys/types.h>
#include <assert.h>

#include "xmalloc.h"

#ifndef XHPFX
# define XHPFX XH_FUNC_PFX
#endif

#ifdef DOXYGEN_PREPROCESSING
# include "xhash_tmpl_h.inc"
#endif

#undef KEY_VAL_PAIR

#define KEY_VAL_PAIR fn(XH_TABLE_NAME, KeyValPair)

struct KEY_VAL_PAIR
{
  XH_KEY key;        
  XH_CARGO payload;  
};

typedef struct KEY_VAL_PAIR* KEY_VAL_PAIR;

#ifndef XH_CREATE_KEY

# define XH_CREATE_KEY(new)
#endif
#ifndef XH_COPY_KEY

# define XH_COPY_KEY(dest, source) (dest = source)
#endif
#ifndef XH_FREE_KEY

# define XH_FREE_KEY(a) 
#endif

#ifndef XH_CREATE_CARGO

# define XH_CREATE_CARGO(new)
#endif
#ifndef XH_COPY_CARGO

# define XH_COPY_CARGO(dest, source) (dest = source)
#endif
#ifndef XH_FREE_CARGO

# define XH_FREE_CARGO(a)
#endif


// define mlist data types for external hashing:
#define MlCargo KEY_VAL_PAIR
#define XH_HASH_LIST_NAME fn(XH_TABLE_NAME, ExtHashList)
#define ML_LIST_NAME XH_HASH_LIST_NAME
#define XH_HASH_LIST_FUNC_PFX fn(XH_FUNC_PFX, ExtHashList)
#define ML_FUNC_PFX XH_HASH_LIST_FUNC_PFX
#define ML_INVALID NULL

#undef ML_IS_VALID_CARGO

#undef ML_CREATE_CARGO

#define ML_CREATE_CARGO(new) (new = (MlCargo) pd_malloc(sizeof(struct KEY_VAL_PAIR)))

#undef ML_COPY_CARGO

#define ML_COPY_CARGO(dest, source) { \
                                      XH_COPY_KEY(dest->key, source->key); \
                                      XH_COPY_CARGO(dest->payload, source->payload);\
                                    }

#undef ML_FREE_CARGO

#define ML_FREE_CARGO(a) { \
                          XH_FREE_KEY(a->key); \
                          XH_FREE_CARGO(a->payload); \
                          pd_free(a); \
                         }

// include mlist for external hashing
#include "mlist_tmpl_h.inc"
#include "mlist_tmpl_c.inc"

struct XH_TABLE_NAME
{
  size_t table_size;               
  XH_HASH_LIST_NAME* table;        
  XH_HASH_LIST_NAME cur_hash_list; 
};

// init hash table
XH_TABLE_NAME fn(XHPFX,Init)(const size_t size)
{
  size_t i;
  // alloc hash table control block
  XH_TABLE_NAME this = (XH_TABLE_NAME) pd_malloc(sizeof(struct XH_TABLE_NAME));

  // alloc hash table
  this->table = (XH_HASH_LIST_NAME*) pd_malloc(sizeof(XH_HASH_LIST_NAME) * size);

  for (i = 0; i < size; ++i)
    *((this->table) + i) = fn(XH_HASH_LIST_FUNC_PFX,Init)();

  this->table_size = size;

  return this;
}

// insert a key value pair
int fn(XHPFX,Insert)(XH_TABLE_NAME this, XH_KEY key, XH_CARGO new_load)
{
  struct KEY_VAL_PAIR kvp;

  // delete object with same key if existing but select the right
  // external hashing list in any case
  fn(XHPFX,Delete)(this, key);

//  XH_CREATE_KEY(kvp.key);
//  XH_COPY_KEY(kvp.key, key);
//  XH_CREATE_CARGO(kvp.payload);
//  XH_COPY_CARGO(kvp.payload, new_load);
  kvp.key = key;
  kvp.payload = new_load;

  fn(XH_HASH_LIST_FUNC_PFX,Append)(this->cur_hash_list, &kvp);

  return 0;
}

inline int fn(XHPFX,Select)(XH_TABLE_NAME this, const XH_KEY key)
{
  size_t hash_val  = XH_CALC_HASH_VAL(key, this->table_size);
  size_t table_ofs = hash_val % this->table_size;
  XH_HASH_LIST_NAME* table_pos = this->table + table_ofs;

  this->cur_hash_list = *(table_pos);

  fn(XH_HASH_LIST_FUNC_PFX,First)(this->cur_hash_list);

  while(!fn(XH_HASH_LIST_FUNC_PFX,IsTail)(this->cur_hash_list))
  {
    KEY_VAL_PAIR kvp = fn(XH_HASH_LIST_FUNC_PFX,GetPayload)(this->cur_hash_list);
    if (XH_KEYS_EQUAL(key, kvp->key))
      return 0;

    fn(XH_HASH_LIST_FUNC_PFX,Next)(this->cur_hash_list);
  }

  return -1;
}

// delete an entry
int fn(XHPFX,Delete)(XH_TABLE_NAME this, XH_KEY key)
{
  if (fn(XHPFX,Select)(this, key) == -1)
    return -1;
  else
    return fn(XH_HASH_LIST_FUNC_PFX,Delete)(this->cur_hash_list);
}

// get a table entry
XH_CARGO fn(XHPFX,Get)(XH_TABLE_NAME this, const XH_KEY key)
{
  return (fn(XHPFX,Select)(this, key) == -1) ? XH_INVALID 
          : fn(XH_HASH_LIST_FUNC_PFX,GetPayload)(this->cur_hash_list)->payload;
}

// delete the table
int fn(XHPFX,Terminate)(XH_TABLE_NAME this)
{
  size_t i;

  for(i = 0; i < this->table_size; ++i)
  {
    this->cur_hash_list = *(this->table + i);
    fn(XH_HASH_LIST_FUNC_PFX,Terminate)(this->cur_hash_list);
  }
  pd_free(this->table);
  pd_free(this);

  return 0;
}


#undef KEY_VAL_PAIR
#undef XH_CREATE_KEY
#undef XH_COPY_KEY
#undef XH_FREE_KEY
#undef XH_CREATE_CARGO
#undef XH_COPY_CARGO
#undef XH_FREE_CARGO
#undef MlCargo
#undef XH_HASH_LIST_NAME
// #undef ML_LIST_NAME
#undef XH_HASH_LIST_FUNC_PFX
//#undef ML_FUNC_PFX
#undef ML_INVALID

//#undef ML_IS_VALID_CARGO

#undef ML_CREATE_CARGO
#undef ML_COPY_CARGO
#undef ML_FREE_CARGO

#undef XHPFX

#endif

---