1 a0d146ed 2005-07-12 devnull #include "stdinc.h"
2 a0d146ed 2005-07-12 devnull #include "dat.h"
3 a0d146ed 2005-07-12 devnull #include "fns.h"
6 a0d146ed 2005-07-12 devnull * An IEStream is a sorted list of index entries.
8 a0d146ed 2005-07-12 devnull struct IEStream
10 a0d146ed 2005-07-12 devnull Part *part;
11 a0d146ed 2005-07-12 devnull u64int off; /* read position within part */
12 a0d146ed 2005-07-12 devnull u64int n; /* number of valid ientries left to read */
13 a0d146ed 2005-07-12 devnull u32int size; /* allocated space in buffer */
14 a0d146ed 2005-07-12 devnull u8int *buf;
15 a0d146ed 2005-07-12 devnull u8int *pos; /* current place in buffer */
16 a0d146ed 2005-07-12 devnull u8int *epos; /* end of valid buffer contents */
19 a0d146ed 2005-07-12 devnull IEStream*
20 a0d146ed 2005-07-12 devnull initiestream(Part *part, u64int off, u64int clumps, u32int size)
22 a0d146ed 2005-07-12 devnull IEStream *ies;
24 28b49df3 2006-07-18 devnull /* out of memory? */
25 a0d146ed 2005-07-12 devnull ies = MKZ(IEStream);
26 a0d146ed 2005-07-12 devnull ies->buf = MKN(u8int, size);
27 a0d146ed 2005-07-12 devnull ies->epos = ies->buf;
28 a0d146ed 2005-07-12 devnull ies->pos = ies->epos;
29 a0d146ed 2005-07-12 devnull ies->off = off;
30 a0d146ed 2005-07-12 devnull ies->n = clumps;
31 a0d146ed 2005-07-12 devnull ies->size = size;
32 a0d146ed 2005-07-12 devnull ies->part = part;
33 a0d146ed 2005-07-12 devnull return ies;
37 a0d146ed 2005-07-12 devnull freeiestream(IEStream *ies)
39 a0d146ed 2005-07-12 devnull if(ies == nil)
41 a0d146ed 2005-07-12 devnull free(ies->buf);
42 a0d146ed 2005-07-12 devnull free(ies);
46 a0d146ed 2005-07-12 devnull * Return the next IEntry (still packed) in the stream.
48 a0d146ed 2005-07-12 devnull static u8int*
49 a0d146ed 2005-07-12 devnull peekientry(IEStream *ies)
51 a0d146ed 2005-07-12 devnull u32int n, nn;
53 a0d146ed 2005-07-12 devnull n = ies->epos - ies->pos;
54 a0d146ed 2005-07-12 devnull if(n < IEntrySize){
55 a0d146ed 2005-07-12 devnull memmove(ies->buf, ies->pos, n);
56 a0d146ed 2005-07-12 devnull ies->epos = &ies->buf[n];
57 a0d146ed 2005-07-12 devnull ies->pos = ies->buf;
58 a0d146ed 2005-07-12 devnull nn = ies->size;
59 a0d146ed 2005-07-12 devnull if(nn > ies->n * IEntrySize)
60 a0d146ed 2005-07-12 devnull nn = ies->n * IEntrySize;
62 a0d146ed 2005-07-12 devnull if(nn == 0)
63 a0d146ed 2005-07-12 devnull return nil;
64 28b49df3 2006-07-18 devnull //fprint(2, "peek %d from %llud into %p\n", nn, ies->off, ies->epos);
65 a0d146ed 2005-07-12 devnull if(readpart(ies->part, ies->off, ies->epos, nn) < 0){
66 a0d146ed 2005-07-12 devnull seterr(EOk, "can't read sorted index entries: %r");
67 a0d146ed 2005-07-12 devnull return nil;
69 a0d146ed 2005-07-12 devnull ies->epos += nn;
70 a0d146ed 2005-07-12 devnull ies->off += nn;
72 a0d146ed 2005-07-12 devnull return ies->pos;
76 a0d146ed 2005-07-12 devnull * Compute the bucket number for the given IEntry.
77 a0d146ed 2005-07-12 devnull * Knows that the score is the first thing in the packed
78 a0d146ed 2005-07-12 devnull * representation.
80 a0d146ed 2005-07-12 devnull static u32int
81 a0d146ed 2005-07-12 devnull iebuck(Index *ix, u8int *b, IBucket *ib, IEStream *ies)
83 a0d146ed 2005-07-12 devnull USED(ies);
84 a0d146ed 2005-07-12 devnull USED(ib);
85 a0d146ed 2005-07-12 devnull return hashbits(b, 32) / ix->div;
89 a0d146ed 2005-07-12 devnull * Fill ib with the next bucket in the stream.
92 a0d146ed 2005-07-12 devnull buildbucket(Index *ix, IEStream *ies, IBucket *ib, uint maxdata)
94 a0d146ed 2005-07-12 devnull IEntry ie1, ie2;
95 a0d146ed 2005-07-12 devnull u8int *b;
96 a0d146ed 2005-07-12 devnull u32int buck;
98 a0d146ed 2005-07-12 devnull buck = TWID32;
99 a0d146ed 2005-07-12 devnull ib->n = 0;
100 a0d146ed 2005-07-12 devnull while(ies->n){
101 a0d146ed 2005-07-12 devnull b = peekientry(ies);
102 a0d146ed 2005-07-12 devnull if(b == nil)
103 a0d146ed 2005-07-12 devnull return TWID32;
104 28b49df3 2006-07-18 devnull /* fprint(2, "b=%p ies->n=%lld ib.n=%d buck=%d score=%V\n", b, ies->n, ib->n, iebuck(ix, b, ib, ies), b); */
105 a0d146ed 2005-07-12 devnull if(ib->n == 0)
106 a0d146ed 2005-07-12 devnull buck = iebuck(ix, b, ib, ies);
108 a0d146ed 2005-07-12 devnull if(buck != iebuck(ix, b, ib, ies))
110 a0d146ed 2005-07-12 devnull if(ientrycmp(&ib->data[(ib->n - 1)* IEntrySize], b) == 0){
112 a0d146ed 2005-07-12 devnull * guess that the larger address is the correct one to use
114 a0d146ed 2005-07-12 devnull unpackientry(&ie1, &ib->data[(ib->n - 1)* IEntrySize]);
115 a0d146ed 2005-07-12 devnull unpackientry(&ie2, b);
116 a0d146ed 2005-07-12 devnull seterr(EOk, "duplicate index entry for score=%V type=%d", ie1.score, ie1.ia.type);
117 a0d146ed 2005-07-12 devnull ib->n--;
118 a0d146ed 2005-07-12 devnull if(ie1.ia.addr > ie2.ia.addr)
119 a0d146ed 2005-07-12 devnull memmove(b, &ib->data[ib->n * IEntrySize], IEntrySize);
122 a0d146ed 2005-07-12 devnull if((ib->n+1)*IEntrySize > maxdata){
123 a0d146ed 2005-07-12 devnull seterr(EOk, "bucket overflow");
124 a0d146ed 2005-07-12 devnull return TWID32;
126 a0d146ed 2005-07-12 devnull memmove(&ib->data[ib->n * IEntrySize], b, IEntrySize);
127 a0d146ed 2005-07-12 devnull ib->n++;
128 a0d146ed 2005-07-12 devnull ies->n--;
129 a0d146ed 2005-07-12 devnull ies->pos += IEntrySize;
131 a0d146ed 2005-07-12 devnull return buck;
