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