Go to the documentation of this file.00001
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076
00077
00078
00079
00080
00081
00082
00083
00084
00085
00086
00087
00088
00089
00090
00091
00092
00093
00094
00095
00096
00097
00098
00099
00100
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
00113 #define USE_FAST_ALLOCATOR 1
00114
00115
00116 #define MAXBLOCKSIZES 32
00117
00118
00119 #define COVEB_KEYTYPE uint32_t
00120
00121
00122 #define MASK_TOTFULL 0x00000010
00123
00124
00125 #define MASK_TOPSIDE 0x00000020
00126
00127
00128 #define MAXDIRECTK 5
00129
00130
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];
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
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
00273
00274
00275
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
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
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
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
00298 void coveb_failout(const char *msg);
00299
00300
00301
00302
00303
00304
00305
00306
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