hash.c

AnyQ服务端源代码(2004/10/28)源码

/* --------------------------------------------------------------------------
 *
 * License
 *
 * The contents of this file are subject to the Jabber Open Source License
 * Version 1.0 (the "License").  You may not copy or use this file, in either
 * source code or executable form, except in compliance with the License.  You
 * may obtain a copy of the License at http://www.jabber.com/license/ or at
 * http://www.opensource.org/.
 *
 * Software distributed under the License is distributed on an "AS IS" basis,
 * WITHOUT WARRANTY OF ANY KIND, either express or implied.  See the License
 * for the specific language governing rights and limitations under the
 * License.
 *
 * Copyrights
 *
 * Portions created by or assigned to Jabber.com, Inc. are
 * Copyright (c) 1999-2000 Jabber.com, Inc.  All Rights Reserved.  Contact
 * information for Jabber.com, Inc. is available at http://www.jabber.com/.
 *
 * Portions Copyright (c) 1998-1999 Jeremie Miller.
 *
 * Acknowledgements
 *
 * Special thanks to the Jabber Open Source Contributors for their
 * suggestions and support of Jabber.
 *
 * --------------------------------------------------------------------------*/

#include "conference.h"

/*
 * ** public domain code by Jerry Coffin, with improvements by HenkJan Wolthuis.
 * ** Rewritten by David Sutton to fix into MU-Conference project
 *
*/

/*
** These are used in freeing a table.  Perhaps I should code up
** something a little less grungy, but it works, so what the heck.
*/

/* Initialize the htable to the size asked for.  Allocates space
** for the correct number of pointers and sets them to NULL.  If it
** can't allocate sufficient memory, signals error by setting the size
** of the table to 0.
*/

htable *htb_init_table(htable *table, size_t size)
{
    size_t i;
    bucket **temp;

    table->size = size;
    table->table = (bucket * *)malloc(sizeof(bucket *) * size);
    log_debug(NAME, "[%s] Malloc: bucket = %d", FZONE, sizeof(bucket *) * size);
    temp = table->table;

    /* malloc failed, return empty table */
    if ( temp == NULL )
    {
        log_debug(NAME, "[%s] Hash malloc failed", ZONE);
        table->size = 0;
        return table;
    }

    /* Initialise bucket ptrs to NULL */
    for (i = 0; i < size; i++)
        temp[i] = NULL;

    return table;
}

htable *htb_init_table_pool(pool p, htable *table, size_t size)
{
    size_t i;
    bucket **temp;

    table->size = size;
    table->table = (bucket * *)pmalloco(p, sizeof(bucket *) * size);
    temp = table->table;

    /* malloc failed, return empty table */
    if ( temp == NULL )
    {
        log_debug(NAME, "[%s] Hash malloc failed", ZONE);
        table->size = 0;
        return table;
    }

    /* Initialise bucket ptrs to NULL */
    for (i = 0; i < size; i++)
        temp[i] = NULL;

    return table;
}

static unsigned hash(const char *s)
{
    /* ELF hash uses unsigned chars and unsigned arithmetic for portability */
    const unsigned char *name = (const unsigned char *)s;
    unsigned long h = 0, g;

    while (*name)
    { /* do some fancy bitwanking on the string */
        h = (h << 4) + (unsigned long)(*name++);
        if ((g = (h & 0xF0000000UL))!=0)
            h ^= (g >> 24);
        h &= ~g;

    }

    return h;
}

/*
** Insert 'key' into hash table.
** Returns pointer to old data associated with the key, if any, or
** NULL if the key wasn't in the table previously.
*/

void *htb_put(htable *table, char *key, void *data)
{
    unsigned val;
    bucket *ptr;
      
    if (key == NULL)
    {
        log_debug(NAME, "[%s] Missing key", FZONE);
        return NULL;
    }

    val = hash(key) % table->size;

    /*
    ** NULL means this bucket hasn't been used yet.  We'll simply
    ** allocate space for our new bucket and put our data there, with
    ** the table pointing at it.
    */

    if ((table->table)[val] == NULL)
    {
        log_debug(NAME, "[%s] New Bucket %d assigned for %s", FZONE, val, key);

        (table->table)[val] = (bucket *)malloc(sizeof(bucket));

        if ((table->table)[val] == NULL)
        {
            log_debug(NAME, "[%s] Malloc failed creating bucket %d for %s", FZONE, val, key);
            return NULL;
        }

        (table->table)[val]->key = j_strdup(key);
        (table->table)[val]->next = NULL;
        (table->table)[val]->data = data;

        return (table->table)[val]->data;
    }

    /*
    ** This spot in the table is already in use.  See if the current string
    ** has already been inserted, and if so, increment its count.
    */

    for (ptr = (table->table)[val];NULL != ptr; ptr = ptr -> next)
    {
        if (j_strcmp(key, ptr->key) == 0)
        {
            void *old_data;
	    log_debug(NAME, "[%s] Existing key %s found, replacing data", FZONE, key);

            old_data = ptr->data;
            ptr->data = data;
            return old_data;
        }
    }

    /*
    ** This key must not be in the table yet.  We'll add it to the head of
    ** the list at this spot in the hash table.  Speed would be
    ** slightly improved if the list was kept sorted instead.  In this case,
    ** this code would be moved into the loop above, and the insertion would
    ** take place as soon as it was determined that the present key in the
    ** list was larger than this one.
    */

    log_debug(NAME, "[%s] Existing bucket %d found, adding new key %s", FZONE, val, key);
    ptr = (bucket *)malloc(sizeof(bucket));

    if (ptr == NULL)
    {
        log_debug(NAME, "Malloc failed: Old bucket %d, new key %s", FZONE, val, key);
        return 0;
    }

    ptr->key = j_strdup(key);
    ptr->data = data;
    ptr->next = (table->table)[val];
    (table->table)[val] = ptr;

    return data;
}


/*
** Look up a key and return the associated data.  Returns NULL if
** the key is not in the table.
*/

void *htb_get(htable *table, char *key)
{
      unsigned val = hash(key) % table->size;
      bucket *ptr;

      if ((table->table)[val] == NULL)
            return NULL;

      for ( ptr = (table->table)[val]; ptr != NULL; ptr = ptr->next )
      {
            if (strcmp(key, ptr->key ) == 0)
                  return ptr->data;
      }
      return NULL;
}

/*
** Delete a key from the hash table and return associated
** data, or NULL if not present.
*/

void *htb_zap(htable *table, const char *key)
{
      unsigned val = hash(key) % table->size;
      bucket *ptr, *last = NULL;

      log_debug(NAME, "[%s] Called to zap key %s", FZONE, key);

      if ((table->table)[val] == NULL)
            return NULL;

      /*
      ** Traverse the list, keeping track of the previous node in the list.
      ** When we find the node to delete, we set the previous node's next
      ** pointer to point to the node after ourself instead.  We then delete
      ** the key from the present node, and return a pointer to the data it
      ** contains.
      */

      for (last = NULL, ptr = (table->table)[val]; ptr != NULL; last = ptr, ptr = ptr->next)
      {
            if (strcmp(key, ptr->key) == 0)
            {
                  log_debug(NAME, "[%s] Found key %s", FZONE, key);

                  if (last != NULL )
                  {
                        log_debug(NAME, "[%s] Found key %s is not last", FZONE, key);

                        last->next = ptr->next;

			free(ptr->key);
                        free(ptr);

                        return NULL;
                  }

                  /*
                  ** If 'last' still equals NULL, it means that we need to
                  ** delete the first node in the list. This simply consists
                  ** of putting our own 'next' pointer in the array holding
                  ** the head of the list.  We then dispose of the current
                  ** node as above.
                  */

                  else
                  {
                        log_debug(NAME, "[%s] 1. Found key %s is last - %s", FZONE, key, ptr->next);

                        (table->table)[val] = ptr->next;
			free(ptr->key);
                        free(ptr);
			ptr = NULL;

                        return NULL;
                  }
            }
      }

      /*
       * Item Not Found
      */

      return NULL;
}

/*
 * Clean up node in the table
*/

/*
static void htb_free_node(const char *key, void *data, void *arg)
{
//      (void) data;
    htable *tcopy = (htable*)arg;

    log_debug(NAME, "[%s] Freeing key %s", FZONE, key);

    htb_zap(tcopy, key);

    log_debug(NAME, "[%s] Freed key", FZONE);
}
*/

/*
 * Destroy any existing data and clean up memory allocation
*/

void htb_free(htable *table)
{
      unsigned i;
      bucket *temp;

      for (i = 0; i < table->size; i++)
      {
            if ((table->table)[i] != NULL)
            {
	        log_debug(NAME, "[%s] Scanning %d", FZONE, i);
	        
                for (temp = (table->table)[i]; temp != NULL; temp = temp->next)
                {
		    log_debug(NAME, "[%s] Ping %d", FZONE, i);

		    if(temp->next == NULL)
		    {
		        log_debug(NAME, "[%s] Last in %s", FZONE, temp);
		        htb_zap(table, temp->key);
			break;
		    }
		    else
		    {
		        log_debug(NAME, "[%s] And on %s", FZONE, temp);
		        htb_zap(table, temp->key);
		    }
                }
            }
      }

      free(table->table);
      table->table = NULL;
      table->size = 0;

}

/*
 * Walk over every element in the hash, passing the results to the function
*/

void htb_walk(htable *table, ht_func func, void *arg)
{
      unsigned i;
      bucket *temp;

      for (i = 0; i < table->size; i++)
      {
            if ((table->table)[i] != NULL)
            {
	        log_debug(NAME, "[%s] Scanning %d", FZONE, i);
	        
                for (temp = (table->table)[i]; temp != NULL; temp = temp->next)
                {
		    log_debug(NAME, "[%s] Loop Interation...", FZONE);
                    (*func)(temp->key, temp->data, arg);
                }
            }
      }
}