swish-e/src/array.c

/*
** This program and library is free software; you can redistribute it and/or
** modify it under the terms of the GNU (Library) General Public License
** as published by the Free Software Foundation; either version 2
** of the License, or any later version.
**
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
** GNU (Library) General Public License for more details.
**
** You should have received a copy of the GNU (Library) General Public License
** along with this program; if not, write to the Free Software
** Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
**-----------------------------------------------------------------
**
**  Virtual Array Code. 
**  11/2001 jmruiz - The intention of this routines is storing and reading
**                   elemnts of arrays of long numbers avoiding the 
**                   allocation in memory of the total array. In other words,
**                   if we need to read only 10 elements of the array, we
**                   will must try to  make the minimal I/O memory and disk
**                   operations.
**
**                   To do that, the data is stored in aligned pages in disk   
**                   Also, a simple cache system is used to speed I/O file
**                   operations.
**
**                   The virtual array is extensible. In other words, you can
**                   add elements whenever you want
**
**    Main routines:
**
**  ARRAY *ARRAY_Create(FILE *fp)   
**    Creates a virtual array. Returns the handle of the array
**
**  ARRAY *ARRAY_Open(FILE *fp, unsigned long root_page) 
**    Opens an existent Virtual Array. root_page is de value returned by
**    Array_Close. Returns de handle of the array.
**
**  unsigned long ARRAY_Close(ARRAY *arr)
**    Closes and frees memory. arr is the value returned by ARRAY_Create or
**    ARRAY_Open. Returns the root page of the array. This value must be
**
**  int ARRAY_Put(ARRAY *arr, int index, unsigned long value)
**    Writes the array element arr[index]=value to the virtual array
**
**  unsigned long ARRAY_Get(ARRAY *arr, int index)
**    Reads the array element index. Returns de value arr[index]
**
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*
#define STANDALONE
#define DEBUG
*/

#ifdef STANDALONE

/* Rourtines to make long integers portable */
unsigned long PACKLONG(unsigned long num)
{
    unsigned long _i = 0L;
    unsigned char *_s;

    if (num)
    {
        _s = (unsigned char *) &_i;
        _s[0] = (unsigned char) ((num >> 24) & 0xFF);
        _s[1] = (unsigned char) ((num >> 16) & 0xFF);
        _s[2] = (unsigned char) ((num >> 8) & 0xFF);
        _s[3] = (unsigned char) (num & 0xFF);
        return _i;
    }
    return num;
}


unsigned long UNPACKLONG(unsigned long num)
{
    unsigned char *_s = (unsigned char *) &num;

    return (_s[0] << 24) + (_s[1] << 16) + (_s[2] << 8) + _s[3];
}


static int num = 0;
char *emalloc(unsigned int size)
{
num++;
return malloc(size);
}

void efree(void *p)
{
num--;
free(p);
}


#else

#include "mem.h"

unsigned long PACKLONG(unsigned long num);
unsigned long UNPACKLONG(unsigned long num);
unsigned char *compress3(int num, unsigned char *buffer);
int uncompress2(unsigned char **buffer);

#endif  /* STANDALONE */


#include "array.h"


/* A ARRAY page size */
#define ARRAY_PageSize 4096

#define SizeInt32 4

/* Round to ARRAY_PageSize */
#define ARRAY_RoundPageSize(n) (((n) + ARRAY_PageSize - 1) & (~(ARRAY_PageSize - 1)))

#define ARRAY_PageHeaderSize (1 * SizeInt32) 

#define ARRAY_PageData(pg) ((pg)->data + ARRAY_PageHeaderSize)
#define ARRAY_Data(pg,i) (ARRAY_PageData((pg)) + (i) * SizeInt32)

#define ARRAY_SetNextPage(pg,num) ( *(int *)((pg)->data + 0 * SizeInt32) = PACKLONG(num))

#define ARRAY_GetNextPage(pg,num) ( (num) = UNPACKLONG(*(int *)((pg)->data + 0 * SizeInt32)))


int ARRAY_WritePageToDisk(FILE *fp, ARRAY_Page *pg)
{
    ARRAY_SetNextPage(pg,pg->next);
    fseek(fp,pg->page_number * ARRAY_PageSize,SEEK_SET);
    return fwrite(pg->data,ARRAY_PageSize,1,fp);
}

int ARRAY_WritePage(ARRAY *b, ARRAY_Page *pg)
{
int hash = pg->page_number % ARRAY_CACHE_SIZE;
ARRAY_Page *tmp;
    pg->modified =1;
    if((tmp = b->cache[hash]))
    {
        while(tmp)
        {
            if(tmp->page_number == pg->page_number)
            {
                return 0;
            }
            tmp = tmp->next_cache;
        }
    }
    pg->next_cache = b->cache[hash];
    b->cache[hash] = pg;
    return 0;
}

int ARRAY_FlushCache(ARRAY *b)
{
int i;
ARRAY_Page *tmp, *next;
    for(i = 0; i < ARRAY_CACHE_SIZE; i++)
    {
        if((tmp = b->cache[i]))
        {
            while(tmp)
            {
#ifdef DEBUG
                if(tmp->in_use)
                {
                    printf("DEBUG Error in FlushCache: Page in use\n");
                    exit(0);
                }
#endif
                next = tmp->next_cache;
                if(tmp->modified)
                {
                    ARRAY_WritePageToDisk(b->fp, tmp);
                    tmp->modified = 0;
                }
                if(tmp != b->cache[i])
                    efree(tmp);

                tmp = next;
            }
            b->cache[i]->next_cache = NULL;
        }
    }
    return 0;
}

int ARRAY_CleanCache(ARRAY *b)
{
int i;
ARRAY_Page *tmp,*next;
    for(i = 0; i < ARRAY_CACHE_SIZE; i++)
    {
        if((tmp = b->cache[i]))
        {
            while(tmp)
            {
                next = tmp->next_cache;
                efree(tmp);
                tmp = next;
            }
            b->cache[i] = NULL;
        }
    }
    return 0;
}

ARRAY_Page *ARRAY_ReadPageFromDisk(FILE *fp, unsigned long page_number)
{
ARRAY_Page *pg = (ARRAY_Page *)emalloc(sizeof(ARRAY_Page) + ARRAY_PageSize);

    fseek(fp,page_number * ARRAY_PageSize,SEEK_SET);
    fread(pg->data,ARRAY_PageSize, 1, fp);

    ARRAY_GetNextPage(pg,pg->next);

    pg->page_number = page_number;
    pg->modified = 0;
    return pg;
}

ARRAY_Page *ARRAY_ReadPage(ARRAY *b, unsigned long page_number)
{
int hash = page_number % ARRAY_CACHE_SIZE;
ARRAY_Page *tmp;
    if((tmp = b->cache[hash]))
    {
        while(tmp)
        {
            if(tmp->page_number == page_number)
            {
                return tmp;
            }
            tmp = tmp->next_cache;
        }
    }

    tmp = ARRAY_ReadPageFromDisk(b->fp, page_number);
    tmp->modified = 0;
    tmp->in_use = 1;
    tmp->next_cache = b->cache[hash];
    b->cache[hash] = tmp;
    return tmp;
}

ARRAY_Page *ARRAY_NewPage(ARRAY *b)
{
ARRAY_Page *pg;
long offset;
FILE *fp = b->fp;
int hash;
int size = ARRAY_PageSize;

    /* Get file pointer */
    if(fseek(fp,0,SEEK_END) !=0)
    {
        printf("mal\n");
    }
    offset = ftell(fp);
    /* Round up file pointer */
    offset = ARRAY_RoundPageSize(offset);

    /* Set new file pointer - data will be aligned */
    if(fseek(fp,offset, SEEK_SET)!=0 || offset != ftell(fp))
    {
        printf("mal\n");
    }

    pg = (ARRAY_Page *)emalloc(sizeof(ARRAY_Page) + size);
    memset(pg,0,sizeof(ARRAY_Page) + size);
    /* Reserve space in file */
    if(fwrite(pg->data,1,size,fp)!=size || ((long)size + offset) != ftell(fp))
    {
        printf("mal\n");
    }

    pg->next = 0;

    pg->page_number = offset/ARRAY_PageSize;

    /* add to cache */
    pg->modified = 1;
    pg->in_use = 1;
    hash = pg->page_number % ARRAY_CACHE_SIZE;
    pg->next_cache = b->cache[hash];
    b->cache[hash] = pg;
    return pg;
}

void ARRAY_FreePage(ARRAY *b, ARRAY_Page *pg)
{
int hash = pg->page_number % ARRAY_CACHE_SIZE;
ARRAY_Page *tmp;

    tmp = b->cache[hash];

#ifdef DEBUG
    if(!(tmp = b->cache[hash]))
    {
        /* This should never happen!!!! */
        printf("Error in FreePage\n");
        exit(0);
    }
#endif

    while(tmp)
    {
        if (tmp->page_number != pg->page_number)
            tmp = tmp->next_cache;
        else
        {
            tmp->in_use = 0;
            break;
        }
    }
}

ARRAY *ARRAY_New(FILE *fp, unsigned int size)
{
ARRAY *b;
int i;
    b = (ARRAY *) emalloc(sizeof(ARRAY));
    b->page_size = size;
    b->fp = fp;
    for(i = 0; i < ARRAY_CACHE_SIZE; i++)
        b->cache[i] = NULL;

    return b;
}

ARRAY *ARRAY_Create(FILE *fp)
{
ARRAY *b;
ARRAY_Page *root;
int size = ARRAY_PageSize;

    b = ARRAY_New(fp , size);
    root = ARRAY_NewPage(b);

    b->root_page = root->page_number;

    ARRAY_WritePage(b, root);
    ARRAY_FreePage(b, root);

    return b;
}


ARRAY *ARRAY_Open(FILE *fp, unsigned long root_page)
{
ARRAY *b;
int size = ARRAY_PageSize;

    b = ARRAY_New(fp , size);

    b->root_page = root_page;

    return b;
}

unsigned long ARRAY_Close(ARRAY *bt)
{
unsigned long root_page = bt->root_page;
    ARRAY_FlushCache(bt);
    ARRAY_CleanCache(bt);
    efree(bt);
    return root_page;
}


int ARRAY_Put(ARRAY *b, int index, unsigned long value)
{
unsigned long next_page; 
ARRAY_Page *root_page, *tmp = NULL, *prev; 
int i, hash, page_reads, page_index;

    page_reads = index / ((ARRAY_PageSize - ARRAY_PageHeaderSize) / SizeInt32);
    hash = page_reads % ((ARRAY_PageSize - ARRAY_PageHeaderSize) / SizeInt32);
    page_reads /= ((ARRAY_PageSize - ARRAY_PageHeaderSize) / SizeInt32);
    page_index = index % ((ARRAY_PageSize - ARRAY_PageHeaderSize) / SizeInt32);

    root_page = ARRAY_ReadPage(b, b->root_page);
    next_page = UNPACKLONG(*(unsigned long *)ARRAY_Data(root_page, hash));

    prev = NULL;
    for(i = 0; i <= page_reads; i++)
    {
        if(!next_page)
        {
            tmp = ARRAY_NewPage(b);
            ARRAY_WritePage(b,tmp);
            if(!i)
            {
                *(unsigned long *)ARRAY_Data(root_page,hash) = PACKLONG(tmp->page_number);
                 ARRAY_WritePage(b,root_page);
            }
            else
            {
                prev->next = tmp->page_number;
                ARRAY_WritePage(b,prev);
            }
        } 
        else
        {
            tmp = ARRAY_ReadPage(b, next_page);
        }
        if(prev)
            ARRAY_FreePage(b,prev);
        prev = tmp;
        next_page = tmp->next;
    }
    *(unsigned long *)ARRAY_Data(tmp,page_index) = PACKLONG(value);
    ARRAY_WritePage(b,tmp);
    ARRAY_FreePage(b,tmp);
    ARRAY_FreePage(b,root_page);

    return 0;
}


unsigned long ARRAY_Get(ARRAY *b, int index)
{
unsigned long next_page, value; 
ARRAY_Page *root_page, *tmp;
int i, hash, page_reads, page_index;

    page_reads = index / ((ARRAY_PageSize - ARRAY_PageHeaderSize) / SizeInt32);
    hash = page_reads % ((ARRAY_PageSize - ARRAY_PageHeaderSize) / SizeInt32);
    page_reads /= ((ARRAY_PageSize - ARRAY_PageHeaderSize) / SizeInt32);
    page_index = index % ((ARRAY_PageSize - ARRAY_PageHeaderSize) / SizeInt32);

    root_page = ARRAY_ReadPage(b, b->root_page);
    next_page = UNPACKLONG(*(unsigned long *)ARRAY_Data(root_page, hash));

    tmp = NULL;
    for(i = 0; i <= page_reads; i++)
    {
        if(tmp)
            ARRAY_FreePage(b, tmp);
        if(!next_page)
        {
            ARRAY_FreePage(b,root_page);
            return 0L;
        } 
        else
        {
            tmp = ARRAY_ReadPage(b, next_page);
        }
        next_page = tmp->next;
    }
    value = UNPACKLONG(*(unsigned long *)ARRAY_Data(tmp,page_index));
    ARRAY_FreePage(b,tmp);
    ARRAY_FreePage(b,root_page);

    return value;
}


#ifdef DEBUG

#include <time.h>

#define N_TEST 50000000

#define F_READ_BINARY           "rb"
#define F_WRITE_BINARY          "wb"
#define F_READWRITE_BINARY      "rb+"

#define F_READ_TEXT             "r"
#define F_WRITE_TEXT            "w"
#define F_READWRITE_TEXT        "r+"

int main()
{
FILE *fp;
ARRAY *bt;
int i;
static unsigned long nums[N_TEST];
unsigned long root_page;
    srand(time(NULL));


    fp = fopen("kkkkk",F_WRITE_BINARY);
    fclose(fp);
    fp = fopen("kkkkk",F_READWRITE_BINARY);

    fwrite("aaa",1,3,fp);

printf("\n\nIndexing\n\n");

    bt = ARRAY_Create(fp);
    for(i=0;i<N_TEST;i++)
    {
        nums[i] = rand();
//        nums[i]=i;
        ARRAY_Put(bt,i,nums[i]);
        if(nums[i]!= ARRAY_Get(bt,i))
            printf("\n\nmal %d\n\n",i);
        if(!(i%1000))
        {
            ARRAY_FlushCache(bt);
            printf("%d            \r",i);
        }
    }

    root_page = ARRAY_Close(bt);
    fclose(fp);

printf("\n\nUnfreed %d\n\n",num);
printf("\n\nSearching\n\n");

    fp = fopen("kkkkk",F_READ_BINARY);
    bt = ARRAY_Open(fp, root_page);

    for(i=0;i<N_TEST;i++)
    {
        if(nums[i] != ARRAY_Get(bt,i))
            printf("\n\nmal %d\n\n",i);
        if(!(i%1000))
            printf("%d            \r",i);
    }

    root_page = ARRAY_Close(bt);

    fclose(fp);
printf("\n\nUnfreed %d\n\n",num);

}

#endif
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	/*
58	#define STANDALONE
59	#define DEBUG
60	*/
61
62	#ifdef STANDALONE
63
64	/* Rourtines to make long integers portable */
65	unsigned long PACKLONG(unsigned long num)
66	{
67	unsigned long _i = 0L;
68	unsigned char *_s;
69
70	if (num)
71	{
72	_s = (unsigned char *) &_i;
73	_s[0] = (unsigned char) ((num >> 24) & 0xFF);
74	_s[1] = (unsigned char) ((num >> 16) & 0xFF);
75	_s[2] = (unsigned char) ((num >> 8) & 0xFF);
76	_s[3] = (unsigned char) (num & 0xFF);
77	return _i;
78	}
79	return num;
80	}
81
82
83	unsigned long UNPACKLONG(unsigned long num)
84	{
85	unsigned char _s = (unsigned char ) &num;
86
87	return (_s[0] << 24) + (_s[1] << 16) + (_s[2] << 8) + _s[3];
88	}
89
90
91	static int num = 0;
92	char *emalloc(unsigned int size)
93	{
94	num++;
95	return malloc(size);
96	}
97
98	void efree(void *p)
99	{
100	num--;
101	free(p);
102	}
103
104
105	#else
106
107	#include "mem.h"
108
109	unsigned long PACKLONG(unsigned long num);
110	unsigned long UNPACKLONG(unsigned long num);
111	unsigned char compress3(int num, unsigned char buffer);
112	int uncompress2(unsigned char **buffer);
113
114	#endif /* STANDALONE */
115
116
117	#include "array.h"
118
119
120	/* A ARRAY page size */
121	#define ARRAY_PageSize 4096
122
123	#define SizeInt32 4
124
125	/* Round to ARRAY_PageSize */
126	#define ARRAY_RoundPageSize(n) (((n) + ARRAY_PageSize - 1) & (~(ARRAY_PageSize - 1)))
127
128	#define ARRAY_PageHeaderSize (1 * SizeInt32)
129
130	#define ARRAY_PageData(pg) ((pg)->data + ARRAY_PageHeaderSize)
131	#define ARRAY_Data(pg,i) (ARRAY_PageData((pg)) + (i) * SizeInt32)
132
133	#define ARRAY_SetNextPage(pg,num) ( (int )((pg)->data + 0 * SizeInt32) = PACKLONG(num))
134
135	#define ARRAY_GetNextPage(pg,num) ( (num) = UNPACKLONG((int )((pg)->data + 0 * SizeInt32)))
136
137
138	int ARRAY_WritePageToDisk(FILE fp, ARRAY_Page pg)
139	{
140	ARRAY_SetNextPage(pg,pg->next);
141	fseek(fp,pg->page_number * ARRAY_PageSize,SEEK_SET);
142	return fwrite(pg->data,ARRAY_PageSize,1,fp);
143	}
144
145	int ARRAY_WritePage(ARRAY b, ARRAY_Page pg)
146	{
147	int hash = pg->page_number % ARRAY_CACHE_SIZE;
148	ARRAY_Page *tmp;
149	pg->modified =1;
150	if((tmp = b->cache[hash]))
151	{
152	while(tmp)
153	{
154	if(tmp->page_number == pg->page_number)
155	{
156	return 0;
157	}
158	tmp = tmp->next_cache;
159	}
160	}
161	pg->next_cache = b->cache[hash];
162	b->cache[hash] = pg;
163	return 0;
164	}
165
166	int ARRAY_FlushCache(ARRAY *b)
167	{
168	int i;
169	ARRAY_Page tmp, next;
170	for(i = 0; i < ARRAY_CACHE_SIZE; i++)
171	{
172	if((tmp = b->cache[i]))
173	{
174	while(tmp)
175	{
176	#ifdef DEBUG
177	if(tmp->in_use)
178	{
179	printf("DEBUG Error in FlushCache: Page in use\n");
180	exit(0);
181	}
182	#endif
183	next = tmp->next_cache;
184	if(tmp->modified)
185	{
186	ARRAY_WritePageToDisk(b->fp, tmp);
187	tmp->modified = 0;
188	}
189	if(tmp != b->cache[i])
190	efree(tmp);
191
192	tmp = next;
193	}
194	b->cache[i]->next_cache = NULL;
195	}
196	}
197	return 0;
198	}
199
200	int ARRAY_CleanCache(ARRAY *b)
201	{
202	int i;
203	ARRAY_Page tmp,next;
204	for(i = 0; i < ARRAY_CACHE_SIZE; i++)
205	{
206	if((tmp = b->cache[i]))
207	{
208	while(tmp)
209	{
210	next = tmp->next_cache;
211	efree(tmp);
212	tmp = next;
213	}
214	b->cache[i] = NULL;
215	}
216	}
217	return 0;
218	}
219
220	ARRAY_Page ARRAY_ReadPageFromDisk(FILE fp, unsigned long page_number)
221	{
222	ARRAY_Page pg = (ARRAY_Page )emalloc(sizeof(ARRAY_Page) + ARRAY_PageSize);
223
224	fseek(fp,page_number * ARRAY_PageSize,SEEK_SET);
225	fread(pg->data,ARRAY_PageSize, 1, fp);
226
227	ARRAY_GetNextPage(pg,pg->next);
228
229	pg->page_number = page_number;
230	pg->modified = 0;
231	return pg;
232	}
233
234	ARRAY_Page ARRAY_ReadPage(ARRAY b, unsigned long page_number)
235	{
236	int hash = page_number % ARRAY_CACHE_SIZE;
237	ARRAY_Page *tmp;
238	if((tmp = b->cache[hash]))
239	{
240	while(tmp)
241	{
242	if(tmp->page_number == page_number)
243	{
244	return tmp;
245	}
246	tmp = tmp->next_cache;
247	}
248	}
249
250	tmp = ARRAY_ReadPageFromDisk(b->fp, page_number);
251	tmp->modified = 0;
252	tmp->in_use = 1;
253	tmp->next_cache = b->cache[hash];
254	b->cache[hash] = tmp;
255	return tmp;
256	}
257
258	ARRAY_Page ARRAY_NewPage(ARRAY b)
259	{
260	ARRAY_Page *pg;
261	long offset;
262	FILE *fp = b->fp;
263	int hash;
264	int size = ARRAY_PageSize;
265
266	/* Get file pointer */
267	if(fseek(fp,0,SEEK_END) !=0)
268	{
269	printf("mal\n");
270	}
271	offset = ftell(fp);
272	/* Round up file pointer */
273	offset = ARRAY_RoundPageSize(offset);
274
275	/* Set new file pointer - data will be aligned */
276	if(fseek(fp,offset, SEEK_SET)!=0 \|\| offset != ftell(fp))
277	{
278	printf("mal\n");
279	}
280
281	pg = (ARRAY_Page *)emalloc(sizeof(ARRAY_Page) + size);
282	memset(pg,0,sizeof(ARRAY_Page) + size);
283	/* Reserve space in file */
284	if(fwrite(pg->data,1,size,fp)!=size \|\| ((long)size + offset) != ftell(fp))
285	{
286	printf("mal\n");
287	}
288
289	pg->next = 0;
290
291	pg->page_number = offset/ARRAY_PageSize;
292
293	/* add to cache */
294	pg->modified = 1;
295	pg->in_use = 1;
296	hash = pg->page_number % ARRAY_CACHE_SIZE;
297	pg->next_cache = b->cache[hash];
298	b->cache[hash] = pg;
299	return pg;
300	}
301
302	void ARRAY_FreePage(ARRAY b, ARRAY_Page pg)
303	{
304	int hash = pg->page_number % ARRAY_CACHE_SIZE;
305	ARRAY_Page *tmp;
306
307	tmp = b->cache[hash];
308
309	#ifdef DEBUG
310	if(!(tmp = b->cache[hash]))
311	{
312	/* This should never happen!!!! */
313	printf("Error in FreePage\n");
314	exit(0);
315	}
316	#endif
317
318	while(tmp)
319	{
320	if (tmp->page_number != pg->page_number)
321	tmp = tmp->next_cache;
322	else
323	{
324	tmp->in_use = 0;
325	break;
326	}
327	}
328	}
329
330	ARRAY ARRAY_New(FILE fp, unsigned int size)
331	{
332	ARRAY *b;
333	int i;
334	b = (ARRAY *) emalloc(sizeof(ARRAY));
335	b->page_size = size;
336	b->fp = fp;
337	for(i = 0; i < ARRAY_CACHE_SIZE; i++)
338	b->cache[i] = NULL;
339
340	return b;
341	}
342
343	ARRAY ARRAY_Create(FILE fp)
344	{
345	ARRAY *b;
346	ARRAY_Page *root;
347	int size = ARRAY_PageSize;
348
349	b = ARRAY_New(fp , size);
350	root = ARRAY_NewPage(b);
351
352	b->root_page = root->page_number;
353
354	ARRAY_WritePage(b, root);
355	ARRAY_FreePage(b, root);
356
357	return b;
358	}
359
360
361	ARRAY ARRAY_Open(FILE fp, unsigned long root_page)
362	{
363	ARRAY *b;
364	int size = ARRAY_PageSize;
365
366	b = ARRAY_New(fp , size);
367
368	b->root_page = root_page;
369
370	return b;
371	}
372
373	unsigned long ARRAY_Close(ARRAY *bt)
374	{
375	unsigned long root_page = bt->root_page;
376	ARRAY_FlushCache(bt);
377	ARRAY_CleanCache(bt);
378	efree(bt);
379	return root_page;
380	}
381
382
383	int ARRAY_Put(ARRAY *b, int index, unsigned long value)
384	{
385	unsigned long next_page;
386	ARRAY_Page root_page, tmp = NULL, *prev;
387	int i, hash, page_reads, page_index;
388
389	page_reads = index / ((ARRAY_PageSize - ARRAY_PageHeaderSize) / SizeInt32);
390	hash = page_reads % ((ARRAY_PageSize - ARRAY_PageHeaderSize) / SizeInt32);
391	page_reads /= ((ARRAY_PageSize - ARRAY_PageHeaderSize) / SizeInt32);
392	page_index = index % ((ARRAY_PageSize - ARRAY_PageHeaderSize) / SizeInt32);
393
394	root_page = ARRAY_ReadPage(b, b->root_page);
395	next_page = UNPACKLONG((unsigned long )ARRAY_Data(root_page, hash));
396
397	prev = NULL;
398	for(i = 0; i <= page_reads; i++)
399	{
400	if(!next_page)
401	{
402	tmp = ARRAY_NewPage(b);
403	ARRAY_WritePage(b,tmp);
404	if(!i)
405	{
406	(unsigned long )ARRAY_Data(root_page,hash) = PACKLONG(tmp->page_number);
407	ARRAY_WritePage(b,root_page);
408	}
409	else
410	{
411	prev->next = tmp->page_number;
412	ARRAY_WritePage(b,prev);
413	}
414	}
415	else
416	{
417	tmp = ARRAY_ReadPage(b, next_page);
418	}
419	if(prev)
420	ARRAY_FreePage(b,prev);
421	prev = tmp;
422	next_page = tmp->next;
423	}
424	(unsigned long )ARRAY_Data(tmp,page_index) = PACKLONG(value);
425	ARRAY_WritePage(b,tmp);
426	ARRAY_FreePage(b,tmp);
427	ARRAY_FreePage(b,root_page);
428
429	return 0;
430	}
431
432
433	unsigned long ARRAY_Get(ARRAY *b, int index)
434	{
435	unsigned long next_page, value;
436	ARRAY_Page root_page, tmp;
437	int i, hash, page_reads, page_index;
438
439	page_reads = index / ((ARRAY_PageSize - ARRAY_PageHeaderSize) / SizeInt32);
440	hash = page_reads % ((ARRAY_PageSize - ARRAY_PageHeaderSize) / SizeInt32);
441	page_reads /= ((ARRAY_PageSize - ARRAY_PageHeaderSize) / SizeInt32);
442	page_index = index % ((ARRAY_PageSize - ARRAY_PageHeaderSize) / SizeInt32);
443
444	root_page = ARRAY_ReadPage(b, b->root_page);
445	next_page = UNPACKLONG((unsigned long )ARRAY_Data(root_page, hash));
446
447	tmp = NULL;
448	for(i = 0; i <= page_reads; i++)
449	{
450	if(tmp)
451	ARRAY_FreePage(b, tmp);
452	if(!next_page)
453	{
454	ARRAY_FreePage(b,root_page);
455	return 0L;
456	}
457	else
458	{
459	tmp = ARRAY_ReadPage(b, next_page);
460	}
461	next_page = tmp->next;
462	}
463	value = UNPACKLONG((unsigned long )ARRAY_Data(tmp,page_index));
464	ARRAY_FreePage(b,tmp);
465	ARRAY_FreePage(b,root_page);
466
467	return value;
468	}
469
470
471
472	#ifdef DEBUG
473
474	#include <time.h>
475
476	#define N_TEST 50000000
477
478	#define F_READ_BINARY "rb"
479	#define F_WRITE_BINARY "wb"
480	#define F_READWRITE_BINARY "rb+"
481
482	#define F_READ_TEXT "r"
483	#define F_WRITE_TEXT "w"
484	#define F_READWRITE_TEXT "r+"
485
486	int main()
487	{
488	FILE *fp;
489	ARRAY *bt;
490	int i;
491	static unsigned long nums[N_TEST];
492	unsigned long root_page;
493	srand(time(NULL));
494
495
496
497	fp = fopen("kkkkk",F_WRITE_BINARY);
498	fclose(fp);
499	fp = fopen("kkkkk",F_READWRITE_BINARY);
500
501	fwrite("aaa",1,3,fp);
502
503	printf("\n\nIndexing\n\n");
504
505	bt = ARRAY_Create(fp);
506	for(i=0;i<N_TEST;i++)
507	{
508	nums[i] = rand();
509	// nums[i]=i;
510	ARRAY_Put(bt,i,nums[i]);
511	if(nums[i]!= ARRAY_Get(bt,i))
512	printf("\n\nmal %d\n\n",i);
513	if(!(i%1000))
514	{
515	ARRAY_FlushCache(bt);
516	printf("%d \r",i);
517	}
518	}
519
520	root_page = ARRAY_Close(bt);
521	fclose(fp);
522
523	printf("\n\nUnfreed %d\n\n",num);
524	printf("\n\nSearching\n\n");
525
526	fp = fopen("kkkkk",F_READ_BINARY);
527	bt = ARRAY_Open(fp, root_page);
528
529	for(i=0;i<N_TEST;i++)
530	{
531	if(nums[i] != ARRAY_Get(bt,i))
532	printf("\n\nmal %d\n\n",i);
533	if(!(i%1000))
534	printf("%d \r",i);
535	}
536
537	root_page = ARRAY_Close(bt);
538
539	fclose(fp);
540	printf("\n\nUnfreed %d\n\n",num);
541
542	}
543
544	#endif