1

/* $Id$ */

     2

     3

#ifndef QUEUE_H

     4

#define QUEUE_H

     5

     6

//#define NOFREE

     7

//#define QUEUE_DEBUG

     8

//#define HASH_DEBUG

     9

//#define HASH_STATS

    10

    11

    12

struct Queue;

    13

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

    14

typedef void* Queue_PopProc(Queue* q);

    15

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

    16

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

    17

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

    18

    19

struct InsSortNode {

    20

	void* item;

    21

	int priority;

    22

	InsSortNode* next;

    23

};

    24

    25

struct BinaryHeapNode {

    26

	void* item;

    27

	int priority;

    28

};

    29

    30

    31

struct Queue{

    32

	/*

    33

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

    34

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

    35

	 */

    36

	Queue_PushProc* push;

    37

	/*

    38

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

    39

	 * is defined by the exact type of queue.

    40

	 */

    41

	Queue_PopProc* pop;

    42

	/*

    43

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

    44

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

    45

	 * if not known.

    46

	 */

    47

	Queue_DeleteProc* del;

    48

    49

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

    50

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

    51

	 * in this way are free()'d.

    52

	 */

    53

	Queue_ClearProc* clear;

    54

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

    55

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

    56

	 * items are free()'d too.

    57

	 */

    58

	Queue_FreeProc* free;

    59

    60

	union {

    61

		struct {

    62

			InsSortNode* first;

    63

		} inssort;

    64

		struct {

    65

			uint max_size;

    66

			uint size;

    67

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

    68

			BinaryHeapNode** elements;

    69

		} binaryheap;

    70

	} data;

    71

};

    72

    73

    74

/*

    75

 * Insertion Sorter

    76

 */

    77

    78

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

    79

 * size */

    80

void init_InsSort(Queue* q);

    81

    82

    83

/*

    84

 *  Binary Heap

    85

 *  For information, see:

    86

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

    87

 */

    88

    89

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

    90

#define BINARY_HEAP_BLOCKSIZE_BITS 10

    91

    92

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

    93

 * max_size elements */

    94

void init_BinaryHeap(Queue* q, uint max_size);

    95

    96

    97

/*

    98

 * Hash

    99

 */

   100

struct HashNode {

   101

	uint key1;

   102

	uint key2;

   103

	void* value;

   104

	HashNode* next;

   105

};

   106

/**

   107

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

   108

 * the resulting range is clearly defined.

   109

 */

   110

typedef uint Hash_HashProc(uint key1, uint key2);

   111

struct Hash {

   112

	/* The hash function used */

   113

	Hash_HashProc* hash;

   114

	/* The amount of items in the hash */

   115

	uint size;

   116

	/* The number of buckets allocated */

   117

	uint num_buckets;

   118

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

   119

	HashNode* buckets;

   120

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

   121

	 * there are any Nodes in the bucket */

   122

	bool* buckets_in_use;

   123

};

   124

   125

/* Call these function to manipulate a hash */

   126

   127

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

   128

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

   129

 * is _not_ free()'d! */

   130

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

   131

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

   132

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

   133

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

   134

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

   135

 * present. */

   136

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

   137

   138

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

   139

   140

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

   141

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

   142

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

   143

/*

   144

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

   145

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

   146

 * are left in the hash.

   147

 */

   148

void delete_Hash(Hash* h, bool free_values);

   149

/*

   150

 * Cleans the hash, but keeps the memory allocated

   151

 */

   152

void clear_Hash(Hash* h, bool free_values);

   153

/*

   154

 * Gets the current size of the Hash

   155

 */

   156

uint Hash_Size(const Hash* h);

   157

   158

#endif /* QUEUE_H */