/*
* lftp - file transfer program
*
* Copyright (c) 1996-2016 by Alexander V. Lukyanov (lav@yars.free.net)
*
* 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; either version 3 of the License, or
* (at your option) any later version.
*
* 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, see .
*/
#include
#include
#include "xmap.h"
#include
void _xmap::new_map()
{
map.get_space(hash_size,1);
map.set_length(hash_size);
for(int i=0; ikey.eq(key))
return ep;
ep=&e->next;
e=*ep;
}
return ep;
}
_xmap::entry *_xmap::_lookup_c(const xstring& key) const
{
for(entry *e=map[make_hash(key)]; e; e=e->next) {
if(e->key.eq(key))
return e;
}
return 0;
}
void _xmap::rebuild_map()
{
static const int primes[]={
17,67,257,1031,4099,16411,65537,262147,1048583,4194319,16777259,
67108879,268435459,1073741827
};
hash_size=entry_count*2;
// a prime is better, find it.
for(unsigned pi=0; pi old_map;
old_map.move_here(map);
new_map();
for(int i=0; inext;
int hash=make_hash(e->key);
e->next=map[hash];
map[hash]=e;
e=next;
}
}
}
_xmap::entry *_xmap::_add(const xstring& key)
{
entry **ep=_lookup(key);
if(*ep==0) {
entry *n=(entry*)xmalloc(sizeof(entry)+value_size);
memset(n,0,sizeof(entry)+value_size);
n->next=0;
n->key.set(key);
*ep=n;
entry_count++;
if(entry_count>hash_size*2)
rebuild_map();
return n;
}
return *ep;
}
void _xmap::_remove(entry **ep)
{
if(!ep || !*ep)
return;
entry *e=*ep;
e->key.unset();
*ep=e->next;
xfree(e);
entry_count--;
}
_xmap::entry *_xmap::_each_begin()
{
each_entry=0;
each_hash=-1;
return _each_next();
}
_xmap::entry *_xmap::_each_next()
{
while(each_hashnext;
return e;
}
each_entry=map[++each_hash];
}
last_entry=0;
return 0;
}
void _xmap::_move_here(_xmap &o)
{
value_size=o.value_size;
hash_size=o.hash_size;
entry_count=o.entry_count;
map.move_here(o.map);
o.hash_size=1;
o.entry_count=0;
o.new_map();
}