/* Implementation of the 'array' ADT, with infinite expandability (subject only to overall memory limitations), plus a short main program for testing. Note: We assume that all elements not explicitly given a value are zero. Many applications have arrays with a high proportion of zero elements, and here we can use this assumption to avoid allocating extra memory just to hold zeroes. The implementation works by allocating memory in chunks, each of the size originally requested in the array_create call. If a location outside the existing regions is assigned a non-zero value, chunks are allocated sufficient to hold all elements beyond the last previously allocated, up to the element being assigned a value now. Each chunk contains the address of (pointer to) the next one. This is a simple linked list, but only limited manipulations are required, namely adding nodes to the end, and freeing the entire list. */ #include "anx15-03.h" #include #include /*static*/ CHUNK *makechunk (int size); /**** array_create **** On entry: size is the number of elements initially needed in the array. On exit: returns a pointer to an array, or NULL. */ ARRAY * array_create(int size) { ARRAY * A; A = (ARRAY*)malloc(sizeof(ARRAY)); if (A == NULL) { return NULL; /* failure */ } A->chunk = makechunk(size); /* obtain first chunk */ if (A->chunk == NULL) { free(A); /* failure */ return NULL; } A->num_chunks = 1; /* There is only 1 chunk */ A->size = A->chunk_size = size; /* So total size == chunk size */ return A; } /*static*/ CHUNK *makechunk (int size) { /* Returns the address of an initialised chunk of 'size' elements */ CHUNK * chunk; chunk = (CHUNK*)malloc(sizeof(CHUNK)); if (chunk == NULL) { return NULL; } chunk->elements = (float*)calloc(size, sizeof(float)); /* NB: calloc is similar to malloc, but initialises memory to zero. See Appendix D. */ if (chunk->elements == NULL) { free(chunk); return NULL; } chunk->next = NULL; /* Default: assume this is the final chunk */ return chunk; } /**** array_free **** On entry: arr is a pointer to an array. On exit: The array has been freed. */ void array_free(ARRAY * arr) { /* Method: free all chunks, then the ARRAY itself. */ CHUNK *chunk, *chunk2; /* Free all chunks: */ chunk = arr->chunk; while (chunk != NULL) { chunk2 = chunk->next; /* Remember the next chunk */ free(chunk->elements); /* Free this chunk */ free(chunk); /* " " " */ chunk = chunk2; /* Advance to next chunk */ } /* Free the ARRAY: */ free(arr); } /*static*/ float *find_element (CHUNK *chunk, int chunk_size, long n); /**** array **** On entry: arr is an ARRAY, n is the index of the required element. On exit: Returns the value of the selected element. */ float array(ARRAY * arr, long n) { float *f; if (n < 0 || n >= arr->size) { /* not in array: assume zero */ return 0.0; } /* Here, we know element is allocated; advance through chunks until we have the one the element is within. */ f = find_element(arr->chunk, arr->chunk_size, n); /* Now return value of element within this chunk */ return *f; } /* find_element: Locates the correct element in an array. On entry: chunk is the address of the first chunk in an array, chunk_size is the size of chunks in that array, n is a positive index of the element required, the array does have indices up to n. On exit: Returns the address of the float element required. */ /*static*/ float *find_element (CHUNK *chunk, int chunk_size, long n) { long first_in_chunk, element_after_chunk; /* Method: find the right chunk, then select the element within it */ first_in_chunk = 0; /* Set up for first chunk */ element_after_chunk = chunk_size; /* ditto */ while (n >= element_after_chunk) { /* Not yet the right chunk */ chunk = chunk->next; /* Advance to next chunk */ if (chunk == NULL) { /* Error check: */ fprintf(stderr, "Logic error: chain has too few chunks. \n"); exit(1); /* This is fatal, as our logic must be faulty. */ } first_in_chunk = element_after_chunk;/* ready for next chunk */ element_after_chunk += chunk_size; /* ditto */ } /* Now we have the right chunk */ return &chunk->elements[n - first_in_chunk]; } /**** array_set **** On entry: arr is an ARRAY, n is the positive index of an element. On exit: Element n of arr has been assigned the value f. Returns 1 on failure (could not expand the array), 0 for success. */ int array_set(ARRAY * arr, long n, float f) { long first_in_chunk, element_after_chunk; CHUNK *chunk, *newchunk; if (n >= arr->size) { /* Outside current limits? */ if (f == 0) { return 0; /* Unassigned elements are assumed to be zero, so don't waste space on them. */ } /* Seek last chunk */ chunk = arr->chunk; while (chunk->next != NULL) { chunk = chunk->next; } /* Now add chunks until we add the one the element belongs in. */ element_after_chunk = arr->size; /* The first unassigned element. */ do { /* do...while is OK, as we know at least one more chunk is needed. */ newchunk = makechunk(arr->chunk_size); if (newchunk == NULL) { /* failed! */ return 1; } first_in_chunk = element_after_chunk; /* for latest chunk */ element_after_chunk += arr->chunk_size; /* ditto */ chunk->next = newchunk; /* connect into array */ chunk = newchunk; /* advance chunk ptr */ arr->size += arr->chunk_size; /* fix ARRAY structure */ arr->num_chunks++; /* ditto */ /* Invariant: chunk refers to last chunk, first_in_chunk, element_after_chunk, & arr correct for last chunk. */ } while (element_after_chunk <= n); chunk->elements[n - first_in_chunk] = f; } else { /* Here, we know the element is within the allocated array */ float *fp; fp = find_element(arr->chunk, arr->chunk_size, n); *fp = f; } return 0; } /************************************************************************ Test main program. Allocates an array with a chunk size of eight. (This is far too small for realistic work, but allows us to see what is going on conveniently.) Allows the user to enter the required subscript and the value to be stored, in a loop, and prints the entire array after each number is entered. If the user enters an illegal character for the float being entered, the program stops asking the user for numbers, and prints every tenth number from element 0 to element 100. Uses a 'walk' function, that is, a function that inspects the entire structure of the array. This uses information about the array internal structure, but this is OK for a 'debugging' function. */ void walk(ARRAY *arr, char *message); main () { ARRAY * ap; long i, status; float f; ap = array_create(8); if (ap == NULL) { fprintf(stderr, "Cannot allocate the array.\n"); exit(1); } walk(ap, "After declaring the array, the contents are:"); while ( printf("Enter subscript and number: "), scanf("%ld %f", &i, &f) == 2 /* Only continue if both read OK */ ) { printf("Previous value of element %ld was %f\n", i, array(ap, i)); status = array_set(ap, i, f); if (status) { printf("Failure to allocate the element\n"); } walk(ap, "After setting that element, the array is:"); } for (i=0; i<=100; i+=10) { printf("ap[%ld] is %f\n", i, array(ap,i)); } array_free(ap); } void walk(ARRAY *arr, char *message) { CHUNK *chunk; int i, chunksize, chunknum; printf("\n%s\n", message); printf( "Array size %ld, chunk size %d, number of chunks %ld\n", arr->size, arr->chunk_size, arr->num_chunks ); chunk = arr->chunk; chunknum = 0; chunksize = arr->chunk_size; while (chunk != NULL) { printf("Chunk %2d:", chunknum); for (i = 0; i elements[i]); } putchar('\n'); chunk = chunk->next; chunknum++; } }