path: root/Source/DirectFB/lib/direct/hash.c

/*
   (c) Copyright 2001-2009  The world wide DirectFB Open Source Community (directfb.org)
   (c) Copyright 2000-2004  Convergence (integrated media) GmbH

   All rights reserved.

   Written by Denis Oliver Kropp <dok@directfb.org>,
              Andreas Hundt <andi@fischlustig.de>,
              Sven Neumann <neo@directfb.org>,
              Ville Syrjälä <syrjala@sci.fi> and
              Claudio Ciccani <klan@users.sf.net>.

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

   This library 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
   Lesser General Public License for more details.

   You should have received a copy of the GNU Lesser General Public
   License along with this library; if not, write to the
   Free Software Foundation, Inc., 59 Temple Place - Suite 330,
   Boston, MA 02111-1307, USA.
*/

#include <config.h>

#include <stdlib.h>

#include <direct/debug.h>
#include <direct/hash.h>
#include <direct/mem.h>
#include <direct/messages.h>


D_DEBUG_DOMAIN( Direct_Hash, "Direct/Hash", "Hash table implementation" );


#define REMOVED  ((void *) -1)

typedef struct {
     unsigned long  key;
     void          *value;
} Element;

struct __D_DirectHash {
     int       magic;

     int       size;

     int       count;
     int       removed;

     Element  *elements;
};

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

static inline int
locate_key( const DirectHash *hash, unsigned long key )
{
     int            pos;
     const Element *element;

     pos = key % hash->size;

     element = &hash->elements[pos];

     while (element->value) {
          if (element->value != REMOVED && element->key == key)
               return pos;

          if (++pos == hash->size)
               pos = 0;

          element = &hash->elements[pos];
     }

     return -1;
}

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

DirectResult
direct_hash_create( int          size,
                    DirectHash **ret_hash )
{
     DirectHash *hash;

     if (size < 17)
          size = 17;

     D_DEBUG_AT( Direct_Hash, "Creating hash table with initial capacity of %d...\n", size );

     hash = D_CALLOC( 1, sizeof (DirectHash) );
     if (!hash) {
          D_WARN( "out of memory" );
          return DR_NOLOCALMEMORY;
     }

     hash->size     = size;
     hash->elements = D_CALLOC( size, sizeof(Element) );

     if (!hash->elements) {
          D_WARN( "out of memory" );
          D_FREE( hash );
          return DR_NOLOCALMEMORY;
     }

     D_MAGIC_SET( hash, DirectHash );

     *ret_hash = hash;

     return DR_OK;
}

void
direct_hash_destroy( DirectHash *hash )
{
     D_MAGIC_ASSERT( hash, DirectHash );

     D_MAGIC_CLEAR( hash );

     D_FREE( hash->elements );
     D_FREE( hash );
}

DirectResult
direct_hash_insert( DirectHash    *hash,
                    unsigned long  key,
                    void          *value )
{
     int      pos;
     Element *element;

     D_MAGIC_ASSERT( hash, DirectHash );
     D_ASSERT( value != NULL );

     /* Need to resize the hash table? */
     if ((hash->count + hash->removed) > hash->size / 4) {
          int      i, size = hash->size * 3;
          Element *elements;

          D_DEBUG_AT( Direct_Hash, "Resizing from %d to %d... (count %d, removed %d)\n",
                      hash->size, size, hash->count, hash->removed );

          elements = D_CALLOC( size, sizeof(Element) );
          if (!elements) {
               D_WARN( "out of memory" );
               return DR_NOLOCALMEMORY;
          }

          for (i=0; i<hash->size; i++) {
               Element *element = &hash->elements[i];
               Element *insertElement;

               if (element->value && element->value != REMOVED) {
                    pos = element->key % size;

                    insertElement = &elements[pos];
                    while (insertElement->value && insertElement->value != REMOVED) {
                        if (++pos == size)
                            pos = 0;
                        insertElement = &elements[pos];
                    }

                    elements[pos] = *element;
               }
          }

          D_FREE( hash->elements );

          hash->size     = size;
          hash->elements = elements;
          hash->removed  = 0;
     }

     pos = key % hash->size;

     D_DEBUG_AT( Direct_Hash, "Attempting to insert key 0x%08lx at position %d...\n", key, pos );

     element = &hash->elements[pos];

     while (element->value && element->value != REMOVED) {
          if (element->key == key) {
               D_BUG( "key already exists" );
               return DR_BUG;
          }

          if (++pos == hash->size)
               pos = 0;

          element = &hash->elements[pos];
     }

     if (element->value == REMOVED)
          hash->removed--;

     element->key   = key;
     element->value = value;

     hash->count++;

     D_DEBUG_AT( Direct_Hash, "...inserted at %d, new count = %d, removed = %d, size = %d, key = 0x%08lx.\n",
                 pos, hash->count, hash->removed, hash->size, key );

     return DR_OK;
}

void
direct_hash_remove( DirectHash    *hash,
                    unsigned long  key )
{
     int pos;

     D_MAGIC_ASSERT( hash, DirectHash );

     pos = locate_key( hash, key );
     if (pos == -1) {
          D_WARN( "key not found" );
          return;
     }

     hash->elements[pos].value = REMOVED;

     hash->count--;
     hash->removed++;

     D_DEBUG_AT( Direct_Hash, "Removed key 0x%08lx at %d, new count = %d, removed = %d, size = %d.\n",
                 key, pos, hash->count, hash->removed, hash->size );
}

void *
direct_hash_lookup( DirectHash    *hash,
                    unsigned long  key )
{
     int pos;

     D_MAGIC_ASSERT( hash, DirectHash );

     pos = locate_key( hash, key );

     return (pos != -1) ? hash->elements[pos].value : NULL;
}

void
direct_hash_iterate( DirectHash             *hash,
                     DirectHashIteratorFunc  func,
                     void                   *ctx )
{
     int i;

     D_MAGIC_ASSERT( hash, DirectHash );

     for (i=0; i<hash->size; i++) {
          Element *element = &hash->elements[i];

          if (!element->value || element->value == REMOVED)
               continue;

          if (!func( hash, element->key, element->value, ctx ) )
               return;
     }
}