Team-Fly in Software

Drawer QR in Software Team-Fly

The Pointer-Array Approach to Sparse Arrays Suppose your spreadsheet has the dimensions 26 by 100 (A1 through Z100), or a total of 2,600 elements In theory, you could use the following array of structures to hold the spreadsheet entries:

struct cell { char cell_name[9]; char formula[128]; } list_entry[2600];

/* 2,600 cells */

However, 2,600 multiplied by 137 (the raw size of the structure) amounts to 356,200 bytes of memory This is a lot of memory to waste on an array that is not fully populated However, you could create an array of pointers to structures of type cell This array of pointers would require a significantly smaller amount of permanent storage than the actual array Each time an array location is assigned data, memory would be allocated for that data and the appropriate pointer in the pointer array would be set to point to that data This scheme offers superior performance over the linked-list and binary-tree methods The declaration that creates such an array of pointers is

struct cell { char cell_name[9]; char formula[128]; } list_entry; struct cell *sheet[2600]; /* array of 2,600 pointers */

You can use this smaller array to hold pointers to the information that is actually entered by the spreadsheet user As each entry is made, a pointer to the information about the cell is stored in the proper location in the array Figure 23-2 shows how this might appear in memory, with the pointer array providing support for the sparse array Before the pointer array can be used, each element must be initialized to null, which indicates that there is no entry in that location The function that does this is

void init_sheet(void) { register int t; for(t=0; t < 2600; ++t) sheet[t] = NULL; }

When the user enters a formula for a cell, the cell location (which is defined by its name) is used to produce an index for the pointer array sheet The index is derived from the cell name by converting the name into a number, as shown in the following listing:

void store(struct cell *i) { int loc; char *p; /* compute index given cell name */ loc = *(i->cell_name) - 'A'; /* column */ p = &(i->cell_name[1]); loc += (atoi(p)-1) * 26; /* number of rows * row width + column */ if(loc >= 2600) { printf(''Cell out of bounds\n"); return; } sheet[loc] = i; /* place pointer in the array */ }

When computing the index, store( ) assumes that all cell names start with a capital letter and are followed by an integer for example, B34, C19, and so on Therefore, using the formula shown in store( ), the cell name Al produces an index of 0, B1

produces an index of 1, A2 produces an index of 26, and so on Because each cell name is unique, each index is also unique, and the pointer to each entry is stored in the proper array element If you compare this procedure to the linked-list or binary-tree version, you will see how much shorter and simpler it is The deletecell( ) function also becomes very short Called with the name of the cell to remove, it simply zeroes the pointer to the element and returns the memory to the system

void deletecell(struct cell *i) { int loc; char *p; /* compute index given cell name */ loc = *(i->cell_name) - 'A'; /* column */ p = &(i->cell_name[1]); loc += (atoi(p)-1) * 26; /* number of rows * row width + column */ if(loc >= 2600) { printf(''Cell out of bounds\n"); return; } if(!sheet[loc]) return; /* don't free a null pointer */ free(sheet[loc]); /* return memory to system */ sheet[loc] = NULL; }

Once again, this code is much faster and simpler than the linked-list version The process of locating a cell given its name is simple because the name itself directly produces the array index Therefore, the function find( ) becomes

struct cell *find(char *cell_name) { int loc; char *p; /* compute index given name */ loc = *(cell_name) - 'A'; /* column */ p = &(cell_name[1]); loc += (atoi(p)-1) * 26; /* number of rows * row width + column */

Page 575 if(loc>=2600 || !sheet[loc]) { /* no entry in that cell */ printf(''Cell not found\n"); return NULL; /* not found */ } else return sheet[loc]; }

Analysis of the Pointer-Array Approach The pointer-array method of sparse-array handling provides much faster access to array elements than either the linked-list or binary-tree method Unless the array is very large, the memory used by the pointer array is not usually a significant drain on the free memory of the system However, the pointer array itself uses some memory for every location whether the pointers are pointing to actual information or not This may be a limitation for certain applications, but it is not a problem in general Hashing Hashing is the process of extracting the index of an array element directly from the information that is stored there The index generated is called the hash Traditionally, hashing has been applied to disk files as a means of decreasing access time However, you can use the same general methods to implement sparse arrays The preceding pointer-array example used a special form of hashing called direct indexing, where each key maps onto one and only one array location In other words, each hashed index is unique (The pointer-array method does not require a direct indexing hash this was just an obvious approach given the spreadsheet problem) In actual practice, such direct hashing schemes are few, and a more flexible method is required This section shows how hashing can be generalized to allow greater power and flexibility The spreadsheet example makes clear that even in the most rigorous environments, not every cell in the sheet will be used Suppose that for virtually all cases, no more than 10 percent of the potential locations are occupied by actual entries Therefore, if the spreadsheet has dimensions 26 by 100 (2,600 locations), only about 260 are actually used at any one time This implies that the largest array necessary to hold all the entries will normally consist of only 260 elements But how do the logical array locations get mapped onto and accessed from this smaller physical array And what happens when this array is full The following discussion describes one possible solution When data for a cell is entered by the user of the spreadsheet (which is the logical array), the cell location, defined by its name, is used to produce an index (a hash) into the smaller physical array As it relates to hashing, the physical array is also called the primary array The index is derived from the cell name, which is converted into a number, as in the pointer-array example However, this number is then divided by 10 to produce an initial entry point into the primary array (Remember, in this example