cdbmake_add.c


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

#include "alloc.h"
#include "cdbmake.h"

void cdbmake_init(cdbm)
struct cdbmake *cdbm;
{
  cdbm->head = 0;
  cdbm->split = 0;
  cdbm->hash = 0;
  cdbm->numentries = 0;
}

int cdbmake_add(cdbm,h,p,alloc)
struct cdbmake *cdbm;
uint32 h;
uint32 p;
char *(*alloc)();
{
  struct cdbmake_hplist *head;

  head = cdbm->head;
  if (!head || (head->num >= CDBMAKE_HPLIST)) {
    head = (struct cdbmake_hplist *) alloc(sizeof(struct cdbmake_hplist));
    if (!head) return 0;
    head->num = 0;
    head->next = cdbm->head;
    cdbm->head = head;
  }
  head->hp[head->num].h = h;
  head->hp[head->num].p = p;
  ++head->num;
  ++cdbm->numentries;
  return 1;
}

int cdbmake_split(cdbm,alloc)
struct cdbmake *cdbm;
char *(*alloc)();
{
  int i;
  uint32 u;
  uint32 memsize;
  struct cdbmake_hplist *x;

  for (i = 0;i < 256;++i)
    cdbm->count[i] = 0;

  for (x = cdbm->head;x;x = x->next) {
    i = x->num;
    while (i--)
      ++cdbm->count[255 & x->hp[i].h];
  }

  memsize = 1;
  for (i = 0;i < 256;++i) {
    u = cdbm->count[i] * 2;
    if (u > memsize)
      memsize = u;
  }

  memsize += cdbm->numentries; /* no overflow possible up to now */
  u = (uint32) 0 - (uint32) 1;
  u /= sizeof(struct cdbmake_hp);
  if (memsize > u) return 0;

  cdbm->split = (struct cdbmake_hp *) alloc(memsize * sizeof(struct cdbmake_hp));
  if (!cdbm->split) return 0;

  cdbm->hash = cdbm->split + cdbm->numentries;

  u = 0;
  for (i = 0;i < 256;++i) {
    u += cdbm->count[i]; /* bounded by numentries, so no overflow */
    cdbm->start[i] = u;
  }

  for (x = cdbm->head;x;x = x->next) {
    i = x->num;
    while (i--)
      cdbm->split[--cdbm->start[255 & x->hp[i].h]] = x->hp[i];
  }

  return 1;
}

uint32 cdbmake_throw(cdbm,pos,b)
struct cdbmake *cdbm;
uint32 pos;
int b;
{
  uint32 len;
  uint32 j;
  uint32 count;
  struct cdbmake_hp *hp;
  uint32 where;

  count = cdbm->count[b];

  len = count + count; /* no overflow possible */
  cdbmake_pack(cdbm->final + 8 * b,pos);
  cdbmake_pack(cdbm->final + 8 * b + 4,len);

  if (len) {
    for (j = 0;j < len;++j)
      cdbm->hash[j].h = cdbm->hash[j].p = 0;

    hp = cdbm->split + cdbm->start[b];
    for (j = 0;j < count;++j) {
      where = (hp->h >> 8) % len;
      while (cdbm->hash[where].p)
	if (++where == len)
	  where = 0;
      cdbm->hash[where] = *hp++;
    }
  }

  return len;
}