# queue.cpp

Go to the documentation of this file.

    00001 /* $Id: queue.cpp 15568 2009-02-24 20:59:17Z smatz $ */
    00002
    00005 #include "stdafx.h"
    00006 #include "queue.h"
    00007 #include "core/alloc_func.hpp"
    00008
    00009
    00010 /*
    00011  * Insertion Sorter
    00012  */
    00013
    00014 static void InsSort_Clear(Queue *q, bool free_values)
    00015 {
    00016   InsSortNode *node = q->data.inssort.first;
    00017   InsSortNode *prev;
    00018
    00019   while (node != NULL) {
    00020     if (free_values) free(node->item);
    00021     prev = node;
    00022     node = node->next;
    00023     free(prev);
    00024   }
    00025   q->data.inssort.first = NULL;
    00026 }
    00027
    00028 static void InsSort_Free(Queue *q, bool free_values)
    00029 {
    00030   q->clear(q, free_values);
    00031 }
    00032
    00033 static bool InsSort_Push(Queue *q, void *item, int priority)
    00034 {
    00035   InsSortNode *newnode = MallocT<InsSortNode>(1);
    00036
    00037   newnode->item = item;
    00038   newnode->priority = priority;
    00039   if (q->data.inssort.first == NULL ||
    00040       q->data.inssort.first->priority >= priority) {
    00041     newnode->next = q->data.inssort.first;
    00042     q->data.inssort.first = newnode;
    00043   } else {
    00044     InsSortNode *node = q->data.inssort.first;
    00045     while (node != NULL) {
    00046       if (node->next == NULL || node->next->priority >= priority) {
    00047         newnode->next = node->next;
    00048         node->next = newnode;
    00049         break;
    00050       }
    00051       node = node->next;
    00052     }
    00053   }
    00054   return true;
    00055 }
    00056
    00057 static void *InsSort_Pop(Queue *q)
    00058 {
    00059   InsSortNode *node = q->data.inssort.first;
    00060   void *result;
    00061
    00062   if (node == NULL) return NULL;
    00063   result = node->item;
    00064   q->data.inssort.first = q->data.inssort.first->next;
    00065   assert(q->data.inssort.first == NULL || q->data.inssort.first->priority >= node->priority);
    00066   free(node);
    00067   return result;
    00068 }
    00069
    00070 static bool InsSort_Delete(Queue *q, void *item, int priority)
    00071 {
    00072   return false;
    00073 }
    00074
    00075 void init_InsSort(Queue *q)
    00076 {
    00077   q->push = InsSort_Push;
    00078   q->pop = InsSort_Pop;
    00079   q->del = InsSort_Delete;
    00080   q->clear = InsSort_Clear;
    00081   q->free = InsSort_Free;
    00082   q->data.inssort.first = NULL;
    00083 }
    00084
    00085
    00086 /*
    00087  * Binary Heap
    00088  * For information, see: http://www.policyalmanac.org/games/binaryHeaps.htm
    00089  */
    00090
    00091 #define BINARY_HEAP_BLOCKSIZE (1 << BINARY_HEAP_BLOCKSIZE_BITS)
    00092 #define BINARY_HEAP_BLOCKSIZE_MASK (BINARY_HEAP_BLOCKSIZE - 1)
    00093
    00094 /* To make our life easy, we make the next define
    00095  *  Because Binary Heaps works with array from 1 to n,
    00096  *  and C with array from 0 to n-1, and we don't like typing
    00097  *  q->data.binaryheap.elements[i - 1] every time, we use this define. */
    00098 #define BIN_HEAP_ARR(i) q->data.binaryheap.elements[((i) - 1) >> BINARY_HEAP_BLOCKSIZE_BITS][((i) - 1) & BINARY_HEAP_BLOCKSIZE_MASK]
    00099
    00100 static void BinaryHeap_Clear(Queue *q, bool free_values)
    00101 {
    00102   /* Free all items if needed and free all but the first blocks of memory */
    00103   uint i;
    00104   uint j;
    00105
    00106   for (i = 0; i < q->data.binaryheap.blocks; i++) {
    00107     if (q->data.binaryheap.elements[i] == NULL) {
    00108       /* No more allocated blocks */
    00109       break;
    00110     }
    00111     /* For every allocated block */
    00112     if (free_values) {
    00113       for (j = 0; j < (1 << BINARY_HEAP_BLOCKSIZE_BITS); j++) {
    00114         /* For every element in the block */
    00115         if ((q->data.binaryheap.size >> BINARY_HEAP_BLOCKSIZE_BITS) == i &&
    00116             (q->data.binaryheap.size & BINARY_HEAP_BLOCKSIZE_MASK) == j) {
    00117           break; // We're past the last element
    00118         }
    00119         free(q->data.binaryheap.elements[i][j].item);
    00120       }
    00121     }
    00122     if (i != 0) {
    00123       /* Leave the first block of memory alone */
    00124       free(q->data.binaryheap.elements[i]);
    00125       q->data.binaryheap.elements[i] = NULL;
    00126     }
    00127   }
    00128   q->data.binaryheap.size = 0;
    00129   q->data.binaryheap.blocks = 1;
    00130 }
    00131
    00132 static void BinaryHeap_Free(Queue *q, bool free_values)
    00133 {
    00134   uint i;
    00135
    00136   q->clear(q, free_values);
    00137   for (i = 0; i < q->data.binaryheap.blocks; i++) {
    00138     if (q->data.binaryheap.elements[i] == NULL) break;
    00139     free(q->data.binaryheap.elements[i]);
    00140   }
    00141   free(q->data.binaryheap.elements);
    00142 }
    00143
    00144 static bool BinaryHeap_Push(Queue *q, void *item, int priority)
    00145 {
    00146 #ifdef QUEUE_DEBUG
    00147   printf("[BinaryHeap] Pushing an element. There are %d elements left\n", q->data.binaryheap.size);
    00148 #endif
    00149
    00150   if (q->data.binaryheap.size == q->data.binaryheap.max_size) return false;
    00151   assert(q->data.binaryheap.size < q->data.binaryheap.max_size);
    00152
    00153   if (q->data.binaryheap.elements[q->data.binaryheap.size >> BINARY_HEAP_BLOCKSIZE_BITS] == NULL) {
    00154     /* The currently allocated blocks are full, allocate a new one */
    00155     assert((q->data.binaryheap.size & BINARY_HEAP_BLOCKSIZE_MASK) == 0);
    00156     q->data.binaryheap.elements[q->data.binaryheap.size >> BINARY_HEAP_BLOCKSIZE_BITS] = MallocT<BinaryHeapNode>(BINARY_HEAP_BLOCKSIZE);
    00157     q->data.binaryheap.blocks++;
    00158 #ifdef QUEUE_DEBUG
    00159     printf("[BinaryHeap] Increasing size of elements to %d nodes\n", q->data.binaryheap.blocks *  BINARY_HEAP_BLOCKSIZE);
    00160 #endif
    00161   }
    00162
    00163   /* Add the item at the end of the array */
    00164   BIN_HEAP_ARR(q->data.binaryheap.size + 1).priority = priority;
    00165   BIN_HEAP_ARR(q->data.binaryheap.size + 1).item = item;
    00166   q->data.binaryheap.size++;
    00167
    00168   /* Now we are going to check where it belongs. As long as the parent is
    00169    * bigger, we switch with the parent */
    00170   {
    00171     BinaryHeapNode temp;
    00172     int i;
    00173     int j;
    00174
    00175     i = q->data.binaryheap.size;
    00176     while (i > 1) {
    00177       /* Get the parent of this object (divide by 2) */
    00178       j = i / 2;
    00179       /* Is the parent bigger then the current, switch them */
    00180       if (BIN_HEAP_ARR(i).priority <= BIN_HEAP_ARR(j).priority) {
    00181         temp = BIN_HEAP_ARR(j);
    00182         BIN_HEAP_ARR(j) = BIN_HEAP_ARR(i);
    00183         BIN_HEAP_ARR(i) = temp;
    00184         i = j;
    00185       } else {
    00186         /* It is not, we're done! */
    00187         break;
    00188       }
    00189     }
    00190   }
    00191
    00192   return true;
    00193 }
    00194
    00195 static bool BinaryHeap_Delete(Queue *q, void *item, int priority)
    00196 {
    00197   uint i = 0;
    00198
    00199 #ifdef QUEUE_DEBUG
    00200   printf("[BinaryHeap] Deleting an element. There are %d elements left\n", q->data.binaryheap.size);
    00201 #endif
    00202
    00203   /* First, we try to find the item.. */
    00204   do {
    00205     if (BIN_HEAP_ARR(i + 1).item == item) break;
    00206     i++;
    00207   } while (i < q->data.binaryheap.size);
    00208   /* We did not find the item, so we return false */
    00209   if (i == q->data.binaryheap.size) return false;
    00210
    00211   /* Now we put the last item over the current item while decreasing the size of the elements */
    00212   q->data.binaryheap.size--;
    00213   BIN_HEAP_ARR(i + 1) = BIN_HEAP_ARR(q->data.binaryheap.size + 1);
    00214
    00215   /* Now the only thing we have to do, is resort it..
    00216    * On place i there is the item to be sorted.. let's start there */
    00217   {
    00218     uint j;
    00219     BinaryHeapNode temp;
    00220     /* Because of the fact that Binary Heap uses array from 1 to n, we need to
    00221      * increase i by 1
    00222      */
    00223     i++;
    00224
    00225     for (;;) {
    00226       j = i;
    00227       /* Check if we have 2 childs */
    00228       if (2 * j + 1 <= q->data.binaryheap.size) {
    00229         /* Is this child smaller than the parent? */
    00230         if (BIN_HEAP_ARR(j).priority >= BIN_HEAP_ARR(2 * j).priority) i = 2 * j;
    00231         /* Yes, we _need_ to use i here, not j, because we want to have the smallest child
    00232          *  This way we get that straight away! */
    00233         if (BIN_HEAP_ARR(i).priority >= BIN_HEAP_ARR(2 * j + 1).priority) i = 2 * j + 1;
    00234       /* Do we have one child? */
    00235       } else if (2 * j <= q->data.binaryheap.size) {
    00236         if (BIN_HEAP_ARR(j).priority >= BIN_HEAP_ARR(2 * j).priority) i = 2 * j;
    00237       }
    00238
    00239       /* One of our childs is smaller than we are, switch */
    00240       if (i != j) {
    00241         temp = BIN_HEAP_ARR(j);
    00242         BIN_HEAP_ARR(j) = BIN_HEAP_ARR(i);
    00243         BIN_HEAP_ARR(i) = temp;
    00244       } else {
    00245         /* None of our childs is smaller, so we stay here.. stop :) */
    00246         break;
    00247       }
    00248     }
    00249   }
    00250
    00251   return true;
    00252 }
    00253
    00254 static void *BinaryHeap_Pop(Queue *q)
    00255 {
    00256   void *result;
    00257
    00258 #ifdef QUEUE_DEBUG
    00259   printf("[BinaryHeap] Popping an element. There are %d elements left\n", q->data.binaryheap.size);
    00260 #endif
    00261
    00262   if (q->data.binaryheap.size == 0) return NULL;
    00263
    00264   /* The best item is always on top, so give that as result */
    00265   result = BIN_HEAP_ARR(1).item;
    00266   /* And now we should get rid of this item... */
    00267   BinaryHeap_Delete(q, BIN_HEAP_ARR(1).item, BIN_HEAP_ARR(1).priority);
    00268
    00269   return result;
    00270 }
    00271
    00272 void init_BinaryHeap(Queue *q, uint max_size)
    00273 {
    00274   assert(q != NULL);
    00275   q->push = BinaryHeap_Push;
    00276   q->pop = BinaryHeap_Pop;
    00277   q->del = BinaryHeap_Delete;
    00278   q->clear = BinaryHeap_Clear;
    00279   q->free = BinaryHeap_Free;
    00280   q->data.binaryheap.max_size = max_size;
    00281   q->data.binaryheap.size = 0;
    00282   /* We malloc memory in block of BINARY_HEAP_BLOCKSIZE
    00283    *   It autosizes when it runs out of memory */
    00284   q->data.binaryheap.elements = CallocT<BinaryHeapNode*>((max_size - 1) / BINARY_HEAP_BLOCKSIZE + 1);
    00285   q->data.binaryheap.elements[0] = MallocT<BinaryHeapNode>(BINARY_HEAP_BLOCKSIZE);
    00286   q->data.binaryheap.blocks = 1;
    00287 #ifdef QUEUE_DEBUG
    00288   printf("[BinaryHeap] Initial size of elements is %d nodes\n", BINARY_HEAP_BLOCKSIZE);
    00289 #endif
    00290 }
    00291
    00292 // Because we don't want anyone else to bother with our defines
    00293 #undef BIN_HEAP_ARR
    00294
    00295 /*
    00296  * Hash
    00297  */
    00298
    00299 void init_Hash(Hash *h, Hash_HashProc *hash, uint num_buckets)
    00300 {
    00301   /* Allocate space for the Hash, the buckets and the bucket flags */
    00302   uint i;
    00303
    00304   assert(h != NULL);
    00305 #ifdef HASH_DEBUG
    00306   debug("Allocated hash: %p", h);
    00307 #endif
    00308   h->hash = hash;
    00309   h->size = 0;
    00310   h->num_buckets = num_buckets;
    00311   h->buckets = (HashNode*)MallocT<byte>(num_buckets * (sizeof(*h->buckets) + sizeof(*h->buckets_in_use)));
    00312 #ifdef HASH_DEBUG
    00313   debug("Buckets = %p", h->buckets);
    00314 #endif
    00315   h->buckets_in_use = (bool*)(h->buckets + num_buckets);
    00316   for (i = 0; i < num_buckets; i++) h->buckets_in_use[i] = false;
    00317 }
    00318
    00319
    00320 void delete_Hash(Hash *h, bool free_values)
    00321 {
    00322   uint i;
    00323
    00324   /* Iterate all buckets */
    00325   for (i = 0; i < h->num_buckets; i++) {
    00326     if (h->buckets_in_use[i]) {
    00327       HashNode *node;
    00328
    00329       /* Free the first value */
    00330       if (free_values) free(h->buckets[i].value);
    00331       node = h->buckets[i].next;
    00332       while (node != NULL) {
    00333         HashNode *prev = node;
    00334
    00335         node = node->next;
    00336         /* Free the value */
    00337         if (free_values) free(prev->value);
    00338         /* Free the node */
    00339         free(prev);
    00340       }
    00341     }
    00342   }
    00343   free(h->buckets);
    00344   /* No need to free buckets_in_use, it is always allocated in one
    00345    * malloc with buckets */
    00346 #ifdef HASH_DEBUG
    00347   debug("Freeing Hash: %p", h);
    00348 #endif
    00349 }
    00350
    00351 #ifdef HASH_STATS
    00352 static void stat_Hash(const Hash *h)
    00353 {
    00354   uint used_buckets = 0;
    00355   uint max_collision = 0;
    00356   uint max_usage = 0;
    00357   uint usage[200];
    00358   uint i;
    00359
    00360   for (i = 0; i < lengthof(usage); i++) usage[i] = 0;
    00361   for (i = 0; i < h->num_buckets; i++) {
    00362     uint collision = 0;
    00363     if (h->buckets_in_use[i]) {
    00364       const HashNode *node;
    00365
    00366       used_buckets++;
    00367       for (node = &h->buckets[i]; node != NULL; node = node->next) collision++;
    00368       if (collision > max_collision) max_collision = collision;
    00369     }
    00370     if (collision >= lengthof(usage)) collision = lengthof(usage) - 1;
    00371     usage[collision]++;
    00372     if (collision > 0 && usage[collision] >= max_usage) {
    00373       max_usage = usage[collision];
    00374     }
    00375   }
    00376   printf(
    00377     "---\n"
    00378     "Hash size: %d\n"
    00379     "Nodes used: %d\n"
    00380     "Non empty buckets: %d\n"
    00381     "Max collision: %d\n",
    00382     h->num_buckets, h->size, used_buckets, max_collision
    00383   );
    00384   printf("{ ");
    00385   for (i = 0; i <= max_collision; i++) {
    00386     if (usage[i] > 0) {
    00387       printf("%d:%d ", i, usage[i]);
    00388 #if 0
    00389       if (i > 0) {
    00390         uint j;
    00391
    00392         for (j = 0; j < usage[i] * 160 / 800; j++) putchar('#');
    00393       }
    00394       printf("\n");
    00395 #endif
    00396     }
    00397   }
    00398   printf ("}\n");
    00399 }
    00400 #endif
    00401
    00402 void clear_Hash(Hash *h, bool free_values)
    00403 {
    00404   uint i;
    00405
    00406 #ifdef HASH_STATS
    00407   if (h->size > 2000) stat_Hash(h);
    00408 #endif
    00409
    00410   /* Iterate all buckets */
    00411   for (i = 0; i < h->num_buckets; i++) {
    00412     if (h->buckets_in_use[i]) {
    00413       HashNode *node;
    00414
    00415       h->buckets_in_use[i] = false;
    00416       /* Free the first value */
    00417       if (free_values) free(h->buckets[i].value);
    00418       node = h->buckets[i].next;
    00419       while (node != NULL) {
    00420         HashNode *prev = node;
    00421
    00422         node = node->next;
    00423         if (free_values) free(prev->value);
    00424         free(prev);
    00425       }
    00426     }
    00427   }
    00428   h->size = 0;
    00429 }
    00430
    00438 static HashNode *Hash_FindNode(const Hash *h, uint key1, uint key2, HashNode** prev_out)
    00439 {
    00440   uint hash = h->hash(key1, key2);
    00441   HashNode *result = NULL;
    00442
    00443 #ifdef HASH_DEBUG
    00444   debug("Looking for %u, %u", key1, key2);
    00445 #endif
    00446   /* Check if the bucket is empty */
    00447   if (!h->buckets_in_use[hash]) {
    00448     if (prev_out != NULL) *prev_out = NULL;
    00449     result = NULL;
    00450   /* Check the first node specially */
    00451   } else if (h->buckets[hash].key1 == key1 && h->buckets[hash].key2 == key2) {
    00452     /* Save the value */
    00453     result = h->buckets + hash;
    00454     if (prev_out != NULL) *prev_out = NULL;
    00455 #ifdef HASH_DEBUG
    00456     debug("Found in first node: %p", result);
    00457 #endif
    00458   /* Check all other nodes */
    00459   } else {
    00460     HashNode *prev = h->buckets + hash;
    00461     HashNode *node;
    00462
    00463     for (node = prev->next; node != NULL; node = node->next) {
    00464       if (node->key1 == key1 && node->key2 == key2) {
    00465         /* Found it */
    00466         result = node;
    00467 #ifdef HASH_DEBUG
    00468         debug("Found in other node: %p", result);
    00469 #endif
    00470         break;
    00471       }
    00472       prev = node;
    00473     }
    00474     if (prev_out != NULL) *prev_out = prev;
    00475   }
    00476 #ifdef HASH_DEBUG
    00477   if (result == NULL) debug("Not found");
    00478 #endif
    00479   return result;
    00480 }
    00481
    00482 void *Hash_Delete(Hash *h, uint key1, uint key2)
    00483 {
    00484   void *result;
    00485   HashNode *prev; // Used as output var for below function call
    00486   HashNode *node = Hash_FindNode(h, key1, key2, &prev);
    00487
    00488   if (node == NULL) {
    00489     /* not found */
    00490     result = NULL;
    00491   } else if (prev == NULL) {
    00492     /* It is in the first node, we can't free that one, so we free
    00493      * the next one instead (if there is any)*/
    00494     /* Save the value */
    00495     result = node->value;
    00496     if (node->next != NULL) {
    00497       HashNode *next = node->next;
    00498       /* Copy the second to the first */
    00499       *node = *next;
    00500       /* Free the second */
    00501 #ifndef NOFREE
    00502       free(next);
    00503 #endif
    00504     } else {
    00505       /* This was the last in this bucket */
    00506       /* Mark it as empty */
    00507       uint hash = h->hash(key1, key2);
    00508       h->buckets_in_use[hash] = false;
    00509     }
    00510   } else {
    00511     /* It is in another node */
    00512     /* Save the value */
    00513     result = node->value;
    00514     /* Link previous and next nodes */
    00515     prev->next = node->next;
    00516     /* Free the node */
    00517 #ifndef NOFREE
    00518     free(node);
    00519 #endif
    00520   }
    00521   if (result != NULL) h->size--;
    00522   return result;
    00523 }
    00524
    00525
    00526 void *Hash_Set(Hash *h, uint key1, uint key2, void *value)
    00527 {
    00528   HashNode *prev;
    00529   HashNode *node = Hash_FindNode(h, key1, key2, &prev);
    00530
    00531   if (node != NULL) {
    00532     /* Found it */
    00533     void *result = node->value;
    00534
    00535     node->value = value;
    00536     return result;
    00537   }
    00538   /* It is not yet present, let's add it */
    00539   if (prev == NULL) {
    00540     /* The bucket is still empty */
    00541     uint hash = h->hash(key1, key2);
    00542     h->buckets_in_use[hash] = true;
    00543     node = h->buckets + hash;
    00544   } else {
    00545     /* Add it after prev */
    00546     node = MallocT<HashNode>(1);
    00547     prev->next = node;
    00548   }
    00549   node->next = NULL;
    00550   node->key1 = key1;
    00551   node->key2 = key2;
    00552   node->value = value;
    00553   h->size++;
    00554   return NULL;
    00555 }
    00556
    00557 void *Hash_Get(const Hash *h, uint key1, uint key2)
    00558 {
    00559   HashNode *node = Hash_FindNode(h, key1, key2, NULL);
    00560
    00561 #ifdef HASH_DEBUG
    00562   debug("Found node: %p", node);
    00563 #endif
    00564   return (node != NULL) ? node->value : NULL;
    00565 }
    00566
    00567 uint Hash_Size(const Hash *h)
    00568 {
    00569   return h->size;
    00570 }