1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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
62
63
64
65
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
|
/********************************************************
* infinite-array -- routines to handle infinite arrays *
* *
* An infinite array is an array that grows as needed. *
* There is no index too large for an infinite array *
* (unless we run out of memory). *
********************************************************/
#include "ia.h" /* get common definitions */
#include <stdio.h>
#include <stdlib.h> /* ANSI Standard only */
/*
* the following three variables implement
* a very simple pointer cache
*
* They store information on the last infinite array used,
* the last bucket we had and the last index used
*
* They are initialized to values we know will never
* be used by any real array.
*/
static struct infinite_array *cache_array_ptr = NULL;
static struct infinite_array *cache_bucket_ptr = NULL;
static int cache_index = -1;
/********************************************************
* ia_store -- store an element into an infinite array. *
* *
* Parameters *
* array_ptr -- pointer to the array to use *
* index -- index into the array *
* store_data -- data to store *
********************************************************/
void ia_store(struct infinite_array * array_ptr,
int index, float store_data)
{
/* pointer to the current bucket */
struct infinite_array *current_ptr;
int current_index; /* index into the current bucket */
/* get the location in an infinite array cell */
struct infinite_array *ia_locate(
struct infinite_array *, int, int *);
current_ptr = ia_locate(array_ptr, index, ¤t_index);
current_ptr->data[current_index] = store_data;
}
/********************************************************
* ia_get -- get an element from an infinite array. *
* *
* Parameters *
* array_ptr -- pointer to the array to use *
* index -- index into the array *
* *
* Returns *
* the value of the element *
********************************************************/
float ia_get(struct infinite_array *array_ptr, int index)
{
/* pointer to the current bucket */
struct infinite_array *current_ptr;
int current_index; /* index into the current bucket */
/* get the location an infinite array cell */
struct infinite_array *ia_locate();
current_ptr = ia_locate(array_ptr, index, ¤t_index);
return (current_ptr->data[current_index]);
}
/********************************************************
* ia_locate -- get the location of an infinite array *
* element. *
* *
* Parameters *
* array_ptr -- pointer to the array to use *
* index -- index into the array *
* current_index -- pointer to the index into this *
* bucket (returned) *
* *
* Returns *
* pointer to the current bucket *
********************************************************/
static struct infinite_array ia_locate(
struct infinite_array *array_ptr, int index
int *current_index_ptr)
{
/* pointer to the current bucket */
struct infinite_array *current_ptr;
/* see if the cache will do us any good */
if ((cache_array_ptr == array_ptr) && (index >= cache_index)) {
current_ptr = cache_bucket_ptr;
*current_index_ptr = index - cache_index;
} else {
current_ptr = array_ptr;
*current_index_ptr = index;
}
while (*current_index_ptr > BLOCK_SIZE) {
if (current_ptr->next == NULL) {
current_ptr->next =
(struct infinite_array *)
malloc(sizeof(struct infinite_array));
if (current_ptr->next == NULL) {
(void) fprintf(stderr, "Error:Out of memory\n");
exit(8);
}
}
current_ptr = current_ptr->next;
*current_index_ptr -= BLOCK_SIZE;
}
cache_index = index - (index % BLOCK_SIZE);
cache_array_ptr = array_ptr;
cache_bucket_ptr = current_ptr;
return (current_ptr);
}
|
