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


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



#include <malloc.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
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
}


/* ================================================================ */
/* ====                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
201
202
    binfo = l2g->blocks;
    for (i = 0; i < l2g->num_blocks; ++i) {
inge's avatar
inge committed
203
204
205
206
207
208
209
	if (binfo->key_block != NULL)
	    free(binfo->key_block);
	free(binfo->value_block);

	binfo++;
    }

210
    /* Free the block pointers. */
Per Cederqvist's avatar
Per Cederqvist committed
211
    l2g->num_blocks = 0;
212
213
214
215
    if (l2g->blocks != NULL) {
	free(l2g->blocks);
	l2g->blocks = NULL;
    }
inge's avatar
inge committed
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
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
}


/*
 * 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?).
 */
void
l2g_append(Local_to_global *l2g, 
	   Local_text_no    lno,
	   Text_no          tno)
{
    L2g_block_info  * binfo;
    int               i;

Per Cederqvist's avatar
Per Cederqvist committed
266
    /* Don't add anything if tno == 0. */
inge's avatar
inge committed
267
268
269
    if (tno == 0)
	return;

Per Cederqvist's avatar
Per Cederqvist committed
270
271
272
    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
273
	binfo->start = lno;
Per Cederqvist's avatar
Per Cederqvist committed
274
275
276
277
    } else {
	/* else let binfo point to the last block. */
	binfo = &(l2g->blocks[l2g->num_blocks - 1]);
    }
inge's avatar
inge committed
278
279

    if (binfo->first_free == L2G_BLOCKSIZE) {
Per Cederqvist's avatar
Per Cederqvist committed
280
	/* If the last block is full, create a new block. */
inge's avatar
inge committed
281
282
283
284
285
286
	binfo = add_block(l2g);

    } else if (binfo->key_block == NULL
	       && lno - binfo->start >= L2G_BLOCKSIZE){
	/* 
	 * If the last block is dense, and LNO is outside the block,
287
288
	 * check if we should convert it to a sparse block or if we 
	 * should allocate a new one.
inge's avatar
inge committed
289
290
291
292
293
294
295
296
297
	 */
	if ((L2G_BLOCKSIZE - binfo->first_free) 
	    + binfo->zeroes > L2G_BLOCKSIZE / 2) {
	    make_sparse(binfo);
	} else {
	    binfo = add_block(l2g);
	}
    }

Per Cederqvist's avatar
Per Cederqvist committed
298
    /* Enter the new value into the block.  */
inge's avatar
inge committed
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
333
334
335
336
337
338
339
340
341
342
343
    if (binfo->first_free == 0) {
	binfo->start = lno;
    } 
    if (binfo->key_block == NULL) {
	/* A dense block. */

	for (i = binfo->first_free; i < lno - binfo->start; ++i)
	    binfo->value_block[i] = 0;
	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
344
	/* A sparse block */
inge's avatar
inge committed
345
346
347
348
349
350
351
352
353
	/* 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++;
	    }
	}
    }
354
355
356
357
358
359
360
361

    /* 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
362
363
364
365
366
367
368
369
370
371
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
}


/*
 * 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
397
 * Return the next local text number which is not 
inge's avatar
inge committed
398
 */
Per Cederqvist's avatar
Per Cederqvist committed
399

inge's avatar
inge committed
400
401
402
Local_text_no
l2g_next_key(Local_to_global *l2g, Local_text_no lno)
{
Per Cederqvist's avatar
Per Cederqvist committed
403
404
405
406
407
408
409
410
    L2g_block_info  * binfo;
    int               i;

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

    /* If lno is lower than the first text, treat this as a special case. */
411
    if (lno >= binfo->start) {
Per Cederqvist's avatar
Per Cederqvist committed
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
	/* 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)
		    return binfo->start + i;
	    }
	} else {
	    /* sparse block */
	    /* FIXME: binary search */
	    for (i = 0; i < binfo->first_free; ++i) {
		if (binfo->key_block[i] > lno)
		    return binfo->key_block[i];
	    }
	}
427
	binfo++;
Per Cederqvist's avatar
Per Cederqvist committed
428
429
430
431
432
433
434
    }

    /*
     * 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.
     */
435
    for (; binfo < l2g->blocks + l2g->num_blocks; ++binfo) {
Per Cederqvist's avatar
Per Cederqvist committed
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452

	/* 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)
			return binfo->start + i;
		}
		
	    } else {
		/* sparse block */
		return binfo->key_block[0];
	    }
	}
    }

inge's avatar
inge committed
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
    return 0;
}


/*
 * 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);
472
473
    l2g_destruct(l2g);
    *l2g = dummy;
inge's avatar
inge committed
474
475
476
477
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
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
}


/*
 * 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++;
    }
}


/*
518
 * Read a Local to global structure from the file FILE.
inge's avatar
inge committed
519
520
521
 */

void
522
l2g_read(Local_to_global *l2g, FILE *fp)
inge's avatar
inge committed
523
{
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
    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
547
548
549
550
}


/*
551
 * Print the structure to the file FILE.
inge's avatar
inge committed
552
553
554
 */

void
555
l2g_write(Local_to_global *l2g, FILE *fp)
inge's avatar
inge committed
556
{
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
    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
588
}