• Main Page
  • Data Structures
  • Files
  • File List
  • Globals

coveb-tree.h

Go to the documentation of this file.
00001 
00003 /*
00004  * coveb : An open source van Emde Boas Priority Queue library
00005  * by Rudi Cilibrasi (cilibrar@cilibrar.com)
00006  *
00007  * Distributed under the BSD license.  Copyright 2008 Rudi Cilibrasi.
00008  *
00009  * v 0.71
00010  *
00011  * Uses stratified trees inspired by van Emde Boas to hold a priority queue
00012  * of unsigned 32-bit integer values.  Standard operations are supported.
00013  * Speed and memory use are optimized for large numbers of elements and
00014  * high queue throughput.  The data structure is designed to take advantage
00015  * of multilevel caches of any size; this property is called being
00016  * "cache oblivious".
00017  *
00018  * Instantiation:
00019  *
00020  * struct coveb_bq *q;
00021  *
00022  *   q = coveb_bq_new();
00023  *
00024  * This allocates a new cache-oblivious bitwise priority queue. To free, use:
00025  *
00026  * Deallocation:
00027  *
00028  *   coveb_bq_free(q);
00029  *
00030  * Insertion of 32-bit unsigned integer values:
00031  *
00032  * void coveb_bq_insert(struct coveb_bq *q, uint32_t x);
00033  *
00034  *    places a new value into the queue, or does nothing if it's already there.
00035  *
00036  * Removal of values:
00037  *
00038  * uint32_t coveb_bq_extractmin(struct coveb_bq *q);
00039  *
00040  *    removes the smallest value (min) from the queue and returns it.  It
00041  *    is illegal to try to remove a value from an empty (size = 0) queue.
00042  *    This is the fastest way to remove elements.
00043  *
00044  * uint32_t coveb_bq_remove(struct coveb_bq *q, uint32_t x);
00045  *
00046  *    This generic function removes any specific value from the queue.
00047  *    It returns 0 if the object was already in the queue, and 1 if not.
00048  *
00049  * Queue status monitoring:
00050  *
00051  *  When the queue is completely full (containing four 'binary' gigasamples),
00052  *  it consumes about one gigabyte of memory.  This means that it uses about 2
00053  *  bits per sample on average when full.  This is only about twice as big as
00054  *  the literal storage cost of a typical queue state.  Because this size
00055  *  is not reportable as a 32-bit integer, the following function is
00056  *  available to detect the full queue condition:
00057  *
00058  *  uint32_t coveb_bq_addresses_full(const struct coveb_bq *q);
00059  *
00060  *  Returns 1 if all 2 ** 32 elements are in the queue, or 0 otherwise.
00061  *  When the queue is not full, the normal size function is exactly accurate:
00062  *
00063  * uint32_t coveb_bq_size(const struct coveb_bq *q);
00064  *
00065  *    returns the count of integers currently stored in the queue.  This
00066  *  can be used to see if an element can be extracted safely (size > 0).
00067  *  Note that in the special case where the queue is completely full and
00068  *  therefore the number of elements in the queue is one greater than the
00069  *  maximum value of an unsigned 32-bit integer, the size function will
00070  *  return instead one less than the actual number of elements.  To
00071  *  detect this uncommon condition use coveb_bq_addresses_full.
00072  *
00073  * Extrema functions
00074  *
00075  * uint32_t coveb_bq_max(const struct coveb_bq *q);
00076  *
00077  *  returns the largest integer stored in the queue without removal.
00078  *
00079  * uint32_t coveb_bq_min(const struct coveb_bq *q);
00080  *
00081  *  returns the smallest integer stored in the queue without removal.
00082  *
00083  * Rangefinding functions
00084  *
00085  * void coveb_bq_locate_smallest_not_less_than(const struct coveb_bq *q,
00086  * uint32_t incl_lower_bound, uint32_t *result_x, uint32_t *gotresult);
00087  *
00088  *   searches for an integer stored in the queue that is not less than
00089  *   incl_lower_bound.  If there is more than one such integer, the smallest
00090  *   is returned.  If an integer is found, *gotresult will be set to 1 and
00091  *   *result_x will hold the integer that was found.  If no such integer is
00092  *   found in the queue, then *gotresult with be set to 0 and *result_x will
00093  *   be untouched.  The queue is not modified in any case.
00094  *
00095  * void coveb_bq_successor(const struct coveb_bq *q,
00096  * uint32_t excl_lower_bound, uint32_t *result_x, uint32_t *gotresult);
00097  *
00098  *   This function scans upward for an integer that is greater than
00099  *   excl_lower_bound.  It is otherwise the same as the
00100  *   coveb_bq_locate_smallest_not_less_than function.
00101  */
00102 
00103 #ifndef __COVEB_QUEUE_H
00104 #define __COVEB_QUEUE_H
00105 
00106 #include <stdio.h>
00107 #include <string.h>
00108 #include <assert.h>
00109 #include <stdlib.h>
00110 #include <stdint.h>
00111 
00112 /* Set to 0 to use plain malloc and free instead. */
00113 #define USE_FAST_ALLOCATOR 1
00114 
00115 /* Maximum number of size slots in custom allocator. Just 5 or so needed.  */
00116 #define MAXBLOCKSIZES 32
00117 
00118 /* The runtime static type used to look things up in the tree. */
00119 #define COVEB_KEYTYPE uint32_t
00120 
00121 /* Flag indicating tree has filled up completely with 2 ** 32 elements. */
00122 #define MASK_TOTFULL    0x00000010
00123 
00124 /* Used for maps */
00125 #define MASK_TOPSIDE    0x00000020
00126 
00127 /* Highest number of bits supported directly by a 32-bit integer bit array. */
00128 #define MAXDIRECTK 5
00129 
00130 /* Tree node structures. */
00131 struct FastAllocFreeNode;
00132 struct FastAllocController;
00133 struct FastAllocArena;
00134 struct vEBPNode;
00135 
00136 struct FastAllocFreeNode {
00137   struct FastAllocFreeNode *nxt;
00138 };
00139 
00140 struct FastAllocArena {
00141   uint32_t blocksize, blocksperchunk, maxbpc;
00142   struct FastAllocFreeNode *freelist;
00143   struct FastAllocFreeNode *bigchunks;
00144 };
00145 
00146 struct FastAllocController {
00147   struct FastAllocArena faa[MAXBLOCKSIZES];
00148   int faa_tot;
00149 };
00150 
00151 struct vEBPNodeTypeIndicator {
00152   uint32_t _size;
00153   uint16_t _fullbitsize;
00154   uint16_t _flags;
00155   struct FastAllocController *_fac;
00156 };
00157 
00158 struct vEBMPNodeTypeIndicator {
00159   uint32_t _size;
00160   uint16_t _fullbitsize;
00161   uint8_t _flags;
00162   uint8_t _payload_bits_minus_one;
00163   struct FastAllocController *_fac;
00164 };
00165 
00166 struct coveb_bq {
00167   struct FastAllocController *fac;
00168   struct vEBPNode *tree;
00169 };
00170 
00171 struct coveb_mq {
00172   struct FastAllocController *fac;
00173   struct vEBMPNode *tree;
00174   uint32_t payload_bits;
00175 };
00176 
00177 struct vEBFullNode {
00178   COVEB_KEYTYPE _min, _max;
00179   struct vEBPNode *_top;
00180   struct vEBPNode **_bot;
00181 };
00182 
00191 struct vEBMPayloadStatic {
00193   uint32_t _pl[8]; /* Maximum 8 bits/byt * 8 words * 4 byt / word = 64 bytes */
00194 };
00195 
00196 struct vEBSingleNode {
00197   COVEB_KEYTYPE _x;
00198 };
00199 
00211 struct vEBMPDatum {
00213   COVEB_KEYTYPE _x;
00214 
00216   struct vEBMPayloadStatic _p;
00217 };
00218 
00219 struct vEBMSingleNode {
00220   struct vEBMPDatum _d;
00221 };
00222 
00223 struct vEBMFullNode {
00224   struct vEBMPDatum _min, _max;
00225   struct vEBMPNode *_top;
00226   struct vEBMPNode **_bot;
00227 };
00228 
00229 struct vEBSimpleBitTable {
00230   uint32_t _bits;
00231 };
00232 
00233 struct vEBPNode
00234  {
00235   struct vEBPNodeTypeIndicator t;
00236   union {
00237     struct vEBSingleNode sn;
00238     struct vEBFullNode fn;
00239     struct vEBSimpleBitTable sbt;
00240   };
00241 };
00242 
00243 struct vEBMPNode
00244  {
00245   struct vEBMPNodeTypeIndicator t;
00246   union {
00247     struct vEBMSingleNode sn;
00248     struct vEBMFullNode fn;
00249     struct vEBSimpleBitTable sbt;
00250   };
00251 };
00252 
00253 /* Advanced searching results for future expansion. */
00254 
00255 struct vEBPSearchResult {
00256   COVEB_KEYTYPE x;
00257   uint32_t is_notfound;
00258   struct vEBPNode *sn;
00259   struct vEBPNode *atmin;
00260   struct vEBPNode *ondirectdata;
00261 };
00262 
00263 struct vEBMPSearchResult {
00264   COVEB_KEYTYPE x;
00265   uint32_t is_notfound;
00266   struct vEBMPNode *sn;
00267   struct vEBMPNode *atmin;
00268   struct vEBMPNode *ondirectdata;
00269 };
00270 
00271 /**************************************/
00272 /* PRIMARY USER-LEVEL QUEUE FUNCTIONS */
00273 /**************************************/
00274 
00275 /* Allocation and freeing */
00276 struct coveb_bq *coveb_bq_new(void);
00277 struct coveb_bq *coveb_bq_clone(const struct coveb_bq *q);
00278 void coveb_bq_free(struct coveb_bq *q);
00279 
00280 /* Mutation */
00281 void coveb_bq_insert(struct coveb_bq *q, uint32_t x);
00282 uint32_t coveb_bq_extractmin(struct coveb_bq *q);
00283 uint32_t coveb_bq_remove(struct coveb_bq *q, uint32_t m);
00284 
00285 /* Inspection */
00286 uint32_t coveb_bq_size(const struct coveb_bq *q);
00287 uint32_t coveb_bq_contains(const struct coveb_bq *q, uint32_t x);
00288 uint32_t coveb_bq_addresses_full(const struct coveb_bq *q);
00289 
00290 /* Scanning */
00291 void coveb_bq_locate_smallest_not_less_than(const struct coveb_bq *q, uint32_t incl_lower_bound, uint32_t *result_x, uint32_t *gotresult);
00292 void coveb_bq_successor(const struct coveb_bq *q, uint32_t excl_lower_bound, uint32_t *result_x, uint32_t *gotresult);
00293 uint32_t coveb_bq_max(const struct coveb_bq *q);
00294 uint32_t coveb_bq_min(const struct coveb_bq *q);
00295 
00296 
00297 /* Error reporting */
00298 void coveb_failout(const char *msg);
00299 
00300 /* The following functions create a mapping priority queue.
00301  * In a mapping priority queue, each entry has a payload attached.
00302  * The payload may be 1, 2, 4, 8, 16, 32, 64, 128, or 256 bits per entry.
00303  * Regardless of the payload size, the type passed is always the largest.
00304  *
00305  * All functions behave equivalently to the simple bitwise queue except
00306  * that payloads are carried for each entry.
00307  */
00308 struct coveb_mq *coveb_mq_new(uint32_t payload_bits);
00309 struct coveb_mq *coveb_mq_clone(const struct coveb_mq *q);
00310 void coveb_mq_free(struct coveb_mq *q);
00311 void coveb_mq_insert(struct coveb_mq *q, struct vEBMPDatum x);
00312 struct vEBMPDatum coveb_mq_extractmin(struct coveb_mq *q);
00313 struct vEBMPDatum coveb_mq_min(const struct coveb_mq *q);
00314 struct vEBMPDatum coveb_mq_max(const struct coveb_mq *q);
00315 void coveb_mq_locate_smallest_not_less_than(const struct coveb_mq *q, uint32_t incl_lower_bound, struct vEBMPDatum *result_x, uint32_t *gotresult);
00316 struct vEBMPDatum fetch_from_bottom_table(struct vEBMPNode *v, uint32_t ind);
00317 void store_to_bottom_table(struct vEBMPNode *v, struct vEBMPDatum d, uint32_t ind);
00318 uint32_t coveb_mq_remove(struct coveb_mq *q, uint32_t x);
00319 uint32_t coveb_mq_addresses_full(const struct coveb_mq *q);
00320 uint32_t coveb_mq_size(const struct coveb_mq *q);
00321 uint32_t coveb_mq_contains(const struct coveb_mq *q, uint32_t x);
00322 void coveb_mq_successor(const struct coveb_mq *q, uint32_t num, struct vEBMPDatum *result_x, uint32_t *gotresult);
00323 
00324 
00325 #endif

Generated on Wed Aug 11 2010 12:56:18 for libcoveb by  doxygen 1.7.1