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


/* FIXME: Use smalloc() et al instead of malloc() */



12
#include <stdlib.h>
13
14
15
16
17
18

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

#include "s-string.h"

inge's avatar
inge committed
19
#include "kom-types.h"
Per Cederqvist's avatar
Per Cederqvist committed
20
#include "local-to-global.h"
21
22
23
#include "log.h"
#include "ram-parse.h"
#include "ram-output.h"
inge's avatar
inge committed
24
25
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
59
60
61


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


/*
 * 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.
 */

static L2g_block_info *
add_block(Local_to_global *l2g)
{
    L2g_block_info  * binfo;

    /* Realloc the block pointer array. */
    l2g->num_blocks++;
    l2g->blocks = (L2g_block_info *) 
	realloc(l2g->blocks, 
		l2g->num_blocks * sizeof(L2g_block_info));

    /* Create a new block info and fill it in. */
    binfo = &(l2g->blocks[l2g->num_blocks - 1]);
    binfo->first_free  = 0;
    binfo->zeroes      = L2G_BLOCKSIZE;
    binfo->start       = 0;
    binfo->key_block   = NULL;
    binfo->value_block = (Text_no *) malloc(L2G_BLOCKSIZE * sizeof(Text_no));

    return binfo;
}


62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
/*
 * 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, 
	     L2g_block_info  *binfo)
{
    /* Remove the blocks from the Block Info */
    if (binfo->key_block != NULL)
	free(binfo->key_block);
    free(binfo->value_block);

    /* Compact the remaining blocks. */
    while (++binfo < l2g->blocks + l2g->num_blocks)
	*(binfo - 1) = *binfo;
    l2g->num_blocks--;
    l2g->blocks = (L2g_block_info *) 
	realloc(l2g->blocks, 
		l2g->num_blocks * sizeof(L2g_block_info));
}


inge's avatar
inge committed
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
/*
 * Make a sparse block from a dense one.
 */
static void
make_sparse(L2g_block_info *binfo)
{
    int  next;
    int  i;

    /* Allocate the room for the key block. */
    binfo->key_block = (Local_text_no *) 
	malloc(L2G_BLOCKSIZE * sizeof(Local_text_no));

    /* Compact the block. */
    next = 0;
    for (i = 0; i < binfo->first_free; ++i) {
	if (binfo->value_block[i] != 0) {
	    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;
    binfo->start = binfo->key_block[0];

    /* FIXME: What happens if next == 0?  Can this happen? */
}


/*
 * 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,
 * so a search within the block must also be done later.
 * 
 * Return NULL if LNO is bigger than the highest number in the structure.
 */

static L2g_block_info *
find_block(Local_to_global *l2g, Local_text_no lno)
{
    L2g_block_info  * binfo;

Per Cederqvist's avatar
Per Cederqvist committed
131
132
133
134
    /* If empty, the number can not be in here. */
    if (l2g->num_blocks == 0)
	return NULL;

inge's avatar
inge committed
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
    /* 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. */
    if (binfo->key_block == NULL) {
	/* A dense block */
	if (lno >= binfo->start + binfo->first_free)
	    return NULL;
    } else {
	/* A sparse block */
	if (lno > binfo->value_block[binfo->first_free - 1])
	    return NULL;
    }

    /* Find the block where lno *could* be. */
    /* FIXME: Binary search? */
    while (binfo > l2g->blocks) {
	if (lno >= binfo->start)
	    return binfo;
	binfo--;
    }

Per Cederqvist's avatar
Per Cederqvist committed
157
    return binfo;
inge's avatar
inge committed
158
159
160
}


inge's avatar
inge committed
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
static Local_text_no
find_block_index_key(Local_to_global *l2g, Local_text_no lno,
		     L2g_block_info **binfo_out,
		     int             *index_out)
{
    L2g_block_info  * binfo;
    int               i;

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

    /* If lno is lower than the first text, treat this as a special case. */
    if (lno >= binfo->start) {
	/* Check the found block */
	if (binfo->key_block == NULL) {
	    /* dense block */
	    for (i = lno - binfo->start + 1; i < binfo->first_free; ++i) {
		if (binfo->value_block[i] != 0) {
		    *binfo_out = binfo;
		    *index_out = i;

		    return binfo->start + i;
		}
	    }
	} else {
	    /* sparse block */
	    /* FIXME: binary search */
	    for (i = 0; i < binfo->first_free; ++i) {
		if (binfo->key_block[i] > lno) {
		    *binfo_out = binfo;
		    *index_out = i;

		    return binfo->key_block[i];
		}
	    }
	}
	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.
     */
    for (; binfo < l2g->blocks + l2g->num_blocks; ++binfo) {

	/* If the block contains anything at all, get the item. */
	if (binfo->zeroes < L2G_BLOCKSIZE){
	    if (binfo->key_block == NULL) {
		/* dense block */
		for (i = 0; i < binfo->first_free; ++i) {
		    if (binfo->value_block[i] != 0) {
			*binfo_out = binfo;
			*index_out = i;

			return binfo->start + i;
		    }
		}
		
	    } else {
		/* sparse block */
		*binfo_out = binfo;
		*index_out = 0;

		return binfo->key_block[0];
	    }
	}
    }

    return 0;
}


inge's avatar
inge committed
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
/* ================================================================ */
/* ====                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;
    l2g->blocks = NULL;
}


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

void
l2g_clear(Local_to_global *l2g)
{
    L2g_block_info  * binfo;
    int               i;

    /* Free the block info structures. */
Per Cederqvist's avatar
Per Cederqvist committed
276
277
    binfo = l2g->blocks;
    for (i = 0; i < l2g->num_blocks; ++i) {
inge's avatar
inge committed
278
279
280
281
282
283
284
	if (binfo->key_block != NULL)
	    free(binfo->key_block);
	free(binfo->value_block);

	binfo++;
    }

285
    /* Free the block pointers. */
Per Cederqvist's avatar
Per Cederqvist committed
286
    l2g->num_blocks = 0;
287
288
289
290
    if (l2g->blocks != NULL) {
	free(l2g->blocks);
	l2g->blocks = NULL;
    }
inge's avatar
inge committed
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
}


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

void
l2g_copy(Local_to_global *from, Local_to_global *to)
{
    L2g_block_info  * binfo;
    int               i, j;

    /* FIXME: More efficient code */
    l2g_clear(to);

    binfo = from->blocks;
    for (i = 0; i < from->num_blocks; ++i) {
	if (binfo->key_block == NULL) {
	    /* Dense block */
	    for (j = 0; j < binfo->first_free; ++j) {
		if (binfo->value_block[j] != 0)
		    l2g_append(to, binfo->start + j, binfo->value_block[j]);
	    }
	} else {
	    /* Sparse block */
	    for (j = 0; j < binfo->first_free; ++j) {
		if (binfo->value_block[j] != 0)
		    l2g_append(to, binfo->key_block[j], binfo->value_block[j]);
	    }
	}

	binfo++;
    }
}


/*
 * Append the pair LNO-TNO.  LNO has to be bigger than the last local 
 * number in the structure (this is not tested FIXME?).
 */
333
334
335

typedef Local_text_no Local_text_no_iter;

inge's avatar
inge committed
336
337
338
339
340
341
void
l2g_append(Local_to_global *l2g, 
	   Local_text_no    lno,
	   Text_no          tno)
{
    L2g_block_info  * binfo;
342
    Local_text_no_iter ix;
inge's avatar
inge committed
343

Per Cederqvist's avatar
Per Cederqvist committed
344
    /* Don't add anything if tno == 0. */
inge's avatar
inge committed
345
346
347
    if (tno == 0)
	return;

Per Cederqvist's avatar
Per Cederqvist committed
348
349
350
    if (l2g->num_blocks == 0) {
	/* If totally empty, add the first block and set binfo to it. */
	binfo = add_block(l2g);
inge's avatar
inge committed
351
	binfo->start = lno;
Per Cederqvist's avatar
Per Cederqvist committed
352
353
354
355
    } else {
	/* else let binfo point to the last block. */
	binfo = &(l2g->blocks[l2g->num_blocks - 1]);
    }
inge's avatar
inge committed
356
357

    if (binfo->first_free == L2G_BLOCKSIZE) {
Per Cederqvist's avatar
Per Cederqvist committed
358
	/* If the last block is full, create a new block. */
inge's avatar
inge committed
359
360
361
362
	binfo = add_block(l2g);

    } else if (binfo->key_block == NULL
	       && lno - binfo->start >= L2G_BLOCKSIZE){
inge's avatar
inge committed
363
364
365
366
367
368
369
370
371
372
373
374
375
376
	/*
	 * First of all, a little optimization:
	 *   If the block contains no entries, the entries in it have
	 *   been deleted.  We can then reuse the block and pretend
	 *   it is a newly allocated block.
	 */
	if (binfo->zeroes == L2G_BLOCKSIZE) {
	    binfo->first_free = 0;
	    binfo->start      = 0;
	    if (binfo->value_block != NULL) {
		free(binfo->value_block);
		binfo->value_block = NULL;
	    }

inge's avatar
inge committed
377
378
	/* 
	 * If the last block is dense, and LNO is outside the block,
379
380
	 * check if we should convert it to a sparse block or if we 
	 * should allocate a new one.
inge's avatar
inge committed
381
	 */
inge's avatar
inge committed
382
	} else if ((L2G_BLOCKSIZE - binfo->first_free) 
inge's avatar
inge committed
383
384
385
386
387
388
389
	    + binfo->zeroes > L2G_BLOCKSIZE / 2) {
	    make_sparse(binfo);
	} else {
	    binfo = add_block(l2g);
	}
    }

Per Cederqvist's avatar
Per Cederqvist committed
390
    /* Enter the new value into the block.  */
inge's avatar
inge committed
391
392
393
394
395
396
    if (binfo->first_free == 0) {
	binfo->start = lno;
    } 
    if (binfo->key_block == NULL) {
	/* A dense block. */

397
398
	for (ix = binfo->first_free; ix < lno - binfo->start; ++ix)
	    binfo->value_block[ix] = 0;
inge's avatar
inge committed
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
	binfo->value_block[lno - binfo->start] = tno;
	binfo->first_free = lno - binfo->start + 1;

    } else {
	/* A sparse block. */

	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
l2g_delete(Local_to_global *l2g, Local_text_no lno)
{
    L2g_block_info  * binfo;
    int               i;

    /* Find block where LNO might be and return if not there. */
    binfo = find_block(l2g, lno);
    if (binfo == NULL)
	return;

    /* Go through the block where it might be and delete LNO */
    if (binfo->key_block == NULL) {
	/* A dense block */
	if (binfo->start <= lno && lno < binfo->start + L2G_BLOCKSIZE)
	    binfo->value_block[lno - binfo->start] = 0;
	binfo->zeroes++;
    } else {
Per Cederqvist's avatar
Per Cederqvist committed
436
	/* A sparse block */
inge's avatar
inge committed
437
438
439
440
441
442
	/* FIXME: Binary search */
	for (i = 0; i < binfo->first_free && binfo->key_block[i] <= lno; ++i) {
	    if (binfo->key_block[i] == lno) {
		/* FIXME: Compacting? */
		binfo->value_block[i] = 0;
		binfo->zeroes++;
inge's avatar
inge committed
443
		break;
inge's avatar
inge committed
444
445
446
	    }
	}
    }
447

inge's avatar
inge committed
448
449
450
#if 0
    /* NOTE: This is disabled since it wreaks havoc with iterators. */

451
452
453
454
455
456
457
    /* Delete the block if it is empty. */
    /* NOTE, FIXME: Check what this does to iterators, and maybe */
    /*              find some other way.  Perhaps we could set */
    /*              next_free to -1 or something and then remove */
    /*              the blocks only when compact() is called. */
    if (binfo->zeroes == L2G_BLOCKSIZE)
	delete_block(l2g, binfo);
inge's avatar
inge committed
458
#endif
inge's avatar
inge committed
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
}


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

Text_no
l2g_lookup(Local_to_global *l2g, Local_text_no lno)
{
    L2g_block_info  * binfo;
    int               i;

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

    if (binfo->key_block == NULL) {
	/* A dense block */
	if (binfo->start <= lno && lno < binfo->start + L2G_BLOCKSIZE)
	    return binfo->value_block[lno - binfo->start];
    } else {
	/* FIXME: Binary search */
	for (i = 0; i < binfo->first_free && binfo->key_block[i] <= lno; ++i) {
	    if (binfo->key_block[i] == lno)
		return binfo->value_block[i];
	}
    }

    return 0;
}


/*
Per Cederqvist's avatar
Per Cederqvist committed
494
 * Return the next local text number which is not 
inge's avatar
inge committed
495
 */
Per Cederqvist's avatar
Per Cederqvist committed
496

inge's avatar
inge committed
497
498
499
Local_text_no
l2g_next_key(Local_to_global *l2g, Local_text_no lno)
{
Per Cederqvist's avatar
Per Cederqvist committed
500
501
502
    L2g_block_info  * binfo;
    int               i;

inge's avatar
inge committed
503
    return find_block_index_key(l2g, lno, &binfo, &i);
inge's avatar
inge committed
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
}


/*
 * Compact the structure as much as possible.
 */

void
l2g_compact(Local_to_global *l2g)
{
    /* We don't have to do any compacting.  It works anyhow. */
    /* However, for memory's sake, we would like to do it. */
    /* FIXME: More efficient code. */

    Local_to_global  dummy;

    l2g_init(&dummy);
    l2g_copy(l2g, &dummy);
522
523
    l2g_destruct(l2g);
    *l2g = dummy;
inge's avatar
inge committed
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
}


/*
 * Dump the internal structure of L2G onto the file FILE.
 */

void
l2g_dump(Local_to_global *l2g, FILE *file)
{
    L2g_block_info  * binfo;
    int               i, j;

    fprintf(file, "Number of blocks: %d\n", l2g->num_blocks);

    binfo = l2g->blocks;
    for (i = 0; i < l2g->num_blocks; ++i) {
	fprintf(file, "%d: %d %d %d (%s) [", i,
		binfo->first_free,
		binfo->zeroes,
		(int) binfo->start,
		((binfo->key_block == NULL) ? "dense" : "sparse"));

	if (binfo->key_block == NULL) {
	    /* A dense block */
	    for (j = 0; j < binfo->first_free; ++j) {
		fprintf(file, "%d ", (int) binfo->value_block[j]);
	    }
	} else {
	    /* A sparse block */
	    for (j = 0; j < binfo->first_free; ++j) {
		fprintf(file, "%d:%d ", 
			(int) binfo->key_block[j],
			(int) binfo->value_block[j]);
	    }
	}
	fprintf(file, "]\n");

	binfo++;
    }
}


/*
568
 * Read a Local to global structure from the file FILE.
inge's avatar
inge committed
569
570
571
 */

void
572
l2g_read(Local_to_global *l2g, FILE *fp)
inge's avatar
inge committed
573
{
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
    int            c;
    Local_text_no  lno;
    Text_no        tno;

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

    /* Read pairs of numbers until the EOL (end-of-l2g :-) ) marker is read. */
    while (1) {
	fskipwhite(fp);
	if ((c = getc(fp)) == ']')
	    break;
	else
	    ungetc(c, fp);

	lno = (Local_text_no) fparse_long(fp);
	tno = (Text_no)       fparse_long(fp);
	l2g_append(l2g, lno, tno);
    }
inge's avatar
inge committed
597
598
599
600
}


/*
601
 * Print the structure to the file FILE.
inge's avatar
inge committed
602
603
604
 */

void
605
l2g_write(Local_to_global *l2g, FILE *fp)
inge's avatar
inge committed
606
{
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
    L2g_block_info  * binfo;
    int               i, j;

    putc('[', fp);

    binfo = l2g->blocks;
    for (i = 0; i < l2g->num_blocks; ++i) {
	if (binfo->key_block == NULL) {
	    /* Dense block */

	    for (j = 0; j < binfo->first_free; ++j) {
		if (binfo->value_block[j] != 0) {
		    foutput_ulong((unsigned long) (binfo->start + j), fp);
		    foutput_ulong((unsigned long) (binfo->value_block[j]), fp);
		}
	    }
	} else {
	    /* Sparse block */

	    for (j = 0; j < binfo->first_free; ++j) {
		if (binfo->value_block[j] != 0) {
		    foutput_ulong((unsigned long) (binfo->key_block[j]), fp);
		    foutput_ulong((unsigned long) (binfo->value_block[j]), fp);
		}
	    }
	}

	binfo++;
    }

    fputs(" ]", fp);
inge's avatar
inge committed
638
}
inge's avatar
inge committed
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763


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


void
l2gi_searchall (L2g_iterator *l2gi, Local_to_global *l2g)
{
    L2g_block_info  * binfo;
    int               index;

    l2gi->l2g = l2g;
    find_block_index_key(l2g, 0, &binfo, &index);
    l2gi->binfo    = binfo;
    l2gi->arrindex = index;
    l2gi->endval   = MAX_LOCAL_TEXT_NO;

    if (binfo == NULL) {
	l2gi->search_ended = 1;
	return;
    }

    if (binfo->key_block == NULL) {
	l2gi->lno = binfo->start + index;
	l2gi->tno = binfo->value_block[index];
    } else {
	l2gi->lno = binfo->key_block[index];
	l2gi->tno = binfo->value_block[index];
    }
}


void
l2gi_searchsome(L2g_iterator *l2gi, Local_to_global *l2g, 
		Local_text_no start, 
		Local_text_no end)
{
    L2g_block_info  * binfo;
    int               index;

    l2gi->l2g = l2g;
    find_block_index_key(l2g, start, &binfo, &index);
    l2gi->binfo    = binfo;
    l2gi->arrindex = index;
    l2gi->endval   = end;

    if (binfo == NULL) {
	l2gi->search_ended = 1;
	return;
    }

    if (binfo->key_block == NULL) {
	l2gi->lno = binfo->start + index;
	l2gi->tno = binfo->value_block[index];
    } else {
	l2gi->lno = binfo->key_block[index];
	l2gi->tno = binfo->value_block[index];
    }
}


void l2gi_next(L2g_iterator *l2gi)
{
    Local_to_global  * l2g;
    L2g_block_info   * binfo;
    int                i;
    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. */
	if (binfo->zeroes == L2G_BLOCKSIZE) 
	    continue;

	if (binfo->key_block == NULL) {
	    /* dense block */
	    for (i = arrindex; i < binfo->first_free; ++i) {
		if (binfo->start + i >= l2gi->endval) {
		    l2gi->search_ended = 1;
		    return;
		}

		if (binfo->value_block[i] != 0) {
		    l2gi->binfo    = binfo;
		    l2gi->arrindex = i;

		    l2gi->lno = binfo->start + i;
		    l2gi->tno = binfo->value_block[i];

		    return;
		}
	    }
	} else {
	    /* sparse block */

	    for (i = arrindex; i < binfo->first_free; ++i) {
		if (binfo->key_block[i] >=l2gi->endval) {
		    l2gi->search_ended = 1;
		    return;
		}

		if (binfo->value_block[i] != 0) {
		    l2gi->binfo    = binfo;
		    l2gi->arrindex = i;

		    l2gi->lno = binfo->key_block[i];
		    l2gi->tno = binfo->value_block[i];

		    return;
		}
	    }
	}
    }

    l2gi->search_ended = 1;
    return;
}