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"
  4 a0d146ed 2005-07-12 devnull #include <bio.h>
  5 a0d146ed 2005-07-12 devnull 
  6 a0d146ed 2005-07-12 devnull typedef struct IEBuck	IEBuck;
  7 a0d146ed 2005-07-12 devnull typedef struct IEBucks	IEBucks;
  8 a0d146ed 2005-07-12 devnull 
  9 a0d146ed 2005-07-12 devnull enum
 10 a0d146ed 2005-07-12 devnull {
 11 a0d146ed 2005-07-12 devnull 	ClumpChunks	= 32*1024
 12 a0d146ed 2005-07-12 devnull };
 13 a0d146ed 2005-07-12 devnull 
 14 a0d146ed 2005-07-12 devnull struct IEBuck
 15 a0d146ed 2005-07-12 devnull {
 16 a0d146ed 2005-07-12 devnull 	u32int	head;		/* head of chain of chunks on the disk */
 17 a0d146ed 2005-07-12 devnull 	u32int	used;		/* usage of the last chunk */
 18 a0d146ed 2005-07-12 devnull 	u64int	total;		/* total number of bytes in this bucket */
 19 a0d146ed 2005-07-12 devnull 	u8int	*buf;		/* chunk of entries for this bucket */
 20 a0d146ed 2005-07-12 devnull };
 21 a0d146ed 2005-07-12 devnull 
 22 a0d146ed 2005-07-12 devnull struct IEBucks
 23 a0d146ed 2005-07-12 devnull {
 24 a0d146ed 2005-07-12 devnull 	Part	*part;
 25 a0d146ed 2005-07-12 devnull 	u64int	off;		/* offset for writing data in the partition */
 26 a0d146ed 2005-07-12 devnull 	u32int	chunks;		/* total chunks written to fd */
 27 a0d146ed 2005-07-12 devnull 	u64int	max;		/* max bytes entered in any one bucket */
 28 a0d146ed 2005-07-12 devnull 	int	bits;		/* number of bits in initial bucket sort */
 29 a0d146ed 2005-07-12 devnull 	int	nbucks;		/* 1 << bits, the number of buckets */
 30 a0d146ed 2005-07-12 devnull 	u32int	size;		/* bytes in each of the buckets chunks */
 31 a0d146ed 2005-07-12 devnull 	u32int	usable;		/* amount usable for IEntry data */
 32 a0d146ed 2005-07-12 devnull 	u8int	*buf;		/* buffer for all chunks */
 33 a0d146ed 2005-07-12 devnull 	u8int	*xbuf;
 34 a0d146ed 2005-07-12 devnull 	IEBuck	*bucks;
 35 a0d146ed 2005-07-12 devnull };
 36 a0d146ed 2005-07-12 devnull 
 37 a0d146ed 2005-07-12 devnull #define	U32GET(p)	(((p)[0]<<24)|((p)[1]<<16)|((p)[2]<<8)|(p)[3])
 38 a0d146ed 2005-07-12 devnull #define	U32PUT(p,v)	(p)[0]=(v)>>24;(p)[1]=(v)>>16;(p)[2]=(v)>>8;(p)[3]=(v)
 39 a0d146ed 2005-07-12 devnull 
 40 a0d146ed 2005-07-12 devnull static IEBucks	*initiebucks(Part *part, int bits, u32int size);
 41 a0d146ed 2005-07-12 devnull static int	flushiebuck(IEBucks *ib, int b, int reset);
 42 a0d146ed 2005-07-12 devnull static int	flushiebucks(IEBucks *ib);
 43 a0d146ed 2005-07-12 devnull static u32int	sortiebuck(IEBucks *ib, int b);
 44 a0d146ed 2005-07-12 devnull static u64int	sortiebucks(IEBucks *ib);
 45 a0d146ed 2005-07-12 devnull static int	sprayientry(IEBucks *ib, IEntry *ie);
 46 a0d146ed 2005-07-12 devnull static u32int	readarenainfo(IEBucks *ib, Arena *arena, u64int a, Bloom *b);
 47 a0d146ed 2005-07-12 devnull static u32int	readiebuck(IEBucks *ib, int b);
 48 a0d146ed 2005-07-12 devnull static void	freeiebucks(IEBucks *ib);
 49 a0d146ed 2005-07-12 devnull 
 50 a0d146ed 2005-07-12 devnull /*
 51 a0d146ed 2005-07-12 devnull  * build a sorted file with all IEntries which should be in ix.
 52 a0d146ed 2005-07-12 devnull  * assumes the arenas' directories are up to date.
 53 a0d146ed 2005-07-12 devnull  * reads each, converts the entries to index entries,
 54 a0d146ed 2005-07-12 devnull  * and sorts them.
 55 a0d146ed 2005-07-12 devnull  */
 56 a0d146ed 2005-07-12 devnull u64int
 57 a0d146ed 2005-07-12 devnull sortrawientries(Index *ix, Part *tmp, u64int *base, Bloom *bloom)
 58 a0d146ed 2005-07-12 devnull {
 59 a0d146ed 2005-07-12 devnull 	IEBucks *ib;
 60 a0d146ed 2005-07-12 devnull 	u64int clumps, sorted;
 61 a0d146ed 2005-07-12 devnull 	u32int n;
 62 a0d146ed 2005-07-12 devnull 	int i, ok;
 63 a0d146ed 2005-07-12 devnull 
 64 28b49df3 2006-07-18 devnull /* ZZZ should allow configuration of bits, bucket size */
 65 a0d146ed 2005-07-12 devnull 	ib = initiebucks(tmp, 8, 64*1024);
 66 a0d146ed 2005-07-12 devnull 	if(ib == nil){
 67 a0d146ed 2005-07-12 devnull 		seterr(EOk, "can't create sorting buckets: %r");
 68 a0d146ed 2005-07-12 devnull 		return TWID64;
 69 a0d146ed 2005-07-12 devnull 	}
 70 a0d146ed 2005-07-12 devnull 	ok = 0;
 71 a0d146ed 2005-07-12 devnull 	clumps = 0;
 72 a0d146ed 2005-07-12 devnull 	fprint(2, "constructing entry list\n");
 73 a0d146ed 2005-07-12 devnull 	for(i = 0; i < ix->narenas; i++){
 74 a0d146ed 2005-07-12 devnull 		n = readarenainfo(ib, ix->arenas[i], ix->amap[i].start, bloom);
 75 a0d146ed 2005-07-12 devnull 		if(n == TWID32){
 76 a0d146ed 2005-07-12 devnull 			ok = -1;
 77 a0d146ed 2005-07-12 devnull 			break;
 78 a0d146ed 2005-07-12 devnull 		}
 79 a0d146ed 2005-07-12 devnull 		clumps += n;
 80 a0d146ed 2005-07-12 devnull 	}
 81 a0d146ed 2005-07-12 devnull 	fprint(2, "sorting %lld entries\n", clumps);
 82 a0d146ed 2005-07-12 devnull 	if(ok == 0){
 83 a0d146ed 2005-07-12 devnull 		sorted = sortiebucks(ib);
 84 a0d146ed 2005-07-12 devnull 		*base = (u64int)ib->chunks * ib->size;
 85 a0d146ed 2005-07-12 devnull 		if(sorted != clumps){
 86 a0d146ed 2005-07-12 devnull 			fprint(2, "sorting messed up: clumps=%lld sorted=%lld\n", clumps, sorted);
 87 a0d146ed 2005-07-12 devnull 			ok = -1;
 88 a0d146ed 2005-07-12 devnull 		}
 89 a0d146ed 2005-07-12 devnull 	}
 90 a0d146ed 2005-07-12 devnull 	freeiebucks(ib);
 91 a0d146ed 2005-07-12 devnull 	if(ok < 0)
 92 a0d146ed 2005-07-12 devnull 		return TWID64;
 93 a0d146ed 2005-07-12 devnull 	return clumps;
 94 a0d146ed 2005-07-12 devnull }
 95 a0d146ed 2005-07-12 devnull 
 96 a0d146ed 2005-07-12 devnull #define CHECK(cis)	if(((ulong*)cis)[-4] != 0xA110C09) xabort();
 97 a0d146ed 2005-07-12 devnull 
 98 a0d146ed 2005-07-12 devnull void
 99 a0d146ed 2005-07-12 devnull xabort(void)
100 a0d146ed 2005-07-12 devnull {
101 a0d146ed 2005-07-12 devnull 	int *x;
102 a0d146ed 2005-07-12 devnull 
103 a0d146ed 2005-07-12 devnull 	x = 0;
104 a0d146ed 2005-07-12 devnull 	*x = 0;
105 a0d146ed 2005-07-12 devnull }
106 a0d146ed 2005-07-12 devnull 
107 a0d146ed 2005-07-12 devnull /*
108 a0d146ed 2005-07-12 devnull  * read in all of the arena's clump directory,
109 a0d146ed 2005-07-12 devnull  * convert to IEntry format, and bucket sort based
110 a0d146ed 2005-07-12 devnull  * on the first few bits.
111 a0d146ed 2005-07-12 devnull  */
112 a0d146ed 2005-07-12 devnull static u32int
113 a0d146ed 2005-07-12 devnull readarenainfo(IEBucks *ib, Arena *arena, u64int a, Bloom *b)
114 a0d146ed 2005-07-12 devnull {
115 a0d146ed 2005-07-12 devnull 	IEntry ie;
116 a0d146ed 2005-07-12 devnull 	ClumpInfo *ci, *cis;
117 a0d146ed 2005-07-12 devnull 	u32int clump;
118 a0d146ed 2005-07-12 devnull 	int i, n, ok, nskip;
119 a0d146ed 2005-07-12 devnull 
120 a0d146ed 2005-07-12 devnull 	if(arena->memstats.clumps)
121 a0d146ed 2005-07-12 devnull 		fprint(2, "\tarena %s: %d entries\n", arena->name, arena->memstats.clumps);
122 a0d146ed 2005-07-12 devnull 	else
123 a0d146ed 2005-07-12 devnull 		fprint(2, "[%s] ", arena->name);
124 a0d146ed 2005-07-12 devnull 
125 a0d146ed 2005-07-12 devnull 	cis = MKN(ClumpInfo, ClumpChunks);
126 a0d146ed 2005-07-12 devnull 	ok = 0;
127 a0d146ed 2005-07-12 devnull 	nskip = 0;
128 a0d146ed 2005-07-12 devnull 	memset(&ie, 0, sizeof(IEntry));
129 a0d146ed 2005-07-12 devnull 	for(clump = 0; clump < arena->memstats.clumps; clump += n){
130 a0d146ed 2005-07-12 devnull 		n = ClumpChunks;
131 a0d146ed 2005-07-12 devnull 		if(n > arena->memstats.clumps - clump)
132 a0d146ed 2005-07-12 devnull 			n = arena->memstats.clumps - clump;
133 a0d146ed 2005-07-12 devnull 		if(readclumpinfos(arena, clump, cis, n) != n){
134 a0d146ed 2005-07-12 devnull 			seterr(EOk, "arena directory read failed: %r");
135 a0d146ed 2005-07-12 devnull 			ok = -1;
136 a0d146ed 2005-07-12 devnull 			break;
137 a0d146ed 2005-07-12 devnull 		}
138 a0d146ed 2005-07-12 devnull 
139 a0d146ed 2005-07-12 devnull 		for(i = 0; i < n; i++){
140 a0d146ed 2005-07-12 devnull 			ci = &cis[i];
141 a0d146ed 2005-07-12 devnull 			ie.ia.type = ci->type;
142 a0d146ed 2005-07-12 devnull 			ie.ia.size = ci->uncsize;
143 a0d146ed 2005-07-12 devnull 			ie.ia.addr = a;
144 a0d146ed 2005-07-12 devnull 			a += ci->size + ClumpSize;
145 a0d146ed 2005-07-12 devnull 			ie.ia.blocks = (ci->size + ClumpSize + (1 << ABlockLog) - 1) >> ABlockLog;
146 a0d146ed 2005-07-12 devnull 			scorecp(ie.score, ci->score);
147 a0d146ed 2005-07-12 devnull 			if(ci->type == VtCorruptType){
148 28b49df3 2006-07-18 devnull 				if(0) print("! %V %22lld %3d %5d %3d\n",
149 28b49df3 2006-07-18 devnull 					ie.score, ie.ia.addr, ie.ia.type, ie.ia.size, ie.ia.blocks);
150 a0d146ed 2005-07-12 devnull 				nskip++;
151 a0d146ed 2005-07-12 devnull 			}else
152 a0d146ed 2005-07-12 devnull 				sprayientry(ib, &ie);
153 a0d146ed 2005-07-12 devnull 			markbloomfilter(b, ie.score);
154 a0d146ed 2005-07-12 devnull 		}
155 a0d146ed 2005-07-12 devnull 	}
156 a0d146ed 2005-07-12 devnull 	free(cis);
157 a0d146ed 2005-07-12 devnull 	if(ok < 0)
158 a0d146ed 2005-07-12 devnull 		return TWID32;
159 a0d146ed 2005-07-12 devnull 	return clump - nskip;
160 a0d146ed 2005-07-12 devnull }
161 a0d146ed 2005-07-12 devnull 
162 a0d146ed 2005-07-12 devnull /*
163 a0d146ed 2005-07-12 devnull  * initialize the external bucket sorting data structures
164 a0d146ed 2005-07-12 devnull  */
165 a0d146ed 2005-07-12 devnull static IEBucks*
166 a0d146ed 2005-07-12 devnull initiebucks(Part *part, int bits, u32int size)
167 a0d146ed 2005-07-12 devnull {
168 a0d146ed 2005-07-12 devnull 	IEBucks *ib;
169 a0d146ed 2005-07-12 devnull 	int i;
170 a0d146ed 2005-07-12 devnull 
171 a0d146ed 2005-07-12 devnull 	ib = MKZ(IEBucks);
172 a0d146ed 2005-07-12 devnull 	if(ib == nil){
173 a0d146ed 2005-07-12 devnull 		seterr(EOk, "out of memory");
174 a0d146ed 2005-07-12 devnull 		return nil;
175 a0d146ed 2005-07-12 devnull 	}
176 a0d146ed 2005-07-12 devnull 	ib->bits = bits;
177 a0d146ed 2005-07-12 devnull 	ib->nbucks = 1 << bits;
178 a0d146ed 2005-07-12 devnull 	ib->size = size;
179 a0d146ed 2005-07-12 devnull 	ib->usable = (size - U32Size) / IEntrySize * IEntrySize;
180 a0d146ed 2005-07-12 devnull 	ib->bucks = MKNZ(IEBuck, ib->nbucks);
181 a0d146ed 2005-07-12 devnull 	if(ib->bucks == nil){
182 a0d146ed 2005-07-12 devnull 		seterr(EOk, "out of memory allocation sorting buckets");
183 a0d146ed 2005-07-12 devnull 		freeiebucks(ib);
184 a0d146ed 2005-07-12 devnull 		return nil;
185 a0d146ed 2005-07-12 devnull 	}
186 a0d146ed 2005-07-12 devnull 	ib->xbuf = MKN(u8int, size * ((1 << bits)+1));
187 d67cd5c3 2005-07-19 devnull 	ib->buf = (u8int*)(((uintptr)ib->xbuf+size-1)&~(uintptr)(size-1));
188 a0d146ed 2005-07-12 devnull 	if(ib->buf == nil){
189 a0d146ed 2005-07-12 devnull 		seterr(EOk, "out of memory allocating sorting buckets' buffers");
190 a0d146ed 2005-07-12 devnull 		freeiebucks(ib);
191 a0d146ed 2005-07-12 devnull 		return nil;
192 a0d146ed 2005-07-12 devnull 	}
193 a0d146ed 2005-07-12 devnull 	for(i = 0; i < ib->nbucks; i++){
194 a0d146ed 2005-07-12 devnull 		ib->bucks[i].head = TWID32;
195 a0d146ed 2005-07-12 devnull 		ib->bucks[i].buf = &ib->buf[i * size];
196 a0d146ed 2005-07-12 devnull 	}
197 a0d146ed 2005-07-12 devnull 	ib->part = part;
198 a0d146ed 2005-07-12 devnull 	return ib;
199 a0d146ed 2005-07-12 devnull }
200 a0d146ed 2005-07-12 devnull 
201 a0d146ed 2005-07-12 devnull static void
202 a0d146ed 2005-07-12 devnull freeiebucks(IEBucks *ib)
203 a0d146ed 2005-07-12 devnull {
204 a0d146ed 2005-07-12 devnull 	if(ib == nil)
205 a0d146ed 2005-07-12 devnull 		return;
206 a0d146ed 2005-07-12 devnull 	free(ib->bucks);
207 a0d146ed 2005-07-12 devnull 	free(ib->buf);
208 a0d146ed 2005-07-12 devnull 	free(ib);
209 a0d146ed 2005-07-12 devnull }
210 a0d146ed 2005-07-12 devnull 
211 a0d146ed 2005-07-12 devnull /*
212 a0d146ed 2005-07-12 devnull  * initial sort: put the entry into the correct bucket
213 a0d146ed 2005-07-12 devnull  */
214 a0d146ed 2005-07-12 devnull static int
215 a0d146ed 2005-07-12 devnull sprayientry(IEBucks *ib, IEntry *ie)
216 a0d146ed 2005-07-12 devnull {
217 a0d146ed 2005-07-12 devnull 	u32int n;
218 a0d146ed 2005-07-12 devnull 	int b;
219 a0d146ed 2005-07-12 devnull 
220 a0d146ed 2005-07-12 devnull 	b = hashbits(ie->score, ib->bits);
221 a0d146ed 2005-07-12 devnull 	n = ib->bucks[b].used;
222 a0d146ed 2005-07-12 devnull 	if(n + IEntrySize > ib->usable){
223 a0d146ed 2005-07-12 devnull 		/* should be flushed below, but if flush fails, this can happen */
224 a0d146ed 2005-07-12 devnull 		seterr(EOk, "out of space in bucket");
225 a0d146ed 2005-07-12 devnull 		return -1;
226 a0d146ed 2005-07-12 devnull 	}
227 a0d146ed 2005-07-12 devnull 	packientry(ie, &ib->bucks[b].buf[n]);
228 a0d146ed 2005-07-12 devnull 	n += IEntrySize;
229 a0d146ed 2005-07-12 devnull 	ib->bucks[b].used = n;
230 a0d146ed 2005-07-12 devnull 	if(n + IEntrySize <= ib->usable)
231 a0d146ed 2005-07-12 devnull 		return 0;
232 a0d146ed 2005-07-12 devnull 	return flushiebuck(ib, b, 1);
233 a0d146ed 2005-07-12 devnull }
234 a0d146ed 2005-07-12 devnull 
235 a0d146ed 2005-07-12 devnull /*
236 a0d146ed 2005-07-12 devnull  * finish sorting:
237 a0d146ed 2005-07-12 devnull  * for each bucket, read it in and sort it
238 a0d146ed 2005-07-12 devnull  * write out the the final file
239 a0d146ed 2005-07-12 devnull  */
240 a0d146ed 2005-07-12 devnull static u64int
241 a0d146ed 2005-07-12 devnull sortiebucks(IEBucks *ib)
242 a0d146ed 2005-07-12 devnull {
243 a0d146ed 2005-07-12 devnull 	u64int tot;
244 a0d146ed 2005-07-12 devnull 	u32int n;
245 a0d146ed 2005-07-12 devnull 	int i;
246 a0d146ed 2005-07-12 devnull 
247 a0d146ed 2005-07-12 devnull 	if(flushiebucks(ib) < 0)
248 a0d146ed 2005-07-12 devnull 		return TWID64;
249 a0d146ed 2005-07-12 devnull 	for(i = 0; i < ib->nbucks; i++)
250 a0d146ed 2005-07-12 devnull 		ib->bucks[i].buf = nil;
251 a0d146ed 2005-07-12 devnull 	ib->off = (u64int)ib->chunks * ib->size;
252 a0d146ed 2005-07-12 devnull 	free(ib->xbuf);
253 27d28098 2007-04-21 devnull 
254 a0d146ed 2005-07-12 devnull 	ib->buf = MKN(u8int, ib->max + U32Size);
255 a0d146ed 2005-07-12 devnull 	if(ib->buf == nil){
256 a0d146ed 2005-07-12 devnull 		seterr(EOk, "out of memory allocating final sorting buffer; try more buckets");
257 a0d146ed 2005-07-12 devnull 		return TWID64;
258 a0d146ed 2005-07-12 devnull 	}
259 a0d146ed 2005-07-12 devnull 	tot = 0;
260 a0d146ed 2005-07-12 devnull 	for(i = 0; i < ib->nbucks; i++){
261 a0d146ed 2005-07-12 devnull 		n = sortiebuck(ib, i);
262 a0d146ed 2005-07-12 devnull 		if(n == TWID32)
263 a0d146ed 2005-07-12 devnull 			return TWID64;
264 a0d146ed 2005-07-12 devnull 		if(n != ib->bucks[i].total/IEntrySize)
265 fa325e9b 2020-01-10 cross 			fprint(2, "bucket %d changed count %d => %d\n",
266 a0d146ed 2005-07-12 devnull 				i, (int)(ib->bucks[i].total/IEntrySize), n);
267 a0d146ed 2005-07-12 devnull 		tot += n;
268 a0d146ed 2005-07-12 devnull 	}
269 a0d146ed 2005-07-12 devnull 	return tot;
270 a0d146ed 2005-07-12 devnull }
271 a0d146ed 2005-07-12 devnull 
272 a0d146ed 2005-07-12 devnull /*
273 a0d146ed 2005-07-12 devnull  * sort from bucket b of ib into the output file to
274 a0d146ed 2005-07-12 devnull  */
275 a0d146ed 2005-07-12 devnull static u32int
276 a0d146ed 2005-07-12 devnull sortiebuck(IEBucks *ib, int b)
277 a0d146ed 2005-07-12 devnull {
278 a0d146ed 2005-07-12 devnull 	u32int n;
279 a0d146ed 2005-07-12 devnull 
280 a0d146ed 2005-07-12 devnull 	n = readiebuck(ib, b);
281 a0d146ed 2005-07-12 devnull 	if(n == TWID32)
282 a0d146ed 2005-07-12 devnull 		return TWID32;
283 a0d146ed 2005-07-12 devnull 	qsort(ib->buf, n, IEntrySize, ientrycmp);
284 d67cd5c3 2005-07-19 devnull 	if(writepart(ib->part, ib->off, ib->buf, n*IEntrySize) < 0){
285 a0d146ed 2005-07-12 devnull 		seterr(EOk, "can't write sorted bucket: %r");
286 a0d146ed 2005-07-12 devnull 		return TWID32;
287 a0d146ed 2005-07-12 devnull 	}
288 a0d146ed 2005-07-12 devnull 	ib->off += n * IEntrySize;
289 a0d146ed 2005-07-12 devnull 	return n;
290 a0d146ed 2005-07-12 devnull }
291 a0d146ed 2005-07-12 devnull 
292 a0d146ed 2005-07-12 devnull /*
293 a0d146ed 2005-07-12 devnull  * write out a single bucket
294 a0d146ed 2005-07-12 devnull  */
295 a0d146ed 2005-07-12 devnull static int
296 a0d146ed 2005-07-12 devnull flushiebuck(IEBucks *ib, int b, int reset)
297 a0d146ed 2005-07-12 devnull {
298 a0d146ed 2005-07-12 devnull 	u32int n;
299 a0d146ed 2005-07-12 devnull 
300 a0d146ed 2005-07-12 devnull 	if(ib->bucks[b].used == 0)
301 a0d146ed 2005-07-12 devnull 		return 0;
302 a0d146ed 2005-07-12 devnull 	n = ib->bucks[b].used;
303 a0d146ed 2005-07-12 devnull 	U32PUT(&ib->bucks[b].buf[n], ib->bucks[b].head);
304 a0d146ed 2005-07-12 devnull 	n += U32Size;
305 a0d146ed 2005-07-12 devnull 	USED(n);
306 a0d146ed 2005-07-12 devnull 	if(writepart(ib->part, (u64int)ib->chunks * ib->size, ib->bucks[b].buf, ib->size) < 0){
307 a0d146ed 2005-07-12 devnull 		seterr(EOk, "can't write sorting bucket to file: %r");
308 a0d146ed 2005-07-12 devnull xabort();
309 a0d146ed 2005-07-12 devnull 		return -1;
310 a0d146ed 2005-07-12 devnull 	}
311 a0d146ed 2005-07-12 devnull 	ib->bucks[b].head = ib->chunks++;
312 a0d146ed 2005-07-12 devnull 	ib->bucks[b].total += ib->bucks[b].used;
313 a0d146ed 2005-07-12 devnull 	if(reset)
314 a0d146ed 2005-07-12 devnull 		ib->bucks[b].used = 0;
315 a0d146ed 2005-07-12 devnull 	return 0;
316 a0d146ed 2005-07-12 devnull }
317 a0d146ed 2005-07-12 devnull 
318 a0d146ed 2005-07-12 devnull /*
319 a0d146ed 2005-07-12 devnull  * write out all of the buckets, and compute
320 a0d146ed 2005-07-12 devnull  * the maximum size of any bucket
321 a0d146ed 2005-07-12 devnull  */
322 a0d146ed 2005-07-12 devnull static int
323 a0d146ed 2005-07-12 devnull flushiebucks(IEBucks *ib)
324 a0d146ed 2005-07-12 devnull {
325 a0d146ed 2005-07-12 devnull 	int i;
326 a0d146ed 2005-07-12 devnull 
327 a0d146ed 2005-07-12 devnull 	for(i = 0; i < ib->nbucks; i++){
328 a0d146ed 2005-07-12 devnull 		if(flushiebuck(ib, i, 0) < 0)
329 a0d146ed 2005-07-12 devnull 			return -1;
330 a0d146ed 2005-07-12 devnull 		if(ib->bucks[i].total > ib->max)
331 a0d146ed 2005-07-12 devnull 			ib->max = ib->bucks[i].total;
332 a0d146ed 2005-07-12 devnull 	}
333 a0d146ed 2005-07-12 devnull 	return 0;
334 a0d146ed 2005-07-12 devnull }
335 a0d146ed 2005-07-12 devnull 
336 a0d146ed 2005-07-12 devnull /*
337 a0d146ed 2005-07-12 devnull  * read in the chained buffers for bucket b,
338 a0d146ed 2005-07-12 devnull  * and return it's total number of IEntries
339 a0d146ed 2005-07-12 devnull  */
340 a0d146ed 2005-07-12 devnull static u32int
341 a0d146ed 2005-07-12 devnull readiebuck(IEBucks *ib, int b)
342 a0d146ed 2005-07-12 devnull {
343 a0d146ed 2005-07-12 devnull 	u32int head, m, n;
344 a0d146ed 2005-07-12 devnull 
345 a0d146ed 2005-07-12 devnull 	head = ib->bucks[b].head;
346 a0d146ed 2005-07-12 devnull 	n = 0;
347 a0d146ed 2005-07-12 devnull 	m = ib->bucks[b].used;
348 a0d146ed 2005-07-12 devnull 	if(m == 0)
349 a0d146ed 2005-07-12 devnull 		m = ib->usable;
350 28b49df3 2006-07-18 devnull 	if(0) if(ib->bucks[b].total)
351 27d28098 2007-04-21 devnull 		fprint(2, "\tbucket %d: %lld entries\n", b, ib->bucks[b].total/IEntrySize);
352 a0d146ed 2005-07-12 devnull 	while(head != TWID32){
353 d67cd5c3 2005-07-19 devnull 		if(readpart(ib->part, (u64int)head * ib->size, &ib->buf[n], m+U32Size) < 0){
354 a0d146ed 2005-07-12 devnull 			seterr(EOk, "can't read index sort bucket: %r");
355 a0d146ed 2005-07-12 devnull 			return TWID32;
356 a0d146ed 2005-07-12 devnull 		}
357 a0d146ed 2005-07-12 devnull 		n += m;
358 a0d146ed 2005-07-12 devnull 		head = U32GET(&ib->buf[n]);
359 a0d146ed 2005-07-12 devnull 		m = ib->usable;
360 a0d146ed 2005-07-12 devnull 	}
361 a0d146ed 2005-07-12 devnull 	if(n != ib->bucks[b].total)
362 a0d146ed 2005-07-12 devnull 		fprint(2, "\tbucket %d: expected %d entries, got %d\n",
363 a0d146ed 2005-07-12 devnull 			b, (int)ib->bucks[b].total/IEntrySize, n/IEntrySize);
364 a0d146ed 2005-07-12 devnull 	return n / IEntrySize;
365 a0d146ed 2005-07-12 devnull }