Power-Programmierung/CD2.mdf/c/library/dos/diverses/leda/src/basic/_ch_hash.c

C/C++ Source or Header | 1991-11-15 | 10.1 KB | 360 lines

/*******************************************************************************
+
+  LEDA  2.1.1                                                 11-15-1991
+
+
+  _ch_hashing.c
+
+
+  Copyright (c) 1991  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 6600 Saarbruecken, FRG
+  All rights reserved.
+
*******************************************************************************/



#include <LEDA/ch_hashing.h>

//----------------------------------------------------------------------
// hashing mit verkettung
// Walter Zimmer
// Literatur : Kurt Mehlhorn : "Datenstrukturen und eff. Algorithmen "
// modifiziert von Stefan Naeher (Mai 1989)
//----------------------------------------------------------------------


//----------------------------------------------------------------------
// gibt zeiger auf wbook_el mit key x zurueck ; falls x nicht im
// wbook => return 0
//----------------------------------------------------------------------

ch_hashing_el* ch_hashing::lookup(ent x) const
{
  TRACE(( " lookup : key = %d \n",int(x) ));

  hash_list* L = *(get_list(x)) ;
  list_item p = ( L ? get_list_el(x,L) : 0);
                             //  L == 0  oder  x nicht in L  =>  p = 0

  if ( p )  return (*L)[p];
  else return 0;                    //falls x nicht in ch_hashing => return 0
}


hash_list_ptr* ch_hashing::get_list(ent x) const
{ return &( hash_table[(*f)(x) & divisor]);}

//----------------------------------------------------------------------
// get_List_el(x,L) : gibt zeiger auf Listenelement mit key x
//                     zurueck , falls x in Liste L , sonst return 0
//----------------------------------------------------------------------

list_item ch_hashing::get_list_el(ent x, hash_list* L) const
{
  TRACE(( " get_list_el(x) : x = %d",int(x) ));

  list_item p ;

  // nicht forall_listitems benutzen , da dieses makro die
  // iteratoren der liste veraendert , die wbook aber selber
  // fuer die eigenen makros benoetigt

 for (  p = L->first();  p ; p = L->succ(p) )
   if ( cmp((*L)[p]->k,x) == 0 ) return p;

 return 0;  // falls element x nicht in l => return 0
}

//----------------------------------------------------------------------
// del(x) : streicht element mit key x aus ch_hashing und gibt zeiger
//          auf das gestrichene element zurueck ;
//          falls kein element mit key x im baum => error
//----------------------------------------------------------------------

ch_hashing_el* ch_hashing::del(ent x)
{
  TRACE(( " del : key = %d \n",int(x) ));

  --counter;

  hash_list* L = *( get_list(x) );
  list_item p = ( L ? get_list_el(x,L) : 0 );
                // falls L == 0  oder x nicht in L  =>   p = 0

  if ( p )   return (L->del(p) );
  return 0;
}

//----------------------------------------------------------------------
// insert(x,y) : fuegt neues element mit key x und entry y in ch_hashing ein
// und gibt zeiger auf das eingefuegte element zurueck
// bem : mehrere elemente mit gleichem key moeglich
//----------------------------------------------------------------------

ch_hashing_el* ch_hashing::insert(ent x, ent y)
{
   TRACE(( " insert : key = %d \n",int(x) ));

   ++ counter ;

   hash_list_ptr* L =  get_list(x);
   hash_list_ptr l = *L;

   copy_key(x);
   copy_inf(y);

   if ( l )         // falls l != 0 => liste existiert schon
       l->push( new ch_hashing_el(x,y) );
   else             //  falls l == 0 => liste muss erst angelegt werden
   {
     // neue liste anlegen und den zeiger an der stelle (*L) in die
     // hash_table eintragen

   (*L) = new hash_list(new ch_hashing_el(x,y));
   }

   return  (*L)->head() ;     // nicht l->head() !!!
}
//----------------------------------------------------------------------
// print(): ausgabe des wbooks ( nur zu testzwecken ) fuer int
//----------------------------------------------------------------------

void ch_hashing::print() const
{
  TRACE(( " print  \n"));

  cout << " size = " << size() << "\n";
  cout << " table_size = " << table_size << "\n";

  hash_list_ptr* p;
  for (  p = &hash_table[table_size-1]; p >= &hash_table[0]                              ; p-- )
     if ( *p )     // falls an dieser stelle liste existiert
     {
       ch_hashing_el* x ;
       forall(x,(*(*p)) )
       {
         print_key(x->k);
         cout << " ";
       }
       cout << "\n";
     }
}


void ch_hashing::init_iterator()
{ if (iterator!=0) (*iterator)->init_iterator();
  iterator = 0;
}

//----------------------------------------------------------------------
// move_iterator() : setzt iterator auf das naechste element und
// gibt zeiger auf dieses zurueck ( fuer macros )
//----------------------------------------------------------------------

ch_hashing_el* ch_hashing::move_iterator()
{
  TRACE(( " move_iterator \n" ));

  ch_hashing_el* p;

  if (!iterator)                // iterator am anfang oder wbook leer
  {
    if ( empty() ) return 0;    // falls wbook leer => return 0
    else                        // sonst existiert nichtleere liste
    {
      // suche nach der ersten nichtleeren liste ;
      // beginne bei hash_table[tablesize-1]

      for ( iterator = &hash_table[ table_size-1 ];                                         ( (*iterator) == 0  || (*iterator)->empty() ); --iterator )
    ;
    }
  }
  else
    if ( !( (*iterator)->next_element(p) ) )
       // falls next_element(p) 0 zurueckgibt => am ende einer liste
       //  =>  naechste nichtleere liste suchen
    {
      do
      {
     if ( iterator == &hash_table[0] )
           {  iterator = 0 ; return 0; }
     else   -- iterator;
      }
      while (  !(*iterator) ||  (*iterator)->empty()   );

      // falls noch nichtleere liste existiert


    }
    else return p;  // noch nicht am ende der aktuellen liste

 // am anfang einer nichtleeren liste => init_iter + next_el(p)

 (*iterator)->init_iterator();
 (*iterator)->next_element(p);
  return p;
}
//----------------------------------------------------------------------
//   remove() : gibt speicherplatz der hash_table wieder frei , d.h.
//   benutzer muss neue table_size und hashfct angeben , falls er ch_hashing
//   nochmal benutzen will
//----------------------------------------------------------------------

void ch_hashing::remove()
{
  TRACE(( " remove \n"));

  clear();
  delete[table_size] hash_table; //  ??? listen loeschen ???
  hash_table = 0;
  table_size = divisor = 0;
  f = 0;
}

//----------------------------------------------------------------------
//   clear() : speicherplatz der hash_table bleibt erhalten , doch
//   werden alle elemente geloescht ;
//   table_size , divisor , cmp , und hash_fct bleiben erhalten
//----------------------------------------------------------------------

void ch_hashing::clear()
{
  TRACE(( " clear \n"));

  for (int i = table_size-1 ; i >= 0 ; --i)
     if ( hash_table[i] )    // falls liste existiert => inhalt loeschen
     {  while (! hash_table[i]->empty())
        { ch_hashing_el* p = hash_table[i]->pop();
          clear_key(p->k);
          clear_inf(p->e);
          delete p;
         }
        delete ( hash_table[i] );
        hash_table[i] = 0;
     }
  counter = 0;
  iterator = 0;
}

//----------------------------------------------------------------------
// (1) : neuen speicherplatz  anlegen und mit 0 initialisieren
// (2) : inhalt des wbooks in neu angelegten  speicherplatz uebertragen
//       mit neuer tablesize und neuer hash_fct ;
// (3) : altes wbook durch remove loeschen
// (4) : neues besetzen der members
//----------------------------------------------------------------------

void ch_hashing::new_size_or_fct(int Table_size,hash_fct F)
{
   TRACE(( " new_size_or_fct \n"));


   Table_size = round(Table_size);
   int Divisor = Table_size -1;
   int Counter = counter;

// (1)

   hash_list_ptr* Hash_table = new hash_list_ptr[Table_size];
   for ( int i=Table_size-1 ; i >= 0 ; --i ) Hash_table[i] = 0;

// (2)

   ch_hashing_el* p;
   forall_in_ch_hashing( p , (*this) )
   {
     hash_list_ptr* L = & ( Hash_table [ F(p->k) & Divisor ] );

     if ( *L )
       (*L)->push( new ch_hashing_el(p) );
     else   //  falls *L == 0  =>  liste muss erst angelegt werden
      (*L) = new hash_list( new ch_hashing_el(p));
   }


// (3)

   remove();

// (4)

   f = F;
   counter = Counter;
   hash_table = Hash_table;
   table_size = Table_size;
   divisor = Divisor;
   // iterator durch remove() auf 0 gesetzt
}
//----------------------------------------------------------------------

ch_hashing::ch_hashing(int Table_size,hash_fct F)
     // auf Vax genuegt int fuer table_size
{
      TRACE(( " ch_hashing-konstruktor \n"));

  table_size = round(Table_size);
  divisor = table_size-1;
  f = F;
  hash_table = new hash_list_ptr[table_size];
  for ( register int i = table_size-1; i >= 0 ; --i )
      hash_table[i] = 0;
  counter = 0;
  iterator = 0;
}

ch_hashing::ch_hashing()
{
  table_size = round(default_hash_tablesize);
  divisor = table_size-1;
  f = default_hash_fct;
  hash_table = new hash_list_ptr[table_size];
  for ( register int i = table_size-1; i >= 0 ; --i )
      hash_table[i] = 0;
  counter = 0;
  iterator = 0;
}

ch_hashing::ch_hashing(int Table_size)
{
  table_size = round(Table_size);
  divisor = table_size-1;
  f = default_hash_fct;
  hash_table = new hash_list_ptr[table_size];
  for ( register int i = table_size-1; i >= 0 ; --i )
      hash_table[i] = 0;
  counter = 0;
  iterator = 0;
}

ch_hashing::ch_hashing(hash_fct F)
{
  table_size = round(default_hash_tablesize);
  divisor = table_size-1;
  f = F;
  hash_table = new hash_list_ptr[table_size];
  for ( register int i = table_size-1; i >= 0 ; --i )
      hash_table[i] = 0;
  counter = 0;
  iterator = 0;
}

//----------------------------------------------------------------------
// runded auf die naechste zweierpotenz auf
//----------------------------------------------------------------------

int ch_hashing::round(int a) const
{
  TRACE(( "round\n"));

  for (int  b = 1 ; a > 0 ; a >>= 1)   b <<= 1;
  return b-1;
}


int default_hash_fct(ent& x) { return int(x); }

//----------------------------------------------------------------------
// end of hash.c
//----------------------------------------------------------------------