Originally Posted by
migf1
Even better, I would use a struct for inventory (instead of an array) part of which would be the array of parts and the num_parts counter. This way I would pass just the address of the inventory into the functions.
I concur. If you make it
Code:
typedef struct {
size_t namelen;
char *name;
int number;
int on_hand;
} part_t;
typedef struct {
size_t parts_max; /* Allocated parts */
size_t parts; /* Parts in inventory */
int next; /* Next free number */
part_t **part; /* Array of pointers, pointer per part */
} inventory_t;
#define INVENTORY_INITIALIZER { 0, 0, 1, NULL }
you can easily grow the inventory dynamically when necessary.
For example, to add a new part to inventory, automatically numbering new parts consecutively:
Code:
part_t *add_inventory(inventory_t *const inventory, const char *const name, const int on_hand)
{
const size_t namelen = (name) ? strlen(name) : 0;
part_t *part;
/* Neither pointer can be NULL, and name cannot be empty. */
if (!inventory || namelen < 1) {
errno = EINVAL;
return NULL;
}
/* Is the inventory full? */
if (inventory->parts >= inventory->parts_max) {
size_t parts_max;
part_t **list;
/* Grow parts_max by a bit more, so we don't reallocate so often. */
if (inventory->parts < 16)
parts_max = 16;
else if (inventory->parts < 1048576)
parts_max = (inventory->parts * 5) / 4;
else
parts_max = (inventory->parts | 131071) + 131073;
list = realloc(inventory->part, parts_max * sizeof *inventory->part);
if (!list) {
errno = ENOMEM;
return NULL;
}
inventory->parts_max = parts_max;
inventory->part = list;
}
/* Allocate memory for the new part.
* We include the name in the same area,
* so if you need to reallocate the name string,
* you need to reallocate the entire structure. */
part = malloc((sizeof *part) + namelen + 1);
if (!part) {
errno = ENOMEM;
return NULL;
}
/* The name immediately follows the structure itself. */
part->name = ((char *)part) + sizeof *part;
part->namelen = namelen;
part->number = inventory->next++;
part->on_hand = on_hand;
/* Copy the name, including the '\0' following it. */
memcpy(part->name, name, namelen + 1);
/* Add to inventory. */
inventory->part[inventory->parts++] = part;
/* Success! */
errno = 0;
return part;
}
Locating a part based on its name or number is also very easy:
Code:
part_t *part_by_number(inventory_t *const inventory, const int number)
{
size_t i;
if (!inventory) {
errno = EINVAL;
return NULL;
}
i = inventory->parts;
while (i-->0)
if (inventory->part[i]->number == number)
return inventory->part[i];
errno = ENOENT;
return NULL;
}
part_t *part_by_name(inventory_t *const inventory, const char *const name)
{
const size_t namelen = (name) ? strlen(name) : 0;
size_t i;
if (!inventory || namelen < 1) {
errno = EINVAL;
return NULL;
}
i = inventory->parts;
while (i-->0)
if (inventory->part[i]->namelen == namelen &&
!strcmp(inventory->part[i]->name, name))
return inventory->part[i];
errno = ENOENT;
return NULL;
}
All you need to do is initialize the inventory to INVENTORY_INITIALIZER (so the parts and parts_max are zero and part NULL). (realloc(NULL, size) is the same as malloc(size), so there is no need to treat the first "allocation" any different than any other reallocations.)
For example,
Code:
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <errno.h>
/* The three above code snippets */
int main(void)
{
inventory_t inventory = INVENTORY_INITIALIZER;
part_t *part;
/* Add a wrench to the inventory. We are only interested in the result,
* not the wrench part itself. */
if (!add_inventory(&inventory, "wrench", 1)) {
fprintf(stderr, "Failed to add a wrench to inventory: %s.\n", strerror(errno));
return 1;
}
/* Add five sprockets to inventory. */
part = add_inventory(&inventory, "sprocket", 5);
if (!part) {
fprintf(stderr, "Failed to add sprockets to inventory: %s.\n", strerror(errno));
return 1;
}
/* Since we saved the return pointer, we already have a handle
* to the sprocket part we added to the inventory. */
printf("Sprocket name is '%s', part number %d, and there are %d on hand.\n",
part->name, part->number, part->on_hand);
/* Look up the wrench. */
part = part_by_name(&inventory, "wrench");
if (part)
printf("Wrench name is '%s', part number %d, and there are %d on hand.\n",
part->name, part->number, part->on_hand);
printf("Inventory contains %lu parts.\n", (unsigned long)inventory.parts);
return 0;
}
Efficiency-wise, there are a large number of ways to make this more efficient.
Perhaps the simplest one would be to have two arrays of part pointers in the inventory instead of one, with parts arranged by name in one, and by number in the other. Then you could use binary search to look for the correct part. To insert, you'd first find the correct position (binary search), then move the pointers one step up, and set the new pointer there. The trick is that you need to do this for both arrays, not just one; the index where the new part is inserted to is usually different in the two arrays.
Even when you read data from disk, it's usually the fastest wall-clock-time wise to do it that way, instead of first reading and then sorting. This is because the I/O is usually the bottleneck, and if you do the "insertion work" while also doing I/O, you basically spend CPU time when otherwise your code would be waiting for reads ti complete. (In other words, you do spend more CPU time, but your task completes in less wall clock time.)
In any case, for up to several hundred thousand parts or more, users won't notice the "slowness", since it'll be instantaneous in human terms on any 32-bit processor with enough memory. So, for an exercise, such optimizations are not needed.
However, those kinds of algorithmic optimizations are quite important in real life -- at least if you care about your user experience --, and not at all difficult to implement when you get more proficient in C. So, I think this is a good thing to revisit at some point in the future.
(I for one don't bother to "optimize code", except for certain math stuff when it happens to be the bottleneck. For best results, optimize your algorithms instead of optimizing your code!)
Hope you find this interesting.
