~drizzle-trunk/drizzle/development

/* -*- mode: c++; c-basic-offset: 2; indent-tabs-mode: nil; -*-

 *  vim:expandtab:shiftwidth=2:tabstop=2:smarttab:

 *

 *  Copyright (C) 2008 Sun Microsystems

 *

 *  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; version 2 of the License.

 *

 *  This program is distributed in the hope that it will be useful,

 *  but WITHOUT ANY WARRANTY; without even the implied warranty of

 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

 *  GNU General Public License for more details.

 *

 *  You should have received a copy of the GNU General Public License

 *  along with this program; if not, write to the Free Software

 *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA

 */

/* The hash functions used for saving keys */

/* One of key_length or key_length_offset must be given */

/* Key length of 0 isn't allowed */

#include <drizzled/global.h>

#include CSTDINT_H

#include <mysys/hash.h>

const uint32_t NO_RECORD= UINT32_MAX;

const int LOWFIND= 1;

const int LOWUSED= 2;

const int HIGHFIND= 4;

const int HIGHUSED= 8;

typedef struct st_hash_info {

  /* index to next key */

  uint32_t next;

  /* data for current entry */

  unsigned char *data;

} HASH_LINK;

static uint32_t hash_mask(uint32_t hashnr, uint32_t buffmax,

                          uint32_t maxlength);

static void movelink(HASH_LINK *array, uint32_t pos,

                     uint32_t next_link, uint32_t newlink);

static int hashcmp(const HASH *hash, HASH_LINK *pos, const unsigned char *key,

                   size_t length);

static uint32_t calc_hash(const HASH *hash, const unsigned char *key,

                          size_t length)

{

  uint32_t nr1=1, nr2=4;

  hash->charset->coll->hash_sort(hash->charset, key,length, &nr1, &nr2);

  return nr1;

}

bool

_hash_init(HASH *hash,uint32_t growth_size, const CHARSET_INFO * const charset,

           uint32_t size, size_t key_offset, size_t key_length,

           hash_get_key get_key,

           hash_free_key free_element, uint32_t flags)

{

  hash->records=0;

  if (my_init_dynamic_array_ci(&hash->array, sizeof(HASH_LINK), size,

                               growth_size))

  {

    /* Allow call to hash_free */

    hash->free=0;

    return true;

  }

  hash->key_offset=key_offset;

  hash->key_length=key_length;

  hash->blength=1;

  hash->get_key=get_key;

  hash->free=free_element;

  hash->flags=flags;

  hash->charset=charset;

  return false;

}

/*

  Call hash->free on all elements in hash.

  SYNOPSIS

  hash_free_elements()

  hash   hash table

  NOTES:

  Sets records to 0

*/

static inline void hash_free_elements(HASH *hash)

{

  if (hash->free)

  {

    HASH_LINK *data=dynamic_element(&hash->array,0,HASH_LINK*);

    HASH_LINK *end= data + hash->records;

    while (data < end)

      (*hash->free)((data++)->data);

  }

  hash->records=0;

}

/*

  Free memory used by hash.

  SYNOPSIS

  hash_free()

  hash   the hash to delete elements of

  NOTES: Hash can't be reused without calling hash_init again.

*/

void hash_free(HASH *hash)

{

  hash_free_elements(hash);

  hash->free= 0;

  delete_dynamic(&hash->array);

  return;

}

/* some helper functions */

/*

  This function is char* instead of unsigned char* as HPUX11 compiler can't

  handle inline functions that are not defined as native types

*/

static inline char*

hash_key(const HASH *hash, const unsigned char *record, size_t *length,

         bool first)

{

  if (hash->get_key)

    return (char*) (*hash->get_key)(record,length,first);

  *length=hash->key_length;

  return (char*) record+hash->key_offset;

}

/* Calculate pos according to keys */

static uint32_t hash_mask(uint32_t hashnr,uint32_t buffmax,uint32_t maxlength)

{

  if ((hashnr & (buffmax-1)) < maxlength) return (hashnr & (buffmax-1));

  return (hashnr & ((buffmax >> 1) -1));

}

static uint32_t hash_rec_mask(const HASH *hash, HASH_LINK *pos,

                              uint32_t buffmax, uint32_t maxlength)

{

  size_t length;

  unsigned char *key= (unsigned char*) hash_key(hash,pos->data,&length,0);

  return hash_mask(calc_hash(hash,key,length),buffmax,maxlength);

}

static

inline

unsigned int rec_hashnr(HASH *hash,const unsigned char *record)

{

  size_t length;

  unsigned char *key= (unsigned char*) hash_key(hash,record,&length,0);

  return calc_hash(hash,key,length);

}

unsigned char* hash_search(const HASH *hash, const unsigned char *key,

                           size_t length)

{

  HASH_SEARCH_STATE state;

  return hash_first(hash, key, length, &state);

}

/*

  Search after a record based on a key

  NOTE

  Assigns the number of the found record to HASH_SEARCH_STATE state

*/

unsigned char* hash_first(const HASH *hash, const unsigned char *key,

                          size_t length,

                          HASH_SEARCH_STATE *current_record)

{

  HASH_LINK *pos;

  uint32_t flag,idx;

  flag=1;

  if (hash->records)

  {

    idx=hash_mask(calc_hash(hash,key,length ? length : hash->key_length),

                  hash->blength,hash->records);

    do

    {

      pos= dynamic_element(&hash->array,idx,HASH_LINK*);

      if (!hashcmp(hash,pos,key,length))

      {

        *current_record= idx;

        return (pos->data);

      }

      if (flag)

      {

        /* Reset flag */

        flag=0;

        if (hash_rec_mask(hash,pos,hash->blength,hash->records) != idx)

          /* Wrong link */

          break;

      }

    }

    while ((idx=pos->next) != NO_RECORD);

  }

  *current_record= NO_RECORD;

  return(0);

}

/* Get next record with identical key */

/* Can only be called if previous calls was hash_search */

unsigned char* hash_next(const HASH *hash, const unsigned char *key,

                         size_t length,

                         HASH_SEARCH_STATE *current_record)

{

  HASH_LINK *pos;

  uint32_t idx;

  if (*current_record != NO_RECORD)

  {

    HASH_LINK *data=dynamic_element(&hash->array,0,HASH_LINK*);

    for (idx=data[*current_record].next; idx != NO_RECORD ; idx=pos->next)

    {

      pos=data+idx;

      if (!hashcmp(hash,pos,key,length))

      {

        *current_record= idx;

        return pos->data;

      }

    }

    *current_record= NO_RECORD;

  }

  return 0;

}

/* Change link from pos to new_link */

static void movelink(HASH_LINK *array, uint32_t find,

                     uint32_t next_link, uint32_t newlink)

{

  HASH_LINK *old_link;

  do

  {

    old_link=array+next_link;

  }

  while ((next_link=old_link->next) != find);

  old_link->next= newlink;

  return;

}

/*

  Compare a key in a record to a whole key. Return 0 if identical

  SYNOPSIS

  hashcmp()

  hash   hash table

  pos    position of hash record to use in comparison

  key    key for comparison

  length length of key

  NOTES:

  If length is 0, comparison is done using the length of the

  record being compared against.

  RETURN

  = 0  key of record == key

  != 0 key of record != key

*/

static int hashcmp(const HASH *hash, HASH_LINK *pos, const unsigned char *key,

                   size_t length)

{

  size_t rec_keylength;

  unsigned char *rec_key= (unsigned char*) hash_key(hash, pos->data,

                                                    &rec_keylength,1);

  return ((length && length != rec_keylength) ||

          my_strnncoll(hash->charset, rec_key, rec_keylength,

                       key, rec_keylength));

}

/* Write a hash-key to the hash-index */

bool my_hash_insert(HASH *info,const unsigned char *record)

{

  int flag;

  size_t idx;

  uint32_t halfbuff,hash_nr,first_index;

  unsigned char *ptr_to_rec=NULL,*ptr_to_rec2=NULL;

  HASH_LINK *data,*empty,*gpos=NULL,*gpos2=NULL,*pos;

  if (HASH_UNIQUE & info->flags)

  {

    unsigned char *key= (unsigned char*) hash_key(info, record, &idx, 1);

    if (hash_search(info, key, idx))

      /* Duplicate entry */

      return(true);

  }

  flag=0;

  if (!(empty=(HASH_LINK*) alloc_dynamic(&info->array)))

    /* No more memory */

    return(true);

  data=dynamic_element(&info->array,0,HASH_LINK*);

  halfbuff= info->blength >> 1;

  idx= first_index= info->records-halfbuff;

  /* If some records */

  if (idx != info->records)

  {

    do

    {

      pos=data+idx;

      hash_nr=rec_hashnr(info,pos->data);

      /* First loop; Check if ok */

      if (flag == 0)

        if (hash_mask(hash_nr,info->blength,info->records) != first_index)

          break;

      if (!(hash_nr & halfbuff))

      {

        /* Key will not move */

        if (!(flag & LOWFIND))

        {

          if (flag & HIGHFIND)

          {

            flag=LOWFIND | HIGHFIND;

            /* key shall be moved to the current empty position */

            gpos=empty;

            ptr_to_rec=pos->data;

            /* This place is now free */

            empty=pos;

          }

          else

          {

            /* key isn't changed */

            flag=LOWFIND | LOWUSED;

            gpos=pos;

            ptr_to_rec=pos->data;

          }

        }

        else

        {

          if (!(flag & LOWUSED))

          {

            /* Change link of previous LOW-key */

            gpos->data=ptr_to_rec;

            gpos->next= (uint32_t) (pos-data);

            flag= (flag & HIGHFIND) | (LOWFIND | LOWUSED);

          }

          gpos=pos;

          ptr_to_rec=pos->data;

        }

      }

      else

      {

        /* key will be moved */

        if (!(flag & HIGHFIND))

        {

          flag= (flag & LOWFIND) | HIGHFIND;

          /* key shall be moved to the last (empty) position */

          gpos2 = empty; empty=pos;

          ptr_to_rec2=pos->data;

        }

        else

        {

          if (!(flag & HIGHUSED))

          {

            /* Change link of previous hash-key and save */

            gpos2->data=ptr_to_rec2;

            gpos2->next=(uint32_t) (pos-data);

            flag= (flag & LOWFIND) | (HIGHFIND | HIGHUSED);

          }

          gpos2=pos;

          ptr_to_rec2=pos->data;

        }

      }

    }

    while ((idx=pos->next) != NO_RECORD);

    if ((flag & (LOWFIND | LOWUSED)) == LOWFIND)

    {

      gpos->data=ptr_to_rec;

      gpos->next=NO_RECORD;

    }

    if ((flag & (HIGHFIND | HIGHUSED)) == HIGHFIND)

    {

      gpos2->data=ptr_to_rec2;

      gpos2->next=NO_RECORD;

    }

  }

  /* Check if we are at the empty position */

  idx=hash_mask(rec_hashnr(info,record),info->blength,info->records+1);

  pos=data+idx;

  if (pos == empty)

  {

    pos->data=(unsigned char*) record;

    pos->next=NO_RECORD;

  }

  else

  {

    /* Check if more records in same hash-nr family */

    empty[0]=pos[0];

    gpos=data+hash_rec_mask(info,pos,info->blength,info->records+1);

    if (pos == gpos)

    {

      pos->data=(unsigned char*) record;

      pos->next=(uint32_t) (empty - data);

    }

    else

    {

      pos->data=(unsigned char*) record;

      pos->next=NO_RECORD;

      movelink(data,(uint32_t) (pos-data),(uint32_t) (gpos-data),(uint32_t) (empty-data));

    }

  }

  if (++info->records == info->blength)

    info->blength+= info->blength;

  return(0);

}

/******************************************************************************

 ** Remove one record from hash-table. The record with the same record

 ** ptr is removed.

 ** if there is a free-function it's called for record if found

 *****************************************************************************/

bool hash_delete(HASH *hash,unsigned char *record)

{

  uint32_t blength,pos2,pos_hashnr,lastpos_hashnr,idx,empty_index;

  HASH_LINK *data,*lastpos,*gpos,*pos,*pos3,*empty;

  if (!hash->records)

    return(1);

  blength=hash->blength;

  data=dynamic_element(&hash->array,0,HASH_LINK*);

  /* Search after record with key */

  pos=data+ hash_mask(rec_hashnr(hash,record),blength,hash->records);

  gpos = 0;

  while (pos->data != record)

  {

    gpos=pos;

    if (pos->next == NO_RECORD)

      /* Key not found */

      return(1);

    pos=data+pos->next;

  }

  if ( --(hash->records) < hash->blength >> 1) hash->blength>>=1;

  lastpos=data+hash->records;

  /* Remove link to record */

  empty=pos; empty_index=(uint32_t) (empty-data);

  if (gpos)

    /* unlink current ptr */

    gpos->next=pos->next;

  else if (pos->next != NO_RECORD)

  {

    empty=data+(empty_index=pos->next);

    pos->data=empty->data;

    pos->next=empty->next;

  }

  /* last key at wrong pos or no next link */

  if (empty == lastpos)

    goto exit;

  /* Move the last key (lastpos) */

  lastpos_hashnr=rec_hashnr(hash,lastpos->data);

  /* pos is where lastpos should be */

  pos=data+hash_mask(lastpos_hashnr,hash->blength,hash->records);

  /* Move to empty position. */

  if (pos == empty)

  {

    empty[0]=lastpos[0];

    goto exit;

  }

  pos_hashnr=rec_hashnr(hash,pos->data);

  /* pos3 is where the pos should be */

  pos3= data+hash_mask(pos_hashnr,hash->blength,hash->records);

  if (pos != pos3)

  {					/* pos is on wrong posit */

    empty[0]=pos[0];			/* Save it here */

    pos[0]=lastpos[0];			/* This should be here */

    movelink(data,(uint32_t) (pos-data),(uint32_t) (pos3-data),empty_index);

    goto exit;

  }

  pos2= hash_mask(lastpos_hashnr,blength,hash->records+1);

  if (pos2 == hash_mask(pos_hashnr,blength,hash->records+1))

  {					/* Identical key-positions */

    if (pos2 != hash->records)

    {

      empty[0]=lastpos[0];

      movelink(data,(uint32_t) (lastpos-data),(uint32_t) (pos-data),empty_index);

      goto exit;

    }

    idx= (uint32_t) (pos-data);		/* Link pos->next after lastpos */

  }

  else idx= NO_RECORD;		/* Different positions merge */

  empty[0]=lastpos[0];

  movelink(data,idx,empty_index,pos->next);

  pos->next=empty_index;

exit:

  pop_dynamic(&hash->array);

  if (hash->free)

    (*hash->free)((unsigned char*) record);

  return(0);

}

unsigned char *hash_element(HASH *hash,uint32_t idx)

{

  if (idx < hash->records)

    return dynamic_element(&hash->array,idx,HASH_LINK*)->data;

  return 0;

}