1 #include "stdinc.h"
2 #include "dat.h"
3 #include "fns.h"
4 
5 struct IEStream
6 {
7 	Part	*part;
8 	u64int	off;		/* read position within part */
9 	u64int	n;		/* number of valid ientries left to read */
10 	u32int	size;		/* allocated space in buffer */
11 	u8int	*buf;
12 	u8int	*pos;		/* current place in buffer */
13 	u8int	*epos;		/* end of valid buffer contents */
14 };
15 
16 IEStream*
17 initiestream(Part *part, u64int off, u64int clumps, u32int size)
18 {
19 	IEStream *ies;
20 
21 //ZZZ out of memory?
22 	ies = MKZ(IEStream);
23 	ies->buf = MKN(u8int, size);
24 	ies->epos = ies->buf;
25 	ies->pos = ies->epos;
26 	ies->off = off;
27 	ies->n = clumps;
28 	ies->size = size;
29 	ies->part = part;
30 	return ies;
31 }
32 
33 void
34 freeiestream(IEStream *ies)
35 {
36 	if(ies == nil)
37 		return;
38 	free(ies->buf);
39 	free(ies);
40 }
41 
42 static u8int*
43 peekientry(IEStream *ies)
44 {
45 	u32int n, nn;
46 
47 	n = ies->epos - ies->pos;
48 	if(n < IEntrySize){
49 		memmove(ies->buf, ies->pos, n);
50 		ies->epos = &ies->buf[n];
51 		ies->pos = ies->buf;
52 		nn = ies->size;
53 		if(nn > ies->n * IEntrySize)
54 			nn = ies->n * IEntrySize;
55 		nn -= n;
56 		if(nn == 0)
57 			return nil;
58 		if(readpart(ies->part, ies->off, ies->epos, nn) < 0){
59 			seterr(EOk, "can't read sorted index entries: %r");
60 			return nil;
61 		}
62 		ies->epos += nn;
63 		ies->off += nn;
64 	}
65 	return ies->pos;
66 }
67 
68 static u32int
69 iebuck(Index *ix, u8int *b)
70 {
71 	return hashbits(b, 32) / ix->div;
72 }
73 
74 u32int
75 buildbucket(Index *ix, IEStream *ies, IBucket *ib)
76 {
77 	IEntry ie1, ie2;
78 	u8int *b;
79 	u32int buck;
80 
81 	buck = TWID32;
82 	ib->n = 0;
83 	ib->depth = 0;
84 	while(ies->n){
85 		b = peekientry(ies);
86 		if(b == nil)
87 			return TWID32;
88 //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 		if(ib->n == 0)
90 			buck = iebuck(ix, b);
91 		else{
92 			if(buck != iebuck(ix, b))
93 				break;
94 			if(ientrycmp(&ib->data[(ib->n - 1)* IEntrySize], b) == 0){
95 				/*
96 				 * guess that the larger address is the correct one to use
97 				 */
98 				unpackientry(&ie1, &ib->data[(ib->n - 1)* IEntrySize]);
99 				unpackientry(&ie2, b);
100 				seterr(EOk, "duplicate index entry for score=%V type=%d\n", ie1.score, ie1.ia.type);
101 				ib->n--;
102 				if(ie1.ia.addr > ie2.ia.addr)
103 					memmove(b, &ib->data[ib->n * IEntrySize], IEntrySize);
104 			}
105 		}
106 		memmove(&ib->data[ib->n * IEntrySize], b, IEntrySize);
107 		ib->n++;
108 		ies->n--;
109 		ies->pos += IEntrySize;
110 	}
111 	return buck;
112 }