123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132 |
- #include "stdinc.h"
- #include "dat.h"
- #include "fns.h"
- /*
- * An IEStream is a sorted list of index entries.
- */
- struct IEStream
- {
- Part *part;
- u64int off; /* read position within part */
- u64int n; /* number of valid ientries left to read */
- u32int size; /* allocated space in buffer */
- u8int *buf;
- u8int *pos; /* current place in buffer */
- u8int *epos; /* end of valid buffer contents */
- };
- IEStream*
- initiestream(Part *part, u64int off, u64int clumps, u32int size)
- {
- IEStream *ies;
- /* out of memory? */
- ies = MKZ(IEStream);
- ies->buf = MKN(u8int, size);
- ies->epos = ies->buf;
- ies->pos = ies->epos;
- ies->off = off;
- ies->n = clumps;
- ies->size = size;
- ies->part = part;
- return ies;
- }
- void
- freeiestream(IEStream *ies)
- {
- if(ies == nil)
- return;
- free(ies->buf);
- free(ies);
- }
- /*
- * Return the next IEntry (still packed) in the stream.
- */
- static u8int*
- peekientry(IEStream *ies)
- {
- u32int n, nn;
- n = ies->epos - ies->pos;
- if(n < IEntrySize){
- memmove(ies->buf, ies->pos, n);
- ies->epos = &ies->buf[n];
- ies->pos = ies->buf;
- nn = ies->size;
- if(nn > ies->n * IEntrySize)
- nn = ies->n * IEntrySize;
- nn -= n;
- if(nn == 0)
- return nil;
- //fprint(2, "peek %d from %llud into %p\n", nn, ies->off, ies->epos);
- if(readpart(ies->part, ies->off, ies->epos, nn) < 0){
- seterr(EOk, "can't read sorted index entries: %r");
- return nil;
- }
- ies->epos += nn;
- ies->off += nn;
- }
- return ies->pos;
- }
- /*
- * Compute the bucket number for the given IEntry.
- * Knows that the score is the first thing in the packed
- * representation.
- */
- static u32int
- iebuck(Index *ix, u8int *b, IBucket *ib, IEStream *ies)
- {
- USED(ies);
- USED(ib);
- return hashbits(b, 32) / ix->div;
- }
- /*
- * Fill ib with the next bucket in the stream.
- */
- u32int
- buildbucket(Index *ix, IEStream *ies, IBucket *ib, uint maxdata)
- {
- IEntry ie1, ie2;
- u8int *b;
- u32int buck;
- buck = TWID32;
- ib->n = 0;
- while(ies->n){
- b = peekientry(ies);
- if(b == nil)
- return TWID32;
- /* 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); */
- if(ib->n == 0)
- buck = iebuck(ix, b, ib, ies);
- else{
- if(buck != iebuck(ix, b, ib, ies))
- break;
- if(ientrycmp(&ib->data[(ib->n - 1)* IEntrySize], b) == 0){
- /*
- * guess that the larger address is the correct one to use
- */
- unpackientry(&ie1, &ib->data[(ib->n - 1)* IEntrySize]);
- unpackientry(&ie2, b);
- seterr(EOk, "duplicate index entry for score=%V type=%d", ie1.score, ie1.ia.type);
- ib->n--;
- if(ie1.ia.addr > ie2.ia.addr)
- memmove(b, &ib->data[ib->n * IEntrySize], IEntrySize);
- }
- }
- if((ib->n+1)*IEntrySize > maxdata){
- seterr(EOk, "bucket overflow");
- return TWID32;
- }
- memmove(&ib->data[ib->n * IEntrySize], b, IEntrySize);
- ib->n++;
- ies->n--;
- ies->pos += IEntrySize;
- }
- return buck;
- }
|