Ordered map for C using AVL tree

I was in the mood for some data structures and I decided to code up an ordered map using AVL tree. I will post only map.h and map.c. The demonstration driver may be found here.

See what I have:

map.h:

```
#ifndef MAP_H
#define MAP_H

#include

#ifdef __cplusplus
extern "C" {
#endif

typedef struct map_entry_t {
void* p_key;
void* p_value;
struct map_entry_t* p_left;
struct map_entry_t* p_right;
struct map_entry_t* p_parent;
int height;
} map_entry_t;

typedef struct map_t {
map_entry_t* p_root;
int (p_comparator)(void, void*);
size_t size;
size_t mod_count;
} map_t;

typedef struct map_iterator_t {
map_t* p_map;
map_entry_t* p_next;
void** p_ret_array;
size_t iterated_count;
size_t expected_mod_count;
} map_iterator_t;

/*
Allocates a new, empty map with given comparator function.
*/
map_t map_t_alloc (int (p_comparator)(void, void));

/*
If p_map contains the key p_key, associates it with value p_value and
returns the old value of that key.
*/
void map_t_put (map_t p_map, void p_key, void p_value);

/*
Returns a positive value if p_key is mapped to some value in this map.
*/
int map_t_contains_key (map_t p_map, void p_key);

/

Hide implentation

In your header, I would remove all the structure definitions and leave only the typedefs. External users of your map shouldn't need to see into your structures. You can keep the structure definitions private by defining them only in your .c file.

const

I think all of the keys and values should be marked const, since you never modify them. Also, various functions could have const arguments such as map_t_contains_key(), map_t_size(), map_t_is_healthy(), etc.

bool

I would prefer using #include and using bool, true and false rather than defining your own TRUE and FALSE. Some of your functions return a boolean value and could be changed to return a bool instead of an int.

Also, for functions that currently return EXIT_SUCCESS and EXIT_FAILURE, I would return a bool with true indicating success and false indicating failure. EXIT_SUCCESS is used for the return value of your program and is system dependant, so it doesn't make a very good return value for a function.

Comparing keys

In find_entry(), you have this line to match a key:

while (p_entry && p_entry->p_key != key)

The pointer comparison of p_entry->p_key != key seems wrong. Two keys can be equal without having the same address (e.g. two strings). You should call the comparator function and let a zero return value mean equal.

Iterator function

First, this comment is wrong:

/*******************************************************************
 * Returns the next key in the iteration order.                    *
 *******************************************************************/  
void**          map_iterator_t_next         (map_iterator_t* p_iterator);

That function returns an array of two void pointers: the key and the value.

Second, there should be a warning that the values in that array will get overwritten by the next iteration. I'm not quite sure I like this hidden array implementation. It might be more straightforward to have two return pointers, like this:

bool map_iterator_next(map_iterator_t* p_iterator, void** pKey, void **pValue)

Another wrong comment

/*******************************************************************
 * Returns the number of keys not yet iterated over.               *
 *******************************************************************/ 
int             map_iterator_t_has_next     (map_iterator_t* p_iterator);

This function actually returns a boolean value, not a number of keys.

Dead code

These if statements will always be false:

if (!p_map->p_comparator) return NULL;
if (!p_iterator->p_map) return FALSE;

You could use assert() if you want to indicate that some condition must be true, rather than an if statement. An assertion says "this must always be the case and if it isn't, something is wrong with my program logic". An if statement says "this case might happen so I need to check for it".

assert(p_map->p_comparator != NULL);
assert(p_iterator->p_map != NULL);

StackExchange Code Review Q#102357, answer score: 2