You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
145 lines
6.3 KiB
145 lines
6.3 KiB
#include <stdio.h>
|
|
#include <string.h>
|
|
#include <stdlib.h>
|
|
#include <stdbool.h>
|
|
#include <sysexits.h>
|
|
|
|
#define SYMBOL_TABLE_CHUNK 4
|
|
|
|
typedef struct symbol_t {
|
|
char *ident;
|
|
bool defined;
|
|
int value;
|
|
} symbol_t;
|
|
|
|
typedef struct table_t {
|
|
symbol_t **array;
|
|
size_t size; // size_t allows your table to grow past the 1G element limit of a 32-bit number on 64-bit machines
|
|
size_t capacity;
|
|
} table_t;
|
|
|
|
// Make a static initialiser for tables so that they never have to be initialised explicitly.
|
|
// The first call to table_insert() will notice size == capacity (0 == 0) and grow the table.
|
|
// The realloc() function is officially documented to work with a NULL pointer, in which case it bahves like malloc().
|
|
// This makes tables 'self-initialising' and therefore much nicer to work with inside libraries and other 'opaque' places.
|
|
// I like to make all my data structures be self-initialising.
|
|
|
|
#define TABLE_INITIALISER { NULL, 0, 0 } // first call to table_insert() will initialise storage
|
|
|
|
table_t table = TABLE_INITIALISER; // safe but not strictly needed on Unix because BSS segment is initialised to all zeroes
|
|
|
|
// this test happens often so let's abstract it
|
|
// (in a large program it would be better to write xcalloc, xrealloc, xstrdup, etc., that perform the test implicitly)
|
|
|
|
void *memcheck(void *ptr)
|
|
{
|
|
if (NULL == ptr) {
|
|
fprintf(stderr, "Error: out of memory\n");
|
|
exit(EX_OSERR); // this is as close as we have for 'resource unavailable'
|
|
}
|
|
return ptr;
|
|
}
|
|
|
|
// Pass 'table *' as first parameter to make it consistent with other table functions.
|
|
// (Being able to think about the 'table_*' functions as 'methods' that operate on tables is a nice API design.
|
|
// Of course, the disadvantage is that this function is now less general: it can no longer be used to search any array of 'symbol *'s.
|
|
// On the other hand, 'table_t' and 'symbol_t' seem to be part of the same facility, so making this search a 'table *' is maybe OK?)
|
|
|
|
// Renamed from binary_search to indicate that the first argument is a 'table *' to make it consistent with all the other table 'methods'.
|
|
|
|
// Return value changed to ssize_t because (1) 64-bit memory size and (2) let's go back to using -ve integers to represent 'not found'!
|
|
|
|
ssize_t table_search(table_t *table, char *ident)
|
|
{
|
|
ssize_t l= 0, r= table->size - 1; // no longer needed as parameters if we pass a table as the first parameter
|
|
while (l <= r) { // swapped the order of l and r because I always visualise data as laid out from left-to-right ;-)
|
|
ssize_t mid= (l + r) / 2;
|
|
int cmpres= strcmp(table->array[mid]->ident, ident);
|
|
if (cmpres > 0) r= mid - 1;
|
|
else if (cmpres < 0) l= mid + 1;
|
|
else return mid; // non-negative result => element found at this index
|
|
}
|
|
// As you pointed out: 0 == -0 so just negating the desired index is not possible.
|
|
// Think of negation as 'reflecting the number around the point X=0', in other words negation of x is '0 - x'.
|
|
// To allow 0 to make a negative result, just reflect around -1 instead of 0, so negation of x is '-1 - x'.
|
|
// This is actually the one's complement of l, but using '~l' here might be obscure (and the compiler will figure it out anyway).
|
|
return -1 - l; // negative result => 'not found', reflected around -1 instead of 0 to allow 'not found' at index 0
|
|
}
|
|
|
|
// ssize_t result because -1 means 'error'
|
|
|
|
ssize_t table_insert(table_t *table, symbol_t *element, size_t pos)
|
|
{
|
|
if (pos > table->size) { // don't need to check for pos < 0 because size_t is unsigned
|
|
return -1;
|
|
}
|
|
|
|
if (table->size >= table->capacity) {
|
|
// on the first call table->array will be NULL and realloc() will behave like malloc()
|
|
table->array = memcheck(realloc(table->array, sizeof(symbol_t *) * (table->capacity + SYMBOL_TABLE_CHUNK)));
|
|
table->capacity += SYMBOL_TABLE_CHUNK;
|
|
}
|
|
|
|
// use memmove() instead of a loop because memmove() is aggressively optimised on most platforms
|
|
// remove a non-local dependency: use sizeof(*pointer-to-element) in case the type of elements changes in the declaration of table_t
|
|
memmove(table->array + pos + 1, table->array + pos, sizeof(*table->array) * (table->size - pos));
|
|
// for (int i = table->size; i > pos; i--) table->array[i] = table->array[i-1];
|
|
table->array[pos] = element;
|
|
return ++(table->size);
|
|
}
|
|
|
|
symbol_t *intern(char *ident, bool create)
|
|
{
|
|
ssize_t res= table_search(&table, ident); // < 0 => not found
|
|
printf("pos:%zi\n", res);
|
|
if (res >= 0) return table.array[res];
|
|
if (!create) return NULL;
|
|
res= -1 - res; // 'un-negate' the resulr by reflecting it around X=-1
|
|
symbol_t *new_symbol = memcheck(calloc(1, sizeof(symbol_t))); // calloc() will init all content to 0 (including .value member)
|
|
new_symbol->ident = memcheck(strdup(ident)); // check for out-of-memory
|
|
new_symbol->defined = false; // implicit in calloc(), but safer to do it explicitly anyway
|
|
printf("insert:%zi\n", table_insert(&table, new_symbol, res));
|
|
return new_symbol;
|
|
}
|
|
|
|
// no longer needed because tables are now self-initialising
|
|
|
|
// void init_table()
|
|
// {
|
|
// table.array = malloc(sizeof(symbol_t *) * SYMBOL_TABLE_CHUNK);
|
|
// if (table.array == NULL) {
|
|
// printf("Error: running out of memory\n");
|
|
// exit(1);
|
|
// }
|
|
// table.size = 0;
|
|
// table.capacity = SYMBOL_TABLE_CHUNK;
|
|
// }
|
|
|
|
symbol_t *update_value(symbol_t * s, int value)
|
|
{
|
|
s->value = value;
|
|
s->defined = true;
|
|
return s;
|
|
}
|
|
|
|
int main()
|
|
{
|
|
// init_table(); // not needed: tables are self-initialising
|
|
char *line= 0; // this and
|
|
size_t linecap= 0; // this are needed for getline()
|
|
intern("chaussure", true); // identifiers will have no trailing newline so let's test with no trailing newline
|
|
for (;;) { // using an infinite loop simplifies the break/continue logic in the body
|
|
ssize_t len= getline(&line, &linecap, stdin); // use getline() to auto-grow the buffer when necessary
|
|
if (len < 0) break; // stop at EOF
|
|
while ((len > 0) && ('\n' == line[len-1])) line[--len]= 0; // trim newlines from the end
|
|
if (len < 1) continue; // ignore empty lines
|
|
printf("intern : %p\n", intern(line, true));
|
|
printf("after size : %zi\n", table.size);
|
|
printf("after capacity : %zi\n", table.capacity);
|
|
printf("\n");
|
|
for (int i = 0; i < table.size; i++) {
|
|
printf("%i %s\n", i, table.array[i]->ident);
|
|
}
|
|
printf("\n");
|
|
}
|
|
}
|