_dp_hashing.c

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

      delete_vec lj;

    wj=5;                          
    rehash=false;
    return true;           
  }                             // Tafel enthaelt jetzt 5 Elemente

                                // Tafel mit >= 5 Elementen
				// injektives Hashing auf Bucket

  int subsize=mal_pot2(sqr(mj),1);
  dpmod(kj,a,dp_erg);
  dp_erg=dp_erg%subsize;

  if ( tj[dp_erg].ke == a)         // gleiches Element
  { 
    tj[dp_erg].set_s(a,b);
    erg=tj+dp_erg;
    rehash=false;
    return false;      
  }

  int oldscard=wj;
  int subcard=(++wj);
  bed+=mal_pot2(subcard,2)-2;

  if ( tj[dp_erg].ke == EMPTY  )    // Position leer -> einfuegen
  { 
    tj[dp_erg].set_s(a,b);
    erg=tj+dp_erg;
    rehash = false;
    return true; 
  }
  else                         // Tafelelement besetzt             
   
    if (subcard<=mj)           // aber noch Platz in Tafel
    {  
      stp lj = new subtable[subcard];
      int i1=0;
                               // Elemente in Liste kopieren
      for (int i2=0; i1<oldscard  ; i2++ )
      {
	if ( tj[i2].ke != EMPTY  )
        {
          lj[i1++]=tj[i2];  
          tj[i2].clear(); 
        }
      }
      lj[i1].set_s(a,b);
                                 // lokales Rehash , alle Elemente in Liste lj

      int injektiv=0;
      while (!injektiv)          // injektive Funktion suchen
      { 
	injektiv=1;
        kj=random(1,maxprim-1);

        for (i1=0; (i1<subcard) && injektiv ; i1++)
        { 
          dpmod(kj,lj[i1].ke,dp_erg);
          dp_erg=dp_erg%subsize;
          if ( tj[dp_erg].ke == EMPTY )
          {
            tj[dp_erg]=lj[i1]; 
	    erg=tj+dp_erg;
          }
          else
          {
	    injektiv=0;                // Injektivitaet verletzt
            for (int g=0;g<i1;g++)     // belegte Positionen loeschen
            {
	      GenPtr help=lj[g].ke;
	      dpmod(kj,help,dp_erg);
              dp_erg=dp_erg%subsize;  
              tj[dp_erg].ke = EMPTY ; 
       	    }
          }
        }                       // Elemente getestet

      }                         // naechster Versuch oder fertig

      delete_vec lj;
      rehash = false;
      return true; 
    }                             // subcard<=mj

    else                          // |Wj|>Mj , d.h. Groesse der
                  	          // Subtable verdoppeln
    { 
      if (bed>=0)                 // Kontrolle des Platzverbrauchs
      {
        rehash = true;
        return true;    
      }
      else                        // Platz in Ordnung             
                                  // Untertafel verdoppeln
      { 
        int oldssize= mal_pot2(sqr(mj),1);
        int i1=0;
                                  // Elemente in Liste retten
        stp lj = new subtable[subcard]; 
        for (int i2=0; i1<oldscard ; i2++)
          if ( tj[i2].ke != EMPTY  )
            lj[i1++]=tj[i2];
        lj[i1].set_s(a,b);

        for ( ; mj<wj ; mj<<=1 ) ;    // Subtable vergroessern
        subsize = mal_pot2(sqr(mj),1); 

        if ((tj>ende)||(tj<anf))      // Speicherverwaltung
          delete_vec tj;

        tj=new subtable[subsize]; 
        int injektiv=0;
                                      // injektive Funktion suchen
        while (!injektiv)       
        {
          injektiv=1;
          kj=random(1,maxprim-1);
          for (i1=0; (i1<subcard) && injektiv ; i1++)
          {
            dpmod(kj,lj[i1].ke,dp_erg);
            dp_erg=dp_erg%subsize;
            if ( tj[dp_erg].ke == EMPTY )
            { 
              tj[dp_erg]=lj[i1]; 
              erg=tj+dp_erg;
            }

             else                       // Injektivitaet verletzt
             {
	       injektiv=0;
               for (int g=0;g<i1;g++)   // Subtables saeubern
               {
		 GenPtr help=lj[g].ke;
		 dpmod(kj,help,dp_erg);
                 dp_erg=dp_erg%subsize;
		 tj[dp_erg].ke = EMPTY ; 
	       }

	     }
          }                             // alle Elemente getestet

        }                               // naechster Versuch oder fertig

    	delete_vec lj;
  	rehash = false;
	return true;
      }
    }
  }                       // insert
   
//-----------------------------------------------------------------
// dinsert
// fuegt ein Paar (Schluessel,Information) in das Bucket ein
// benutzt Informationen aus Konstruktor oder Rehash_all
// gibt true zurueck, falls erfolgreich


int headertable::dinsert(GenPtr a,GenPtr b,
			  stp ende,stp& wo,stp& erg)

{
  if (mj==1)                    // nur ein Element in Tafel 
  {				// und Tafel anlegen  
    tj=wo;
    wo++; 
    tj->set_s(a,b);    
    erg=tj;
    return true;  
  }                             // leere Tafel jetzt mit Element

  if (mj==2)                    // zwei Elemente in Tafel 
  {
    if (!tj)       		// und Tafel anlegen
    { 
      wj=1;
      tj=wo;
      wo+=2; 
      tj[0].set_s(a,b);    
      erg=tj;
      return true;  
    }                           // leere Tafel jetzt mit Element
    else
    { 
      if (a==tj[0].ke)
      {
	tj[0].inf = b;
	erg = tj;
	return false;
      }
      wj=2;
      tj[1].set_s(a,b);
      erg=tj+1;
      return true;
    }
  }

  if (mj<=4)                    // max 4 Elemente in Tafel 
  {
    if (!tj)       		// und Tafel anlegen
    { 
      wj=1;
      tj=wo;
      wo+=4; 
      tj[0].set_s(a,b);    
      erg=tj;
      return true;  
    }                           // leere Tafel jetzt mit Element
    else
    { 
      for (int i1=0; i1<wj; i1++)
        if (a==tj[i1].ke)
        {
	  tj[i1].inf = b;
	  erg = tj+i1;
	  return false;
        }

      tj[wj].set_s(a,b);
      erg=tj+wj;
      wj++;
      return true;
    }
  }



  if (!tj)                      // Tafel muss angelegt werden
				// Tafel mit meheren Elementen
				// erstes Element kommt hinein
  { 
    int q=mal_pot2(sqr(mj),1);  // Platz anfordern aus Pool
    tj=wo;
    wo+=q; 
    if (wo>ende+1)
      error_handler(1,"memory allocation error");

    kj=random(1,maxprim-1);     // erstes Element einfuegen
    unsigned dp_erg=0;
    dpmod(kj,a,dp_erg);
    dp_erg=dp_erg%q;
    tj[dp_erg].set_s(a,b);
    erg=tj+dp_erg;
    wj = 1;                     // jetzt aktuelles wj
    return true;       
  }                             // leere Tafel jetzt mit 1.Element

                                // Tafel ist schon angelegt und enthaelt Element
                                // Tafel bekommt mindestens 5 Elemente
  unsigned dp_erg=0;
  int subsize=mal_pot2(sqr(mj),1);
  dpmod(kj,a,dp_erg);
  dp_erg=dp_erg%subsize;

  if ( tj[dp_erg].ke == a)           // gleicher Schluessel
  { 
    tj[dp_erg].set_s(a,b);
    erg=tj+dp_erg;
    return false;      
  }

  if ( tj[dp_erg].ke == EMPTY  )     // Position leer
  { tj[dp_erg].set_s(a,b);   
    erg=tj+dp_erg;
  }

  else                          // Position besetzt -> lokales Rehash 
  {  
				// Elemente sammeln
     stp lj = new subtable[wj+1];
     int i1=0;
     int i2=0;
     for (i2=0; i1<wj ; i2++)   // Elemente in Liste kopieren
     { if ( tj[i2].ke != EMPTY  )
       { lj[i1++]=tj[i2];  
         tj[i2].clear() ; 
       }
     }

     lj[i1++].set_s(a,b);         // i1 = wj+1

                                  // lokales Rehash , alle Elemente in Liste lj
     int injektiv=0;
                                  // injektive Funktion suchen
     while (!injektiv)         
     {
       injektiv=1;
       kj=random(1,maxprim-1);

       for (i2=0; (i2<i1) && injektiv ; i2++)
       { 
         dpmod(kj,lj[i2].ke,dp_erg);
	 dp_erg=dp_erg%subsize;
         if ( tj[dp_erg].ke == EMPTY )
	 {
	   tj[dp_erg]=lj[i2]; 
	   erg=tj+dp_erg;
         }
         else                      // Injektivitaet verletzt
         {
	   injektiv=0;
           for (int g=0;g<i2;g++)  // Subtables saeubern
           {
	     GenPtr help=lj[g].ke;
             unsigned dp_erg=0;
	     dpmod(kj,help,dp_erg);
             dp_erg=dp_erg%subsize;
             tj[dp_erg].ke = EMPTY ;
	   }
         }
       }                           // alle Elemente getestet 

     }                             // neuer Versuch oder fertig

     delete_vec lj;
  }

  wj++;                           // aktuelle Anzahl updaten
  return true;

}


// ----------------------------------------------------------------
// lookup
// sucht nach Eintrag mit Schluessel a
// gibt Pointer auf Eintrag zurueck, falls gefunden
// 0 sonst

stp headertable::lookup(GenPtr a)

{ 
   if (!wj)  return 0;              // Headertable leer

   if (mj==1)                       // Headertable einelementig
   { 
     if (a==tj->ke) 
       return tj;
     else
       return 0;
   }

   if (mj<=4)                       // Tafel mit max 4 Elementen
   { 
     for (int i1=0; i1<wj; i1++)
       if (a==tj[i1].ke) 
         return tj+i1;
     return 0;
   }
                                    // Headertable mit mehr als 4 Subtables
   unsigned dp_erg=0;
   dpmod(kj,a,dp_erg);
   dp_erg=dp_erg%(mal_pot2(sqr(mj),1));   // Position

   if (tj[dp_erg].ke==a)
     return tj+dp_erg;
   else
     return 0; 
 } 

// ----------------------------------------------------------------
// del
// loescht Element in Tafel
// gibt true zurueck, wenn erfolgreich

bool headertable::del(GenPtr a,stp anf,stp ende)

{
  if (!wj) return false;             // leere Headertable

  if (mj==1)                         // Headertable einelementig
  { 
    if (a==tj->ke) 
    {
      wj=0;                          // Schluessel gefunden
      tj->clear() ;
      if ((tj<anf)||(tj>ende))
      {
	delete tj;
	tj = 0;
	mj = 0;
      } 
      return true;    
    }
    else
      return false;
  }
	 
  if (mj<=4)           
  { 
    if (wj>1)                        // Headertable mit mind 2 Elementen
    {
      for (int i1=0; i1<wj; i1++)
      { 
	if (tj[i1].ke==a)            // Element gefunden
        { 
          wj--;
          tj[i1]=tj[wj];             // Loch fuellen
          tj[wj].clear();
          return true;
        }
      }
      return false;
    }
    else                               // ein Element in Bucket
    {
      if (tj[0].ke==a) 
      {
	wj=0;                          // Schluessel gefunden
        tj[0].clear() ;
        if ((tj<anf)||(tj>ende))
        {
	  delete_vec tj;
	  tj = 0;
	  mj = 0;
        } 
        return true;    
      }
      else
        return false;
    }
  }
	 
				      // Headertable mit mehreren Subtables
  unsigned dp_erg=0;
  dpmod(kj,a,dp_erg);
  dp_erg=dp_erg%(mal_pot2(sqr(mj),1));   // Position

  if (tj[dp_erg].ke==a)
  {
    wj--;                             // Schluessel gefunden
    tj[dp_erg].clear() ;

    if (wj==0)                        // Bucket nun leer
      if ((tj<anf)||(tj>ende))
      {
	delete_vec tj;
	tj = 0;
	mj = 0;
      } 
    return true;    
  } 
  else return false;
}

// ---------------------------------------------------------
// give_elements()
// haengt Elemente der Tafel an Liste an
// gibt Anzahl der Elemente zurueck


int headertable::give_elements(stp& wo,stp anf,stp ende)

{ 
  int j=0;

  if (!wj) { 
	     if ( tj && ((tj<anf)||(tj>ende))) 
             {
	       if (mj>1)
                 delete_vec tj;
	       else 
                 delete tj;

	       tj = 0;
	       mj = 0;
             }
	     return 0;
	   }

  if (mj==1)                    // Headertable einelementig
  { 
    (*wo)=(*tj);                // Element kopieren
    wo++;