Direct-address Set

• Tweet
• 

        A direct-address set, based on the solution given at UBC
to exercise 11.1-4 in Introduction to Algorithms.

Header:

#ifndef _DIRECTSET_D29C82D7_063F_4316_B7F6_20521FB44CB7
#define _DIRECTSET_D29C82D7_063F_4316_B7F6_20521FB44CB7

struct _directset;

typedef struct _directset directset;

typedef int BOOL;

/*Creates a set that can hold keys from 0 to max_entry inclusive.
Passing a key with a higher value than max_entry to any of these functions
results in undefined behaviour.*/
directset* directmake(unsigned max_entry);

/*Returns a non-negative number if the key is in the set, otherwise 0.*/
BOOL directlook(unsigned key, directset* set);

/*Inserts a key into the set. If the key is already present, nothing happens.*/
void directins(unsigned key, directset* set);

/*Deletes a key from the set. The key must be present in the set.*/
void directdel(unsigned key, directset* set);

/*Deletes the entire set.*/
void directfree(directset* set);

#endif

C file:

#include <stdlib.h>
#include <limits.h>
#include <assert.h>
#include "directset.h"

struct _directset {
	/*Entries - an array of keys
	Table - if a key is in the set, this array gives a hint as to where to look in entries.
	Emptys - an array of the indices in entries that contain tombstones.*/

	unsigned *entries, *table, *emptys;
	unsigned n_entries, n_emptys, max_entry;
};

directset* directmake(unsigned max_entry) {
	directset* set = malloc(sizeof(directset));

	if (!set) return NULL;
	set->table = set->entries = set->emptys = NULL; /*So directfree can be used to free data
													if malloc fails*/
	if ((set->table = malloc((max_entry + 1) * sizeof(unsigned)))
		&& (set->entries = malloc((max_entry + 1) * sizeof(unsigned)))
		&& (set->emptys = malloc((max_entry + 1) * sizeof(unsigned)))) {
		set->n_entries = 0;
		set->n_emptys = 0;
		set->max_entry = max_entry;
		return set;
	} else {
		directfree(set);
		return NULL;
	}
}

BOOL directlook(unsigned key, directset* set) {
	assert(key <= set->max_entry);

	/*Entries is used to confirm the key is in the set.*/
	return set->table[key] < set->n_entries && set->entries[set->table[key]] == key;
}

void directins(unsigned key, directset* set) {
	unsigned ins_at;

	assert(key <= set->max_entry);

	if (!directlook(key, set)) {
		/*If there is an empty slot from an earlier deletion,
		insert the key there, otherwise insert it at the end
		of the entries array.*/
		if (set->n_emptys) {
			set->n_emptys--;
			ins_at = set->emptys[set->n_emptys];
		} else {
			ins_at = set->n_entries;
			set->n_entries++;
		}

		set->table[key] = ins_at;
		set->entries[ins_at] = key;
	}
}

void directdel(unsigned key, directset* set) {
	assert(directlook(key, set));
	
	set->emptys[set->n_emptys] = set->table[key];
	set->n_emptys++;

	/*UINT_MAX can't be a valid index into set->tables,
	so it is used as a tombstone for deleted keys.*/
	set->entries[set->table[key]] = UINT_MAX;
}

void directfree(directset* set) {
	free(set->table);
	free(set->entries);
	free(set->emptys);
	free(set);
}

Tags:
• direct
• set
• table