/*--------------------------------------------------------------------------

                  Memcheck
A simple memory leak detection program.
call deb_check to see all unallocated memory, and 
deb_dest to terminate the program, and delete the datastructures.
Doing so will free all detected memory leaks.

 * Author: Fredrik Altenstedt (pomakis@pobox.com)
 * Date:   Mar, 2002
 * Released to the public domain.

This program relies heavily (a majority of the functionality) on a public domain hash-table implementation by 
    Keith Pomakis (pomakis@pobox.com)
    The names on all functions has been changed in order not to clash with
    the original package



--------------------------------------------------------------------------*/

#include <string.h>
#include <stdio.h>



typedef struct valdata {
  int line;
  int size;
  char *file;
}valdata;

#define VALUETYPE valdata
#define KEYTYPE void*

typedef struct KeyValuePair_struct {
    KEYTYPE key;
    VALUETYPE value;
    struct KeyValuePair_struct *next;
} KeyValuePair;

typedef struct {
    long numOfBuckets;
    long numOfElements;
    KeyValuePair **bucketArray;
    float idealRatio, lowerRehashThreshold, upperRehashThreshold;
    int (*keycmp)(const KEYTYPE key1, const KEYTYPE key2);
    int (*valuecmp)(const VALUETYPE value1, const VALUETYPE value2);
    unsigned long (*hashFunction)(const KEYTYPE key);
    void (*keyDeallocator)(KEYTYPE key);
    void (*valueDeallocator)(VALUETYPE value);
} MemTable;







#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* #include "memtable.h"*/

static int DefaultKeyCmp(const KEYTYPE key1, const KEYTYPE key2);
static unsigned long DefaultHashFunction(const KEYTYPE key);
static int isProbablePrime(long number);
static long calculateIdealNumOfBuckets(MemTable *MemTable);


static void my_valuedeallocator(VALUETYPE val)
{
  free(val.file);
}


/*--------------------------------------------------------------------------*\
 *  NAME:
 *      MemTableCreate() - creates a new MemTable
 *  DESCRIPTION:
 *      Creates a new MemTable.  When finished with this MemTable, it
 *      should be explicitly destroyed by calling the MemTableDestroy()
 *      function.
 *  EFFICIENCY:
 *      O(1)
 *  ARGUMENTS:
 *      numOfBuckets - the number of buckets to start the MemTable out with.
 *                     Must be greater than zero, and should be prime.
 *                     Ideally, the number of buckets should between 1/5
 *                     and 1 times the expected number of elements in the
 *                     MemTable.  Values much more or less than this will
 *                     result in wasted memory or decreased performance
 *                     respectively.  The number of buckets in a MemTable
 *                     can be re-calculated to an appropriate number by
 *                     calling the MemTableRehash() function once the
 *                     MemTable has been populated.  The number of buckets
 *                     in a MemTable may also be re-calculated
 *                     automatically if the ratio of elements to buckets
 *                     passes the thresholds set by MemTableSetIdealRatio().
 *  RETURNS:
 *      MemTable    - a new MemTable, or NULL on error
\*--------------------------------------------------------------------------*/

static MemTable *MemTableCreate(long numOfBuckets) {
    MemTable *memtable;
    int i;


    memtable = (MemTable *) malloc(sizeof(MemTable));
    if (memtable == (MemTable*)NULL)
        return (MemTable*)NULL;

    memtable->bucketArray = (KeyValuePair **)
                        malloc(numOfBuckets * sizeof(KeyValuePair *));
    if (memtable->bucketArray == NULL) {
        free(memtable);
        return (MemTable*)NULL;
    }
    
    memtable->numOfBuckets = numOfBuckets;
    memtable->numOfElements = 0;

    for (i=0; i<numOfBuckets; i++)
        memtable->bucketArray[i] = NULL;

    memtable->idealRatio = 3.0;
    memtable->lowerRehashThreshold = 0.0;
    memtable->upperRehashThreshold = 15.0;

    memtable->keycmp = DefaultKeyCmp;
    /*    MemTable->valuecmp = DefaultValueCmp;
    MemTable->hashFunction = DefaultHashFunction;
    MemTable->keyDeallocator = NULL;*/
    memtable->valuecmp = NULL;
    memtable->hashFunction = DefaultHashFunction;
    memtable->keyDeallocator = NULL;
    memtable->valueDeallocator = my_valuedeallocator;

    return memtable;
}

/*--------------------------------------------------------------------------*\
 *  NAME:
 *      MemTableDestroy() - destroys an existing MemTable
 *  DESCRIPTION:
 *      Destroys an existing MemTable.
 *  EFFICIENCY:
 *      O(n)
 *  ARGUMENTS:
 *      MemTable    - the MemTable to destroy
 *  RETURNS:
 *      <nothing>
\*--------------------------------------------------------------------------*/

static void MemTableDestroy(MemTable *MemTable) {
    int i;

    for (i=0; i<MemTable->numOfBuckets; i++) {
        KeyValuePair *pair = MemTable->bucketArray[i];
        while (pair != (KeyValuePair*)NULL) {
            KeyValuePair *nextPair = pair->next;
            if (MemTable->keyDeallocator != NULL)
                MemTable->keyDeallocator(pair->key);
            if (MemTable->valueDeallocator != NULL)
                MemTable->valueDeallocator(pair->value);
	    free(pair->key);
            free(pair);
	    
            pair = nextPair;
        }
    }

    free(MemTable->bucketArray);
    free(MemTable);
}

/*--------------------------------------------------------------------------*\
 *  NAME:
 *      MemTableCheck() - reports all undeallocated memory
 *  ARGUMENTS:
 *      MemTable    - the MemTable to check
 *  RETURNS:
 *      <nothing>
\*--------------------------------------------------------------------------*/

static void MemTableCheck(MemTable *MemTable) {
    int i;
    int totblocks=0;
    int totbytes=0;

    for (i=0; i<MemTable->numOfBuckets; i++) {
        KeyValuePair *pair = MemTable->bucketArray[i];
        while (pair != (KeyValuePair*)NULL) {
            KeyValuePair *nextPair = pair->next;
	    /* we found something */
	    fprintf(stderr,"found %i unallocated bytes, source line %i file %s\n",
		    pair->value.size,
		    pair->value.line,
		    pair->value.file);
	    totblocks++;
	    totbytes+=pair->value.size;
            pair = nextPair;
        }
    }
    fprintf(stderr,"a total of %i bytes in %i blocks was leaked\n",
	    totbytes,totblocks);

}

/*--------------------------------------------------------------------------*\
 *  NAME:
 *      MemTableGet() - retrieves the value of a key in a MemTable
 *  DESCRIPTION:
 *      Retrieves the value of the specified key in the specified MemTable.
 *      Uses the comparison function specified by
 *      MemTableSetKeyComparisonFunction().
 *  EFFICIENCY:
 *      O(1), assuming a good hash function and element-to-bucket ratio
 *  ARGUMENTS:
 *      MemTable    - the MemTable to search
 *      key          - the key whose value is desired
 *  RETURNS:
 *      KeyValuePair *       - the value of the specified key, or NULL if the key
 *                            doesn't exist in the MemTable
\*--------------------------------------------------------------------------*/

static KeyValuePair* MemTableGet(const MemTable *MemTable, const KEYTYPE key) {
    long hashValue = MemTable->hashFunction(key) % MemTable->numOfBuckets;
    KeyValuePair *pair = MemTable->bucketArray[hashValue];

    while (pair != NULL && MemTable->keycmp(key, pair->key) != 0)
        pair = pair->next;
    return pair;
}
/*--------------------------------------------------------------------------*\
 *  NAME:
 *      MemTableContainsKey() - checks the existence of a key in a MemTable
 *  DESCRIPTION:
 *      Determines whether or not the specified MemTable contains the
 *      specified key.  Uses the comparison function specified by
 *      MemTableSetKeyComparisonFunction().
 *  EFFICIENCY:
 *      O(1), assuming a good hash function and element-to-bucket ratio
 *  ARGUMENTS:
 *      MemTable    - the MemTable to search
 *      key          - the key to search for
 *  RETURNS:
 *      bool         - whether or not the specified MemTable contains the
 *                     specified key.
\*--------------------------------------------------------------------------*/

int MemTableContainsKey(const MemTable *MemTable, const KEYTYPE key) {
    return (int)(MemTableGet(MemTable, key) != (KeyValuePair*)NULL);
}

/*--------------------------------------------------------------------------*\
 *  NAME:
 *      MemTableRehash() - reorganizes a MemTable to be more efficient
 *  DESCRIPTION:
 *      Reorganizes a MemTable to be more efficient.  If a number of
 *      buckets is specified, the MemTable is rehashed to that number of
 *      buckets.  If 0 is specified, the MemTable is rehashed to a number
 *      of buckets which is automatically calculated to be a prime number
 *      that achieves (as closely as possible) the ideal element-to-bucket 
 *      ratio specified by the MemTableSetIdealRatio() function.
 *  EFFICIENCY:
 *      O(n)
 *  ARGUMENTS:
 *      MemTable    - the MemTable to be reorganized
 *      numOfBuckets - the number of buckets to rehash the MemTable to.
 *                     Should be prime.  Ideally, the number of buckets
 *                     should be between 1/5 and 1 times the expected
 *                     number of elements in the MemTable.  Values much
 *                     more or less than this will result in wasted memory
 *                     or decreased performance respectively.  If 0 is
 *                     specified, an appropriate number of buckets is
 *                     automatically calculated.
 *  RETURNS:
 *      <nothing>
\*--------------------------------------------------------------------------*/

static void MemTableRehash(MemTable *MemTable, long numOfBuckets) {
    KeyValuePair **newBucketArray;
    int i;

    if (numOfBuckets == 0)
        numOfBuckets = calculateIdealNumOfBuckets(MemTable);

    if (numOfBuckets == MemTable->numOfBuckets)
        return; /* already the right size! */

    newBucketArray = (KeyValuePair **)
                                malloc(numOfBuckets * sizeof(KeyValuePair *));
    if (newBucketArray == NULL) {
        /* Couldn't allocate memory for the new array.  This isn't a fatal
         * error; we just can't perform the rehash. */
        return;
    }

    for (i=0; i<numOfBuckets; i++)
        newBucketArray[i] = NULL;

    for (i=0; i<MemTable->numOfBuckets; i++) {
        KeyValuePair *pair = MemTable->bucketArray[i];
        while (pair != NULL) {
            KeyValuePair *nextPair = pair->next;
            long hashValue = MemTable->hashFunction(pair->key) % numOfBuckets;
            pair->next = newBucketArray[hashValue];
            newBucketArray[hashValue] = pair;
            pair = nextPair;
        }
    }

    free(MemTable->bucketArray);
    MemTable->bucketArray = newBucketArray;
    MemTable->numOfBuckets = numOfBuckets;
}


/*--------------------------------------------------------------------------*\
 *  NAME:
 *      MemTablePut() - adds a key/value pair to a MemTable
 *  DESCRIPTION:
 *      Adds the specified key/value pair to the specified MemTable.  If
 *      the key already exists in the MemTable (determined by the comparison
 *      function specified by MemTableSetKeyComparisonFunction()), its value
 *      is replaced by the new value.  May trigger an auto-rehash (see
 *      MemTableSetIdealRatio()).  It is illegal to specify NULL as the
 *      key or value.
 *  EFFICIENCY:
 *      O(1), assuming a good hash function and element-to-bucket ratio
 *  ARGUMENTS:
 *      MemTable    - the MemTable to add to
 *      key          - the key to add or whose value to replace
 *      value        - the value associated with the key
 *  RETURNS:
 *      err          - 0 if successful, -1 if an error was encountered
\*--------------------------------------------------------------------------*/

static int MemTablePut(MemTable *MemTable, const KEYTYPE key, VALUETYPE value) {
    long hashValue;
    KeyValuePair *pair;


    hashValue = MemTable->hashFunction(key) % MemTable->numOfBuckets;
    pair = MemTable->bucketArray[hashValue];

    while (pair != NULL && MemTable->keycmp(key, pair->key) != 0)
        pair = pair->next;

    if (pair) {
        if (pair->key != key) {
            if (MemTable->keyDeallocator != NULL)
                MemTable->keyDeallocator((void *) pair->key);
            pair->key = (KEYTYPE)key;
        }
	MemTable->valueDeallocator(pair->value);
	pair->value = value;
    }
    else {
        KeyValuePair *newPair = (KeyValuePair *) malloc(sizeof(KeyValuePair));
        if (newPair == NULL) {
            return -1;
        }
        else {
            newPair->key = (KEYTYPE)key;
            newPair->value = value;
            newPair->next = MemTable->bucketArray[hashValue];
            MemTable->bucketArray[hashValue] = newPair;
            MemTable->numOfElements++;

            if (MemTable->upperRehashThreshold > MemTable->idealRatio) {
                float elementToBucketRatio = (float) MemTable->numOfElements /
                                             (float) MemTable->numOfBuckets;
                if (elementToBucketRatio > MemTable->upperRehashThreshold)
                    MemTableRehash(MemTable, 0);
            }
        }
    }

    return 0;
}


/*--------------------------------------------------------------------------*\
 *  NAME:
 *      MemTableRemove() - removes a key/value pair from a MemTable
 *  DESCRIPTION:
 *      Removes the key/value pair identified by the specified key from the
 *      specified MemTable if the key exists in the MemTable.  May trigger
 *      an auto-rehash (see MemTableSetIdealRatio()).
 *  EFFICIENCY:
 *      O(1), assuming a good hash function and element-to-bucket ratio
 *  ARGUMENTS:
 *      MemTable    - the MemTable to remove the key/value pair from
 *      key          - the key specifying the key/value pair to be removed
 *  RETURNS:
 *      <nothing>
\*--------------------------------------------------------------------------*/

static int MemTableRemove(MemTable *MemTable, const KEYTYPE key) {
    long hashValue = MemTable->hashFunction(key) % MemTable->numOfBuckets;
    KeyValuePair *pair = MemTable->bucketArray[hashValue];
    KeyValuePair *previousPair = NULL;

    while (pair != NULL && MemTable->keycmp(key, pair->key) != 0) {
        previousPair = pair;
        pair = pair->next;
    }

    if (pair != NULL) {
        if (MemTable->keyDeallocator != NULL)
            MemTable->keyDeallocator( pair->key);
        if (MemTable->valueDeallocator != NULL)
            MemTable->valueDeallocator(pair->value);
        if (previousPair != NULL)
            previousPair->next = pair->next;
        else
            MemTable->bucketArray[hashValue] = pair->next;
        free(pair);
        MemTable->numOfElements--;

        if (MemTable->lowerRehashThreshold > 0.0) {
            float elementToBucketRatio = (float) MemTable->numOfElements /
                                         (float) MemTable->numOfBuckets;
            if (elementToBucketRatio < MemTable->lowerRehashThreshold)
                MemTableRehash(MemTable, 0);
        }
	return 0;
    }
    return -1;
}

/*--------------------------------------------------------------------------*\
 *  NAME:
 *      MemTableRemoveAll() - removes all key/value pairs from a MemTable
 *  DESCRIPTION:
 *      Removes all key/value pairs from the specified MemTable.  May trigger
 *      an auto-rehash (see MemTableSetIdealRatio()).
 *  EFFICIENCY:
 *      O(n)
 *  ARGUMENTS:
 *      MemTable    - the MemTable to remove all key/value pairs from
 *  RETURNS:
 *      <nothing>
\*--------------------------------------------------------------------------*/

static void MemTableRemoveAll(MemTable *MemTable) {
    int i;

    for (i=0; i<MemTable->numOfBuckets; i++) {
        KeyValuePair *pair = MemTable->bucketArray[i];
        while (pair != NULL) {
            KeyValuePair *nextPair = pair->next;
            if (MemTable->keyDeallocator != NULL)
                MemTable->keyDeallocator(pair->key);
            if (MemTable->valueDeallocator != NULL)
                MemTable->valueDeallocator(pair->value);
            free(pair);
            pair = nextPair;
        }
        MemTable->bucketArray[i] = NULL;
    }

    MemTable->numOfElements = 0;
    MemTableRehash(MemTable, 5);
}

/*--------------------------------------------------------------------------*\
 *  NAME:
 *      MemTableIsEmpty() - determines if a MemTable is empty
 *  DESCRIPTION:
 *      Determines whether or not the specified MemTable contains any
 *      key/value pairs.
 *  EFFICIENCY:
 *      O(1)
 *  ARGUMENTS:
 *      MemTable    - the MemTable to check
 *  RETURNS:
 *      bool         - whether or not the specified MemTable contains any
 *                     key/value pairs
\*--------------------------------------------------------------------------*/

static int MemTableIsEmpty(const MemTable *MemTable) {
    return (MemTable->numOfElements == 0);
}

/*--------------------------------------------------------------------------*\
 *  NAME:
 *      MemTableSize() - returns the number of elements in a MemTable
 *  DESCRIPTION:
 *      Returns the number of key/value pairs that are present in the
 *      specified MemTable.
 *  EFFICIENCY:
 *      O(1)
 *  ARGUMENTS:
 *      MemTable    - the MemTable whose size is requested
 *  RETURNS:
 *      long         - the number of key/value pairs that are present in
 *                     the specified MemTable
\*--------------------------------------------------------------------------*/

static long MemTableSize(const MemTable *MemTable) {
    return MemTable->numOfElements;
}

/*--------------------------------------------------------------------------*\
 *  NAME:
 *      MemTableGetNumBuckets() - returns the number of buckets in a MemTable
 *  DESCRIPTION:
 *      Returns the number of buckets that are in the specified MemTable.
 *      This may change dynamically throughout the life of a MemTable if
 *      automatic or manual rehashing is performed.
 *  EFFICIENCY:
 *      O(1)
 *  ARGUMENTS:
 *      MemTable    - the MemTable whose number of buckets is requested
 *  RETURNS:
 *      long         - the number of buckets that are in the specified
 *                     MemTable
\*--------------------------------------------------------------------------*/

long MemTableGetNumBuckets(const MemTable *MemTable) {
    return MemTable->numOfBuckets;
}

/*--------------------------------------------------------------------------*\
 *  NAME:
 *      MemTableSetKeyComparisonFunction()
 *              - specifies the function used to compare keys in a MemTable
 *  DESCRIPTION:
 *      Specifies the function used to compare keys in the specified
 *      MemTable.  The specified function should return zero if the two
 *      keys are considered equal, and non-zero otherwise.  The default
 *      function is one that simply compares pointers.
 *  ARGUMENTS:
 *      MemTable    - the MemTable whose key comparison function is being
 *                     specified
 *      keycmp       - a function which returns zero if the two arguments
 *                     passed to it are considered "equal" keys and non-zero
 *                     otherwise
 *  RETURNS:
 *      <nothing>
\*--------------------------------------------------------------------------*/

static void MemTableSetKeyComparisonFunction(MemTable *MemTable,
        int (*keycmp)(const KEYTYPE key1, const KEYTYPE key2)) {
    MemTable->keycmp = keycmp;
}


/*--------------------------------------------------------------------------*\
 *  NAME:
 *      MemTableSetHashFunction()
 *              - specifies the hash function used by a MemTable
 *  DESCRIPTION:
 *      Specifies the function used to determine the hash value for a key
 *      in the specified MemTable (before modulation).  An ideal hash
 *      function is one which is easy to compute and approximates a
 *      "random" function.  The default function is one that works
 *      relatively well for pointers.  If the MemTable keys are to be
 *      strings (which is probably the case), then this default function
 *      will not suffice, in which case consider using the provided
 *      MemTableStringHashFunction() function.
 *  ARGUMENTS:
 *      MemTable    - the MemTable whose hash function is being specified
 *      hashFunction - a function which returns an appropriate hash code
 *                     for a given key
 *  RETURNS:
 *      <nothing>
\*--------------------------------------------------------------------------*/

static void MemTableSetHashFunction(MemTable *MemTable,
        unsigned long (*hashFunction)(const KEYTYPE key))
{
    MemTable->hashFunction = hashFunction;
}

/*--------------------------------------------------------------------------*\
 *  NAME:
 *      MemTableSetIdealRatio()
 *              - sets the ideal element-to-bucket ratio of a MemTable
 *  DESCRIPTION:
 *      Sets the ideal element-to-bucket ratio, as well as the lower and
 *      upper auto-rehash thresholds, of the specified MemTable.  Note
 *      that this function doesn't actually perform a rehash.
 *
 *      The default values for these properties are 3.0, 0.0 and 15.0
 *      respectively.  This is likely fine for most situations, so there
 *      is probably no need to call this function.
 *  ARGUMENTS:
 *      MemTable    - a MemTable
 *      idealRatio   - the ideal element-to-bucket ratio.  When a rehash
 *                     occurs (either manually via a call to the
 *                     MemTableRehash() function or automatically due the
 *                     the triggering of one of the thresholds below), the
 *                     number of buckets in the MemTable will be
 *                     recalculated to be a prime number that achieves (as
 *                     closely as possible) this ideal ratio.  Must be a
 *                     positive number.
 *      lowerRehashThreshold
 *                   - the element-to-bucket ratio that is considered
 *                     unacceptably low (i.e., too few elements per bucket).
 *                     If the actual ratio falls below this number, a
 *                     rehash will automatically be performed.  Must be
 *                     lower than the value of idealRatio.  If no ratio
 *                     is considered unacceptably low, a value of 0.0 can
 *                     be specified.
 *      upperRehashThreshold
 *                   - the element-to-bucket ratio that is considered
 *                     unacceptably high (i.e., too many elements per bucket).
 *                     If the actual ratio rises above this number, a
 *                     rehash will automatically be performed.  Must be
 *                     higher than idealRatio.  However, if no ratio
 *                     is considered unacceptably high, a value of 0.0 can
 *                     be specified.
 *  RETURNS:
 *      <nothing>
\*--------------------------------------------------------------------------*/

static void MemTableSetIdealRatio(MemTable *MemTable, float idealRatio,
        float lowerRehashThreshold, float upperRehashThreshold) {

    MemTable->idealRatio = idealRatio;
    MemTable->lowerRehashThreshold = lowerRehashThreshold;
    MemTable->upperRehashThreshold = upperRehashThreshold;
}

/*--------------------------------------------------------------------------*\
 *  NAME:
 *      MemTableSetDeallocationFunctions()
 *              - sets the key and value deallocation functions of a MemTable
 *  DESCRIPTION:
 *      Sets the key and value deallocation functions of the specified
 *      MemTable.  This determines what happens to a key or a value when it
 *      is removed from the MemTable.  If the deallocation function is NULL
 *      (the default if this function is never called), its reference is
 *      simply dropped and it is up to the calling program to perform the
 *      proper memory management.  If the deallocation function is non-NULL,
 *      it is called to free the memory used by the object.  E.g., for simple
 *      objects, an appropriate deallocation function may be free().
 *
 *      This affects the behaviour of the MemTableDestroy(), MemTablePut(),
 *      MemTableRemove() and MemTableRemoveAll() functions.
 *  ARGUMENTS:
 *      MemTable    - a MemTable
 *      keyDeallocator
 *                   - if non-NULL, the function to be called when a key is
 *                     removed from the MemTable.
 *      valueDeallocator
 *                   - if non-NULL, the function to be called when a value is
 *                     removed from the MemTable.
 *  RETURNS:
 *      <nothing>
\*--------------------------------------------------------------------------*/

static void MemTableSetDeallocationFunctions(MemTable *MemTable,
        void (*keyDeallocator)(KEYTYPE key),
        void (*valueDeallocator)(VALUETYPE value)) {
    MemTable->keyDeallocator = keyDeallocator;
    MemTable->valueDeallocator = valueDeallocator;
}

/*--------------------------------------------------------------------------*\
 *  NAME:
 *      MemTableStringHashFunction() - a good hash function for strings
 *  DESCRIPTION:
 *      A hash function that is appropriate for hashing strings.  Note that
 *      this is not the default hash function.  To make it the default hash
 *      function, call MemTableSetHashFunction(MemTable,
 *      MemTableStringHashFunction).
 *  ARGUMENTS:
 *      key    - the key to be hashed
 *  RETURNS:
 *      unsigned long - the unmodulated hash value of the key
\*--------------------------------------------------------------------------*/

static unsigned long MemTableStringHashFunction(const char * key) {
    const unsigned char *str = (const unsigned char *) key;
    unsigned long hashValue = 0;
    int i;

    for (i=0; str[i] != '\0'; i++)
        hashValue = hashValue * 37 + str[i];

    return hashValue;
}

static int DefaultKeyCmp(const KEYTYPE key1, const KEYTYPE key2) {
    return (key1 != key2);
}

static unsigned long DefaultHashFunction(const KEYTYPE key) {
    return ((unsigned long) key) >> 4;
}

static int isProbablePrime(long oddNumber) {
    long i;

    for (i=3; i<51; i+=2)
        if (oddNumber == i)
            return 1;
        else if (oddNumber%i == 0)
            return 0;

    return 1; /* maybe */
}

static long calculateIdealNumOfBuckets(MemTable *MemTable) {
    long idealNumOfBuckets = MemTable->numOfElements / MemTable->idealRatio;
    if (idealNumOfBuckets < 5)
        idealNumOfBuckets = 5;
    else
        idealNumOfBuckets |= 0x01; /* make it an odd number */
    while (!isProbablePrime(idealNumOfBuckets))
        idealNumOfBuckets += 2;

    return idealNumOfBuckets;
}



/* This code written by Fredrik Altenstedt */

MemTable *memdata;

int first_call=1;



/*--------------------------------------------------------------------------*\
 *  NAME:
 *      deb_malloc
 *  DESCRIPTION:
 *      debug replacement for malloc, logs all call to the hashtable memdata
 *  ARGUMENTS:
 *      size    - requested size
 *      line    - line number of call
 *      file    - file of call
 *  RETURNS:
 *      void *  - pointer to allocated memory
\*--------------------------------------------------------------------------*/
void *deb_malloc(size_t size, int line, char *file)
{
  int status;
  void *ret;
  
  valdata value;

  if (first_call)
    {
      memdata=MemTableCreate(1000);
      first_call=0;
    }

  ret=(void*)malloc(size);
  
  if (ret)
    {
      value.line=line;
      value.size=size;
      value.file=strdup(file);
      status=MemTablePut(memdata,ret,value);
      if (status)
	return NULL;
    }
  return ret;
}

/*--------------------------------------------------------------------------*\
 *  NAME:
 *      deb_free
 *  DESCRIPTION:
 *      debug replacement for free, checks that freed 
        memory has been allocated
 *  ARGUMENTS:
 *      ptr     - pointer to memory to free
 *      line    - line number of call
 *      file    - file of call
 *  RETURNS:
 *      nothing
\*--------------------------------------------------------------------------*/
void deb_free(void *ptr, int line, char *file)
{
  
  int status;

  if (!ptr)
    return;
    
    

  if (first_call)
    {
      memdata=MemTableCreate(1000);
      first_call=0;
    }

  /* find in database */
  status=MemTableRemove(memdata,ptr);
  if (status)
    {
      fprintf(stderr,"freeing unallocated memory on line %i of %s\n",
	      line,file);
    }
  else
    free(ptr);
}


/*--------------------------------------------------------------------------*\
 *  NAME:
 *      deb_realloc
 *  DESCRIPTION:
 *      debug replacement for realloc, checks that we are not reallocating 
 *      unallocated memory
 *  ARGUMENTS:
 *      ptr     - pointer to memory to realloc
 *      size    - wanted size of memory block
 *      line    - line number of call
 *      file    - file of call
 *  RETURNS:
 *      void *  - pointer to allocated memory
\*--------------------------------------------------------------------------*/
void *deb_realloc(void *ptr, size_t size, int line, char *file)
{
  int status;
  void *ret;
  KeyValuePair *pair;

  valdata value;

  if (first_call)
    {
      memdata=MemTableCreate(1000);
      first_call=0;
    }
  
  /* check for null pointer */
  if (!ptr)
    return deb_malloc(size,line,file);
  if (!size)
    {
      deb_free(ptr,line,file);
      return NULL;
    }
  
  /* check if we are reallocating something we should not */
  pair=MemTableGet(memdata,ptr);
  if (pair)
    {
      /* ok, we got it, change size */
      pair->value.size=size;
      ret=(void*)realloc(ptr,size);
      if (ret!=ptr)
	{
	  /* position has moved */
	  /* make a copy */
	  value=pair->value;
	  value.file=strdup(pair->value.file);
	  MemTableRemove(memdata,ptr);
	  
	  status=MemTablePut(memdata,ret,value);
	  if (status)
	    return NULL;
	}
    }
  else
    {
      fprintf(stderr,"reallocating unallocated memory, line %i, file %s\n",
	      line,file);
      return deb_malloc(size,line,file);
    }
  return ret;
}  


/*--------------------------------------------------------------------------*\
 *  NAME:
 *      deb_calloc
 *  DESCRIPTION:
 *      debug replacement for malloc, logs all call to the hashtable memdata
 *  ARGUMENTS:
 *      size    - requested size of elements
 *      elems   - requested no of elements
 *      line    - line number of call
 *      file    - file of call
 *  RETURNS:
 *      void *  - pointer to allocated memory
\*--------------------------------------------------------------------------*/
void *deb_calloc(size_t elems,size_t size,int line ,char *file)
{
  int status;
  void *ret;
  
  valdata value;

  if (first_call)
    {
      memdata=MemTableCreate(1000);
      first_call=0;
    }

  ret=(void*)calloc(elems,size);
  
  if (ret)
    {
      value.line=line;
      value.size=size*elems;
      value.file=strdup(file);
      status=MemTablePut(memdata,ret,value);
      if (status)
	return NULL;
    }
  return ret;
}

/*--------------------------------------------------------------------------*\
 *  NAME:
 *      deb_strdup
 *  DESCRIPTION:
 *      debug replacement for strdup, logs all call to the hashtable memdata
 *  ARGUMENTS:
 *      in      - Pointer to memory string to copy
 *      line    - line number of call
 *      file    - file of call
 *  RETURNS:
 *      char *  - pointer to copy of string
\*--------------------------------------------------------------------------*/
char* deb_strdup(char* in,int line,char *file)
{
  int len;
  char *out;
  KeyValuePair *pair;
  len=strlen(in);
  
  out=(char*)deb_malloc((len+1)*sizeof(char),line,file);
  pair=MemTableGet(memdata,out);
  if (!pair)
    {
      fprintf(stderr,"Ooops");
      exit(-1);
    }
  strcpy(out,in);
  return out;
}


/*--------------------------------------------------------------------------*\
 *  NAME:
 *      deb_check
 *  DESCRIPTION:
 *      checks the allocated memory and lists all allocated data blocks
 *  ARGUMENTS:
 *      none
 *  RETURNS:
 *      nothing
\*--------------------------------------------------------------------------*/
void deb_check()
{
  if (first_call)
    {
      memdata=MemTableCreate(1000);
      first_call=0;
    }

  MemTableCheck(memdata);
}

/*--------------------------------------------------------------------------*\
 *  NAME:
 *      deb_dest
 *  DESCRIPTION:
 *      terminates by reporting all non-freed memory, freeing all non-freed memory
 *      and destroying the hashtable. If you are lazy, you may in principle
 *      use this functionality to reclaim all allocated memory.
 *  ARGUMENTS:
 *      none
 *  RETURNS:
 *      nothing
\*--------------------------------------------------------------------------*/
void deb_dest()
{
  if (first_call)
    {
      memdata=MemTableCreate(1000);
      first_call=0;
    }

  MemTableCheck(memdata);
  MemTableDestroy(memdata);
  first_call=1;
}