1 7a4ee46d 2003-11-23 devnull #include "stdinc.h"
2 7a4ee46d 2003-11-23 devnull #include "dat.h"
3 7a4ee46d 2003-11-23 devnull #include "fns.h"
5 7a4ee46d 2003-11-23 devnull struct IEStream
7 7a4ee46d 2003-11-23 devnull Part *part;
8 7a4ee46d 2003-11-23 devnull u64int off; /* read position within part */
9 7a4ee46d 2003-11-23 devnull u64int n; /* number of valid ientries left to read */
10 7a4ee46d 2003-11-23 devnull u32int size; /* allocated space in buffer */
11 7a4ee46d 2003-11-23 devnull u8int *buf;
12 7a4ee46d 2003-11-23 devnull u8int *pos; /* current place in buffer */
13 7a4ee46d 2003-11-23 devnull u8int *epos; /* end of valid buffer contents */
16 7a4ee46d 2003-11-23 devnull IEStream*
17 7a4ee46d 2003-11-23 devnull initiestream(Part *part, u64int off, u64int clumps, u32int size)
19 7a4ee46d 2003-11-23 devnull IEStream *ies;
21 7a4ee46d 2003-11-23 devnull //ZZZ out of memory?
22 7a4ee46d 2003-11-23 devnull ies = MKZ(IEStream);
23 7a4ee46d 2003-11-23 devnull ies->buf = MKN(u8int, size);
24 7a4ee46d 2003-11-23 devnull ies->epos = ies->buf;
25 7a4ee46d 2003-11-23 devnull ies->pos = ies->epos;
26 7a4ee46d 2003-11-23 devnull ies->off = off;
27 7a4ee46d 2003-11-23 devnull ies->n = clumps;
28 7a4ee46d 2003-11-23 devnull ies->size = size;
29 7a4ee46d 2003-11-23 devnull ies->part = part;
30 7a4ee46d 2003-11-23 devnull return ies;
34 7a4ee46d 2003-11-23 devnull freeiestream(IEStream *ies)
36 7a4ee46d 2003-11-23 devnull if(ies == nil)
38 7a4ee46d 2003-11-23 devnull free(ies->buf);
39 7a4ee46d 2003-11-23 devnull free(ies);
42 7a4ee46d 2003-11-23 devnull static u8int*
43 7a4ee46d 2003-11-23 devnull peekientry(IEStream *ies)
45 7a4ee46d 2003-11-23 devnull u32int n, nn;
47 7a4ee46d 2003-11-23 devnull n = ies->epos - ies->pos;
48 7a4ee46d 2003-11-23 devnull if(n < IEntrySize){
49 7a4ee46d 2003-11-23 devnull memmove(ies->buf, ies->pos, n);
50 7a4ee46d 2003-11-23 devnull ies->epos = &ies->buf[n];
51 7a4ee46d 2003-11-23 devnull ies->pos = ies->buf;
52 7a4ee46d 2003-11-23 devnull nn = ies->size;
53 7a4ee46d 2003-11-23 devnull if(nn > ies->n * IEntrySize)
54 7a4ee46d 2003-11-23 devnull nn = ies->n * IEntrySize;
56 7a4ee46d 2003-11-23 devnull if(nn == 0)
57 7a4ee46d 2003-11-23 devnull return nil;
58 7a4ee46d 2003-11-23 devnull if(readpart(ies->part, ies->off, ies->epos, nn) < 0){
59 7a4ee46d 2003-11-23 devnull seterr(EOk, "can't read sorted index entries: %r");
60 7a4ee46d 2003-11-23 devnull return nil;
62 7a4ee46d 2003-11-23 devnull ies->epos += nn;
63 7a4ee46d 2003-11-23 devnull ies->off += nn;
65 7a4ee46d 2003-11-23 devnull return ies->pos;
68 7a4ee46d 2003-11-23 devnull static u32int
69 7a4ee46d 2003-11-23 devnull iebuck(Index *ix, u8int *b)
71 7a4ee46d 2003-11-23 devnull return hashbits(b, 32) / ix->div;
75 7a4ee46d 2003-11-23 devnull buildbucket(Index *ix, IEStream *ies, IBucket *ib)
77 7a4ee46d 2003-11-23 devnull IEntry ie1, ie2;
78 7a4ee46d 2003-11-23 devnull u8int *b;
79 7a4ee46d 2003-11-23 devnull u32int buck;
81 7a4ee46d 2003-11-23 devnull buck = TWID32;
82 7a4ee46d 2003-11-23 devnull ib->n = 0;
83 9ffbb5ad 2004-03-12 devnull ib->depth = 0;
84 7a4ee46d 2003-11-23 devnull while(ies->n){
85 7a4ee46d 2003-11-23 devnull b = peekientry(ies);
86 7a4ee46d 2003-11-23 devnull if(b == nil)
87 7a4ee46d 2003-11-23 devnull return TWID32;
88 7a4ee46d 2003-11-23 devnull //fprint(2, "b=%p ies->n=%lld ib.n=%d buck=%d score=%V\n", b, ies->n, ib->n, iebuck(ix, b), b);
89 7a4ee46d 2003-11-23 devnull if(ib->n == 0)
90 7a4ee46d 2003-11-23 devnull buck = iebuck(ix, b);
92 7a4ee46d 2003-11-23 devnull if(buck != iebuck(ix, b))
94 7a4ee46d 2003-11-23 devnull if(ientrycmp(&ib->data[(ib->n - 1)* IEntrySize], b) == 0){
96 7a4ee46d 2003-11-23 devnull * guess that the larger address is the correct one to use
98 7a4ee46d 2003-11-23 devnull unpackientry(&ie1, &ib->data[(ib->n - 1)* IEntrySize]);
99 7a4ee46d 2003-11-23 devnull unpackientry(&ie2, b);
100 7a4ee46d 2003-11-23 devnull seterr(EOk, "duplicate index entry for score=%V type=%d\n", ie1.score, ie1.ia.type);
101 7a4ee46d 2003-11-23 devnull ib->n--;
102 7a4ee46d 2003-11-23 devnull if(ie1.ia.addr > ie2.ia.addr)
103 7a4ee46d 2003-11-23 devnull memmove(b, &ib->data[ib->n * IEntrySize], IEntrySize);
106 7a4ee46d 2003-11-23 devnull memmove(&ib->data[ib->n * IEntrySize], b, IEntrySize);
107 7a4ee46d 2003-11-23 devnull ib->n++;
108 7a4ee46d 2003-11-23 devnull ies->n--;
109 7a4ee46d 2003-11-23 devnull ies->pos += IEntrySize;
111 7a4ee46d 2003-11-23 devnull return buck;
