---

epHash.c

Go to the documentation of this file.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "epDefs.h"
#include "epUtils.h"
#include "epHash.h"

epHash_t *epHash_create(const ulong numOfBuckets,
  boolean_t (*keyComparisonFunction)(const void *key1, const void *key2),
  uint    (*hashFunction)(const void *key),
  int     (*keyDeallocatorFunction)(void *key),
  int     (*valueDeallocatorFunction)(void *value))
{
  epHash_t *hashTable;
  int i;
        
  _DEBUG("epHash_create call");
        
  if(keyComparisonFunction == NULL || hashFunction == NULL)
    {                                }
  else if((hashTable =(epHash_t *) malloc(sizeof(epHash_t))) == NULL)
    { /*err_set(errno, SYS_ERROR);*/ } 
  else if((hashTable->bucketArray =
           (struct epHashElt_s **) malloc(sizeof(struct epHashElt_s *) * 
                                          numOfBuckets)) == NULL) 
    {
      /*err_set(errno, SYS_ERROR); */
      free(hashTable);
      hashTable = NULL;
    } else {
      hashTable->numOfBuckets = numOfBuckets<5? 5: numOfBuckets;
      hashTable->numOfElements = 0;

      /* par défaut, pas de rehashage automatique décrémentiel */
      hashTable->lowerRehashThreshold = _DEFAULT_LowerRehashThreshold;
      hashTable->upperRehashThreshold = _DEFAULT_UpperRehashThreshold;
      hashTable->idealRatio = _DEFAULT_IdealRatio;

      /* on sait que les 2 1ères fncts ne sont pas nulles(cf 'if')*/
      hashTable->keyComparisonFunction = keyComparisonFunction;
      hashTable->hashFunction = hashFunction;
      hashTable->keyDeallocatorFunction = (keyDeallocatorFunction != NULL?
                                           keyDeallocatorFunction:
                                           epUtils_ptrDeallocatorFunction);
      hashTable->valueDeallocatorFunction = (valueDeallocatorFunction != NULL?
                                             valueDeallocatorFunction:
                                             epUtils_ptrDeallocatorFunction);

      /* initialisation de la table de hashage */       
      for(i = 0; i < numOfBuckets; i++) {
        hashTable->bucketArray[i] = NULL;
      }
    }

  return(hashTable);
}

int epHash_destroy(epHash_t *hashTable)
{
  int i;
  struct epHashElt_s *curElt,
                     *nextElt;

  _DEBUG("epHash_destroy call");

  /* 1. On supprime tous les couple <clé, valeur> de la table */        
  for(i = 0; i < hashTable->numOfBuckets; i++)
    {
      curElt = hashTable->bucketArray[i];

      while(curElt != NULL)
        {
          nextElt = curElt->next;

          (void) hashTable->keyDeallocatorFunction(curElt->key);
          (void) hashTable->valueDeallocatorFunction(curElt->value);
          free(curElt);

          curElt = nextElt;
        }
    }

  /* 2. On libère l'espace mémoire occupé par la table de Hashage */
  free(hashTable->bucketArray);
  free(hashTable);
  
  return(0);
}

uint epHash_size(epHash_t *hashTable)
{
  _DEBUG("epHash_size call");
  return(hashTable->numOfElements);
}

boolean_t epHash_isEmpty(epHash_t *hashTable)
{
  _DEBUG("epHash_isEmpty call");
  return(hashTable->numOfElements == 0? _true: _false);
}

uint epHash_getNumOfBuckets(epHash_t *hashTable)
{
  _DEBUG("epHash_getNumOfBuckets call");
  return(hashTable->numOfBuckets);
}

int epHash_put(epHash_t *hashTable, const void *key, const void *value)
{
  int retVal = -1;             /* valeur de retour */
  struct epHashElt_s *curElt;
  uint hashVal;

  _DEBUG("epHash_put call");

  hashVal = (hashTable->hashFunction(key) % hashTable->numOfBuckets);

  /* on vérifie que la clé n'est pas déjà présente dans la table 
     de hashage                                                  */
  curElt = hashTable->bucketArray[hashVal]; 

  while(curElt != NULL && 
        !hashTable->keyComparisonFunction(curElt->key, key))
    { curElt = curElt->next; }
      
  /* on a trouvé la même clé */
  if(curElt != NULL)
    {
      _DEBUG("clé déjà présente");
      //err_set(KEY_EXIST, PER_ERROR);                  
    } else if((curElt =
               (struct epHashElt_s *) malloc(sizeof(struct epHashElt_s))) == 
              NULL) {  
      //err_set(errno, SYS_ERROR);
    } else {
      curElt->key = (void *)key;
      curElt->value = (void *)value;

      /* le nouvel élément est inséré comme premier élément du bucket 
         considéré                                                    */
      curElt->next = hashTable->bucketArray[hashVal];
      hashTable->bucketArray[hashVal] = curElt;

      hashTable->numOfElements++;

      /* rehashage automatique si autorisé et nécessaire */
      if(HAS_TO_BE_REHASHED(hashTable))
        { epHash_rehash(hashTable, 0); }
      
      retVal = 0;
    }
    
  return(retVal);
}

void *epHash_get(const epHash_t *hashTable, const void *key)
{
  void *value;              /* valeur de retour */
  struct epHashElt_s *curElt;
  uint hashVal;

  _DEBUG("epHash_get call");

  hashVal = hashTable->hashFunction(key) % hashTable->numOfBuckets;

  curElt = hashTable->bucketArray[hashVal]; 
  while(curElt != NULL && 
        !hashTable->keyComparisonFunction(curElt->key, key))
    { curElt = curElt->next; }

  if(curElt == NULL)
    {
      //err_set(KEY_NEXIST, PER_ERROR);
      value = NULL;
    } 
  else 
    { value = curElt->value; }

  return(value);
}

int epHash_remove(epHash_t *hashTable, const void *key)
{
  struct epHashElt_s *curElt,
                     *prevElt;
  uint hashVal;

  _DEBUG("epHash_remove call");

  hashVal = hashTable->hashFunction(key) % hashTable->numOfBuckets;

  curElt = hashTable->bucketArray[hashVal];
  prevElt = NULL;

  while(curElt != NULL && 
        !hashTable->keyComparisonFunction(curElt->key, key))
    {
      prevElt = curElt;
      curElt = curElt->next;
    }
  
  if(curElt != NULL)
    {
      hashTable->keyDeallocatorFunction(curElt->key);
      hashTable->valueDeallocatorFunction(curElt->value);

      if(prevElt == NULL)
        { hashTable->bucketArray[hashVal] = curElt->next; }
      else
        { prevElt->next = curElt->next; }

      free(curElt);
      hashTable->numOfElements--;
    }
  
  /* rehashage automatique si autorisé et nécessaire */
  if(HAS_TO_BE_REHASHED(hashTable))
    { epHash_rehash(hashTable, 0); }

  return(0);
}

boolean_t epHash_containsKey(epHash_t *hashTable, const void *key)
{
  _DEBUG("epHash_containsKey call");
  return(epHash_get(hashTable, key) != NULL? _true: _false);
}

int epHash_rehash(epHash_t *hashTable, uint numOfBuckets)
{
  int i;
  uint hashVal;
  struct epHashElt_s **newBucketArray,
                      *curElt, 
                      *nextElt;
  
  _DEBUG("epHash_rehash call");

  if(numOfBuckets == 0)
    { numOfBuckets = calculateIdealNumOfBuckets(hashTable); }
  else if(numOfBuckets < 5)
    { numOfBuckets = 5; }

  if(numOfBuckets != hashTable->numOfBuckets)
    {
      if((newBucketArray =
          (struct epHashElt_s **) malloc(sizeof(struct epHashElt_s *) * 
                                         numOfBuckets)) != NULL)
        {
          for(i = 0; i < numOfBuckets; newBucketArray[i] = NULL, i++);
            
          for(i = 0; i < hashTable->numOfBuckets; i++)
            {
              curElt = hashTable->bucketArray[i];

              while(curElt != NULL)
                {
                  nextElt = curElt->next;
                  hashVal = hashTable->hashFunction(curElt->key) % 
                    numOfBuckets;

                  curElt->next = newBucketArray[hashVal];
                  newBucketArray[hashVal] = curElt;
                  curElt = nextElt;
                  }
            }

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

  return(0);
}

void epHash_setIdealRatio(epHash_t *hashTable, double idealRatio,
                          double lowerRehashThreshold, 
                          double upperRehashThreshold)
{
  _DEBUG("epHash_setIdealRatio call");

  /* tester tous > à 0 */
  hashTable->idealRatio = idealRatio;
  hashTable->lowerRehashThreshold = lowerRehashThreshold;
  /* tester > à idealRatio */
  hashTable->upperRehashThreshold = upperRehashThreshold;
}

uint calculateIdealNumOfBuckets(const epHash_t *hashTable)
{
  uint idealNumOfBuckets;

  _DEBUG("calculateIdealNumOfBuckets call");

  idealNumOfBuckets =(uint) (hashTable->numOfElements / 
                             hashTable->idealRatio);

  if(idealNumOfBuckets < 5)
    { idealNumOfBuckets = 5; }
  else
    {
      idealNumOfBuckets |= 0x01; /* make it an odd number */
      
      while (!epUtils_isProbablePrime(idealNumOfBuckets))
        { idealNumOfBuckets += 2; }
    }
  
  return(idealNumOfBuckets);
}

---