-
Notifications
You must be signed in to change notification settings - Fork 0
/
queue.h
75 lines (67 loc) · 1.54 KB
/
queue.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#ifndef QUEUE_H
#define QUEUE_H
#include "base_type.h"
/*
*
* structure of element:
* cost: sizeof(Dollar)
* positionHintB: size1-sizeof(Dollar)
*/
typedef struct _TaskQueue{
/**
* size of each element
*/
int size1;
/**
* number of elements in each block
*/
int size2;
/**
* number of blocks
*/
int size3;
/**
* current number of blocks
* always greater than 0
*/
int size3_;
/**
* has length of size3+1
* key in data[i] are less than interval[t] for all i<=t
*/
Double *interval;
/**
* has length of size3+1
* dataSize[t] is the actual number of elements in data[t]
*/
int* dataSize;
/**
* array of arrays storing blocks
* first size3_ array are valid, others should not be accessed
*/
gpointer* data;
} TaskQueue;
/**
* reorder block such that block[t].cost<block[c].cost iff t<c
* equality are not handled strictly
* it is not stable
* each element has <code>size</code>byte
* b is the number of elements
*/
Double quickselect(gpointer block,gpointer tmp,int size,gint32 b,gint32 c);
/**
*
*/
TaskQueue *queue_init(TaskQueue *f,int size1,int size2,int size3);
/**
* return
* 0 when no split happened
* 1 when split tailing block
* 2 when split without remove tail
* 3 when split and remove tail
*/
gchar queue_insert(TaskQueue *queue,gconstpointer element);
gpointer queue_pull(TaskQueue *queue);
void queue_free(TaskQueue *queue);
void queue_print(GLogLevelFlags flags, TaskQueue *queue);
#endif