1 // Copyright (C) 1999,2000 Bruce Guenter <bruceg@em.ca>

     2 //

     3 // This program is free software; you can redistribute it and/or modify

     4 // it under the terms of the GNU General Public License as published by

     5 // the Free Software Foundation; either version 2 of the License, or

     6 // (at your option) any later version.

     7 //

     8 // This program is distributed in the hope that it will be useful,

     9 // but WITHOUT ANY WARRANTY; without even the implied warranty of

    10 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

    11 // GNU General Public License for more details.

    12 //

    13 // You should have received a copy of the GNU General Public License

    14 // along with this program; if not, write to the Free Software

    15 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

    16 

    17 #include "cdb++.h"

    18 #include "internal.h"

    19 

    20 cdbmake::cdbmake()

    21   : head(0), split(0), hash(0), numentries(0)

    22 {

    23 }

    24 

    25 cdbmake::~cdbmake()

    26 {

    27   delete[] split;

    28   hplist* x = head;

    29   while(x) {

    30     hplist* next = x->next;

    31     delete x;

    32     x = next;

    33   }

    34 }

    35 

    36 int cdbmake::add(uint32 h, uint32 p)

    37 {

    38   hplist *chead = head;

    39 

    40   if (!chead || (chead->num >= CDBMAKE_HPLIST)) {

    41     chead = new hplist;

    42     if (!chead) return 0;

    43     chead->num = 0;

    44     chead->next = head;

    45     head = chead;

    46   }

    47   chead->hp[chead->num].h = h;

    48   chead->hp[chead->num].p = p;

    49   ++chead->num;

    50   ++numentries;

    51   return 1;

    52 }

    53 

    54 int cdbmake::split_hashes()

    55 {

    56   for (int i = 0; i < 256; ++i)

    57     count[i] = 0;

    58 

    59   for (hplist* x = head; x; x = x->next) {

    60     for(int i = x->num; i--; )

    61       ++count[255 & x->hp[i].h];

    62   }

    63 

    64   uint32 memsize = 1;

    65   for (int i = 0; i < 256; ++i) {

    66     uint32 u = count[i] * 2;

    67     if (u > memsize)

    68       memsize = u;

    69   }

    70 

    71   memsize += numentries;	// no overflow possible up to now

    72   uint32 u = (uint32) 0 - (uint32) 1;

    73   u /= sizeof(hp);

    74   if (memsize > u) return 0;

    75 

    76   split = new hp[memsize];

    77   if (!split) return 0;

    78 

    79   hash = split + numentries;

    80 

    81   u = 0;

    82   for (int i = 0;i < 256;++i) {

    83     u += count[i];		// bounded by numentries, so no overflow

    84     start[i] = u;

    85   }

    86 

    87   for (hplist* x = head; x; x = x->next) {

    88     int i = x->num;

    89     while (i--)

    90       split[--start[255 & x->hp[i].h]] = x->hp[i];

    91   }

    92 

    93   return 1;

    94 }

    95 

    96 uint32 cdbmake::throw_hash(uint32 pos, int b)

    97 {

    98   uint32 c = count[b];

    99   uint32 len = c + c;		// no overflow possible

   100   pack(final + 8 * b, pos);

   101   pack(final + 8 * b + 4, len);

   102 

   103   if (len) {

   104     for (uint32 j = 0; j < len; ++j)

   105       hash[j].h = hash[j].p = 0;

   106 

   107     hp* hp = split + start[b];

   108     for (uint32 j = 0; j < count[b]; ++j) {

   109       uint32 where = (hp->h >> 8) % len;

   110       while (hash[where].p)

   111 	if (++where == len)

   112 	  where = 0;

   113       hash[where] = *hp++;

   114     }

   115   }

   116 

   117   return len;

   118 }