General Observations
The code displays some good programming habits already, such as include guards, good indentation, and wrapping all in if statements, else clauses and loops in braces ({ and }). The file structure is good and it is easy to find which files need to be modified in maintenance. Many of the private sub functions are already removed from the global namespace using the keyword static. The comments are appropriate and don’t require a lot of maintenance.
The areas for improvement are C library functions (don’t reinvent the wheel), memory allocation in C, function complexity, function naming due to complexity, possible performance issues, and C programming conventions.
The rest of this review is organized by listing the items that can be improved in descending order from most major to most minor.
The question would have gotten more attention and wouldn’t have needed a bounty if the following were improved or added:
- A definition of what a hash cons is, I had to google it:
In computer science, particularly in functional programming, hash consing is a technique used to share values that are structurally equal. The term hash consing originates from implementations of Lisp that attempt to reuse cons cells that have been constructed before, avoiding the penalty of memory allocation.
- Rather than just providing a link to a PDF file for the definition of It uses larger twin primes as the capacity and double hashing (open addressing) put at least some of the text in the PDF in the question and make that a link to the PDF for more information.
- Include the entire program in the embedded code.
- Remove commented out code before a code review, it shows that the code may not be ready for a code review.
Contrary to Code Review rules, the review does cover code in the repository that is not included in the code embedded in the question. FYI I know for a fact that 3000 or more can be included in the question, because I have posted questions with more than 3000 lines. Unlike Stack Overflow on Code Review we encourage more of the code to be posted so that we have a really good idea of what the code does, this helps us give a better review.
Improve the Unit Test
The second for loop in main() does not really test if the items were found in the hash cons table. The loop should have a void pointer that receives the value from ``.
printf("starting to get stuff\n");
for (i = 0; i < count; i++) {
void *item = create_dummy(i);
hash_cons_get(item, sizeof(struct dummy), hc);
}
The test should be something like this:
printf("starting to get stuff\n");
for (i = 0; i < count; i++) {
void *item = create_dummy(i);
if (hash_cons_get(item, sizeof(struct dummy), hc) == NULL)
{
printf("Item %d not found\n", i);
}
}
Memory Allocation in the C Programming Language
Unlike some more high level and modern languages, there is no garbage collection of memory that is no longer used. The C programming language provides a library function called free that is used for deallocating memory when it isn’t needed anymore. There is only one call to free() in the code and that is in static void hc_resize(HASH_CONS_TABLE hc, const int capacity). Since the hash cons table itself is allocated as well as the table field within the hash cons table the code currently contains a huge memory leak. The table needs to be deallocated as well.
In the function static void hc_resize(HASH_CONS_TABLE hc, const int capacity) most of the code is unnecessary if the C library function realloc(void *ptr, size_t new_size) is used.
The realloc() function automatically copies the contents of the memory of the original block allocated.
All the calls to malloc() and calloc() are missing necessary error checking. While it is uncommon with modern computers, the C programming memory allocation functions can fail. If they do fail they return NULL. Every call to malloc(), calloc() or realloc() should test that there was a block of memory returned immediately after the call before using the pointer returned. This is especially true in embedded programming where memory might be restricted. The following would be more appropriate in the code, in main()
HASH_CONS_TABLE hc = malloc(sizeof(hc));
if (hc == NULL)
{
fprintf(stderr, "Memory allocation of the hashcons table failed, program exiting.\n");
return EXIT_FAILURE;
}
In the function void hc_initialize(HASH_CONS_TABLE hc, const int base_size) the for loop is unnecessary after you change the code from malloc() to calloc(). Since calloc() was created to allocate arrays the function zeros out the memory during the allocation. If you stayed with the malloc() call it would have been better to use void * memset ( void * ptr, int value, size_t num ). The function memset() is optimized and it should before better than the for loop.
Function Complexity
There are several functions in the program that are too complex (do too much), and their names don't necessarily indicate the complexity. Some of these functions are main(), void hc_insert(HASH_CONS_TABLE hc, void *item) and static void hc_resize(HASH_CONS_TABLE hc, const int capacity). While the C programming language is not object oriented, there are some object oriented principles that can be applied.
The programming principle called the Single Responsibility Principle that applies here. The Single Responsibility Principle states:
that every module, class, or function should have responsibility over a single part of the functionality provided by the software, and that responsibility should be entirely encapsulated by that module, class or function.
There is possible recursion in the functions void hc_insert(HASH_CONS_TABLE hc, void *item), static void hc_resize_up(HASH_CONS_TABLE hc) and static void hc_resize(HASH_CONS_TABLE hc, const int capacity), although I don’t think the recursion is intended.
One possible change in the design would be to have a function that just does an insert into the table and have that function called by void hc_insert(HASH_CONS_TABLE hc, void *item), static void hc_resize_up(HASH_CONS_TABLE hc) and static void hc_resize(HASH_CONS_TABLE hc, const int capacity).
static void private_insert(HASH_CONS_TABLE hc, void *item)
{
int h1 = hash1(hc, item);
int h2 = hash2(hc, item);
// if collision occurs
if (hc->table[h1] != NULL) {
int attempt = 1;
while (true) {
// get new index
int index = hc_get_index(h1, h2, attempt, hc->capacity);
// if no collision occurs, store
if (hc->table[index] == NULL) {
hc->table[index] = item;
break;
}
attempt++;
}
}
// if no collision occurs
else {
hc->table[h1] = item;
}
hc->size++;
}
static void hc_resize(HASH_CONS_TABLE hc, const int capacity) {
HASH_CONS_TABLE temp_hc = malloc(sizeof(struct hash_cons_table));
hc_initialize(temp_hc, capacity);
temp_hc->equalf = hc->equalf;
temp_hc->hashf = hc->hashf;
for (int i = 0; i < hc->capacity; i++) {
void *item = hc->table[i];
if (item != NULL) {
private_insert(temp_hc, item);
}
}
hc->table = temp_hc->table;
hc->capacity = capacity;
free(temp_hc);
}
void hc_insert(HASH_CONS_TABLE hc, void *item) {
if (hc->size > hc->capacity * MAX_DENSITY) {
hc_resize_up(hc);
}
private_insert(hc, item);
}
Another concept we can use from object oriented programming is Data Hiding and private functions. For instance the functionhc_insert() above should be a static function since it isn’t exported by the hashcons.h header file.
A good constructor function for the *HASH_CONS_TABLE struct might be added to hashcons.c and exported by hashcons.h as well as a destructor for the table.
hashcons.h:
extern HASH_CONS_TABLE hash_cons_table_create(HASH_CONS_HASH hashf, HASH_CONS_EQUAL equalf);
extern HASH_CONS_TABLE hash_cons_table_delete(HASH_CONS_TABLE table);
hashcons.c
Hash_Cons_Table_Ptr hash_cons_table_create(Hash_Cons_Hash hashf, Hash_Cons_Equal equalf)
{
Hash_Cons_Table_Ptr hc = malloc(sizeof(*hc));
if (hc == NULL)
{
fprintf(stderr, "Memory allocation of the hashcons table failed, program exiting.\n");
return NULL;
}
memset(hc, 0, sizeof(*hc));
hc->hashf = hashf;
hc->equalf = equalf;
return hc;
}
HASH_CONS_TABLE hash_cons_table_delete(HASH_CONS_TABLE hc)
{
for (size_t i = 0; i < hc->capacity)
{
if (hc->table[i])
{
free(hc->table[i]);
}
}
free(hc->table);
free(hc);
return NULL;
}
main.c:
static int test_adding_items(HASH_CONS_TABLE hc, int test_sample)
{
printf("starting to add stuff\n");
int failure_count = 0;
for (int i = 0; i < test_sample; i++) {
void *item = create_dummy(i);
if (!hash_cons_get(item, sizeof(struct dummy), hc))
{
failure_count++;
}
}
printf("finished adding stuff\n");
return failure_count;
}
static int test_getting_times(HASH_CONS_TABLE hc, int test_sample)
{
printf("starting to get stuff\n");
int failure_count = 0;
for (size_t i = 0; i < test_sample; i++) {
void *item = create_dummy(i);
if (hash_cons_get(item, sizeof(struct dummy), hc) == NULL)
{
failure_count++;
printf("Item %d not found\n", i);
}
}
printf("finished getting stuff\n");
return failure_count;
}
int main() {
HASH_CONS_TABLE hc = hash_cons_table_create(hash, equal);
if (hc == NULL)
{
fprintf(stderr, "Memory allocation of the hashcons table failed, program exiting.\n");
return EXIT_FAILURE;
}
int count = 30000;
printf("There were %d failures in test_adding_items", test_adding_items(hc, count));
printf("There were %d failures in test_getting_times", test_getting_times(hc, count));
hc = hash_cons_table_delete(hc);
printf("Done!");
return EXIT_SUCCESS;
}
It might be better to add a max_density field to the HASH_CONS_TABLE struct so that it could be set by flags during creation. Once the table is actually in use, the user may want to increase the density.
Possible Performance Improvements
Rather than performing a search for the proper primes when resizing the table, it would be better to build a table of paired primes when the hash cons table is constructed using the Sieve of Eratosthenes. When the table needs to be resized just index to the next pair of primes in the table and use those. This will prevent large overhead during item insert and improve performance. There will be a performance hit when the hash cons table is created, but that will be once rather than many times during execution.
Portability (Don’t Reinvent the Wheel)
The code would be much more portable if the standard header file stdbool.h was include instead of the symbolic constants defined in common.h. This would allow the code to have Boolean types and use true and false rather than TRUE and FALSE. This will come in handy if the code is ported to C++ as some point, and stdbool.h should be available wherever C90 is available.
Conventions
Rather than using int as an index into a table, prefer unsigned values such as unsigned int, unsigned long or size_t. This will prevent negative indexes in a table, especially when it is possible for integer overflow to happen (integers can go negative if they are incremented too far.
Capitalize types rather than making them all capitals, all capitals is generally reserved for macros and constants (the code is already doing this).
#include <stdbool.h>
typedef long (*Hash_Cons_Hash)(void *item);
typedef bool (*Hash_Cons_Equal)(void *item1, void *item2);
typedef struct hash_cons_table {
int size;
int capacity;
void **table;
Hash_Cons_Hash hashf;
Hash_Cons_Equal equalf;
} *Hash_Cons_Table_Ptr;
Include the variable names in the function prototypes so that users have some idea of what should be passed in. (self-documenting code)
The header file stdlib.h includes 2 symbolic constants for C program exit status. These are EXIT_SUCCESS and EXIT_FAILURE. These symbolic constants make main() easier to read and understand.
In main.c it might be better if 13, 17 and 3000 were symbolic constants that would make the code more self-documenting, it is unclear why those numbers were chosen.
