开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数值算法/人工智能 > 查看源码
_dp_hash.c
资源名称：leda.tar.gz　[点击查看]
上传用户：gzelex
上传日期：2007-01-07
资源大小：707k
文件大小：31k
源码类别：

数值算法/人工智能

开发平台：

MultiPlatform

_dp_hash.c：源码内容
  2. //------------------------------------------------------------------------------
  3. // Dynamic Perfect Hashing  [DKMMRT]
  4. //
  5. // Michael Wenzel           ( 1990/91 ) 
  6. //
  7. //------------------------------------------------------------------------------
  10. #include <LEDA/impl/dp_hash.h>
  13. // ----------------------------------------------------------------
  14. // random source
  15. // ----------------------------------------------------------------
  17. random_source ran(1,maxprim-1);
  20. // ----------------------------------------------------------------
  21. // allgemeine Funktionen und Konstanten
  22. // ----------------------------------------------------------------
  25. // Universum [1..dp_exp_31-1]
  26. // 2-er Potenzen, Shift Operationen sparen
  27. #define dp_exp_31 2147483648
  28. #define dp_exp_30 1073741824
  29. #define dp_exp_29 536870912 
  30. #define dp_exp_28 268435456 
  31. #define dp_exp_27 134217728 
  32. #define dp_exp_26 67108864 
  33. #define dp_exp_25 33554432 
  36. // Konstante fuer Groesse beim Rehashing 
  37. #define _dp_h_c 1
  39. // allgmeine Quadrat- und Multiplikationsfunktion fuer 2-er Potenz
  40. #define sqr(x) ((x)*(x))                  
  41. #define mal_pot2(x,y) ((x)<<(y))
  43. // Berechnung von (k*x)%p
  44. // fuer p=2^31+11  ( kleinste Primzahl > 2^31 )
  47. #define DPMOD_BODY(k,x,dp_erg)
  48. { unsigned long dp_k1=k>>16;
  49.   unsigned long dp_k2=k&65535;
  50.   unsigned long dp_x1=(unsigned long)x >> 16;
  51.   unsigned long dp_x2=(unsigned long)x & 65535;
  52.   unsigned long dp_e1=dp_k1*dp_x1+((dp_k1*dp_x2+dp_k2*dp_x1)>>16);
  53.   unsigned long dp_e2=dp_k2*dp_x2;
  54.   unsigned long dp_e3=((dp_k1*dp_x2+dp_k2*dp_x1)&65535)<<16;
  55.   unsigned long dp_e5=dp_e2+dp_e3;
  56.   if ((dp_e2&dp_exp_31)&&(dp_e3&dp_exp_31))
  57.     dp_e1++;
  58.   else if (((dp_e2&dp_exp_31)||(dp_e3&dp_exp_31))&&(!(dp_e5&dp_exp_31)))
  59.  dp_e1++; 
  60.   long dp_f=(dp_e5&0x7fffffff)-22*(dp_e1&0x03ffffff);
  61.   if (dp_e1&dp_exp_26)
  62.     if(dp_f<1476394997)
  63.       dp_f+=671088651;
  64.     else dp_f-=1476395008;
  65.   if (dp_e1&dp_exp_27)
  66.     if(dp_f<805306346)
  67.       dp_f+=1342177302;
  68.     else dp_f-=805306357;
  69.   if (dp_e1&dp_exp_28)
  70.     if(dp_f<1610612703)
  71.       dp_f+=536870945;
  72.     else dp_f-=1610612714;
  73.   if (dp_e1&dp_exp_29)
  74.     if(dp_f<1073741758)
  75.       dp_f+=1073741890;
  76.     else dp_f-=1073741769;
  77.   if (dp_e1&dp_exp_30)
  78.     if(dp_f<2147483527)
  79.       dp_f+=121;
  80.     else dp_f-=2147483538;
  81.   if (dp_e5&dp_exp_31)
  82.     if (dp_f<0)
  83.       dp_f+=2147483648;
  84.     else dp_f-=11;
  85.   if (dp_f<0)
  86.     dp_erg=(unsigned long)(dp_f+2147483659);
  87.   else  dp_erg=(unsigned long)(dp_f);
  88. }
  90. #ifdef __TURBOC__
  92. /* Function "dpmod"  */
  94. static void dpmod(unsigned long k, GenPtr x, unsigned long& dp_erg)
  95. DPMOD_BODY(k,x,dp_erg)
  97. #else
  99. /* Macro "dpmod" */
  101. #define dpmod(k,x,dp_erg) DPMOD_BODY(k,x,dp_erg)
  103. #endif
  106. // ----------------------------------------------------------------
  107. // member-functions of class headertable 
  108. // ----------------------------------------------------------------
  110. //-----------------------------------------------------------------
  111. // insert
  112. // fuegt ein Paar (Schluessel,Information) in das Bucket ein
  113. // berechnet Informationen neu
  114. // returns true, falls Element eingefuegt     
  117. bool headertable::insert(GenPtr a,GenPtr b,stp& erg,int& bed,bool& rehash,
  118.  stp anf,stp ende)
  119. { 
  120.   unsigned long dp_erg=0;
  121.   if (!wj)                             // leere Headertable
  122.   { 
  123.     wj=1;
  125.     if (!tj)
  126.     { 
  127.       mj=1;
  128.       tj=new subtable(a,b);            // einfach einfuegen
  129.       erg=tj;
  130.     }
  131.     else                               // Tafel war angelegt
  132.     {
  133.       if (mj==1)                       // nur einelementig  
  134.       {
  135. tj->set_s(a,b);
  136. erg=tj;
  137.       }
  138.       else                             // groessere Tafel
  139.         if (mj<=4)                     // nur 2 oder 4-elementig  
  140.         {
  141.   tj[0].set_s(a,b);
  142.           erg=tj;
  143.         }
  144. else
  145.         {
  146.           dpmod(kj,a,dp_erg);
  147.           dp_erg=dp_erg%mal_pot2(sqr(mj),1);
  148.           tj[dp_erg].set_s(a,b);
  149.           erg=tj+dp_erg;
  150.         }
  151.     }
  152.    
  153.     bed+=2; 
  154.     rehash=false;
  155.     return true;         
  156.   }                                    // leere Tafel jetzt mit Element
  158.   if (wj==1)                           // Tafel mit einem Element
  159.   { 
  160.     if (mj==1)
  161.     {
  162.       if (a==tj->ke)                   // gleiches Element
  163.       { 
  164.         tj->inf=b;
  165.         erg=tj;
  166.         rehash=false;
  167.         return false; 
  168.       }
  169.       else
  170.       { 
  171.         wj=2;                          // Einfuegen
  172.         bed+=6;
  173.         if (bed>=0)                    // Platz genug?
  174.         { 
  175.           rehash=true;
  176.           return true; 
  177.         }
  179.         mj=2;                          // Speicher anfordern
  180.        // und Elemente verteilen
  181.         stp lj=tj;
  182.         tj=new subtable[2];
  183.         tj[0] = (*lj);
  184.         tj[1].set_s(a,b);
  185.         erg = tj+1;
  186.     
  187.         if ((lj>ende)||(lj<anf)) 
  188.           delete lj;
  189.       }
  191.       rehash = false;
  192.       return true;
  193.     }
  195.     if (mj<=4)
  196.     {
  197.       if (a==tj[0].ke)               // gleiches Element
  198.       { 
  199.         tj[0].inf=b;
  200.         erg=tj;
  201.         rehash=false;
  202.         return false; 
  203.       }
  204.       else
  205.       { 
  206. wj = 2;
  207.         bed+=6;
  208. tj[1].set_s(a,b);
  209.         erg = tj+1;
  210. rehash=false;
  211. return true;
  212.       }
  213.     }
  214.     else                               // groessere Tafel
  215.     {
  216.       dpmod(kj,a,dp_erg);
  217.       dp_erg=dp_erg%mal_pot2(sqr(mj),1);
  219.       if (a==tj[dp_erg].ke)            // gleiches Element
  220.       { 
  221. tj[dp_erg].inf = b;
  222. erg=tj+dp_erg;
  223. rehash=false;
  224. return false;
  225.       }
  227.       wj=2;
  228.       bed+=6;
  230.       if ( tj[dp_erg].ke == EMPTY )    // Position leer
  231.       { 
  232.         tj[dp_erg].set_s(a,b);
  233.         erg=tj+dp_erg;
  234. rehash=false;
  235. return true;
  236.       }
  237.       else                             // lokales Rehash
  238.       { 
  239. stp lj = new subtable(tj[dp_erg]);
  240. tj[dp_erg].clear();
  241. int subsize = mal_pot2(sqr(mj),1);
  242.         int injektiv=0;            
  243.        // injektive Funktion suchen
  244.     
  245.         while (!injektiv)
  246.         { injektiv=1;
  247.           ran >> kj;
  249.           unsigned long dp_erg=0;
  250.           dpmod(kj,lj->ke,dp_erg);
  251.           dp_erg=dp_erg%subsize;
  252.           tj[dp_erg]=(*lj);
  254.           dpmod(kj,a,dp_erg);
  255.           dp_erg=dp_erg%subsize;
  256.           if ( tj[dp_erg].ke == EMPTY )
  257.           {
  258.     tj[dp_erg].set_s(a,b);
  259.     erg=tj+dp_erg;
  260.           }
  261.           else
  262.           {
  263.             tj[dp_erg].clear(); 
  264.             injektiv=0;
  265.           }
  266.         }                              // Elemente injektiv verteilt 
  268.         delete lj;
  269.         rehash=false;
  270.         return true;           
  271.       }
  272.     }
  273.   }                                    // Tafel enthaelt jetzt 2 Elemente
  275.   if (wj<4)                            // Tafel mit 2 oder 3 Elementen
  276.   { 
  277.     for (int i1=0; i1<wj ; i1++)
  278.       if (a==tj[i1].ke)                // gleiches Element
  279.       { 
  280.         tj[i1].inf=b;
  281.         erg=tj+i1;
  282.         rehash=false;
  283.         return false; 
  284.       }
  286.        // neues Element
  287.     if (wj==2)
  288.       bed+=10;
  289.     else
  290.       bed+=14;
  292.     if (mj==2)
  293.     {
  294.       if (bed>=0)                      // Platz genug?
  295.       { 
  296.         rehash=true;
  297.         return true; 
  298.       }
  300.       mj=4;                            // Speicher anfordern
  301.       stp lj=tj;
  302.       tj=new subtable[4];
  304.       int i1;
  305.       for (i1=0; i1<wj ; i1++)
  306.         tj[i1] = lj[i1];
  307.       tj[i1].set_s(a,b);
  308.       erg = tj+wj;
  309.     
  310.       if ((lj>ende)||(lj<anf)) 
  311.         delete lj;
  313.       wj++;       
  314.       rehash = false;
  315.       return true;
  316.     }
  318.     if (mj==4)
  319.     {
  320.       tj[wj].set_s(a,b);
  321.       erg = tj+wj;
  322.       wj++;       
  323.       rehash=false;
  324.       return true;
  325.     }
  326.     else                               // groessere Tafel
  327.     {
  328.       dpmod(kj,a,dp_erg);
  329.       dp_erg=dp_erg%mal_pot2(sqr(mj),1);
  330.       if ( tj[dp_erg].ke == EMPTY )    // Position leer
  331.       { 
  332.         tj[dp_erg].set_s(a,b);
  333.         erg=tj+dp_erg;
  334.         wj++;       
  335. rehash=false;
  336. return true;
  337.       }
  338.       else                             // lokales Rehash
  339.       {
  340. stp lj = new subtable[++wj];
  341.         int i1=0;
  342.                                             // Elemente in Liste kopieren
  343.         for (int i2=0; i1<wj-1 ; i2++ )
  344.         { 
  345.   if ( tj[i2].ke != EMPTY  )
  346.           { 
  347.     lj[i1++]=tj[i2];  
  348.             tj[i2].clear(); 
  349.   }
  350.         }
  351.         lj[i1].set_s(a,b);
  353.         int subsize = mal_pot2(sqr(mj),1);
  354.         int injektiv=0;                     // injektive Funktion suchen
  355.     
  356.         while (!injektiv)
  357.         { injektiv=1;
  358.           ran >> kj;
  360.           for (i1=0; (i1<wj) && injektiv ; i1++)
  361.           { 
  362.             dpmod(kj,lj[i1].ke,dp_erg);
  363.             dp_erg=dp_erg%subsize;
  365.             if ( tj[dp_erg].ke == EMPTY )
  366.               tj[dp_erg]=lj[i1];
  367.             else
  368.             { 
  369.       injektiv=0;
  370.               for (int g=0;g<i1;g++)     // belegte Positionen loeschen
  371.               { 
  372.         GenPtr help=lj[g].ke;
  373.                 dpmod(kj,help,dp_erg);
  374.                 dp_erg=dp_erg%subsize;  
  375.                 tj[dp_erg].ke = EMPTY ; 
  376.               }
  377.             }
  378.           }                            // Elemente injektiv verteilt  
  379.         }       
  381.         delete lj;
  382.         rehash=false;
  383.         return true;           
  384.       }                                // lokales Rehash beendet
  385.     }
  386.   }                                    // Tafel enthaelt jetzt 2 oder 3 Elemente
  388.   if (wj==4)                           // Tafel mit 4 Elementen
  389.   { 
  390.     for (int i1=0; i1<4; i1++)
  391.       if (a==tj[i1].ke)                // gleiches Element
  392.       { 
  393.         tj[i1].inf=b;
  394.         erg=tj+i1;
  395.         rehash=false;
  396.         return false; 
  397.       }
  398.   
  399.        // neues Element einfuegen
  400.     bed+=18;
  402.     if (bed>=0)                        // Platz genug?
  403.     { 
  404.       rehash=true;
  405.       return true; 
  406.     }
  408.     mj=8;                               // Speicher anfordern
  409. // und Elemente verteilen
  410.     stp lj=tj;
  411.     tj=new subtable[128];
  412.     int injektiv=0;       
  413. // injektive Funktion suchen
  414.     
  415.     while (!injektiv)
  416.     {
  417.       injektiv=1;
  418.       ran >>kj;
  420.       int i1;
  421.       for (i1=0; (i1<4) && injektiv ; i1++)
  422.       { 
  423.         dpmod(kj,lj[i1].ke,dp_erg);
  424.         dp_erg=dp_erg%128;
  426.         if ( tj[dp_erg].ke == EMPTY )
  427.           tj[dp_erg]=lj[i1];
  428.         else
  429.         { 
  430.   injektiv=0;
  431.           for (int g=0;g<i1;g++)     // belegte Positionen loeschen
  432.           { 
  433.     GenPtr help=lj[g].ke;
  434.             dpmod(kj,help,dp_erg);
  435.             dp_erg=dp_erg%128;  
  436.             tj[dp_erg].ke = EMPTY ; 
  437.           }
  438.         }
  439.       }
  440.       if (injektiv)                  // letztes Element hashen
  441.       {
  442.         dpmod(kj,a,dp_erg);
  443.         dp_erg=dp_erg%128;
  444.         if ( tj[dp_erg].ke == EMPTY )
  445.         { 
  446.           tj[dp_erg].set_s(a,b);
  447.           erg=tj+dp_erg;
  448.         }
  449.         else
  450.         { 
  451.           injektiv=0;
  452.           for (int g=0;g<i1;g++)     // belegte Positionen loeschen
  453.           { 
  454.             GenPtr help=lj[g].ke;
  455.             dpmod(kj,help,dp_erg);
  456.             dp_erg=dp_erg%128;  
  457.             tj[dp_erg].clear() ; 
  458.           }
  459.         }                            // letztes Element 
  460.       }             
  461.     }                                // Elemente injektiv verteilt 
  463.     if ((lj>ende)||(lj<anf)) 
  464.       delete lj;
  466.     wj=5;                          
  467.     rehash=false;
  468.     return true;           
  469.   }                             // Tafel enthaelt jetzt 5 Elemente
  471.                                 // Tafel mit >= 5 Elementen
  472. // injektives Hashing auf Bucket
  474.   int subsize=mal_pot2(sqr(mj),1);
  475.   dpmod(kj,a,dp_erg);
  476.   dp_erg=dp_erg%subsize;
  478.   if ( tj[dp_erg].ke == a)         // gleiches Element
  479.   { 
  480.     tj[dp_erg].set_s(a,b);
  481.     erg=tj+dp_erg;
  482.     rehash=false;
  483.     return false;      
  484.   }
  486.   int oldscard=wj;
  487.   int subcard=(++wj);
  488.   bed+=mal_pot2(subcard,2)-2;
  490.   if ( tj[dp_erg].ke == EMPTY  )    // Position leer -> einfuegen
  491.   { 
  492.     tj[dp_erg].set_s(a,b);
  493.     erg=tj+dp_erg;
  494.     rehash = false;
  495.     return true; 
  496.   }
  497.   else                         // Tafelelement besetzt             
  498.    
  499.     if (subcard<=mj)           // aber noch Platz in Tafel
  500.     {  
  501.       stp lj = new subtable[subcard];
  502.       int i1=0;
  503.                                // Elemente in Liste kopieren
  504.       for (int i2=0; i1<oldscard  ; i2++ )
  505.       {
  506. if ( tj[i2].ke != EMPTY  )
  507.         {
  508.           lj[i1++]=tj[i2];  
  509.           tj[i2].clear(); 
  510.         }
  511.       }
  512.       lj[i1].set_s(a,b);
  513.                                  // lokales Rehash , alle Elemente in Liste lj
  515.       int injektiv=0;
  516.       while (!injektiv)          // injektive Funktion suchen
  517.       { 
  518. injektiv=1;
  519.         ran >> kj;
  521.         for (i1=0; (i1<subcard) && injektiv ; i1++)
  522.         { 
  523.           dpmod(kj,lj[i1].ke,dp_erg);
  524.           dp_erg=dp_erg%subsize;
  525.           if ( tj[dp_erg].ke == EMPTY )
  526.           {
  527.             tj[dp_erg]=lj[i1]; 
  528.     erg=tj+dp_erg;
  529.           }
  530.           else
  531.           {
  532.     injektiv=0;                // Injektivitaet verletzt
  533.             for (int g=0;g<i1;g++)     // belegte Positionen loeschen
  534.             {
  535.       GenPtr help=lj[g].ke;
  536.       dpmod(kj,help,dp_erg);
  537.               dp_erg=dp_erg%subsize;  
  538.               tj[dp_erg].ke = EMPTY ; 
  539.             }
  540.           }
  541.         }                       // Elemente getestet
  543.       }                         // naechster Versuch oder fertig
  545.       delete lj;
  546.       rehash = false;
  547.       return true; 
  548.     }                             // subcard<=mj
  550.     else                          // |Wj|>Mj , d.h. Groesse der
  551.                              // Subtable verdoppeln
  552.     { 
  553.       if (bed>=0)                 // Kontrolle des Platzverbrauchs
  554.       {
  555.         rehash = true;
  556.         return true;    
  557.       }
  558.       else                        // Platz in Ordnung             
  559.                                   // Untertafel verdoppeln
  560.       { 
  561.         // int oldssize= mal_pot2(sqr(mj),1); ( never used)
  562.         int i1=0;
  563.                                   // Elemente in Liste retten
  564.         stp lj = new subtable[subcard]; 
  565.         for (int i2=0; i1<oldscard ; i2++)
  566.           if ( tj[i2].ke != EMPTY  )
  567.             lj[i1++]=tj[i2];
  568.         lj[i1].set_s(a,b);
  570.         for ( ; mj<wj ; mj<<=1 ) ;    // Subtable vergroessern
  571.         subsize = mal_pot2(sqr(mj),1); 
  573.         if ((tj>ende)||(tj<anf))      // Speicherverwaltung
  574.           delete tj;
  576.         tj=new subtable[subsize]; 
  577.         int injektiv=0;
  578.                                       // injektive Funktion suchen
  579.         while (!injektiv)       
  580.         {
  581.           injektiv=1;
  582.           ran >> kj;
  583.           for (i1=0; (i1<subcard) && injektiv ; i1++)
  584.           {
  585.             dpmod(kj,lj[i1].ke,dp_erg);
  586.             dp_erg=dp_erg%subsize;
  587.             if ( tj[dp_erg].ke == EMPTY )
  588.             { 
  589.               tj[dp_erg]=lj[i1]; 
  590.               erg=tj+dp_erg;
  591.             }
  593.              else                       // Injektivitaet verletzt
  594.              {
  595.        injektiv=0;
  596.                for (int g=0;g<i1;g++)   // Subtables saeubern
  597.                {
  598.  GenPtr help=lj[g].ke;
  599.  dpmod(kj,help,dp_erg);
  600.                  dp_erg=dp_erg%subsize;
  601.  tj[dp_erg].ke = EMPTY ; 
  602.        }
  604.      }
  605.           }                             // alle Elemente getestet
  607.         }                               // naechster Versuch oder fertig
  609.      delete lj;
  610.    rehash = false;
  611. return true;
  612.       }
  613.     }
  614.   }                       // insert
  615.    
  616. //-----------------------------------------------------------------
  617. // dinsert
  618. // fuegt ein Paar (Schluessel,Information) in das Bucket ein
  619. // benutzt Informationen aus Konstruktor oder Rehash_all
  620. // gibt true zurueck, falls erfolgreich
  623. int headertable::dinsert(GenPtr a,GenPtr b,
  624.   stp ende,stp& wo,stp& erg)
  626. {
  627.   if (mj==1)                    // nur ein Element in Tafel 
  628.   { // und Tafel anlegen  
  629.     tj=wo;
  630.     wo++; 
  631.     tj->set_s(a,b);    
  632.     erg=tj;
  633.     return true;  
  634.   }                             // leere Tafel jetzt mit Element
  636.   if (mj==2)                    // zwei Elemente in Tafel 
  637.   {
  638.     if (!tj)        // und Tafel anlegen
  639.     { 
  640.       wj=1;
  641.       tj=wo;
  642.       wo+=2; 
  643.       tj[0].set_s(a,b);    
  644.       erg=tj;
  645.       return true;  
  646.     }                           // leere Tafel jetzt mit Element
  647.     else
  648.     { 
  649.       if (a==tj[0].ke)
  650.       {
  651. tj[0].inf = b;
  652. erg = tj;
  653. return false;
  654.       }
  655.       wj=2;
  656.       tj[1].set_s(a,b);
  657.       erg=tj+1;
  658.       return true;
  659.     }
  660.   }
  662.   if (mj<=4)                    // max 4 Elemente in Tafel 
  663.   {
  664.     if (!tj)        // und Tafel anlegen
  665.     { 
  666.       wj=1;
  667.       tj=wo;
  668.       wo+=4; 
  669.       tj[0].set_s(a,b);    
  670.       erg=tj;
  671.       return true;  
  672.     }                           // leere Tafel jetzt mit Element
  673.     else
  674.     { 
  675.       for (int i1=0; i1<wj; i1++)
  676.         if (a==tj[i1].ke)
  677.         {
  678.   tj[i1].inf = b;
  679.   erg = tj+i1;
  680.   return false;
  681.         }
  683.       tj[wj].set_s(a,b);
  684.       erg=tj+wj;
  685.       wj++;
  686.       return true;
  687.     }
  688.   }
  692.   if (!tj)                      // Tafel muss angelegt werden
  693. // Tafel mit meheren Elementen
  694. // erstes Element kommt hinein
  695.   { 
  696.     int q=mal_pot2(sqr(mj),1);  // Platz anfordern aus Pool
  697.     tj=wo;
  698.     wo+=q; 
  699.     if (wo>ende+1)
  700.       error_handler(1,"memory allocation error");
  702.     ran >> kj;     // erstes Element einfuegen
  703.     unsigned long dp_erg=0;
  704.     dpmod(kj,a,dp_erg);
  705.     dp_erg=dp_erg%q;
  706.     tj[dp_erg].set_s(a,b);
  707.     erg=tj+dp_erg;
  708.     wj = 1;                     // jetzt aktuelles wj
  709.     return true;       
  710.   }                             // leere Tafel jetzt mit 1.Element
  712.                                 // Tafel ist schon angelegt und enthaelt Element
  713.                                 // Tafel bekommt mindestens 5 Elemente
  714.   unsigned long dp_erg=0;
  715.   int subsize=mal_pot2(sqr(mj),1);
  716.   dpmod(kj,a,dp_erg);
  717.   dp_erg=dp_erg%subsize;
  719.   if ( tj[dp_erg].ke == a)           // gleicher Schluessel
  720.   { 
  721.     tj[dp_erg].set_s(a,b);
  722.     erg=tj+dp_erg;
  723.     return false;      
  724.   }
  726.   if ( tj[dp_erg].ke == EMPTY  )     // Position leer
  727.   { tj[dp_erg].set_s(a,b);   
  728.     erg=tj+dp_erg;
  729.   }
  731.   else                          // Position besetzt -> lokales Rehash 
  732.   {  
  733. // Elemente sammeln
  734.      stp lj = new subtable[wj+1];
  735.      int i1=0;
  736.      int i2=0;
  737.      for (i2=0; i1<wj ; i2++)   // Elemente in Liste kopieren
  738.      { if ( tj[i2].ke != EMPTY  )
  739.        { lj[i1++]=tj[i2];  
  740.          tj[i2].clear() ; 
  741.        }
  742.      }
  744.      lj[i1++].set_s(a,b);         // i1 = wj+1
  746.                                   // lokales Rehash , alle Elemente in Liste lj
  747.      int injektiv=0;
  748.                                   // injektive Funktion suchen
  749.      while (!injektiv)         
  750.      {
  751.        injektiv=1;
  752.        ran >> kj;
  754.        for (i2=0; (i2<i1) && injektiv ; i2++)
  755.        { 
  756.          dpmod(kj,lj[i2].ke,dp_erg);
  757.  dp_erg=dp_erg%subsize;
  758.          if ( tj[dp_erg].ke == EMPTY )
  759.  {
  760.    tj[dp_erg]=lj[i2]; 
  761.    erg=tj+dp_erg;
  762.          }
  763.          else                      // Injektivitaet verletzt
  764.          {
  765.    injektiv=0;
  766.            for (int g=0;g<i2;g++)  // Subtables saeubern
  767.            {
  768.      GenPtr help=lj[g].ke;
  769.              unsigned long dp_erg=0;
  770.      dpmod(kj,help,dp_erg);
  771.              dp_erg=dp_erg%subsize;
  772.              tj[dp_erg].ke = EMPTY ;
  773.    }
  774.          }
  775.        }                           // alle Elemente getestet 
  777.      }                             // neuer Versuch oder fertig
  779.      delete lj;
  780.   }
  782.   wj++;                           // aktuelle Anzahl updaten
  783.   return true;
  785. }
  788. // ----------------------------------------------------------------
  789. // lookup
  790. // sucht nach Eintrag mit Schluessel a
  791. // gibt Pointer auf Eintrag zurueck, falls gefunden
  792. // 0 sonst
  794. stp headertable::lookup(GenPtr a)
  796. { 
  797.    if (!wj)  return 0;              // Headertable leer
  799.    if (mj==1)                       // Headertable einelementig
  800.    { 
  801.      if (a==tj->ke) 
  802.        return tj;
  803.      else
  804.        return 0;
  805.    }
  807.    if (mj<=4)                       // Tafel mit max 4 Elementen
  808.    { 
  809.      for (int i1=0; i1<wj; i1++)
  810.        if (a==tj[i1].ke) 
  811.          return tj+i1;
  812.      return 0;
  813.    }
  814.                                     // Headertable mit mehr als 4 Subtables
  815.    unsigned long dp_erg=0;
  816.    dpmod(kj,a,dp_erg);
  817.    dp_erg=dp_erg%(mal_pot2(sqr(mj),1));   // Position
  819.    if (tj[dp_erg].ke==a)
  820.      return tj+dp_erg;
  821.    else
  822.      return 0; 
  823.  } 
  825. // ----------------------------------------------------------------
  826. // del
  827. // loescht Element in Tafel
  828. // gibt true zurueck, wenn erfolgreich
  830. bool headertable::del(GenPtr a,stp anf,stp ende)
  832. {
  833.   if (!wj) return false;             // leere Headertable
  835.   if (mj==1)                         // Headertable einelementig
  836.   { 
  837.     if (a==tj->ke) 
  838.     {
  839.       wj=0;                          // Schluessel gefunden
  840.       tj->clear() ;
  841.       if ((tj<anf)||(tj>ende))
  842.       {
  843. delete tj;
  844. tj = 0;
  845. mj = 0;
  846.       } 
  847.       return true;    
  848.     }
  849.     else
  850.       return false;
  851.   }
  852.  
  853.   if (mj<=4)           
  854.   { 
  855.     if (wj>1)                        // Headertable mit mind 2 Elementen
  856.     {
  857.       for (int i1=0; i1<wj; i1++)
  858.       { 
  859. if (tj[i1].ke==a)            // Element gefunden
  860.         { 
  861.           wj--;
  862.           tj[i1]=tj[wj];             // Loch fuellen
  863.           tj[wj].clear();
  864.           return true;
  865.         }
  866.       }
  867.       return false;
  868.     }
  869.     else                               // ein Element in Bucket
  870.     {
  871.       if (tj[0].ke==a) 
  872.       {
  873. wj=0;                          // Schluessel gefunden
  874.         tj[0].clear() ;
  875.         if ((tj<anf)||(tj>ende))
  876.         {
  877.   delete tj;
  878.   tj = 0;
  879.   mj = 0;
  880.         } 
  881.         return true;    
  882.       }
  883.       else
  884.         return false;
  885.     }
  886.   }
  887.  
  888.       // Headertable mit mehreren Subtables
  889.   unsigned long dp_erg=0;
  890.   dpmod(kj,a,dp_erg);
  891.   dp_erg=dp_erg%(mal_pot2(sqr(mj),1));   // Position
  893.   if (tj[dp_erg].ke==a)
  894.   {
  895.     wj--;                             // Schluessel gefunden
  896.     tj[dp_erg].clear() ;
  898.     if (wj==0)                        // Bucket nun leer
  899.       if ((tj<anf)||(tj>ende))
  900.       {
  901. delete tj;
  902. tj = 0;
  903. mj = 0;
  904.       } 
  905.     return true;    
  906.   } 
  907.   else return false;
  908. }
  910. // ---------------------------------------------------------
  911. // give_elements()
  912. // haengt Elemente der Tafel an Liste an
  913. // gibt Anzahl der Elemente zurueck
  916. int headertable::give_elements(stp& wo,stp anf,stp ende)
  918. { 
  919.   int j=0;
  921.   if (!wj) { 
  922.      if ( tj && ((tj<anf)||(tj>ende))) 
  923.              {
  924.        if (mj>1)
  925.                  delete tj;
  926.        else 
  927.                  delete tj;
  929.        tj = 0;
  930.        mj = 0;
  931.              }
  932.      return 0;
  933.    }
  935.   if (mj==1)                    // Headertable einelementig
  936.   { 
  937.     (*wo)=(*tj);                // Element kopieren
  938.     wo++;
  939.     if ((tj<anf)||(tj>ende))     // gebe Speicher frei
  940.     {
  941.       delete tj;
  942.       tj = 0;
  943.       mj = 0;
  944.     }
  945.     return 1; 
  946.   }
  948.   if (mj<=4)                     // Headertable maximal vierelementig
  949.   { 
  950.     j=0;   
  951.     while ( (tj[j].ke != EMPTY) && (j<mj) )
  952.     { 
  953.       (*wo)=tj[j];
  954.       wo++;
  955.       j++;
  956.     }
  958.     if ((tj<anf)||(tj>ende))     // gebe Speicher frei
  959.     { 
  960.       delete tj;
  961.       tj = 0;
  962.       mj = 0;
  963.     }
  964.     return j; 
  965.   }
  967.  // Headertable mit meheren Elementen
  968.   bool weiter=true;
  969.   int subsize=mal_pot2(sqr(mj),1);
  970.   j=0;
  972.   for (int k=0;(k<subsize)&&weiter;k++)  // suche Elemente
  973.     if ( tj[k].ke != EMPTY  )
  974.     {                                    // haenge Element an Liste
  975.       (*wo)=tj[k];
  976.       wo++; j++;
  977.       if (j>=wj) weiter=false; 
  978.     }
  979.   if ((tj<anf)||(tj>ende))               // gebe Speicher frei
  980.   { 
  981.     delete tj;
  982.     tj = 0;
  983.     mj = 0;
  984.   }
  985.   return j;
  986. }
  988. // ----------------------------------------------------------------
  989. // member-functions of class dp_hash
  990. // ----------------------------------------------------------------
  992. // -------------------------------------------------------
  993. // rehash_all
  994. //
  995. // stellt Headertables neu auf, um Platzverbrauch korrekt
  996. // zu halten
  997. // fuegt Element dann neu ein
  999. stp dp_hash::rehash_all( GenPtr x, GenPtr y )
  1001. { 
  1002.   int i,i1,j,nsave,platz;
  1003.   unsigned long dp_erg=0;
  1005.   stp erg=0;
  1006.   stp l=new subtable[n];         // Sammle Elemente in Liste l
  1008.   i=0;
  1009.   stp pos = l;
  1010.   nsave = ( x == EMPTY ? n : n-1 );
  1012.   while ( (i<sM) && (nsave>0) )  // Sammle Element aus allen Headertables
  1013.   { 
  1014.     if (htablep[i])
  1015.     {
  1016.       nsave -= htablep[i]->give_elements(pos,anf,ende) ;
  1017.       delete htablep[i];
  1018.     }
  1019.     i++;   
  1020.   }
  1022.   if ( x != EMPTY )               // fuege neues Element hinzu
  1023.     l[n-1].set_s(x,y);
  1025.   free ((char*)htablep);          // Speicher freigeben
  1026.   if (anf) 
  1027.     delete anf; 
  1028.     // neue Parameter setzen
  1030.   M=int((1+_dp_h_c)*n);
  1031.   sM = int(((4.0/3.0)*wursechs)*(1+_dp_h_c)*n);
  1033.                        // Speicher allokieren
  1034.   htablep=(htp*) calloc(sM,sizeof(htp));  // schneller als new+init
  1035.   int* buckets=new int[n];
  1037.   if (!htablep)
  1038.     error_handler(1,"memory overflow");
  1040.   platz=n;
  1041.   i1=0;
  1042.   while (!i1)                    // Top-Funktion suchen
  1043.   { 
  1044.     bed=0;
  1045.     ran >> k;
  1047.     for (i=0;i<n;i++)           // Hashe alle Elemente
  1048.     {
  1049.       GenPtr help=l[i].ke;
  1050.       dpmod(k,help,dp_erg);
  1051.       dp_erg=dp_erg%sM;
  1052.       buckets[i] = dp_erg;      // Merke Headertable
  1054.       if (!htablep[dp_erg]) 
  1055.         htablep[dp_erg] = new headertable;
  1057.                                 // Aendere Headertables
  1058.       int f=++(htablep[dp_erg]->wj);
  1059.       int* groesse=&(htablep[dp_erg]->mj);
  1061.       if (f<=2)
  1062.  (*groesse)++;
  1063.       else
  1064.         if (*groesse<f)
  1065.         { 
  1066.   (*groesse)<<=1;      
  1067.   
  1068.   if (*groesse==4)       // vergroessere Feld
  1069.     platz++;
  1070.           else
  1071.     if (*groesse==8)     // Uebergang von Feld auf Tafel
  1072.       platz+=123;
  1073.             else
  1074.       platz+=3*sqr(*groesse)/2; 
  1075.         }
  1076. else                     // Tafel nicht vergroessert
  1077.   platz--;
  1079.       bed+=mal_pot2(f,2)-2; 
  1080.     }                            // alle Elemente gehasht
  1082.                                  // bed-=(((8.0*sqr(M))/sM)+2*M);
  1083.     float _bed=(wursechs+2)*M;   // Vereinfachung durch Einsetzen von sM
  1084.     bed-=int(_bed);
  1085.     i1=(bed<0);                  // kontrolliere Platz
  1087.     if (!i1)                     // nicht erfolgreich, saeubere Headertables
  1088.     {
  1089.       platz=n;
  1090.       for (j=0; j<sM; j++)
  1091.         if (htablep[j]) 
  1092. { 
  1093.   delete htablep[j];
  1094.   htablep[j] = 0 ;   
  1095. }
  1096.     }
  1098.   }                              // Top-Funktion gefunden
  1101.   anf=new subtable[platz];        // allokiere Speicher fuer alle Subtables
  1102.   wo=anf;
  1103.   ende=anf+platz-1;
  1105.   for (i=0; i<n; i++)             // fuege Elemente wieder ein
  1106.   { 
  1107.     int bucket=buckets[i];  
  1108.     htablep[bucket]->dinsert(l[i].ke,l[i].inf,ende,wo,erg);
  1109.   }
  1111.   delete buckets;
  1112.   delete l;
  1113.   return erg;
  1114. }
  1116. // --------------------------------------------------------
  1117. // insert
  1118. //
  1119. // fuegt Element in die entsprechende Headertable ein
  1121. stp dp_hash::insert(GenPtr x,GenPtr y)
  1123. { 
  1124.   if ( (unsigned long)x>maxuni )  
  1125.     error_handler(2,string("dp_hash: key %d out of range",x));
  1127.   copy_key(x);
  1128.   copy_inf(y);
  1130.   unsigned long dp_erg=0;
  1131.   dpmod(k,x,dp_erg);
  1132.   dp_erg=dp_erg%sM;                   // Toptafel
  1134.   bool rehash = false;
  1135.   stp  erg    = 0;
  1137.   if ( !htablep[dp_erg] ) 
  1138.     htablep[dp_erg] = new headertable;
  1140.   if ( htablep[dp_erg]->insert(x,y,erg,bed,rehash,anf,ende) )  n++;
  1142.   if ( rehash )  erg=rehash_all(x,y);
  1144.   return erg;
  1145. }
  1147. // --------------------------------------------------------
  1148. // del
  1149. //
  1150. // loescht Element aus entsprechender Headertable
  1152. void dp_hash::del(GenPtr x)
  1154. { 
  1156.   if ( (unsigned long)x>maxuni )  
  1157.     error_handler(2,string("key %d out of range",x));
  1159. // s.n. :
  1161. stp p = lookup(x);
  1162. if (p==0) return;
  1163. clear_key(p->ke);
  1164. clear_inf(p->inf);
  1167.   unsigned long dp_erg=0;
  1168.   dpmod(k,x,dp_erg);
  1169.   dp_erg=dp_erg%sM;                   // Toptafel
  1171.   if ( !htablep[dp_erg] ) return;     // Headertable nicht vorhanden
  1172.          // in Toptafel loeschen
  1174.   if ( htablep[dp_erg]->del(x,anf,ende) ) n--;     
  1176.   if ( !htablep[dp_erg]->wj )
  1177.   { 
  1178.     delete htablep[dp_erg];
  1179.     htablep[dp_erg] = 0;
  1180.   }
  1182.   if ((n*(1+3*_dp_h_c)<M) && (n>3))
  1183.     rehash_all(); 
  1185. } 
  1187. // -------------------------------------------------------
  1188. // lookup,change_inf
  1189. //
  1190. // suchen in Headertable nach Element mit Schluessel
  1191. // change_inf setzt Information des Elementes auf y
  1194. stp dp_hash::lookup(GenPtr x) const 
  1196. { 
  1197.   if ( (unsigned long)x>maxuni )  
  1198.     error_handler(2,string("key %d out of range",x));
  1200.   unsigned long dp_erg=0;
  1201.   dpmod(k,x,dp_erg);
  1202.   dp_erg=dp_erg%sM;                   // Toptafel
  1204.   if (!htablep[dp_erg]) 
  1205.     return 0;
  1207.   stp y=htablep[dp_erg]->lookup(x);
  1208.   return y ;
  1210. }
  1211.  
  1212. stp dp_hash::change_inf(GenPtr x,GenPtr y)      
  1213. { 
  1214.   if ( (unsigned long)x>maxuni )  
  1215.     error_handler(2,string("key %d out of range",x));
  1217.   unsigned long dp_erg=0;
  1218.   dpmod(k,x,dp_erg);
  1219.   dp_erg=dp_erg%sM;                   // Toptafel
  1222.   if (!htablep[dp_erg])
  1223.     return 0;
  1225.   stp t = htablep[dp_erg]->lookup(x) ;
  1226.   if (t)
  1227.     t->inf = y ;
  1228.   return t;
  1230. }
  1232. // -------------------------------------------------------
  1233. // clear
  1234. //
  1235. // loescht alle Elemente und
  1236. // setzt Hashing auf Leerzustand
  1238. void dp_hash::clear()
  1240. { 
  1241.   stp l = new subtable[n];
  1242.   stp pos=l;
  1244.   for (int i=0;i<sM;i++)           // Headertables loeschen
  1245.     if (htablep[i])
  1246.     { 
  1247.       htablep[i]->give_elements(pos,anf,ende);
  1248.       delete htablep[i];                         
  1249.     }
  1251.   free ((char*)htablep) ;          // Speicher freigeben
  1253.   if (anf) 
  1254.     delete anf;
  1256.   delete l;
  1258.   n = 0;                           // Leerinitialisierung
  1259.   M=4;
  1260.   sM=13;
  1261.   ran >> k;
  1262.   bed=-17;
  1263.   htablep=(htp*) calloc(sM,sizeof(htp));
  1264.   anf = wo = ende = 0;
  1266. }
  1268. // ------------------------------------------------------------
  1269. // Konstruktoren und Destruktor
  1271. dp_hash::dp_hash()
  1273. { 
  1274.   n=0;
  1275.   M=4;
  1276.   sM=13;
  1277.   //ran >> k;
  1278.   k = 9061960;
  1279.   bed=-17;
  1280.   htablep=(htp*) calloc(sM,sizeof(htp));
  1281.   anf = wo = ende = 0;
  1283. }
  1285. dp_hash::dp_hash(int an,GenPtr* keys,GenPtr* inhalte)   
  1286.                                           // wie rehash_all
  1287.                                           // die Elemente stehen aber schon in Listen
  1288. { 
  1289.   int i,i1,j,nsave,platz;
  1290.   unsigned long dp_erg=0;
  1291.   stp erg=0;
  1293.   n=an;
  1294.   M=int((1+_dp_h_c)*n);
  1295.   sM = int(((4.0/3.0)*wursechs)*(1+_dp_h_c)*n);
  1297.   htablep=(htp*) calloc(sM,sizeof(htp));
  1298.   int* buckets = new int[n];
  1300.   if (!htablep)
  1301.     error_handler(1,"memory overflow");
  1303.   platz=n;
  1304.   i1=0;
  1306.   while (!i1)
  1307.   {
  1308.     bed=0;
  1309.     ran >> k;
  1311.     for (i=0;i<n;i++)
  1312.     {
  1313.       GenPtr help=keys[i];
  1314.       if ( (unsigned long)help>maxuni )  
  1315.          error_handler(2,string("key %d out of range",help));
  1317.       dpmod(k,help,dp_erg);
  1318.       dp_erg=dp_erg%sM;
  1319.       buckets[i] = dp_erg;
  1321.       if (!htablep[dp_erg]) 
  1322. htablep[dp_erg] = new headertable;
  1324.       int f=++(htablep[dp_erg]->wj);
  1325.       int* groesse=&(htablep[dp_erg]->mj);
  1327.       if (f<=2)
  1328.  (*groesse)++;
  1329.       else
  1330.         if (*groesse<f)
  1331.         { 
  1332.   (*groesse)<<=1;      
  1333.   
  1334.   if (*groesse==4)       // vergroessere Feld
  1335.     platz++;
  1336.           else
  1337.     if (*groesse==8)     // Uebergang von Feld auf Tafel
  1338.       platz+=123;
  1339.             else
  1340.       platz+=3*sqr(*groesse)/2; 
  1341.         }
  1342. else                     // Tafel nicht vergroessert
  1343.   platz--;
  1345.       bed+=mal_pot2(f,2)-2; 
  1346.     }
  1348.                                  // bed-=(((8.0*sqr(M))/sM)+2*M);
  1349.     float _bed=(wursechs+2)*M;   // Vereinfachung durch Einsetzen von sM
  1350.     bed-=int(_bed);
  1351.     i1=(bed<0);
  1353.     if (!i1)
  1354.     { 
  1355.       platz=n;
  1356.       for (j=0; j<sM; j++)
  1357. if (htablep[j]) 
  1358. { 
  1359.   delete htablep[j];
  1360.   htablep[j] = 0;   
  1361. }
  1362.     }
  1363.   }
  1365.   nsave=an;
  1366.   anf=new subtable[platz];
  1368.   wo=anf;
  1369.   ende=wo+platz-1;
  1370.   n=0;
  1372.   for (i=0; i<nsave; i++)
  1373.   {
  1374.     int bucket = buckets[i];
  1375.     n += (htablep[bucket]->dinsert(keys[i],inhalte[i],ende,wo,erg));
  1376.   } 
  1378.   delete buckets;
  1380.   if ((n*(1+3*_dp_h_c)<M) && (n>3))
  1381.     rehash_all();   
  1383. }
  1385. dp_hash::~dp_hash()
  1386. { 
  1387.   clear();                            // loesche alles
  1389.   free ((char*)htablep);              // gebe Speicher frei
  1390.   if (anf) delete anf;
  1392.   n=M=sM=0;
  1393.   k=0;
  1394.   anf=wo=ende=0;
  1395.   htablep=0;
  1397. }