← Back to branch summary

~ubuntu-branches/ubuntu/warty/swish-e/warty

« back to all changes in this revision

Viewing changes to src/array.c

  • Committer: Bazaar Package Importer
  • Author(s): Ludovic Drolez
  • Date: 2004-03-11 08:41:07 UTC
  • mfrom: (1.1.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20040311084107-7vp0mu82blq1qjvo
Tags: 2.4.1-3
http://bugs.debian.org/237332
Oops ! A comment was not removed to disable interactive compilation.
Closes: Bug#237332

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/array.c
 
1
/*
 
2
** This program and library is free software; you can redistribute it and/or
 
3
** modify it under the terms of the GNU (Library) General Public License
 
4
** as published by the Free Software Foundation; either version 2
 
5
** of the License, or any later version.
 
6
**
 
7
** This program is distributed in the hope that it will be useful,
 
8
** but WITHOUT ANY WARRANTY; without even the implied warranty of
 
9
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 
10
** GNU (Library) General Public License for more details.
 
11
**
 
12
** You should have received a copy of the GNU (Library) General Public License
 
13
** along with this program; if not, write to the Free Software
 
14
** Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 
15
**-----------------------------------------------------------------
 
16
**
 
17
**  Virtual Array Code. 
 
18
**  11/2001 jmruiz - The intention of this routines is storing and reading
 
19
**                   elemnts of arrays of long numbers avoiding the 
 
20
**                   allocation in memory of the total array. In other words,
 
21
**                   if we need to read only 10 elements of the array, we
 
22
**                   will must try to  make the minimal I/O memory and disk
 
23
**                   operations.
 
24
**
 
25
**                   To do that, the data is stored in aligned pages in disk   
 
26
**                   Also, a simple cache system is used to speed I/O file
 
27
**                   operations.
 
28
**
 
29
**                   The virtual array is extensible. In other words, you can
 
30
**                   add elements whenever you want
 
31
**
 
32
**    Main routines:
 
33
**
 
34
**  ARRAY *ARRAY_Create(FILE *fp)   
 
35
**    Creates a virtual array. Returns the handle of the array
 
36
**
 
37
**  ARRAY *ARRAY_Open(FILE *fp, unsigned long root_page) 
 
38
**    Opens an existent Virtual Array. root_page is de value returned by
 
39
**    Array_Close. Returns de handle of the array.
 
40
**
 
41
**  unsigned long ARRAY_Close(ARRAY *arr)
 
42
**    Closes and frees memory. arr is the value returned by ARRAY_Create or
 
43
**    ARRAY_Open. Returns the root page of the array. This value must be
 
44
**
 
45
**  int ARRAY_Put(ARRAY *arr, int index, unsigned long value)
 
46
**    Writes the array element arr[index]=value to the virtual array
 
47
**
 
48
**  unsigned long ARRAY_Get(ARRAY *arr, int index)
 
49
**    Reads the array element index. Returns de value arr[index]
 
50
**
 
51
*/
 
52
 
 
53
#include <stdio.h>
 
54
#include <stdlib.h>
 
55
#include <string.h>
 
56
 
 
57
#include "swish.h"
 
58
#include "mem.h"
 
59
#include "compress.h"
 
60
#include "array.h"
 
61
 
 
62
 
 
63
/* A ARRAY page size */
 
64
#define ARRAY_PageSize 4096
 
65
 
 
66
#define SizeInt32 4
 
67
 
 
68
/* Round to ARRAY_PageSize */
 
69
#define ARRAY_RoundPageSize(n) (((n) + ARRAY_PageSize - 1) & (~(ARRAY_PageSize - 1)))
 
70
 
 
71
#define ARRAY_PageHeaderSize (1 * SizeInt32) 
 
72
 
 
73
#define ARRAY_PageData(pg) ((pg)->data + ARRAY_PageHeaderSize)
 
74
#define ARRAY_Data(pg,i) (ARRAY_PageData((pg)) + (i) * SizeInt32)
 
75
 
 
76
#define ARRAY_SetNextPage(pg,num) ( *(int *)((pg)->data + 0 * SizeInt32) = PACKLONG(num))
 
77
 
 
78
#define ARRAY_GetNextPage(pg,num) ( (num) = UNPACKLONG(*(int *)((pg)->data + 0 * SizeInt32)))
 
79
 
 
80
 
 
81
int ARRAY_WritePageToDisk(FILE *fp, ARRAY_Page *pg)
 
82
{
 
83
    ARRAY_SetNextPage(pg,pg->next);
 
84
    fseek(fp,pg->page_number * ARRAY_PageSize,SEEK_SET);
 
85
    return fwrite(pg->data,ARRAY_PageSize,1,fp);
 
86
}
 
87
 
 
88
int ARRAY_WritePage(ARRAY *b, ARRAY_Page *pg)
 
89
{
 
90
int hash = pg->page_number % ARRAY_CACHE_SIZE;
 
91
ARRAY_Page *tmp;
 
92
    pg->modified =1;
 
93
    if((tmp = b->cache[hash]))
 
94
    {
 
95
        while(tmp)
 
96
        {
 
97
            if(tmp->page_number == pg->page_number)
 
98
            {
 
99
                return 0;
 
100
            }
 
101
            tmp = tmp->next_cache;
 
102
        }
 
103
    }
 
104
    pg->next_cache = b->cache[hash];
 
105
    b->cache[hash] = pg;
 
106
    return 0;
 
107
}
 
108
 
 
109
int ARRAY_FlushCache(ARRAY *b)
 
110
{
 
111
int i;
 
112
ARRAY_Page *tmp, *next;
 
113
    for(i = 0; i < ARRAY_CACHE_SIZE; i++)
 
114
    {
 
115
        if((tmp = b->cache[i]))
 
116
        {
 
117
            while(tmp)
 
118
            {
 
119
#ifdef DEBUG
 
120
                if(tmp->in_use)
 
121
                {
 
122
                    printf("DEBUG Error in FlushCache: Page in use\n");
 
123
                    exit(0);
 
124
                }
 
125
#endif
 
126
                next = tmp->next_cache;
 
127
                if(tmp->modified)
 
128
                {
 
129
                    ARRAY_WritePageToDisk(b->fp, tmp);
 
130
                    tmp->modified = 0;
 
131
                }
 
132
                if(tmp != b->cache[i])
 
133
                    efree(tmp);
 
134
 
 
135
                tmp = next;
 
136
            }
 
137
            b->cache[i]->next_cache = NULL;
 
138
        }
 
139
    }
 
140
    return 0;
 
141
}
 
142
 
 
143
int ARRAY_CleanCache(ARRAY *b)
 
144
{
 
145
int i;
 
146
ARRAY_Page *tmp,*next;
 
147
    for(i = 0; i < ARRAY_CACHE_SIZE; i++)
 
148
    {
 
149
        if((tmp = b->cache[i]))
 
150
        {
 
151
            while(tmp)
 
152
            {
 
153
                next = tmp->next_cache;
 
154
                efree(tmp);
 
155
                tmp = next;
 
156
            }
 
157
            b->cache[i] = NULL;
 
158
        }
 
159
    }
 
160
    return 0;
 
161
}
 
162
 
 
163
ARRAY_Page *ARRAY_ReadPageFromDisk(FILE *fp, unsigned long page_number)
 
164
{
 
165
ARRAY_Page *pg = (ARRAY_Page *)emalloc(sizeof(ARRAY_Page) + ARRAY_PageSize);
 
166
 
 
167
    fseek(fp,page_number * ARRAY_PageSize,SEEK_SET);
 
168
    fread(pg->data,ARRAY_PageSize, 1, fp);
 
169
 
 
170
    ARRAY_GetNextPage(pg,pg->next);
 
171
 
 
172
    pg->page_number = page_number;
 
173
    pg->modified = 0;
 
174
    return pg;
 
175
}
 
176
 
 
177
ARRAY_Page *ARRAY_ReadPage(ARRAY *b, unsigned long page_number)
 
178
{
 
179
int hash = page_number % ARRAY_CACHE_SIZE;
 
180
ARRAY_Page *tmp;
 
181
    if((tmp = b->cache[hash]))
 
182
    {
 
183
        while(tmp)
 
184
        {
 
185
            if(tmp->page_number == page_number)
 
186
            {
 
187
                return tmp;
 
188
            }
 
189
            tmp = tmp->next_cache;
 
190
        }
 
191
    }
 
192
 
 
193
    tmp = ARRAY_ReadPageFromDisk(b->fp, page_number);
 
194
    tmp->modified = 0;
 
195
    tmp->in_use = 1;
 
196
    tmp->next_cache = b->cache[hash];
 
197
    b->cache[hash] = tmp;
 
198
    return tmp;
 
199
}
 
200
 
 
201
ARRAY_Page *ARRAY_NewPage(ARRAY *b)
 
202
{
 
203
ARRAY_Page *pg;
 
204
long offset;
 
205
FILE *fp = b->fp;
 
206
int hash;
 
207
int size = ARRAY_PageSize;
 
208
 
 
209
    /* Get file pointer */
 
210
    if(fseek(fp,0,SEEK_END) !=0)
 
211
        progerrno("Failed to seek to eof: ");
 
212
 
 
213
    offset = ftell(fp);
 
214
    /* Round up file pointer */
 
215
    offset = ARRAY_RoundPageSize(offset);
 
216
 
 
217
    /* Set new file pointer - data will be aligned */
 
218
    if(fseek(fp,offset, SEEK_SET)!=0 || offset != ftell(fp))
 
219
        progerrno("Failed during seek: ");
 
220
 
 
221
 
 
222
    pg = (ARRAY_Page *)emalloc(sizeof(ARRAY_Page) + size);
 
223
    memset(pg,0,sizeof(ARRAY_Page) + size);
 
224
    /* Reserve space in file */
 
225
    if(fwrite(pg->data,1,size,fp)!=size || ((long)size + offset) != ftell(fp))
 
226
        progerrno("Failed to write ARRAY_page: ");
 
227
 
 
228
    pg->next = 0;
 
229
 
 
230
    pg->page_number = offset/ARRAY_PageSize;
 
231
 
 
232
    /* add to cache */
 
233
    pg->modified = 1;
 
234
    pg->in_use = 1;
 
235
    hash = pg->page_number % ARRAY_CACHE_SIZE;
 
236
    pg->next_cache = b->cache[hash];
 
237
    b->cache[hash] = pg;
 
238
    return pg;
 
239
}
 
240
 
 
241
void ARRAY_FreePage(ARRAY *b, ARRAY_Page *pg)
 
242
{
 
243
int hash = pg->page_number % ARRAY_CACHE_SIZE;
 
244
ARRAY_Page *tmp;
 
245
 
 
246
    tmp = b->cache[hash];
 
247
 
 
248
#ifdef DEBUG
 
249
    if(!(tmp = b->cache[hash]))
 
250
    {
 
251
        /* This should never happen!!!! */
 
252
        printf("Error in FreePage\n");
 
253
        exit(0);
 
254
    }
 
255
#endif
 
256
 
 
257
    while(tmp)
 
258
    {
 
259
        if (tmp->page_number != pg->page_number)
 
260
            tmp = tmp->next_cache;
 
261
        else
 
262
        {
 
263
            tmp->in_use = 0;
 
264
            break;
 
265
        }
 
266
    }
 
267
}
 
268
 
 
269
ARRAY *ARRAY_New(FILE *fp, unsigned int size)
 
270
{
 
271
ARRAY *b;
 
272
int i;
 
273
    b = (ARRAY *) emalloc(sizeof(ARRAY));
 
274
    b->page_size = size;
 
275
    b->fp = fp;
 
276
    for(i = 0; i < ARRAY_CACHE_SIZE; i++)
 
277
        b->cache[i] = NULL;
 
278
 
 
279
    return b;
 
280
}
 
281
 
 
282
ARRAY *ARRAY_Create(FILE *fp)
 
283
{
 
284
ARRAY *b;
 
285
ARRAY_Page *root;
 
286
int size = ARRAY_PageSize;
 
287
 
 
288
    b = ARRAY_New(fp , size);
 
289
    root = ARRAY_NewPage(b);
 
290
 
 
291
    b->root_page = root->page_number;
 
292
 
 
293
    ARRAY_WritePage(b, root);
 
294
    ARRAY_FreePage(b, root);
 
295
 
 
296
    return b;
 
297
}
 
298
 
 
299
 
 
300
ARRAY *ARRAY_Open(FILE *fp, unsigned long root_page)
 
301
{
 
302
ARRAY *b;
 
303
int size = ARRAY_PageSize;
 
304
 
 
305
    b = ARRAY_New(fp , size);
 
306
 
 
307
    b->root_page = root_page;
 
308
 
 
309
    return b;
 
310
}
 
311
 
 
312
unsigned long ARRAY_Close(ARRAY *bt)
 
313
{
 
314
unsigned long root_page = bt->root_page;
 
315
    ARRAY_FlushCache(bt);
 
316
    ARRAY_CleanCache(bt);
 
317
    efree(bt);
 
318
    return root_page;
 
319
}
 
320
 
 
321
 
 
322
int ARRAY_Put(ARRAY *b, int index, unsigned long value)
 
323
{
 
324
unsigned long next_page; 
 
325
ARRAY_Page *root_page, *tmp = NULL, *prev; 
 
326
int i, hash, page_reads, page_index;
 
327
 
 
328
    page_reads = index / ((ARRAY_PageSize - ARRAY_PageHeaderSize) / SizeInt32);
 
329
    hash = page_reads % ((ARRAY_PageSize - ARRAY_PageHeaderSize) / SizeInt32);
 
330
    page_reads /= ((ARRAY_PageSize - ARRAY_PageHeaderSize) / SizeInt32);
 
331
    page_index = index % ((ARRAY_PageSize - ARRAY_PageHeaderSize) / SizeInt32);
 
332
 
 
333
    root_page = ARRAY_ReadPage(b, b->root_page);
 
334
    next_page = UNPACKLONG(*(unsigned long *)ARRAY_Data(root_page, hash));
 
335
 
 
336
    prev = NULL;
 
337
    for(i = 0; i <= page_reads; i++)
 
338
    {
 
339
        if(!next_page)
 
340
        {
 
341
            tmp = ARRAY_NewPage(b);
 
342
            ARRAY_WritePage(b,tmp);
 
343
            if(!i)
 
344
            {
 
345
                *(unsigned long *)ARRAY_Data(root_page,hash) = PACKLONG(tmp->page_number);
 
346
                 ARRAY_WritePage(b,root_page);
 
347
            }
 
348
            else
 
349
            {
 
350
                prev->next = tmp->page_number;
 
351
                ARRAY_WritePage(b,prev);
 
352
            }
 
353
        } 
 
354
        else
 
355
        {
 
356
            tmp = ARRAY_ReadPage(b, next_page);
 
357
        }
 
358
        if(prev)
 
359
            ARRAY_FreePage(b,prev);
 
360
        prev = tmp;
 
361
        next_page = tmp->next;
 
362
    }
 
363
    *(unsigned long *)ARRAY_Data(tmp,page_index) = PACKLONG(value);
 
364
    ARRAY_WritePage(b,tmp);
 
365
    ARRAY_FreePage(b,tmp);
 
366
    ARRAY_FreePage(b,root_page);
 
367
 
 
368
    return 0;
 
369
}
 
370
 
 
371
 
 
372
unsigned long ARRAY_Get(ARRAY *b, int index)
 
373
{
 
374
unsigned long next_page, value; 
 
375
ARRAY_Page *root_page, *tmp;
 
376
int i, hash, page_reads, page_index;
 
377
 
 
378
    page_reads = index / ((ARRAY_PageSize - ARRAY_PageHeaderSize) / SizeInt32);
 
379
    hash = page_reads % ((ARRAY_PageSize - ARRAY_PageHeaderSize) / SizeInt32);
 
380
    page_reads /= ((ARRAY_PageSize - ARRAY_PageHeaderSize) / SizeInt32);
 
381
    page_index = index % ((ARRAY_PageSize - ARRAY_PageHeaderSize) / SizeInt32);
 
382
 
 
383
    root_page = ARRAY_ReadPage(b, b->root_page);
 
384
    next_page = UNPACKLONG(*(unsigned long *)ARRAY_Data(root_page, hash));
 
385
 
 
386
    tmp = NULL;
 
387
    for(i = 0; i <= page_reads; i++)
 
388
    {
 
389
        if(tmp)
 
390
            ARRAY_FreePage(b, tmp);
 
391
        if(!next_page)
 
392
        {
 
393
            ARRAY_FreePage(b,root_page);
 
394
            return 0L;
 
395
        } 
 
396
        else
 
397
        {
 
398
            tmp = ARRAY_ReadPage(b, next_page);
 
399
        }
 
400
        next_page = tmp->next;
 
401
    }
 
402
    value = UNPACKLONG(*(unsigned long *)ARRAY_Data(tmp,page_index));
 
403
    ARRAY_FreePage(b,tmp);
 
404
    ARRAY_FreePage(b,root_page);
 
405
 
 
406
    return value;
 
407
}
 
408
 
 
409
 
 
410
 
 
411
#ifdef DEBUG
 
412
 
 
413
#include <time.h>
 
414
 
 
415
#define N_TEST 50000000
 
416
 
 
417
#define F_READ_BINARY           "rb"
 
418
#define F_WRITE_BINARY          "wb"
 
419
#define F_READWRITE_BINARY      "rb+"
 
420
 
 
421
#define F_READ_TEXT             "r"
 
422
#define F_WRITE_TEXT            "w"
 
423
#define F_READWRITE_TEXT        "r+"
 
424
 
 
425
int main()
 
426
{
 
427
FILE *fp;
 
428
ARRAY *bt;
 
429
int i;
 
430
static unsigned long nums[N_TEST];
 
431
unsigned long root_page;
 
432
    srand(time(NULL));
 
433
 
 
434
 
 
435
 
 
436
    fp = fopen("kkkkk",F_WRITE_BINARY);
 
437
    fclose(fp);
 
438
    fp = fopen("kkkkk",F_READWRITE_BINARY);
 
439
 
 
440
    fwrite("aaa",1,3,fp);
 
441
 
 
442
printf("\n\nIndexing\n\n");
 
443
 
 
444
    bt = ARRAY_Create(fp);
 
445
    for(i=0;i<N_TEST;i++)
 
446
    {
 
447
        nums[i] = rand();
 
448
//        nums[i]=i;
 
449
        ARRAY_Put(bt,i,nums[i]);
 
450
        if(nums[i]!= ARRAY_Get(bt,i))
 
451
            printf("\n\nmal %d\n\n",i);
 
452
        if(!(i%1000))
 
453
        {
 
454
            ARRAY_FlushCache(bt);
 
455
            printf("%d            \r",i);
 
456
        }
 
457
    }
 
458
 
 
459
    root_page = ARRAY_Close(bt);
 
460
    fclose(fp);
 
461
 
 
462
printf("\n\nUnfreed %d\n\n",num);
 
463
printf("\n\nSearching\n\n");
 
464
 
 
465
    fp = fopen("kkkkk",F_READ_BINARY);
 
466
    bt = ARRAY_Open(fp, root_page);
 
467
 
 
468
    for(i=0;i<N_TEST;i++)
 
469
    {
 
470
        if(nums[i] != ARRAY_Get(bt,i))
 
471
            printf("\n\nmal %d\n\n",i);
 
472
        if(!(i%1000))
 
473
            printf("%d            \r",i);
 
474
    }
 
475
 
 
476
    root_page = ARRAY_Close(bt);
 
477
 
 
478
    fclose(fp);
 
479
printf("\n\nUnfreed %d\n\n",num);
 
480
 
 
481
}
 
482
 
 
483
#endif