1

/* $Id$ */

     2

     3

/** @file queue.h Simple Queue/Hash implementations. */

     4

     5

#ifndef QUEUE_H

     6

#define QUEUE_H

     7

     8

//#define NOFREE

     9

//#define QUEUE_DEBUG

    10

//#define HASH_DEBUG

    11

//#define HASH_STATS

    12

    13

    14

struct Queue;

    15

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

    16

typedef void* Queue_PopProc(Queue *q);

    17

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

    18

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

    19

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

    20

    21

struct InsSortNode {

    22

	void *item;

    23

	int priority;

    24

	InsSortNode* next;

    25

};

    26

    27

struct BinaryHeapNode {

    28

	void *item;

    29

	int priority;

    30

};

    31

    32

    33

struct Queue{

    34

	/*

    35

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

    36

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

    37

	 */

    38

	Queue_PushProc *push;

    39

	/*

    40

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

    41

	 * is defined by the exact type of queue.

    42

	 */

    43

	Queue_PopProc *pop;

    44

	/*

    45

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

    46

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

    47

	 * if not known.

    48

	 */

    49

	Queue_DeleteProc *del;

    50

    51

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

    52

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

    53

	 * in this way are free()'d.

    54

	 */

    55

	Queue_ClearProc *clear;

    56

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

    57

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

    58

	 * items are free()'d too.

    59

	 */

    60

	Queue_FreeProc *free;

    61

    62

	union {

    63

		struct {

    64

			InsSortNode *first;

    65

		} inssort;

    66

		struct {

    67

			uint max_size;

    68

			uint size;

    69

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

    70

			BinaryHeapNode **elements;

    71

		} binaryheap;

    72

	} data;

    73

};

    74

    75

    76

/**

    77

 * Insertion Sorter

    78

 */

    79

    80

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

    81

 * size */

    82

void init_InsSort(Queue *q);

    83

    84

    85

/*

    86

 *  Binary Heap

    87

 *  For information, see:

    88

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

    89

 */

    90

    91

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

    92

#define BINARY_HEAP_BLOCKSIZE_BITS 10

    93

    94

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

    95

 * max_size elements */

    96

void init_BinaryHeap(Queue *q, uint max_size);

    97

    98

    99

/*

   100

 * Hash

   101

 */

   102

struct HashNode {

   103

	uint key1;

   104

	uint key2;

   105

	void *value;

   106

	HashNode *next;

   107

};

   108

/**

   109

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

   110

 * the resulting range is clearly defined.

   111

 */

   112

typedef uint Hash_HashProc(uint key1, uint key2);

   113

struct Hash {

   114

	/* The hash function used */

   115

	Hash_HashProc *hash;

   116

	/* The amount of items in the hash */

   117

	uint size;

   118

	/* The number of buckets allocated */

   119

	uint num_buckets;

   120

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

   121

	HashNode *buckets;

   122

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

   123

	 * there are any Nodes in the bucket */

   124

	bool *buckets_in_use;

   125

};

   126

   127

/* Call these function to manipulate a hash */

   128

   129

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

   130

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

   131

 * is _not_ free()'d! */

   132

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

   133

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

   134

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

   135

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

   136

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

   137

 * present. */

   138

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

   139

   140

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

   141

   142

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

   143

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

   144

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

   145

/**

   146

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

   147

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

   148

 * are left in the hash.

   149

 */

   150

void delete_Hash(Hash *h, bool free_values);

   151

/**

   152

 * Cleans the hash, but keeps the memory allocated

   153

 */

   154

void clear_Hash(Hash *h, bool free_values);

   155

/**

   156

 * Gets the current size of the Hash

   157

 */

   158

uint Hash_Size(const Hash *h);

   159

   160

#endif /* QUEUE_H */