static int insert(hashmap* map, void* data, char* key)
{
    hashmapEntry* entry;
    
    if (map->size == map->count)
        rehash(map);
    
    do
    {
        entry = find(map, key);
        
        if (entry)
        {
            entry->data = data;
            
            if (entry->key)
            {
                /* updated the entry */
                free(key);
                return HASHMAP_UPDATE;
            }
            else
            {
                /* inserted the entry */
                ++map->count;
                entry->key = key;
                return HASHMAP_INSERT;
            }
        }
        
        rehash(map);
    }
    while (1);
}

    /**
     * Insert an element if no other equivalent element is registered.
     * @param elem the element to be inserted.
     * @return reference to the element in the table.
     */
    T& add(T const& elem) {
        assert(!(elem == T()));
        if (tableSize_ == 0) rehash();
        size_t i;

        while (1) {
            i = hashFunc(elem) % tableSize_;

            while (!(table[i] == T())) {
                if (eqFunc(table[i], elem)) return table[i];
                ++collisions_;
                ++i;
                if (i >= tableSize_) i = 0;
            }

            if (size_ < maxSize_) break;

            /* Rehash only when new element is inserted. */
            rehash(size_ * 2);
        }

        ++size_;
        table[i] = elem;
        return table[i];
    }

	bool insert(const K& key, const V& val) {
		if (n_elements + 1 >= next_rehash)
			rehash();

		size_t i = hash_func(key) % buckets;
		HashBucket *b = &data[i];

		while (b->size == BUCKET_SIZE) {
			rehash();

			i = hash_func(key) % buckets;
			b = &data[i];
		}

		size_t e = 0;
		for (; e < b->size; e++) {
			if (b->data[e].key == key)
				return false;
		}
		b->data[e].key = key;
		b->data[e].val = val;
		b->size++;

		n_elements++;
		return true;
	}

/* Insert an element into the hash table pH.  The key is pKey,nKey
** and the data is "data".
**
** If no element exists with a matching key, then a new
** element is created.  A copy of the key is made if the copyKey
** flag is set.  NULL is returned.
**
** If another element already exists with the same key, then the
** new data replaces the old data and the old data is returned.
** The key is not copied in this instance.  If a malloc fails, then
** the new data is returned and the hash table is unchanged.
**
** If the "data" parameter to this function is NULL, then the
** element corresponding to "key" is removed from the hash table.
*/
void *sqlite3HashInsert(Hash *pH, const void *pKey, int nKey, void *data){
  int hraw;             /* Raw hash value of the key */
  int h;                /* the hash of the key modulo hash table size */
  HashElem *elem;       /* Used to loop thru the element list */
  HashElem *new_elem;   /* New element added to the pH */

  assert( pH!=0 );
  hraw = strHash(pKey, nKey);
  if( pH->htsize ){
    h = hraw % pH->htsize;
    elem = findElementGivenHash(pH,pKey,nKey,h);
    if( elem ){
      void *old_data = elem->data;
      if( data==0 ){
        removeElementGivenHash(pH,elem,h);
      }else{
        elem->data = data;
        if( !pH->copyKey ){
          elem->pKey = (void *)pKey;
        }
        assert(nKey==elem->nKey);
      }
      return old_data;
    }
  }
  if( data==0 ) return 0;
  new_elem = (HashElem*)sqlite3Malloc( sizeof(HashElem) );
  if( new_elem==0 ) return data;
  if( pH->copyKey && pKey!=0 ){
    new_elem->pKey = sqlite3Malloc( nKey );
    if( new_elem->pKey==0 ){
      sqlite3_free(new_elem);
      return data;
    }
    memcpy((void*)new_elem->pKey, pKey, nKey);
  }else{
    new_elem->pKey = (void*)pKey;
  }
  new_elem->nKey = nKey;
  pH->count++;
  if( pH->htsize==0 ){
    rehash(pH, 128/sizeof(pH->ht[0]));
    if( pH->htsize==0 ){
      pH->count = 0;
      if( pH->copyKey ){
        sqlite3_free(new_elem->pKey);
      }
      sqlite3_free(new_elem);
      return data;
    }
  }
  if( pH->count > pH->htsize ){
    rehash(pH,pH->htsize*2);
  }
  assert( pH->htsize>0 );
  h = hraw % pH->htsize;
  insertElement(pH, &pH->ht[h], new_elem);
  new_elem->data = data;
  return 0;
}

/* Insert an element into the hash table pH.  The key is pKey,nKey
** and the data is "data".
**
** If no element exists with a matching key, then a new
** element is created.  A copy of the key is made if the copyKey
** flag is set.  NULL is returned.
**
** If another element already exists with the same key, then the
** new data replaces the old data and the old data is returned.
** The key is not copied in this instance.  If a malloc fails, then
** the new data is returned and the hash table is unchanged.
**
** If the "data" parameter to this function is NULL, then the
** element corresponding to "key" is removed from the hash table.
*/
void * HashInsert(
  Hash *pH,        /* The hash table to insert into */
  const void *pKey,    /* The key */
  int nKey,            /* Number of bytes in the key */
  void *data           /* The data */
){
  int hraw;                 /* Raw hash value of the key */
  int h;                    /* the hash of the key modulo hash table size */
  HashElem *elem;       /* Used to loop thru the element list */
  HashElem *new_elem;   /* New element added to the pH */
  
  assert( pH!=0 );
  hraw = binHash(pKey, nKey);
  assert( (pH->htsize & (pH->htsize-1))==0 );
  h = hraw & (pH->htsize-1);
  elem = findElementGivenHash(pH,pKey,nKey,h);
  if( elem ){
    void *old_data = elem->data;
    if( data==0 ){
      removeElementGivenHash(pH,elem,h);
    }else{
      elem->data = data;
    }
    return old_data;
  }
  if( data==0 ) return 0;
  new_elem = (HashElem*)pH->xMalloc( sizeof(HashElem) );
  if( new_elem==0 ) return data;
  if( pH->copyKey && pKey!=0 ){
    new_elem->pKey = pH->xMalloc( nKey );
    if( new_elem->pKey==0 ){
      pH->xFree(new_elem);
      return data;
    }
    memcpy((void*)new_elem->pKey, pKey, nKey);
  }else{
    new_elem->pKey = (void*)pKey;
  }
  new_elem->nKey = nKey;
  pH->count++;
  if( pH->htsize==0 ){
    rehash(pH,8);
    if( pH->htsize==0 ){
      pH->count = 0;
      pH->xFree(new_elem);
      return data;
    }
  }
  if( pH->count > pH->htsize ){
    rehash(pH,pH->htsize*2);
  }
  assert( pH->htsize>0 );
  assert( (pH->htsize & (pH->htsize-1))==0 );
  h = hraw & (pH->htsize-1);
  insertElement(pH, &pH->ht[h], new_elem);
  new_elem->data = data;
  return 0;
}

void remove_ip_leases(main_server_st* s, struct proc_st* proc)
{
	if (proc->ipv4) {
		htable_del(&s->ip_leases.ht, rehash(proc->ipv4, NULL), proc->ipv4);
		free(proc->ipv4);
		proc->ipv4 = NULL;
	}
	if (proc->ipv6) {
		htable_del(&s->ip_leases.ht, rehash(proc->ipv6, NULL), proc->ipv6);
		free(proc->ipv6);
		proc->ipv6 = NULL;
	}
}

int hm_set ( hashmap_t *hm, char *key, void *value )
{
    int hashed;
    int count = 0;
    int rtn;
    bucket_t *b_ptr;
    entry_t *e_ptr;

    if ( ( hm->size + 1 ) >= THRESHOLD ( hm->capacity ) )
        rehash ( hm );

    hashed = hashstr ( hm, key );

    if ( hm->buckets[ hashed ] == NULL )
    {
        /* No bucket. */

        b_ptr = malloc ( sizeof ( bucket_t ) );
        e_ptr = b_ptr->entries;
    }
    else if ( b_ptr != NULL )
    {
        /* Bucket exists. */
        if ( b_ptr->numentries >= BUCKETTHOLD )
            rehash ( hm );

        for ( ; ( e_ptr = b_ptr->entries->next ) != NULL ; ) {
            if ( strcmp ( e_ptr->key, key ) != 0 )
                return 1;
        }
        e_ptr = e_ptr->next;
    }

    e_ptr = calloc ( 1, sizeof ( entry_t ) );
    if ( e_ptr == NULL )
        return 2;

    e_ptr->key = calloc ( strlen( key ) + 1, sizeof( char * ) );
    if ( e_ptr->key == NULL )
        return 3;

    strncpy( e_ptr->key, key, strlen( key ) );
    e_ptr->value = value;

    b_ptr->numentries++;
    b_ptr->entries =  e_ptr;
    hm->buckets[ hashed ] = b_ptr;
    hm->size++;
    
}

static void
mono_g_hash_table_insert_replace (MonoGHashTable *hash, gpointer key, gpointer value, gboolean replace)
{
	guint hashcode;
	Slot *s;
	GEqualFunc equal;
	
	g_return_if_fail (hash != NULL);

	equal = hash->key_equal_func;
	if (hash->in_use >= hash->threshold)
		rehash (hash);

	hashcode = ((*hash->hash_func) (key)) % hash->table_size;
	for (s = hash->table [hashcode]; s != NULL; s = s->next){
		if ((*equal) (s->key, key)){
			if (replace){
				if (hash->key_destroy_func != NULL)
					(*hash->key_destroy_func)(s->key);
				s->key = key;
			}
			if (hash->value_destroy_func != NULL)
				(*hash->value_destroy_func) (s->value);
			s->value = value;
			return;
		}
	}
	s = new_slot (hash);
	s->key = key;
	s->value = value;
	s->next = hash->table [hashcode];
	hash->table [hashcode] = s;
	hash->in_use++;
}

bool Hash2KeysSetOf<THasher>::putIfNotPresent(const void* key1, int key2)
{
    // First see if the key exists already
    XMLSize_t hashVal;
    Hash2KeysSetBucketElem* newBucket = findBucketElem(key1, key2, hashVal);

    //
    //  If so,then update its value. If not, then we need to add it to
    //  the right bucket
    //
    if (newBucket)
        return false;

    // Apply 4 load factor to find threshold.
    XMLSize_t threshold = fHashModulus * 4;

    // If we've grown too big, expand the table and rehash.
    if (fCount >= threshold)
        rehash();

    if(fAvailable==0)
        newBucket = (Hash2KeysSetBucketElem*)fMemoryManager->allocate(sizeof(Hash2KeysSetBucketElem));
    else
    {
        newBucket = fAvailable;
        fAvailable = fAvailable->fNext;
    }
    newBucket->fKey1 = key1;
    newBucket->fKey2 = key2;
    newBucket->fNext = fBucketList[hashVal];
    fBucketList[hashVal] = newBucket;
    fCount++;
    return true;
}

int
st_find_or_add(st_table *table, char *key, char ***slot)
{
    int hash_val;
    st_table_entry *newEntry, *ptr, **last;

    hash_val = do_hash(key, table);

    FIND_ENTRY(table, hash_val, key, ptr, last);

    if (ptr == NULL) {
	if (table->num_entries / table->num_bins >= table->max_density) {
	    if (rehash(table) == ST_OUT_OF_MEM) {
		return ST_OUT_OF_MEM;
	    }
	    hash_val = do_hash(key, table);
	}
	newEntry = ABC_ALLOC(st_table_entry, 1);
	if (newEntry == NULL) {
	    return ST_OUT_OF_MEM;
	}
	newEntry->key = key;
	newEntry->record = (char *) 0;
	newEntry->next = table->bins[hash_val];
	table->bins[hash_val] = newEntry;
	table->num_entries++;
	if (slot != NULL) *slot = &newEntry->record;
	return 0;
    } else {
	if (slot != NULL) *slot = &ptr->record;
	return 1;
    }
}

// You may assume that no duplicate PuzzleState is ever added.
void ResizeChainHashDict::add(PuzzleState *key, PuzzleState *pred) {

  // Rehash if adding one more element pushes load factor over 1/2
  if (2*(number+1) > size) rehash();  // DO NOT CHANGE THIS LINE

  // TODO:  Your code goes here...
  string kID = key->getUniqId(); 
  int h = hash(kID);

  ChainNode * node = new ChainNode();
  node->key = key;
  node->keyID = kID;
  node->data = pred;
  node->next = NULL;
  
 if(table[h] == NULL) { 
   table[h] = node; 
 }  
 else {
   node->next = table[h];
   table[h] = node;
 }
 
 number++;
 return;
}

const void *
h_put(HASHSET h, const void *key)
{
	uint_t hash = h->h_hash(key);
	uint_t indx = hash % h->h_tableSize;
	ENTRY *e;

	for (e = h->h_table[indx]; e; e = e->e_next)
		if (e->e_hash == hash && h->h_equal(e->e_key, key))
			return (key);

	if (h->h_count >= h->h_threshold) {
		rehash(h);

		indx = hash % h->h_tableSize;
	}

	e = exmalloc(sizeof (ENTRY));
	e->e_hash = hash;
	e->e_key = (void *) key;
	e->e_next = h->h_table[indx];

	h->h_table[indx] = e;
	h->h_count++;

	return (NULL);
}

int
st_insert(st_table *table, const char *key, char *value)
{
    int hash_val;
    st_table_entry *newEntry;
    st_table_entry *ptr, **last;

    hash_val = do_hash(key, table);

    FIND_ENTRY(table, hash_val, key, ptr, last);

    if (ptr == NULL) {
	if (table->num_entries/table->num_bins >= table->max_density) {
	    if (rehash(table) == ST_OUT_OF_MEM) {
		return ST_OUT_OF_MEM;
	    }
	    hash_val = do_hash(key, table);
	}
	newEntry = ABC_ALLOC(st_table_entry, 1);
	if (newEntry == NULL) {
	    return ST_OUT_OF_MEM;
	}
	newEntry->key = (char *)key;
	newEntry->record = value;
	newEntry->next = table->bins[hash_val];
	table->bins[hash_val] = newEntry;
	table->num_entries++;
	return 0;
    } else {
	ptr->record = value;
	return 1;
    }
}

/*
 * Half the size of the array in hashtable.
 * Relocate the hashtable elements from old array to the shrunk array
 * by calling rehash(...).
 */
static
int
shrink(struct hashtable* h)
{
    struct list** old_array = h->vals;
    unsigned int old_arraysize = h->arraysize;
    unsigned int new_arraysize = old_arraysize / 2;

    /* Allocate a new array half the size. */
    struct list** new_array
        = (struct list**)malloc(new_arraysize * sizeof(struct list*));
    if (new_array == NULL) {
        return ENOMEM;         
    }
    /* Allocate lists for the new array. */
    int err = init_array_with_lists(new_array, 0, new_arraysize);
    if (err == ENOMEM) {
        return ENOMEM;
    }

    /* replace old array with new array in hash table. */
    h->vals = new_array;
    h->size = 0;
    h->arraysize = new_arraysize;

    /* relocate all items from old array to new array */
    rehash(h, old_array, old_arraysize);
    
    /* cleanup list objects in old array and free old array. */
    cleanup_array_with_lists(old_array, 0, old_arraysize);
    free(old_array);

    return 0;
}

/*
** Remove hash entry from table return entry if removed
** return NULL if not removed
** NOTE: hash_remove() differs from hash_erase() in that
**       it returns entry (not the template) and does
**       *not* call the free() callback.
*/
void *
hash_remove(Hash *h, void *tmpl)
{
    HashValue hval = h->fun.hash(tmpl);
    int ix = hval % h->size;
    HashBucket *b = h->bucket[ix];
    HashBucket *prev = NULL;
	
    while (b) {
	if ((b->hvalue == hval) && (h->fun.cmp(tmpl, (void*)b) == 0)) {
	    if (prev)
		prev->next = b->next;
	    else
		h->bucket[ix] = b->next;
	    if (h->bucket[ix] == NULL)
		h->used--;
	    if (h->used < h->size20percent)  /* rehash at 20% */
		rehash(h, 0);
	    return (void *) b;
	}
	prev = b;
	b = b->next;
    }
    return NULL;
}

static INLINE
PAIR *createPair(CRDS *crds, PCODE pcode, CODE left, CODE right, uint f_pos)
{
  PAIR *pair = (PAIR *)malloc(sizeof(PAIR));
  uint h;
  PAIR *q;
  PQUE *p_que = crds->p_que[pcode];

  pair->pcode  = pcode;
  pair->left   = left;
  pair->right  = right;
  pair->freq   = 1;
  pair->f_pos  = pair->b_pos  = f_pos;
  pair->p_prev = pair->p_next = NULL;

  p_que->num_pairs++;

  if (p_que->num_pairs >= primes[p_que->h_num]) {
    rehash(crds, pcode);
  }

  h = hash_val(p_que->h_num, left, right);
  q = p_que->h_entry[h];
  p_que->h_entry[h] = pair;
  pair->h_next = q;

  insertPair(crds, pair);

  return pair;
}

//ハッシュ表の探索
//find: KEY -> DATA
DATA *find(KEY key){
    //ハッシュ値を求める
    int h, count;
    KEY k;

    h = hash(key);
    count = 0;

    //空白になるまでKEYの照合をする
    while((k = table[h].key) != EMPTY){
        //削除済みではなく、KEYが等しい場合
        if (k != EMPTY && keyequal(k, key)){
            printf("データの探索key: %d, data: %d\n", k, table[h].data);
            return &table[h].data;
        }
        //見つからずに、バケット数以上を探索した場合
        if (++count > BUCKET_SIZE){
            printf("データの追加をしたが、追加する余地が存在しなかった\n");
            return NULL;
        }
        //再ハッシュ
        h = rehash(h);
    }
    return NULL;
} 

 // Insert a new entry into the map.
 std::pair<iterator, bool> insert(const value_type& v)
 {
   if (size_ + 1 >= num_buckets_)
     rehash(hash_size(size_ + 1));
   size_t bucket = calculate_hash_value(v.first) % num_buckets_;
   iterator it = buckets_[bucket].first;
   if (it == values_.end())
   {
     buckets_[bucket].first = buckets_[bucket].last =
       values_insert(values_.end(), v);
     ++size_;
     return std::pair<iterator, bool>(buckets_[bucket].last, true);
   }
   iterator end = buckets_[bucket].last;
   ++end;
   while (it != end)
   {
     if (it->first == v.first)
       return std::pair<iterator, bool>(it, false);
     ++it;
   }
   buckets_[bucket].last = values_insert(end, v);
   ++size_;
   return std::pair<iterator, bool>(buckets_[bucket].last, true);
 }

void RefHashTableOf<TVal, THasher>::put(void* key, TVal* const valueToAdopt)
{
    // Apply 0.75 load factor to find threshold.
    XMLSize_t threshold = fHashModulus * 3 / 4;

    // If we've grown too big, expand the table and rehash.
    if (fCount >= threshold)
        rehash();

    // First see if the key exists already
    XMLSize_t hashVal;
    RefHashTableBucketElem<TVal>* newBucket = findBucketElem(key, hashVal);

    //
    //  If so,then update its value. If not, then we need to add it to
    //  the right bucket
    //
    if (newBucket)
    {
        if (fAdoptedElems)
            delete newBucket->fData;
        newBucket->fData = valueToAdopt;
        newBucket->fKey = key;
    }
    else
    {
        newBucket =
             new (fMemoryManager->allocate(sizeof(RefHashTableBucketElem<TVal>)))
             RefHashTableBucketElem<TVal>(key, valueToAdopt, fBucketList[hashVal]);
        fBucketList[hashVal] = newBucket;
        fCount++;
    }
}

extern sd_hash_iter_t* sd_hash_lookadd(sd_hash_t* a_this, const void* a_key)
{
    int			h;
    sd_hash_iter_t*	p;

    if (a_this == 0 || a_key == 0)			return 0;
    if ((p = sd_hash_lookup(a_this, a_key)) != 0)	return p;
    if ((p = sd_calloc(1, sizeof(*p))) == 0)		return 0;

    if (a_this->ops->key_dup != 0)
        p->key = a_this->ops->key_dup(a_key);
    else
        p->key = (void*) a_key;

    p->hash					= a_this;
    p->__hkey					= a_this->ops->hash(a_key);

    if (a_this->nelem > SD_HASH_FULLTAB * a_this->size) rehash(a_this);

    h						= hindex(p->__hkey,
                                     a_this->size);
    p->__next					= a_this->tab[h];
    a_this->tab[h]				= p;
    if (p->__next != 0) p->__next->__prev	= p;

    a_this->nelem++;

    return p;
}