7a5bebba75bbb14a3cb347b2a03abe52454af898
[charm.git] / src / conv-core / queueing.h
1 #ifndef QUEUEING_H
2 #define QUEUEING_H
3 /*#define FASTQ*/
4
5 /** 
6     @file 
7     Declarations of queuing data structure functions.
8     @ingroup CharmScheduler   
9
10     @addtogroup CharmScheduler
11     @{
12  */
13
14 #ifdef __cplusplus
15 extern "C" {
16 #endif
17
18
19 /** A memory limit threshold for adaptively scheduling */
20 extern int schedAdaptMemThresholdMB;
21
22 #ifndef CINTBITS
23 #define CINTBITS ((unsigned int) (sizeof(int)*8))
24 #endif
25 #ifndef CLONGBITS
26 #define CLONGBITS ((unsigned int) (sizeof(CmiInt8)*8))
27 #endif
28
29 /** Stores a variable bit length priority */
30 typedef struct prio_struct
31 {
32   unsigned short bits;
33   unsigned short ints;
34   unsigned int data[1];
35 }
36 *_prio;
37
38 /**
39    A double ended queue of void* pointers stored in a circular buffer,
40    with internal space for 4 entries
41 */
42 typedef struct deq_struct
43 {
44   /* Note: if head==tail, circ is empty */
45   void **bgn; /**< Pointer to first slot in circular buffer */
46   void **end; /**< Pointer past last slot in circular buffer */
47   void **head; /**< Pointer to first used slot in circular buffer */
48   void **tail; /**< Pointer to next available slot in circular buffer */
49   void *space[4]; /**< Enough space for the first 4 entries */
50 }
51 *_deq;
52
53 #ifndef FASTQ
54 /**
55    A bucket in a priority queue which contains a deque(storing the
56    void* pointers) and references to other buckets in the hash
57    table.
58 */
59 typedef struct prioqelt_struct
60 {
61   struct deq_struct data;
62   struct prioqelt_struct *ht_next; /**< Pointer to next bucket in hash table. */
63   struct prioqelt_struct **ht_handle; /**< Pointer to pointer that points to me (!) */
64   struct prio_struct pri;
65 }
66 *_prioqelt;
67 #else
68 typedef struct prioqelt_struct
69 {
70   struct deq_struct data;
71   struct prioqelt_struct *ht_left; /**< Pointer to left bucket in hash table. */
72   struct prioqelt_struct *ht_right; /**< Pointer to right bucket in hash table. */
73   struct prioqelt_struct *ht_parent; /**< Pointer to the parent bucket in the hash table */
74   struct prioqelt_struct **ht_handle; /**< Pointer to pointer in the hashtable that points to me (!) */
75   struct prio_struct pri;
76   /*  int deleted; */
77 }
78 *_prioqelt;
79 #endif
80 /*
81 #ifndef FASTQ
82 #define PRIOQ_TABSIZE 1017
83 #else */
84 #define PRIOQ_TABSIZE 1017
85 /*#endif */
86
87 /*#ifndef FASTQ*/
88 /**
89    A priority queue, implemented as a heap of prioqelt_struct buckets
90    (each bucket represents a single priority value and contains a
91    deque of void* pointers)
92 */
93 typedef struct prioq_struct
94 {
95   int heapsize; 
96   int heapnext;
97   _prioqelt *heap; /**< An array of prioqelt's */
98   _prioqelt *hashtab;
99   int hash_key_size;
100   int hash_entry_size;
101 }
102 *_prioq;
103 /*#else
104 typedef struct prioq1_struct
105 {
106   int heapsize;
107   int heapnext;
108   prioqelt1 *heap;
109   prioqelt1 hashtab[PRIOQ_TABSIZE];
110 }
111 *prioq1;
112 #endif
113 */
114
115 /*#ifndef FASTQ*/
116 /**
117    A set of 3 queues: a positive priority prioq_struct, a negative
118    priority prioq_struct, and a zero priority deq_struct.
119    
120    If the user modifies the queue, NULL entries may be present, and
121    hence NULL values will be returned by CqsDequeue().
122 */
123 typedef struct Queue_struct
124 {
125   unsigned int length;
126   unsigned int maxlen;
127   struct deq_struct zeroprio; /**< A double ended queue for zero priority messages */
128   struct prioq_struct negprioq; /**< A priority queue for negative priority messages */
129   struct prioq_struct posprioq; /**< A priority queue for negative priority messages */
130 }
131 *Queue;
132 /*#else
133 typedef struct Queue1_struct
134 {
135   unsigned int length;
136   unsigned int maxlen;
137   struct deq_struct zeroprio;
138   struct prioq1_struct negprioq;
139   struct prioq1_struct posprioq;
140 }
141 *Queue;
142 #endif
143 */
144
145 /**
146     Initialize a Queue and its three internal queues (for positive,
147     negative, and zero priorities)
148 */
149 Queue CqsCreate(void);
150
151 /** Delete a Queue */
152 void CqsDelete(Queue);
153
154 /** Enqueue with priority 0 */
155 void CqsEnqueue(Queue, void *msg);
156
157 /** Enqueue behind other elements of priority 0 */
158 void CqsEnqueueFifo(Queue, void *msg);
159
160 /** Enqueue ahead of other elements of priority 0 */
161 void CqsEnqueueLifo(Queue, void *msg);
162
163 /**
164     Enqueue something (usually an envelope*) into the queue in a
165     manner consistent with the specified strategy and priority.
166 */
167 void CqsEnqueueGeneral(Queue, void *msg, int strategy, 
168                        int priobits, unsigned int *prioPtr);
169
170 /**
171     Produce an array containing all the entries in a Queue
172     @return a newly allocated array filled with copies of the (void*)
173     elements in the Queue.
174     @param [in] q a Queue
175     @param [out] resp an array of pointer entries found in the Queue,
176     with as many entries as the Queue's length. The caller must
177     CmiFree this.
178 */
179 void CqsEnumerateQueue(Queue q, void ***resp);
180
181 /**
182    Retrieve the highest priority message (one with most negative
183    priority)
184 */
185 void CqsDequeue(Queue, void **msgPtr);
186
187 unsigned int CqsLength(Queue);
188 int CqsEmpty(Queue);
189 int CqsPrioGT_(unsigned int ints1, unsigned int *data1, unsigned int ints2, unsigned int *data2);
190 int CqsPrioGT(_prio, _prio);
191
192 /** Get the priority of the highest priority message in q */
193 _prio CqsGetPriority(Queue);
194
195 void CqsIncreasePriorityForEntryMethod(Queue q, const int entrymethod);
196
197 /**
198     Remove an occurence of a specified entry from the Queue by setting
199     its entry to NULL.
200
201     The size of the Queue will not change, it will now just contain an
202     entry for a NULL pointer.
203 */
204 void CqsRemoveSpecific(Queue, const void *msgPtr);
205
206 #ifdef ADAPT_SCHED_MEM
207 void CqsIncreasePriorityForMemCriticalEntries(Queue q);
208 #endif
209
210 #ifdef __cplusplus
211 }
212 #endif
213
214 /** @} */
215
216 #endif