1

#ifndef QUEUE_H

     2

#define QUEUE_H

     3

     4

//#define NOFREE

     5

//#define QUEUE_DEBUG

     6

//#define HASH_DEBUG

     7

//#define HASH_STATS

     8

     9

    10

typedef struct Queue Queue;

    11

typedef bool Queue_PushProc(Queue* q, void* item, int priority);

    12

typedef void* Queue_PopProc(Queue* q);

    13

typedef bool Queue_DeleteProc(Queue* q, void* item, int priority);

    14

typedef void Queue_ClearProc(Queue* q, bool free_values);

    15

typedef void Queue_FreeProc(Queue* q, bool free_values);

    16

    17

typedef struct InsSortNode InsSortNode;

    18

struct InsSortNode {

    19

	void* item;

    20

	int priority;

    21

	InsSortNode* next;

    22

};

    23

typedef struct BinaryHeapNode BinaryHeapNode;

    24

	struct BinaryHeapNode {

    25

	void* item;

    26

	int priority;

    27

};

    28

    29

    30

struct Queue{

    31

	/*

    32

	 * Pushes an element into the queue, at the appropriate place for the queue.

    33

	 * Requires the queue pointer to be of an appropriate type, of course.

    34

	 */

    35

	Queue_PushProc* push;

    36

	/*

    37

	 * Pops the first element from the queue. What exactly is the first element,

    38

	 * is defined by the exact type of queue.

    39

	 */

    40

	Queue_PopProc* pop;

    41

	/*

    42

	 * Deletes the item from the queue. priority should be specified if

    43

	 * known, which speeds up the deleting for some queue's. Should be -1

    44

	 * if not known.

    45

	 */

    46

	Queue_DeleteProc* del;

    47

    48

	/* Clears the queue, by removing all values from it. It's state is

    49

	 * effectively reset. If free_items is true, each of the items cleared

    50

	 * in this way are free()'d.

    51

	 */

    52

	Queue_ClearProc* clear;

    53

	/* Frees the queue, by reclaiming all memory allocated by it. After

    54

	 * this it is no longer usable. If free_items is true, any remaining

    55

	 * items are free()'d too.

    56

	 */

    57

	Queue_FreeProc* free;

    58

    59

	union {

    60

		struct {

    61

			uint max_size;

    62

			uint size;

    63

			void** elements;

    64

		} stack;

    65

		struct {

    66

			uint max_size;

    67

			uint head; /* The index where the last element should be inserted */

    68

			uint tail; /* The index where the next element should be read */

    69

			void** elements;

    70

		} fifo;

    71

		struct {

    72

			InsSortNode* first;

    73

		} inssort;

    74

		struct {

    75

			uint max_size;

    76

			uint size;

    77

			uint blocks; /* The amount of blocks for which space is reserved in elements */

    78

			BinaryHeapNode** elements;

    79

		} binaryheap;

    80

	} data;

    81

    82

	/* If true, this struct will be free'd when the

    83

	 * Queue is deleted. */

    84

	bool freeq;

    85

};

    86

    87

/* Initializes a stack and allocates internal memory. */

    88

void init_Stack(Queue* q, uint max_size);

    89

    90

/* Allocate a new stack with a maximum of max_size elements. */

    91

Queue* new_Stack(uint max_size);

    92

    93

/*

    94

 * Fifo

    95

 */

    96

    97

/* Initializes a fifo and allocates internal memory for maximum of max_size

    98

 * elements */

    99

void init_Fifo(Queue* q, uint max_size);

   100

   101

/* Allocate a new fifo and initializes it with a maximum of max_size elements. */

   102

Queue* new_Fifo(uint max_size);

   103

   104

Queue* new_Fifo_in_buffer(uint max_size, void* buffer);

   105

   106

int build_Fifo(void* buffer, uint size);

   107

   108

/*

   109

 * Insertion Sorter

   110

 */

   111

   112

/* Initializes a inssort and allocates internal memory. There is no maximum

   113

 * size */

   114

void init_InsSort(Queue* q);

   115

   116

/* Allocate a new fifo and initializes it. There is no maximum size */

   117

Queue* new_InsSort(void);

   118

   119

/*

   120

 *  Binary Heap

   121

 *  For information, see:

   122

 *   http://www.policyalmanac.org/games/binaryHeaps.htm

   123

 */

   124

   125

/* The amount of elements that will be malloc'd at a time */

   126

#define BINARY_HEAP_BLOCKSIZE_BITS 10

   127

   128

/* Initializes a binary heap and allocates internal memory for maximum of

   129

 * max_size elements */

   130

void init_BinaryHeap(Queue* q, uint max_size);

   131

   132

/* Allocate a new binary heap and initializes it with a maximum of max_size

   133

 * elements. */

   134

Queue* new_BinaryHeap(uint max_size);

   135

   136

/*

   137

 * Hash

   138

 */

   139

typedef struct HashNode HashNode;

   140

struct HashNode {

   141

	uint key1;

   142

	uint key2;

   143

	void* value;

   144

	HashNode* next;

   145

};

   146

/**

   147

 * Generates a hash code from the given key pair. You should make sure that

   148

 * the resulting range is clearly defined.

   149

 */

   150

typedef uint Hash_HashProc(uint key1, uint key2);

   151

typedef struct Hash {

   152

	/* The hash function used */

   153

	Hash_HashProc* hash;

   154

	/* The amount of items in the hash */

   155

	uint size;

   156

	/* The number of buckets allocated */

   157

	uint num_buckets;

   158

	/* A pointer to an array of num_buckets buckets. */

   159

	HashNode* buckets;

   160

	/* A pointer to an array of numbuckets booleans, which will be true if

   161

	 * there are any Nodes in the bucket */

   162

	bool* buckets_in_use;

   163

	/* If true, buckets will be freed in delete_hash */

   164

	bool freeb;

   165

	/* If true, the pointer to this struct will be freed in delete_hash */

   166

	bool freeh;

   167

} Hash;

   168

   169

/* Call these function to manipulate a hash */

   170

   171

/* Deletes the value with the specified key pair from the hash and returns

   172

 * that value. Returns NULL when the value was not present. The value returned

   173

 * is _not_ free()'d! */

   174

void* Hash_Delete(Hash* h, uint key1, uint key2);

   175

/* Sets the value associated with the given key pair to the given value.

   176

 * Returns the old value if the value was replaced, NULL when it was not yet present. */

   177

void* Hash_Set(Hash* h, uint key1, uint key2, void* value);

   178

/* Gets the value associated with the given key pair, or NULL when it is not

   179

 * present. */

   180

void* Hash_Get(Hash* h, uint key1, uint key2);

   181

   182

/* Call these function to create/destroy a hash */

   183

   184

/* Builds a new hash, with num_buckets buckets. Make sure that hash() always

   185

 * returns a hash less than num_buckets! Call delete_hash after use */

   186

Hash* new_Hash(Hash_HashProc* hash, int num_buckets);

   187

/* Builds a new hash in an existing struct. Make sure that hash() always

   188

 * returns a hash less than num_buckets! Call delete_hash after use */

   189

void init_Hash(Hash* h, Hash_HashProc* hash, uint num_buckets);

   190

/*

   191

 * Deletes the hash and cleans up. Only cleans up memory allocated by new_Hash

   192

 * & friends. If free is true, it will call free() on all the values that

   193

 * are left in the hash.

   194

 */

   195

void delete_Hash(Hash* h, bool free_values);

   196

/*

   197

 * Cleans the hash, but keeps the memory allocated

   198

 */

   199

void clear_Hash(Hash* h, bool free_values);

   200

/*

   201

 * Gets the current size of the Hash

   202

 */

   203

uint Hash_Size(Hash* h);

   204

   205

#endif /* QUEUE_H */