_dp_hashing.c

数据类型和算法库LEDA 数据类型和算法库LEDA

    if ((tj<anf)||(tj>ende))     // gebe Speicher frei
    {
      delete tj;
      tj = 0;
      mj = 0;
    }
    return 1; 
  }

  if (mj<=4)                     // Headertable maximal vierelementig
  { 
    j=0;   
    while ( (tj[j].ke != EMPTY) && (j<mj) )
    { 
      (*wo)=tj[j];
      wo++;
      j++;
    }

    if ((tj<anf)||(tj>ende))     // gebe Speicher frei
    { 
      delete_vec tj;
      tj = 0;
      mj = 0;
    }
    return j; 
  }

				 // Headertable mit meheren Elementen
  bool weiter=true;
  int subsize=mal_pot2(sqr(mj),1);
  j=0;

  for (int k=0;(k<subsize)&&weiter;k++)  // suche Elemente
    if ( tj[k].ke != EMPTY  )
    {                                    // haenge Element an Liste
      (*wo)=tj[k];
      wo++; j++;
      if (j>=wj) weiter=false; 
    }
  if ((tj<anf)||(tj>ende))               // gebe Speicher frei
  { 
    delete_vec tj;
    tj = 0;
    mj = 0;
  }
  return j;
}

// ----------------------------------------------------------------
// member-functions of class dphash
// ----------------------------------------------------------------

// -------------------------------------------------------
// rehash_all
//
// stellt Headertables neu auf, um Platzverbrauch korrekt
// zu halten
// fuegt Element dann neu ein

stp dphash::rehash_all( GenPtr x=EMPTY , GenPtr y=0 )

{ 
  int i,i1,j,nsave,platz;
  unsigned dp_erg=0;

  stp erg=0;
  stp l=new subtable[n];         // Sammle Elemente in Liste l

  i=0;
  stp pos = l;
  nsave = ( x == EMPTY ? n : n-1 );

  while ( (i<sM) && (nsave>0) )  // Sammle Element aus allen Headertables
  { 
    if (htablep[i])
    {
      nsave -= htablep[i]->give_elements(pos,anf,ende) ;
      delete htablep[i];
    }
    i++;   
  }

  if ( x != EMPTY )               // fuege neues Element hinzu
    l[n-1].set_s(x,y);

  free ((char*)htablep);          // Speicher freigeben
  if (anf) 
    delete_vec anf; 
					    // neue Parameter setzen

  M=int((1+_dp_h_c)*n);
  sM = int(((4.0/3.0)*wursechs)*(1+_dp_h_c)*n);

                    			  // Speicher allokieren
  htablep=(htp*) calloc(sM,sizeof(htp));  // schneller als new+init
  int* buckets=new int[n];

  if (!htablep)
    error_handler(1,"memory overflow");

  platz=n;
  i1=0;
  while (!i1)                    // Top-Funktion suchen
  { 
    bed=0;
    k=random(1,maxprim-1);
    for (i=0;i<n;i++)           // Hashe alle Elemente
    {
      GenPtr help=l[i].ke;
      dpmod(k,help,dp_erg);
      dp_erg=dp_erg%sM;
      buckets[i] = dp_erg;      // Merke Headertable

      if (!htablep[dp_erg]) 
        htablep[dp_erg] = new headertable;

                                // Aendere Headertables
      int f=++(htablep[dp_erg]->wj);
      int* groesse=&(htablep[dp_erg]->mj);

      if (f<=2)
	 (*groesse)++;
      else
        if (*groesse<f)
        { 
	  (*groesse)<<=1;      
  
	  if (*groesse==4)       // vergroessere Feld
	    platz++;
          else
	    if (*groesse==8)     // Uebergang von Feld auf Tafel
	      platz+=123;
            else
	      platz+=3*sqr(*groesse)/2; 
        }
	else                     // Tafel nicht vergroessert
	  platz--;

      bed+=mal_pot2(f,2)-2; 
    }                            // alle Elemente gehasht

                                 // bed-=(((8.0*sqr(M))/sM)+2*M);
    float _bed=(wursechs+2)*M;   // Vereinfachung durch Einsetzen von sM
    bed-=int(_bed);
    i1=(bed<0);                  // kontrolliere Platz

    if (!i1)                     // nicht erfolgreich, saeubere Headertables
    {
      platz=n;
      for (j=0; j<sM; j++)
        if (htablep[j]) 
	{ 
	  delete htablep[j];
	  htablep[j] = 0 ;   
	}
    }

  }                              // Top-Funktion gefunden


  anf=new subtable[platz];        // allokiere Speicher fuer alle Subtables
  wo=anf;
  ende=anf+platz-1;

  for (i=0; i<n; i++)             // fuege Elemente wieder ein
  { 
    int bucket=buckets[i];  
    htablep[bucket]->dinsert(l[i].ke,l[i].inf,ende,wo,erg);
  }

  delete buckets;
  delete_vec l;
  return erg;
}

// --------------------------------------------------------
// insert
//
// fuegt Element in die entsprechende Headertable ein

stp dphash::insert(GenPtr x,GenPtr y)

{ 
  if ( (unsigned)x>maxuni )  
    error_handler(2,string("key %d out of range",x));

  copy_key(x);
  copy_inf(y);

  unsigned dp_erg=0;
  dpmod(k,x,dp_erg);
  dp_erg=dp_erg%sM;                   // Toptafel

  bool rehash = false;
  stp  erg    = 0;

  if ( !htablep[dp_erg] ) 
    htablep[dp_erg] = new headertable;

  if ( htablep[dp_erg]->insert(x,y,erg,bed,rehash,anf,ende) )  n++;

  if ( rehash )  erg=rehash_all(x,y);

  return erg;
}

// --------------------------------------------------------
// del
//
// loescht Element aus entsprechender Headertable

void dphash::del(GenPtr x)

{ 

  if ( (unsigned)x>maxuni )  
    error_handler(2,string("key %d out of range",x));

// s.n. :

stp p = lookup(x);
if (p==0) return;
clear_key(p->ke);
clear_inf(p->inf);


  unsigned dp_erg=0;
  dpmod(k,x,dp_erg);
  dp_erg=dp_erg%sM;                   // Toptafel

  if ( !htablep[dp_erg] ) return;     // Headertable nicht vorhanden
  				      // in Toptafel loeschen

  if ( htablep[dp_erg]->del(x,anf,ende) ) n--;     

  if ( !htablep[dp_erg]->wj )
  { 
    delete htablep[dp_erg];
    htablep[dp_erg] = 0;
  }

  if ((n*(1+3*_dp_h_c)<M) && (n>3))
    rehash_all(); 

} 

// -------------------------------------------------------
// member,lookup,change_inf
//
// suchen in Headertable nach Element mit Schluessel
// change_inf setzt Information des Elementes auf y

int dphash::member(GenPtr x)

{ 
  if ( (unsigned)x>maxuni )  
    error_handler(2,string("key %d out of range",x));

  unsigned dp_erg=0;
  dpmod(k,x,dp_erg);
  dp_erg=dp_erg%sM;                   // Toptafel

  if (!htablep[dp_erg])
    return 0;                         // Headertable nicht vorhanden

  return ( htablep[dp_erg]->lookup(x) ? 1 : 0 ); 

}

stp dphash::lookup(GenPtr x)                 // wie member

{ 
  if ( (unsigned)x>maxuni )  
    error_handler(2,string("key %d out of range",x));

  unsigned dp_erg=0;
  dpmod(k,x,dp_erg);
  dp_erg=dp_erg%sM;                   // Toptafel

  if (!htablep[dp_erg]) 
    return 0;

  stp y=htablep[dp_erg]->lookup(x);
  return y ;

}
 
stp dphash::change_inf(GenPtr x,GenPtr y)       // wie member

{ 
  if ( (unsigned)x>maxuni )  
    error_handler(2,string("key %d out of range",x));

  unsigned dp_erg=0;
  dpmod(k,x,dp_erg);
  dp_erg=dp_erg%sM;                   // Toptafel


  if (!htablep[dp_erg])
    return 0;

  stp t = htablep[dp_erg]->lookup(x) ;
  if (t)
    t->inf = y ;
  return t;

}

// -------------------------------------------------------
// clear
//
// loescht alle Elemente und
// setzt Hashing auf Leerzustand

void dphash::clear()

{ 
  stp l = new subtable[n];
  stp pos=l;

  for (int i=0;i<sM;i++)           // Headertables loeschen
    if (htablep[i])
    { 
      htablep[i]->give_elements(pos,anf,ende);
      delete htablep[i];                         
    }

  free ((char*)htablep) ;          // Speicher freigeben

  if (anf) 
    delete_vec anf;

  delete_vec l;

  n = 0;                           // Leerinitialisierung
  M=4;
  sM=13;
  k=random(1,maxprim-1);
  bed=-17;
  htablep=(htp*) calloc(sM,sizeof(htp));
  anf = wo = ende = 0;

}

// ------------------------------------------------------------
// Konstruktoren und Destruktor

dphash::dphash()

{ 
  n=0;
  M=4;
  sM=13;
  k=random(1,maxprim-1);
  bed=-17;
  htablep=(htp*) calloc(sM,sizeof(htp));
  anf = wo = ende = 0;

}

dphash::dphash(int an,GenPtr* keys,GenPtr* inhalte)   
                                          // wie rehash_all
                                          // die Elemente stehen aber schon in Listen
{ 
  int i,i1,j,nsave,platz;
  unsigned dp_erg=0;
  stp erg=0;

  n=an;
  M=int((1+_dp_h_c)*n);
  sM = int(((4.0/3.0)*wursechs)*(1+_dp_h_c)*n);

  htablep=(htp*) calloc(sM,sizeof(htp));
  int* buckets = new int[n];

  if (!htablep)
    error_handler(1,"memory overflow");

  platz=n;
  i1=0;

  while (!i1)
  {
    bed=0;
    k=random(1,maxprim-1);

    for (i=0;i<n;i++)
    {
      GenPtr help=keys[i];
      if ( (unsigned)help>maxuni )  
         error_handler(2,string("key %d out of range",help));

      dpmod(k,help,dp_erg);
      dp_erg=dp_erg%sM;
      buckets[i] = dp_erg;

      if (!htablep[dp_erg]) 
	htablep[dp_erg] = new headertable;

      int f=++(htablep[dp_erg]->wj);
      int* groesse=&(htablep[dp_erg]->mj);

      if (f<=2)
	 (*groesse)++;
      else
        if (*groesse<f)
        { 
	  (*groesse)<<=1;      
  
	  if (*groesse==4)       // vergroessere Feld
	    platz++;
          else
	    if (*groesse==8)     // Uebergang von Feld auf Tafel
	      platz+=123;
            else
	      platz+=3*sqr(*groesse)/2; 
        }
	else                     // Tafel nicht vergroessert
	  platz--;

      bed+=mal_pot2(f,2)-2; 
    }
	
                                 // bed-=(((8.0*sqr(M))/sM)+2*M);
    float _bed=(wursechs+2)*M;   // Vereinfachung durch Einsetzen von sM
    bed-=int(_bed);
    i1=(bed<0);

    if (!i1)
    { 
      platz=n;
      for (j=0; j<sM; j++)
	if (htablep[j]) 
	{ 
	  delete htablep[j];
	  htablep[j] = 0;   
	}
    }
  }

  nsave=an;
  anf=new subtable[platz];

  wo=anf;
  ende=wo+platz-1;
  n=0;

  for (i=0; i<nsave; i++)
  {
    int bucket = buckets[i];
    n += (htablep[bucket]->dinsert(keys[i],inhalte[i],ende,wo,erg));
  } 

  delete buckets;

  if ((n*(1+3*_dp_h_c)<M) && (n>3))
    rehash_all();   

}

dphash::~dphash()
{ 
  clear();                            // loesche alles

  free ((char*)htablep);              // gebe Speicher frei
  if (anf) delete_vec anf;

  n=M=sM=0;
  k=0;
  anf=wo=ende=0;
  htablep=0;

}