local-to-global.c 23.5 KB
Newer Older
inge's avatar
inge committed
1
2
3
4
5
6
7
/*
 * File: local_to_global.c
 *
 * Copyright 1996 Inge Wallin, Per Cederqvist
 */


8
9
10
11
12
13
14
#include <assert.h>
#ifdef HAVE_STDLIB_H
#  include <stdlib.h>
#endif
#ifndef NULL
#  include <stdio.h>
#endif
15
16
17
18
19
20

#include <sys/types.h>
#include <time.h>

#include "s-string.h"

inge's avatar
inge committed
21
#include "kom-types.h"
Per Cederqvist's avatar
Per Cederqvist committed
22
#include "local-to-global.h"
23
24
25
#include "log.h"
#include "ram-parse.h"
#include "ram-output.h"
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include "lyskomd.h"
#include "server/smalloc.h"

/* The test suite requires L2G_BLOCKSIZE to be 10, but that small
   blocks will result in far too much malloc-overhead.  A value of at
   least 100 is probably needed for reasonable performance. */
/* FIXME: make this a global variable that is initialized to, say,
   250, and that the test suite program can change to 10 before it
   does anything else.  */
#define  L2G_BLOCKSIZE   10	     /* Doesn't seem to matter much. */


struct l2g_block_info {
    /* An index into key_block and value_block that indicates the
       first free spot.  This can also be thought of as the number of
       entries in key_block and value_block that are actually in use. */
    int first_free;

    /* Number of entries in the block that contain the value 0.  For
       purposes of calculating this value, data past the end of the
       block is counted as zeroes. */
    int zeroes;

    /* First local text no in this block. */
    Local_text_no start;

    /* NULL if this is a dense block, or a block of L2G_BLOCKSIZE
       Local_text_nos if this is a sparse block. */
    Local_text_no *key_block;

    /* A block of L2G_BLOCKSIZE Text_nos. */
    Text_no *value_block;
};
inge's avatar
inge committed
59
60
61
62
63
64
65


/* ================================================================ */
/* ====                     Static functions                   ==== */
/* ================================================================ */


66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
static inline int
is_dense(const struct l2g_block_info *binfo)
{
    return binfo->key_block == NULL;
}

static inline int
is_empty(const struct l2g_block_info *binfo)
{
    return binfo->zeroes == L2G_BLOCKSIZE;
}

static inline Local_text_no
key_value(const struct l2g_block_info *binfo,
	  int index)
{
    if (is_dense(binfo))
	return binfo->start + index;
    else
	return binfo->key_block[index];
}


static inline int
sparse_skip_deleted(const struct l2g_block_info *binfo,
		    int i)
{
    while (i < binfo->first_free && binfo->value_block[i] == 0)
	++i;

    return i;
}


/* Search for LNO in BINFO, and return the index for it.  BINFO must
   be a non-empty sparse block.  If LNO isn't present in the block
   this will return the index of next higher entry.  If LNO is larger
   than the last entry, the index past the largest entry will be
   returned.  This function never returns the index of a deleted entry. */
static inline int
sparse_locate_value(const struct l2g_block_info *binfo,
		    Local_text_no lno)
{
    int i;

    assert(!is_empty(binfo));
    assert(!is_dense(binfo));
    
    /* FIXME: implement a binary search instead. */
    for (i = 0; i < binfo->first_free && binfo->key_block[i] < lno; ++i)
	continue;

    /* Skip any lingering deleted entries. */
    i = sparse_skip_deleted(binfo, i);

    assert(i == binfo->first_free || binfo->key_block[i] >= lno);
    assert(i == binfo->first_free || binfo->value_block[i] != 0);

    return i;
}

static void
sparse_compact(struct l2g_block_info *binfo)
{
    int from, to;

    if (binfo->first_free + binfo->zeroes == L2G_BLOCKSIZE)
	return;

    assert(binfo->first_free + binfo->zeroes > L2G_BLOCKSIZE);

    for (from = to = 0; from < binfo->first_free; ++from)
	if (binfo->value_block[from] != 0)
	{
	    if (from != to)
	    {
		binfo->value_block[to] = binfo->value_block[from];
		binfo->key_block[to] = binfo->key_block[from];
	    }
	    ++to;
	}

    binfo->first_free = to;
    assert(binfo->first_free + binfo->zeroes == L2G_BLOCKSIZE);
}


inge's avatar
inge committed
153
154
155
156
157
158
159
160
/*
 * Add a new block to the Local_to_global L2G.
 * Since we always add consecutively, we always start out by making 
 * a new block dense.
 *
 * Return a pointer to the newly created block info.
 */

161
static struct l2g_block_info *
inge's avatar
inge committed
162
163
add_block(Local_to_global *l2g)
{
164
165
166
167
    struct l2g_block_info  * binfo;
#ifndef NDEBUG
    int i;
#endif
inge's avatar
inge committed
168
169
170

    /* Realloc the block pointer array. */
    l2g->num_blocks++;
171
172
    l2g->blocks = srealloc(l2g->blocks,
			   l2g->num_blocks * sizeof(struct l2g_block_info));
inge's avatar
inge committed
173
174
175
176
177

    /* Create a new block info and fill it in. */
    binfo = &(l2g->blocks[l2g->num_blocks - 1]);
    binfo->first_free  = 0;
    binfo->zeroes      = L2G_BLOCKSIZE;
178
179
180
#ifndef NDEBUG
    binfo->start       = 0xdeadbeef;
#endif
inge's avatar
inge committed
181
    binfo->key_block   = NULL;
182
183
184
185
186
187
    binfo->value_block = smalloc(L2G_BLOCKSIZE * sizeof(Text_no));
    
#ifndef NDEBUG
    for (i = 0; i < L2G_BLOCKSIZE; ++i)
	binfo->value_block[i] = 0xdeadbeef;
#endif
inge's avatar
inge committed
188
189
190
191
192

    return binfo;
}


193
194
195
196
197
198
199
/*
 * Delete a block from the Local_to_global L2G.  The pointer BINFO
 * points at the block, which is supposed to be empty.
 */

static void
delete_block(Local_to_global *l2g, 
200
	     struct l2g_block_info  *binfo)
201
{
202
203
    assert(is_empty(binfo));

204
205
    /* Remove the blocks from the Block Info */
    if (binfo->key_block != NULL)
206
207
	sfree(binfo->key_block);
    sfree(binfo->value_block);
208
209
210
211
212

    /* Compact the remaining blocks. */
    while (++binfo < l2g->blocks + l2g->num_blocks)
	*(binfo - 1) = *binfo;
    l2g->num_blocks--;
213
214
    l2g->blocks = srealloc(l2g->blocks,
			   l2g->num_blocks * sizeof(struct l2g_block_info));
215
216
217
}


inge's avatar
inge committed
218
219
220
221
/*
 * Make a sparse block from a dense one.
 */
static void
222
make_sparse(struct l2g_block_info *binfo)
inge's avatar
inge committed
223
224
225
226
{
    int  next;
    int  i;

227
228
    assert(is_dense(binfo));

inge's avatar
inge committed
229
    /* Allocate the room for the key block. */
230
231
232
233
234
    binfo->key_block = smalloc(L2G_BLOCKSIZE * sizeof(Local_text_no));
#ifndef NDEBUG
    for (i = 0; i < L2G_BLOCKSIZE; ++i)
	binfo->key_block[i] = 0xdeadbeef;
#endif
inge's avatar
inge committed
235
236
237

    /* Compact the block. */
    next = 0;
238
239
240
    for (i = 0; i < binfo->first_free; ++i)
	if (binfo->value_block[i] != 0)
	{
inge's avatar
inge committed
241
242
243
244
245
246
247
248
249
250
251
252
253
254
	    binfo->key_block[next]   = binfo->start + i;
	    binfo->value_block[next] = binfo->value_block[i];
	    next++;
	}

    /* Set the rest of the fields. */
    binfo->first_free = next;
    binfo->zeroes = L2G_BLOCKSIZE - next;
}


/*
 * Find the block where the local text no LNO is and return a pointer
 * to it.  Returning a pointer does not mean that the text still exists,
255
256
257
 * so a search within the block must also be done later.  If LNO is
 * smaller than the smallest number in the structure a pointer to the
 * first block will be returned.
inge's avatar
inge committed
258
 * 
259
260
 * Return NULL if LNO is bigger than the highest number in the
 * structure, or if the structure is empty.
inge's avatar
inge committed
261
262
 */

263
264
static const struct l2g_block_info *
find_block(const Local_to_global *l2g, Local_text_no lno)
inge's avatar
inge committed
265
{
266
    const struct l2g_block_info  * binfo;
inge's avatar
inge committed
267

Per Cederqvist's avatar
Per Cederqvist committed
268
269
270
271
    /* If empty, the number can not be in here. */
    if (l2g->num_blocks == 0)
	return NULL;

inge's avatar
inge committed
272
273
274
275
    /* Let binfo point to the last block. */
    binfo = &(l2g->blocks[l2g->num_blocks - 1]);

    /* If lno is greater than the biggest local number, return NULL. */
276
277
278
    assert(binfo->first_free > 0);
    if (lno > key_value(binfo, binfo->first_free - 1))
	return NULL;
inge's avatar
inge committed
279
280
281

    /* Find the block where lno *could* be. */
    /* FIXME: Binary search? */
282
283
    while (binfo > l2g->blocks)
    {
inge's avatar
inge committed
284
285
286
287
288
	if (lno >= binfo->start)
	    return binfo;
	binfo--;
    }

Per Cederqvist's avatar
Per Cederqvist committed
289
    return binfo;
inge's avatar
inge committed
290
291
292
}


293
294
295
296
297
298
299
/* Find the first local text number higher than LNO and return it.
   Return 0 if LNO is higher than any local text number in the
   structure.  The block where the returned value was found is stored
   in BINFO_OUT, and the position within the block is stored in
   INDEX_OUT.  BINFO_OUT and INDEX_OUT are only filled in if the
   return value is non-zero.  */

inge's avatar
inge committed
300
static Local_text_no
301
302
find_block_index_key(const Local_to_global *l2g, Local_text_no lno,
		     const struct l2g_block_info **binfo_out,
inge's avatar
inge committed
303
304
		     int             *index_out)
{
305
    const struct l2g_block_info  * binfo;
inge's avatar
inge committed
306
307
308
309
310
311
312
    int               i;

    /* If the number is not to be found, return 0. */
    binfo = find_block(l2g, lno);
    if (binfo == NULL)
	return 0;

313
314
315
316
317
318
319
320
321
322
323
324
    /* If lno is lower than the first existing entry, return the first
       existing entry.  The search in the first block is performed the
       same way as when no entry was found after LNO in binfo. */
    if (lno >= binfo->start)
    {
	/* Check the found block.  See if there is another entry after
	   the entry for LNO.  If so, return it. */
	if (is_dense(binfo))
	{
	    for (i = lno - binfo->start + 1; i < binfo->first_free; ++i)
		if (binfo->value_block[i] != 0)
		{
inge's avatar
inge committed
325
326
327
328
329
		    *binfo_out = binfo;
		    *index_out = i;

		    return binfo->start + i;
		}
330
331
332
333
334
335
336
337
338
339
340
	}
	else
	{
	    i = sparse_locate_value(binfo, lno);
	    if (i < binfo->first_free && binfo->key_block[i] == lno)
		++i;
	    i = sparse_skip_deleted(binfo, i);
	    if (i < binfo->first_free)
	    {
		*binfo_out = binfo;
		*index_out = i;
inge's avatar
inge committed
341

342
		return binfo->key_block[i];
inge's avatar
inge committed
343
344
345
346
347
348
349
350
351
352
	    }
	}
	binfo++;
    }

    /*
     * If the block didn't contain anything more, try next block
     * until there are no more blocks.  Blocks can be completely
     * empty due to removals of entries.
     */
353
354
    for (; binfo < l2g->blocks + l2g->num_blocks; ++binfo)
    {
inge's avatar
inge committed
355
	/* If the block contains anything at all, get the item. */
356
357
358
359
360
361
362
363
	if (!is_empty(binfo))
	{
	    for (i = 0; i < binfo->first_free; ++i)
		if (binfo->value_block[i] != 0)
		{
		    *binfo_out = binfo;
		    *index_out = i;
		    return key_value(binfo, i);
inge's avatar
inge committed
364
		}
365
	    restart_kom("find_block_index_key found nothing\n");
inge's avatar
inge committed
366
367
368
369
370
371
	}
    }

    return 0;
}

372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
static void
join_range(Local_to_global *l2g,
	   struct l2g_block_info *first,
	   struct l2g_block_info *last)
{
    int next;
    int i;
    struct l2g_block_info *binfo;

    assert(first < last);
    assert(l2g->blocks <= first && first < l2g->blocks + l2g->num_blocks);
    assert(l2g->blocks <= last  && last  < l2g->blocks + l2g->num_blocks);

    if (is_dense(first))
	make_sparse(first);
    else
	sparse_compact(first);

    next = first->first_free;
    for (binfo = first + 1; binfo <= last; ++binfo)
    {
	for (i = 0; i < binfo->first_free; ++i)
	    if (binfo->value_block[i] != 0)
	    {
		first->value_block[next] = binfo->value_block[i];
		first->key_block[next]  = key_value(binfo, i);
		next++;
	    }
	if (!is_dense(binfo))
	    sfree(binfo->key_block);
	sfree(binfo->value_block);
    }

    while (binfo < l2g->blocks + l2g->num_blocks)
    {
407
	assert(binfo - (last - first) > first);
408
409
410
411
412
413
414
	*(binfo - (last - first)) = *binfo;
	++binfo;
    }

    assert(next <= L2G_BLOCKSIZE);
    first->first_free = next;
    first->zeroes = L2G_BLOCKSIZE - next;
415
416
417
418

    l2g->num_blocks -= last - first;
    l2g->blocks = srealloc(l2g->blocks,
			   l2g->num_blocks * sizeof(struct l2g_block_info));
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
}
    
    
static int
join_blocks(Local_to_global *l2g,
	    struct l2g_block_info *binfo)
{
    int zeroes;
    int gain;
    int best;
    int i;

    if (binfo->zeroes == 0)
	/* This block is full. */
	return 0;

    /* Note: on rare occasions we might be able to create one dense
       block from two (dense or sparse) blocks or one sparse block.
       We don't bother.  The gain would probably be small, and it
       would complicate the algorithm significantly.  */

    zeroes = L2G_BLOCKSIZE;
    gain = 0;
    best = 0;

    for (i = 0; zeroes > 0 && i <= binfo - l2g->blocks; ++i)
    {
	zeroes -= (L2G_BLOCKSIZE - (binfo-i)->zeroes);
	gain += (is_dense(binfo-i) ? 1 : 2);
	if (gain > 2 && zeroes >= 0)
	    best = i;
    }

    if (best > 0)
    {
	join_range(l2g, binfo - best, binfo);
	return 1;
    }

    zeroes = L2G_BLOCKSIZE;
    gain = 0;
    best = 0;
    for (i = 0; zeroes > 0 && i < l2g->num_blocks - (binfo - l2g->blocks); ++i)
    {
	zeroes -= (L2G_BLOCKSIZE - (binfo+i)->zeroes);
	gain += (is_dense(binfo+i) ? 1 : 2);
	if (gain > 2 && zeroes >= 0)
	    best = i;
    }

    if (best > 0)
    {
	join_range(l2g, binfo, binfo + best);
	return 1;
    }

    return 0;
}
inge's avatar
inge committed
477

inge's avatar
inge committed
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
/* ================================================================ */
/* ====                Outside accessible functions            ==== */
/* ================================================================ */


/*
 * Remove all memory associated with the structure.
 */

void
l2g_destruct(Local_to_global *l2g)
{
    l2g_clear(l2g);
}


/*
 * Initialize an empty piece of memory to be a Local to global structure.
 */

void
l2g_init(Local_to_global *l2g)
{
    /* Initialize the main structure */
    l2g->num_blocks = 0;
503
    l2g->first_unused = 1;
inge's avatar
inge committed
504
505
506
507
508
509
510
511
512
513
514
    l2g->blocks = NULL;
}


/*
 * Make L2G into an empty structure, ready to put the first data into it.
 */

void
l2g_clear(Local_to_global *l2g)
{
515
    struct l2g_block_info  * binfo;
inge's avatar
inge committed
516
517
518
    int               i;

    /* Free the block info structures. */
Per Cederqvist's avatar
Per Cederqvist committed
519
    binfo = l2g->blocks;
520
521
    for (i = 0; i < l2g->num_blocks; ++i)
    {
inge's avatar
inge committed
522
	if (binfo->key_block != NULL)
523
524
	    sfree(binfo->key_block);
	sfree(binfo->value_block);
inge's avatar
inge committed
525
526
527
528

	binfo++;
    }

529
    /* Free the block pointers. */
Per Cederqvist's avatar
Per Cederqvist committed
530
    l2g->num_blocks = 0;
531
532
533
534
    l2g->first_unused = 1;
    if (l2g->blocks != NULL)
    {
	sfree(l2g->blocks);
535
536
	l2g->blocks = NULL;
    }
inge's avatar
inge committed
537
538
539
540
541
542
543
544
545
}


/*
 * Copy everything from one l2g structure (FROM) into another (TO).
 * TO has to be an initialized structure.
 */

void
546
l2g_copy(Local_to_global *dest, const Local_to_global *src)
inge's avatar
inge committed
547
{
548
549
    const struct l2g_block_info *binfo;
    int i;
inge's avatar
inge committed
550
551

    /* FIXME: More efficient code */
552
    l2g_clear(dest);
inge's avatar
inge committed
553

554
555
556
557
558
    for (binfo = src->blocks; binfo < src->blocks + src->num_blocks; ++binfo)
	for (i = 0; i < binfo->first_free; ++i)
	    l2g_append(dest, key_value(binfo, i), binfo->value_block[i]);
    assert(src->first_unused >= dest->first_unused);
    dest->first_unused = src->first_unused;
inge's avatar
inge committed
559
560
561
562
563
}


/*
 * Append the pair LNO-TNO.  LNO has to be bigger than the last local 
564
 * number in the structure.
inge's avatar
inge committed
565
 */
566
567
568

typedef Local_text_no Local_text_no_iter;

inge's avatar
inge committed
569
570
571
572
573
void
l2g_append(Local_to_global *l2g, 
	   Local_text_no    lno,
	   Text_no          tno)
{
574
    struct l2g_block_info  * binfo;
575
    Local_text_no_iter ix;
inge's avatar
inge committed
576

577
578
579
580
581
582
583
584
585
586
    if (lno < l2g->first_unused)
    {
	log("l2g_append: won't add %lu<%lu> when first_unused=%lu\n",
	    (unsigned long)tno, (unsigned long)lno,
	    (unsigned long)l2g->first_unused);
	return;
    }

    l2g->first_unused = lno + 1;
	    
Per Cederqvist's avatar
Per Cederqvist committed
587
    /* Don't add anything if tno == 0. */
inge's avatar
inge committed
588
589
590
    if (tno == 0)
	return;

591
592
    if (l2g->num_blocks == 0)
    {
Per Cederqvist's avatar
Per Cederqvist committed
593
594
	/* If totally empty, add the first block and set binfo to it. */
	binfo = add_block(l2g);
inge's avatar
inge committed
595
	binfo->start = lno;
596
597
598
    }
    else
    {
Per Cederqvist's avatar
Per Cederqvist committed
599
600
601
	/* else let binfo point to the last block. */
	binfo = &(l2g->blocks[l2g->num_blocks - 1]);
    }
inge's avatar
inge committed
602

603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
    /* Try to make room for the new data in the last block (pointed to
       by binfo).  If that fails, allocate a new block and let binfo
       point to it. */
    if (is_dense(binfo))
    {
	if (lno - binfo->start >= L2G_BLOCKSIZE)
	{
	    /* The last block is a dense block, and this text does not
	       fit in it.  Or is there anything we can do to make it fit?  */

	    /* First of all, a little optimization: If the block
	       contains no entries, all entries in it have been
	       deleted.  We can then reuse the block and pretend it is
	       a newly allocated block.  */
	    if (is_empty(binfo))
	    {
		binfo->first_free = 0;
		binfo->start      = 0;
inge's avatar
inge committed
621
	    }
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
	    else if (binfo->zeroes >= L2G_BLOCKSIZE / 2)
		/* Arbitrary limit: make the block sparse if at least
		   half of it contains zeroes.  (Remeber that any
		   unused entries past binfo->first_free are counted
		   in binfo->zeroes). */
		make_sparse(binfo);
	    else
		/* There is no way to make room in the last block, so
		   allocate a new one.  (There *could* be ways to make
		   this entry fit into the last block: if the next to
		   last block is sparse and has room for an entry, we
		   might be able to slide the last block, and fit in
		   the new entry.  However, we never move data between
		   blocks.  That would be too complex and error-prone,
		   and the gain would be very small.) */
		binfo = add_block(l2g);
inge's avatar
inge committed
638
639
	}
    }
640
641
642
643
644
645
646
    else
    {
	/* The last block was sparse. */
	sparse_compact(binfo);
	if (binfo->first_free == L2G_BLOCKSIZE)
	    binfo = add_block(l2g);
    }
inge's avatar
inge committed
647

648
649
    /* Enter the new value into the last block. */
    if (binfo->first_free == 0)
inge's avatar
inge committed
650
651
	binfo->start = lno;

652
653
    if (is_dense(binfo))
    {
654
655
	for (ix = binfo->first_free; ix < lno - binfo->start; ++ix)
	    binfo->value_block[ix] = 0;
inge's avatar
inge committed
656
657
	binfo->value_block[lno - binfo->start] = tno;
	binfo->first_free = lno - binfo->start + 1;
658
659
660
    }
    else
    {
inge's avatar
inge committed
661
662
663
664
665
666
667
668
669
670
671
672
673
674
	binfo->key_block  [binfo->first_free] = lno;
	binfo->value_block[binfo->first_free] = tno;
	binfo->first_free++;
    }
    
    binfo->zeroes--;
}


/*
 * Delete the local text LNO from the structure L2G.
 */

void
675
676
l2g_delete(Local_to_global *l2g,
	   Local_text_no lno)
inge's avatar
inge committed
677
{
678
679
680
    struct l2g_block_info *binfo;
    int i;
    
inge's avatar
inge committed
681
    /* Find block where LNO might be and return if not there. */
682
    binfo = /*const_cast*/(struct l2g_block_info*)find_block(l2g, lno);
inge's avatar
inge committed
683
684
685
686
    if (binfo == NULL)
	return;

    /* Go through the block where it might be and delete LNO */
687
688
    if (is_dense(binfo))
    {
inge's avatar
inge committed
689
	if (binfo->start <= lno && lno < binfo->start + L2G_BLOCKSIZE)
690
691
692
	    if (binfo->value_block[lno - binfo->start] != 0)
	    {
		binfo->value_block[lno - binfo->start] = 0;
inge's avatar
inge committed
693
694
		binfo->zeroes++;
	    }
695
696
697
698
699
700
701
702
703
    }
    else
    {
	i = sparse_locate_value(binfo, lno);
	if (i < binfo->first_free && binfo->key_block[i] == lno)
	{
	    assert(binfo->value_block[i] != 0); /* See sparse_locate_value. */
	    binfo->value_block[i] = 0;
	    binfo->zeroes++;
inge's avatar
inge committed
704
705
	}
    }
706

707
708
709
    /* Delete the block if it became empty. */
    if (is_empty(binfo))
    {
710
	delete_block(l2g, binfo);
711
712
713
714
715
716
717
718
719
720
721
722
	return;
    }

    /* Check if we can save space by joining adjoining blocks. */
    if (!join_blocks(l2g, binfo))
	/* Could not join.  Compact this block if it is a sparse block
           with more than half of the entries zeroes.  */
	if (!is_dense(binfo)
	    && binfo->zeroes + binfo->first_free/2 > L2G_BLOCKSIZE)
	{
	    sparse_compact(binfo);
	}
inge's avatar
inge committed
723
724
725
726
727
728
729
730
731
}


/*
 * Lookup the global text number which corresponds to the local text
 * number LNO.
 */

Text_no
732
733
l2g_lookup(const Local_to_global *l2g,
	   Local_text_no lno)
inge's avatar
inge committed
734
{
735
    const struct l2g_block_info  * binfo;
inge's avatar
inge committed
736
737
738
739
740
741
    int               i;

    binfo = find_block(l2g, lno);
    if (binfo == NULL)
	return 0;

742
743
744
    if (is_dense(binfo))
    {
	if (binfo->start <= lno && lno < binfo->start + binfo->first_free)
inge's avatar
inge committed
745
	    return binfo->value_block[lno - binfo->start];
746
747
748
749
750
751
    }
    else
    {
	i = sparse_locate_value(binfo, lno);
	if (i < binfo->first_free && binfo->key_block[i] == lno)
	    return binfo->value_block[i];
inge's avatar
inge committed
752
753
754
755
756
757
758
    }

    return 0;
}


/*
Per Cederqvist's avatar
Per Cederqvist committed
759
 * Return the next local text number which is not 
inge's avatar
inge committed
760
 */
Per Cederqvist's avatar
Per Cederqvist committed
761

inge's avatar
inge committed
762
Local_text_no
763
764
l2g_next_key(const Local_to_global *l2g,
	     Local_text_no lno)
inge's avatar
inge committed
765
{
766
    const struct l2g_block_info  * binfo;
Per Cederqvist's avatar
Per Cederqvist committed
767
768
    int               i;

inge's avatar
inge committed
769
    return find_block_index_key(l2g, lno, &binfo, &i);
inge's avatar
inge committed
770
771
772
}


773
774
775
776
777
Local_text_no
l2g_first_appendable_key(const Local_to_global *l2g)
{
    return l2g->first_unused;
}
inge's avatar
inge committed
778
779

void
780
781
l2g_delete_global_in_sorted(Local_to_global *l2g,
			    Text_no tno)
inge's avatar
inge committed
782
{
783
784
785
786
787
788
789
790
791
792
793
    /* This implementation performs a linear search through the list,
       but since we know that both the key and the data are sorted in
       ascending order we could do a binary search instead.
       FIXME: profile the code and se if it is worthwhile to implement
       something fancier.  */

    L2g_iterator iter;

    for (l2gi_searchall(&iter, l2g); !iter.search_ended; l2gi_next(&iter))
	if (iter.tno == tno)
	{
794
795
796
797
798
799
800
801
802
	    L;
    binfo->value_block = smalloc(L2G_BLOCKSIZE * sizeof(Text_no));
    
#ifndef NDEBUG
    for (i = 0; i < L2G_BLOCKSIZE; ++i)
	binfo->value_block[i] = 0xdeadbeef;
#endif

    return binfo;
inge's avatar
inge committed
803
804
805
806
}


/*
807
808
 * Delete a block from the Local_to_global L2G.  The pointer BINFO
 * points at the block, which is supposed to be empty.
inge's avatar
inge committed
809
810
 */

811
812
813
static void
delete_block(Local_to_global *l2g, 
	     struct l2g_block_info  *binfo)
inge's avatar
inge committed
814
{
815
    assert(is_empty(binfo));
inge's avatar
inge committed
816

817
818
819
820
    /* Remove the blocks from the Block Info */
    if (binfo->key_block != NULL)
	sfree(binfo->key_block);
    sfree(binfo->value_block);
inge's avatar
inge committed
821

822
823
824
825
826
827
    /* Compact the remaining blocks. */
    while (++binfo < l2g->blocks + l2g->num_blocks)
	*(binfo - 1) = *binfo;
    l2g->num_blocks--;
    l2g->blocks = srealloc(l2g->blocks,
			   l2g->num_blocks * sizeof(struct l2g_block_info));
inge's avatar
inge committed
828
829
830
831
}


/*
832
 * Make a sparse block from a dense one.
inge's avatar
inge committed
833
 */
834
835
static void
make_sparse(struct l2g_block_info *binfo)
inge's avatar
inge committed
836
{
837
838
839
840
841
842
    int  next;
    int  i;

    assert(is_dense(binfo));

    /* Allocate the room for the key bl int            c;
843
844
    Local_text_no  lno;
    Text_no        tno;
845
846
847
    Local_text_no  first_unused;

    l2g_clear(l2g);
848
849
850

    /* Read past the start marker */
    fskipwhite(fp);
851
852
    if ( (c = getc(fp)) == EOF || c != '[')
    {
853
	log("l2g_read() failed at pos %lu.\n", (unsigned long) ftell(fp));
854
	return FAILURE;
855
856
    }

857
858
859
    fskipwhite(fp);
    first_unused = fparse_long(fp);

860
    /* Read pairs of numbers until the EOL (end-of-l2g :-) ) marker is read. */
861
862
    while (1)
    {
863
864
865
	fskipwhite(fp);
	if ((c = getc(fp)) == ']')
	    break;
866
867
868
869
870
871
872
873
874

	if (c == EOF)
	{
	    log("l2g_read(): unexpected EOF at pos %lu.\n",
		(unsigned long) ftell(fp));
	    return FAILURE;
	}
	
	ungetc(c, fp);
875
876
877
878
879

	lno = (Local_text_no) fparse_long(fp);
	tno = (Text_no)       fparse_long(fp);
	l2g_append(l2g, lno, tno);
    }
880
881
882
883
	
    assert(first_unused >= l2g->first_unused);
    l2g->first_unused = first_unused;
    return OK;
inge's avatar
inge committed
884
885
886
887
}


/*
888
 * Print the structure to the file FILE.
inge's avatar
inge committed
889
890
891
 */

void
892
l2g_write(FILE *fp, const Local_to_global *l2g)
inge's avatar
inge committed
893
{
894
895
    const struct l2g_block_info *binfo;
    int ix;
896
897
898

    putc('[', fp);

899
    foutput_ulong((unsigned long) l2g->first_unused, fp);
900

901
902
903
904
905
906
    for (binfo = l2g->blocks; binfo < l2g->blocks + l2g->num_blocks; ++binfo)
	for (ix = 0; ix < binfo->first_free; ++ix)
	    if (binfo->value_block[ix] != 0)
	    {
		foutput_ulong((unsigned long) key_value(binfo, ix), fp);
		foutput_ulong((unsigned long) binfo->value_block[ix], fp);
907
	    }
908
    
909
    fputs(" ]", fp);
inge's avatar
inge committed
910
}
inge's avatar
inge committed
911
912
913
914
915
916
917
918


/* ================================================================ */
/* ===                     Iterator code                        === */
/* ================================================================ */


void
919
920
l2gi_searchall (L2g_iterator *l2gi,
		const Local_to_global *l2g)
inge's avatar
inge committed
921
{
922
    l2gi_searchsome(l2gi, l2g, 1, 0);
inge's avatar
inge committed
923
924
925
926
}


void
927
928
929
l2gi_searchsome(L2g_iterator *l2gi,
		const Local_to_global *l2g, 
		Local_text_no begin, 
inge's avatar
inge committed
930
931
		Local_text_no end)
{
932
    const struct l2g_block_info  * binfo;
inge's avatar
inge committed
933
934
    int               index;

935
936
937
938
939
940
941
    if (begin < 1)
    {
	log("l2gi_searchsome(%lu, %lu) called: min is 1\n",
	    (unsigned long)begin, (unsigned long)end);
	begin = 1;
    }

inge's avatar
inge committed
942
    l2gi->l2g = l2g;
943
    l2gi->beginval = begin;
inge's avatar
inge committed
944
    l2gi->endval   = end;
945
    l2gi->search_ended = 1;
inge's avatar
inge committed
946

947
    if (end != 0 && begin >= end)
inge's avatar
inge committed
948
949
	return;

950
951
952
953
954
955
956
957
958
959
960
961
    if (find_block_index_key(l2g, begin-1, &binfo, &index) == 0)
	return;

    l2gi->binfo    = binfo;
    l2gi->arrindex = index;

    assert(binfo != NULL);
    
    l2gi->search_ended = 0;

    l2gi->lno = key_value(binfo, index);
    l2gi->tno = binfo->value_block[index];
inge's avatar
inge committed
962
963
964
965
966
}


void l2gi_next(L2g_iterator *l2gi)
{
967
968
    const Local_to_global *l2g;
    const struct l2g_block_info *binfo;
inge's avatar
inge committed
969
970
971
972
973
974
975
976
977
978
979
    int                arrindex;

    l2g      = l2gi->l2g;
    arrindex = l2gi->arrindex + 1;
    for (binfo = l2gi->binfo;
	 binfo < l2g->blocks + l2g->num_blocks;
	 ++binfo, arrindex = 0)
    {

	/* If the block contains nothing at all, skip to next block item. */
	/* This works even the first time around. */
980
	if (is_empty(binfo)) 
inge's avatar
inge committed
981
982
	    continue;

983
984
985
986
987
988
989
	for (; arrindex < binfo->first_free; ++arrindex)
	{
	    if (l2gi->endval != 0
		&& key_value(binfo, arrindex) >= l2gi->endval)
	    {
		l2gi->search_ended = 1;
		return;
inge's avatar
inge committed
990
991
	    }

992
993
994
995
	    if (binfo->value_block[arrindex] != 0)
	    {
		l2gi->binfo    = binfo;
		l2gi->arrindex = arrindex;
inge's avatar
inge committed
996

997
998
		l2gi->lno = key_value(binfo, arrindex);
		l2gi->tno = binfo->value_block[arrindex];
inge's avatar
inge committed
999

1000
		return;
inge's avatar
inge committed
1001
1002
1003
1004
1005
1006
1007
	    }
	}
    }

    l2gi->search_ended = 1;
    return;
}
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022


Local_text_no
l2gi_begin(const L2g_iterator *l2gi)
{
    return l2gi->beginval;
}


Local_text_no
l2gi_end(const L2g_iterator *l2gi)
{
    return l2gi->endval;
}