/*

 * 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 <http://www.gnu.org/licenses/>.

 */

#include <config.h>

#include <assert.h>

#include "xmap.h"

#include <stdio.h>

void _xmap::new_map()

{

   map.get_space(hash_size,1);

   map.set_length(hash_size);

   for(int i=0; i

      map[i]=0;

}

_xmap::_xmap(int vs)

   : value_size(vs)

{

   entry_count=0;

   hash_size=1;

   new_map();

}

void _xmap::_empty()

{

   for(int i=0; i

      while(map[i])

	 _remove(&map[i]);

   }

   assert(entry_count==0);

}

_xmap::~_xmap()

{

   _empty();

}

int _xmap::make_hash(const xstring& s) const

{

   if(hash_size==1)

      return 0;

   unsigned hash=0x12345678;

   for(unsigned i=0; i

      hash+=(hash<<5)+s[i];

   }

   hash+=(hash<<5)+s.length();

   hash%=hash_size;

   return hash;

}

_xmap::entry **_xmap::_lookup(const xstring& key)

{

   int hash=make_hash(key);

   entry **ep=&map[hash];

   entry *e=*ep;

   while(e) {

      if(e->key.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

      if(hash_size

	 hash_size=primes[pi];

	 break;

      }

   }

   xarray_p<_xmap::entry> old_map;

   old_map.move_here(map);

   new_map();

   for(int i=0; i

      entry *e=old_map[i];

      old_map[i]=0;

      while(e) {

	 entry *next=e->next;

	 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_hash

      entry *e=each_entry;

      if(e) {

	 last_entry=e;

	 each_entry=e->next;

	 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();

}