📄 _dp_hashing.c
字号:
/*******************************************************************************
+
+ LEDA 3.0
+
+
+ _dp_hashing.c
+
+
+ Copyright (c) 1992 by Max-Planck-Institut fuer Informatik
+ Im Stadtwald, 6600 Saarbruecken, FRG
+ All rights reserved.
+
*******************************************************************************/
// Implementierung der Member-Funktionen
// von Dynamic Perfect Hashing nach [DKMMRT]
//
// Fopra / Diplomarbeit
// Michael Wenzel ( 1989/90 )
//
//---------------------------------------------------------------
#include <LEDA/impl/dp_hashing.h>
#if defined(__MSDOS__) || __GNUG__ == 1
#define delete_vec delete[0]
#else
#define delete_vec delete[]
#endif
// ----------------------------------------------------------------
// allgemeine Funktionen und Konstanten
// ----------------------------------------------------------------
// Universum [1..dp_exp_31-1]
// 2-er Potenzen, Shift Operationen sparen
#define dp_exp_31 2147483648
#define dp_exp_30 1073741824
#define dp_exp_29 536870912
#define dp_exp_28 268435456
#define dp_exp_27 134217728
#define dp_exp_26 67108864
#define dp_exp_25 33554432
// Konstante fuer Groesse beim Rehashing
#define _dp_h_c 1
// allgmeine Quadrat- und Multiplikationsfunktion fuer 2-er Potenz
#define sqr(x) ((x)*(x))
#define mal_pot2(x,y) ((x)<<(y))
// Berechnung von (k*x)%p
// fuer p=2^31+11 ( kleinste Primzahl > 2^31 )
#define DPMOD_BODY(k,x,dp_erg)\
{ unsigned dp_k1=k>>16;\
unsigned dp_k2=k&65535;\
unsigned dp_x1=(unsigned(x))>>16;\
unsigned dp_x2=(unsigned(x))&65535;\
unsigned dp_e1=dp_k1*dp_x1+((dp_k1*dp_x2+dp_k2*dp_x1)>>16);\
unsigned dp_e2=dp_k2*dp_x2;\
unsigned dp_e3=((dp_k1*dp_x2+dp_k2*dp_x1)&65535)<<16;\
unsigned dp_e5=dp_e2+dp_e3;\
if ((dp_e2&dp_exp_31)&&(dp_e3&dp_exp_31))\
dp_e1++;\
else if (((dp_e2&dp_exp_31)||(dp_e3&dp_exp_31))&&(!(dp_e5&dp_exp_31)))\
dp_e1++; \
long dp_f=(dp_e5&0x7fffffff)-22*(dp_e1&0x03ffffff);\
if (dp_e1&dp_exp_26)\
if(dp_f<1476394997)\
dp_f+=671088651;\
else dp_f-=1476395008;\
if (dp_e1&dp_exp_27)\
if(dp_f<805306346)\
dp_f+=1342177302;\
else dp_f-=805306357;\
if (dp_e1&dp_exp_28)\
if(dp_f<1610612703)\
dp_f+=536870945;\
else dp_f-=1610612714;\
if (dp_e1&dp_exp_29)\
if(dp_f<1073741758)\
dp_f+=1073741890;\
else dp_f-=1073741769;\
if (dp_e1&dp_exp_30)\
if(dp_f<2147483527)\
dp_f+=121;\
else dp_f-=2147483538;\
if (dp_e5&dp_exp_31)\
if (dp_f<0)\
dp_f+=2147483648;\
else dp_f-=11;\
if (dp_f<0)\
dp_erg=unsigned(dp_f+2147483659);\
else dp_erg=unsigned(dp_f);\
}
#ifdef __TURBOC__
/* Function "dpmod" */
static void dpmod(unsigned k, GenPtr x, unsigned& dp_erg) DPMOD_BODY(k,x,dp_erg)
#else
/* Macro "dpmod" */
#define dpmod(k,x,dp_erg) DPMOD_BODY(k,x,dp_erg)
#endif
// ----------------------------------------------------------------
// member-functions of class headertable
// ----------------------------------------------------------------
//-----------------------------------------------------------------
// insert
// fuegt ein Paar (Schluessel,Information) in das Bucket ein
// berechnet Informationen neu
// returns true, falls Element eingefuegt
bool headertable::insert(GenPtr a,GenPtr b,stp& erg,int& bed,bool& rehash,
stp anf,stp ende)
{
unsigned dp_erg=0;
if (!wj) // leere Headertable
{
wj=1;
if (!tj)
{
mj=1;
tj=new subtable(a,b); // einfach einfuegen
erg=tj;
}
else // Tafel war angelegt
{
if (mj==1) // nur einelementig
{
tj->set_s(a,b);
erg=tj;
}
else // groessere Tafel
if (mj<=4) // nur 2 oder 4-elementig
{
tj[0].set_s(a,b);
erg=tj;
}
else
{
dpmod(kj,a,dp_erg);
dp_erg=dp_erg%mal_pot2(sqr(mj),1);
tj[dp_erg].set_s(a,b);
erg=tj+dp_erg;
}
}
bed+=2;
rehash=false;
return true;
} // leere Tafel jetzt mit Element
if (wj==1) // Tafel mit einem Element
{
if (mj==1)
{
if (a==tj->ke) // gleiches Element
{
tj->inf=b;
erg=tj;
rehash=false;
return false;
}
else
{
wj=2; // Einfuegen
bed+=6;
if (bed>=0) // Platz genug?
{
rehash=true;
return true;
}
mj=2; // Speicher anfordern
// und Elemente verteilen
stp lj=tj;
tj=new subtable[2];
tj[0] = (*lj);
tj[1].set_s(a,b);
erg = tj+1;
if ((lj>ende)||(lj<anf))
delete lj;
}
rehash = false;
return true;
}
if (mj<=4)
{
if (a==tj[0].ke) // gleiches Element
{
tj[0].inf=b;
erg=tj;
rehash=false;
return false;
}
else
{
wj = 2;
bed+=6;
tj[1].set_s(a,b);
erg = tj+1;
rehash=false;
return true;
}
}
else // groessere Tafel
{
dpmod(kj,a,dp_erg);
dp_erg=dp_erg%mal_pot2(sqr(mj),1);
if (a==tj[dp_erg].ke) // gleiches Element
{
tj[dp_erg].inf = b;
erg=tj+dp_erg;
rehash=false;
return false;
}
wj=2;
bed+=6;
if ( tj[dp_erg].ke == EMPTY ) // Position leer
{
tj[dp_erg].set_s(a,b);
erg=tj+dp_erg;
rehash=false;
return true;
}
else // lokales Rehash
{
stp lj = new subtable(tj[dp_erg]);
tj[dp_erg].clear();
int subsize = mal_pot2(sqr(mj),1);
int injektiv=0;
// injektive Funktion suchen
while (!injektiv)
{ injektiv=1;
kj=random(1,maxprim-1);
unsigned dp_erg=0;
dpmod(kj,lj->ke,dp_erg);
dp_erg=dp_erg%subsize;
tj[dp_erg]=(*lj);
dpmod(kj,a,dp_erg);
dp_erg=dp_erg%subsize;
if ( tj[dp_erg].ke == EMPTY )
{
tj[dp_erg].set_s(a,b);
erg=tj+dp_erg;
}
else
{
tj[dp_erg].clear();
injektiv=0;
}
} // Elemente injektiv verteilt
delete lj;
rehash=false;
return true;
}
}
} // Tafel enthaelt jetzt 2 Elemente
if (wj<4) // Tafel mit 2 oder 3 Elementen
{
for (int i1=0; i1<wj ; i1++)
if (a==tj[i1].ke) // gleiches Element
{
tj[i1].inf=b;
erg=tj+i1;
rehash=false;
return false;
}
// neues Element
if (wj==2)
bed+=10;
else
bed+=14;
if (mj==2)
{
if (bed>=0) // Platz genug?
{
rehash=true;
return true;
}
mj=4; // Speicher anfordern
stp lj=tj;
tj=new subtable[4];
for (int i1=0; i1<wj ; i1++)
tj[i1] = lj[i1];
tj[i1].set_s(a,b);
erg = tj+wj;
if ((lj>ende)||(lj<anf))
delete_vec lj;
wj++;
rehash = false;
return true;
}
if (mj==4)
{
tj[wj].set_s(a,b);
erg = tj+wj;
wj++;
rehash=false;
return true;
}
else // groessere Tafel
{
dpmod(kj,a,dp_erg);
dp_erg=dp_erg%mal_pot2(sqr(mj),1);
if ( tj[dp_erg].ke == EMPTY ) // Position leer
{
tj[dp_erg].set_s(a,b);
erg=tj+dp_erg;
wj++;
rehash=false;
return true;
}
else // lokales Rehash
{
stp lj = new subtable[++wj];
int i1=0;
// Elemente in Liste kopieren
for (int i2=0; i1<wj-1 ; i2++ )
{
if ( tj[i2].ke != EMPTY )
{
lj[i1++]=tj[i2];
tj[i2].clear();
}
}
lj[i1].set_s(a,b);
int subsize = mal_pot2(sqr(mj),1);
int injektiv=0; // injektive Funktion suchen
while (!injektiv)
{ injektiv=1;
kj=random(1,maxprim-1);
for (i1=0; (i1<wj) && 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];
else
{
injektiv=0;
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 injektiv verteilt
}
delete_vec lj;
rehash=false;
return true;
} // lokales Rehash beendet
}
} // Tafel enthaelt jetzt 2 oder 3 Elemente
if (wj==4) // Tafel mit 4 Elementen
{
for (int i1=0; i1<4; i1++)
if (a==tj[i1].ke) // gleiches Element
{
tj[i1].inf=b;
erg=tj+i1;
rehash=false;
return false;
}
// neues Element einfuegen
bed+=18;
if (bed>=0) // Platz genug?
{
rehash=true;
return true;
}
mj=8; // Speicher anfordern
// und Elemente verteilen
stp lj=tj;
tj=new subtable[128];
int injektiv=0;
// injektive Funktion suchen
while (!injektiv)
{
injektiv=1;
kj=random(1,maxprim-1);
for (int i1=0; (i1<4) && injektiv ; i1++)
{
dpmod(kj,lj[i1].ke,dp_erg);
dp_erg=dp_erg%128;
if ( tj[dp_erg].ke == EMPTY )
tj[dp_erg]=lj[i1];
else
{
injektiv=0;
for (int g=0;g<i1;g++) // belegte Positionen loeschen
{
GenPtr help=lj[g].ke;
dpmod(kj,help,dp_erg);
dp_erg=dp_erg%128;
tj[dp_erg].ke = EMPTY ;
}
}
}
if (injektiv) // letztes Element hashen
{
dpmod(kj,a,dp_erg);
dp_erg=dp_erg%128;
if ( tj[dp_erg].ke == EMPTY )
{
tj[dp_erg].set_s(a,b);
erg=tj+dp_erg;
}
else
{
injektiv=0;
for (int g=0;g<i1;g++) // belegte Positionen loeschen
{
GenPtr help=lj[g].ke;
dpmod(kj,help,dp_erg);
dp_erg=dp_erg%128;
tj[dp_erg].clear() ;
}
} // letztes Element
}
} // Elemente injektiv verteilt
if ((lj>ende)||(lj<anf))
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -