hash.c

卡内基梅隆大学（CMU）开发的移动机器人控制开发软件包。可对多种机器人进行控制

 /*********************************************************
 *
 * This source code is part of the Carnegie Mellon Robot
 * Navigation Toolkit (CARMEN)
 *
 * CARMEN Copyright (c) 2002 Michael Montemerlo, Nicholas
 * Roy, Sebastian Thrun, Dirk Haehnel, Cyrill Stachniss,
 * and Jared Glover
 *
 * CARMEN 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; 
 * either version 2 of the License, or (at your option)
 * any later version.
 *
 * CARMEN 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 CARMEN; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place, 
 * Suite 330, Boston, MA  02111-1307 USA
 *
 ********************************************************/

#include <carmen/carmen.h>
#include <assert.h>
#include "hash.h"

struct cache *hash_new(unsigned int size, unsigned int (*hash_func)(), 
		       int (*compare_func)())
{
  struct cache *cache;
  assert(size);
  assert(!(size & (size - 1)));

  cache = (struct cache *) calloc(1, sizeof(struct cache));
  carmen_test_alloc(cache);

  cache->node_table = (struct cache_node **)
    calloc(size, sizeof(struct cache_node*));
  carmen_test_alloc(cache->node_table);

  cache->size = size;
  cache->mask = size - 1;
  cache->hash_func = hash_func;
  cache->compare_func = compare_func;
  
  return cache;
}


void hash_delete(struct cache *cache) 
{
  struct cache_node *node;
  
  while ((node = hash_next(cache, NULL)) != NULL) {
    hash_remove(cache, node->key);
  }
  free(cache->node_table);
  
  free(cache);
  
}

void hash_add(struct cache **cachep, void *key, void *value) 
{
  unsigned int indx; 
  struct cache_node *node; 
  struct cache_node *node1; 
  struct cache *new; 
#if 0
  struct cache *crap1;
  struct cache **crap2;
#endif

  indx = (*cachep)->hash_func(*cachep, key);
  node = (struct cache_node *) calloc(1, sizeof(struct cache_node));
  carmen_test_alloc(node);

  assert(node);
  node->key = key;
  node->value = value;
  node->next = (*cachep)->node_table[indx];
  (*cachep)->node_table[indx] = node;
  (*cachep)->used++;
  if ((((*cachep)->size * 75) / 100) <= (*cachep)->used) {
    node1 = NULL;
    new = hash_new((*cachep)->size * 2, (*cachep)->hash_func, 
		   (*cachep)->compare_func);
    while ((node1 = hash_next(*cachep, node1)) != NULL) {
      hash_add(&new, node1->key, node1->value);
    }
    hash_delete(*cachep);
    
    *cachep = new;
  }
  
}

void hash_remove(struct cache *cache, void *key) 
{
  unsigned int indx;
  struct cache_node *node;
  indx = cache->hash_func(cache, key);
  node = cache->node_table[indx];
  
  assert(node);

  if (cache->compare_func(node->key, key)) {
    cache->node_table[indx] = node->next;
    free(node);
  } else {

    struct cache_node *prev = node;
    char removed = 0;
    do {
      if (cache->compare_func(node->key, key)) {
	prev->next = node->next;
	removed = 1;
	free(node);
      } else {
	prev = node;
	node = node->next;
      }
    } while (!removed && (node != NULL));
    assert(removed);
  }
  cache->used--;
}

struct cache_node *hash_next(struct cache *cache, struct cache_node *node) 
{
  if (node == NULL) {
    cache->last_bucket = 0;
  }
  
  if (node != NULL) {
    if (node->next != NULL) {
      return node->next;
    } else {
      cache->last_bucket++;
      
    }
  }
  
  if (cache->last_bucket < cache->size) {
    while (cache->last_bucket < cache->size) {
      if (cache->node_table[cache->last_bucket] != NULL) {
	return cache->node_table[cache->last_bucket];
      } else {
	cache->last_bucket++;
      }
    }

    return 0;    
  } else
    return 0;
  
}

void *hash_value_for_key(struct cache *cache, void *key)
{
  struct cache_node *node; 
  void *retval;
  node = cache->node_table[cache->hash_func(cache, key)];
  retval = NULL;
  if (node != NULL) {
    do {
      
      if (cache->compare_func(node->key, key)) {
	retval = node->value;
      } else {
	node = node->next;
      }
      
      
    } while ((retval == NULL) && (node));
    
    
    
  } 
  
  return retval;
    
}



void *hash_change_key_value(struct cache *cache, void *key, void *new_value)
{
  struct cache_node *node;
  void *retval;
  node = cache->node_table[cache->hash_func(cache, key)];
  retval = NULL;
  if (node != NULL) {
    do {
      if (cache->compare_func(node->key, key)) {
	retval = node->value = new_value;
      } else 
	node = node->next;
    } while ((retval == NULL) && (node != NULL));
    

  }
  
  return retval;
}