gk_mkpqueue2.h
Go to the documentation of this file.
1 
12 #ifndef _GK_MKPQUEUE2_H
13 #define _GK_MKPQUEUE2_H
14 
15 
16 #define GK_MKPQUEUE2(FPRFX, PQT, KT, VT, KMALLOC, VMALLOC, KMAX, KEY_LT)\
17 /*************************************************************************/\
18 \
19 /**************************************************************************/\
20 PQT *FPRFX ## Create2(ssize_t maxnodes)\
21 {\
22  PQT *queue; \
23 \
24  if ((queue = (PQT *)gk_malloc(sizeof(PQT), "gk_pqCreate2: queue")) != NULL) {\
25  memset(queue, 0, sizeof(PQT));\
26  queue->nnodes = 0;\
27  queue->maxnodes = maxnodes;\
28  queue->keys = KMALLOC(maxnodes, "gk_pqCreate2: keys");\
29  queue->vals = VMALLOC(maxnodes, "gk_pqCreate2: vals");\
30 \
31  if (queue->keys == NULL || queue->vals == NULL)\
32  gk_free((void **)&queue->keys, &queue->vals, &queue, LTERM);\
33  }\
34 \
35  return queue;\
36 }\
37 \
38 \
39 /*************************************************************************/\
40 \
41 /**************************************************************************/\
42 void FPRFX ## Reset2(PQT *queue)\
43 {\
44  queue->nnodes = 0;\
45 }\
46 \
47 \
48 /*************************************************************************/\
49 \
50 /**************************************************************************/\
51 void FPRFX ## Destroy2(PQT **r_queue)\
52 {\
53  PQT *queue = *r_queue; \
54  if (queue == NULL) return;\
55  gk_free((void **)&queue->keys, &queue->vals, &queue, LTERM);\
56  *r_queue = NULL;\
57 }\
58 \
59 \
60 /*************************************************************************/\
61 \
62 /**************************************************************************/\
63 size_t FPRFX ## Length2(PQT *queue)\
64 {\
65  return queue->nnodes;\
66 }\
67 \
68 \
69 /*************************************************************************/\
70 \
71 /**************************************************************************/\
72 int FPRFX ## Insert2(PQT *queue, VT val, KT key)\
73 {\
74  ssize_t i, j;\
75  KT *keys=queue->keys;\
76  VT *vals=queue->vals;\
77 \
78  ASSERT2(FPRFX ## CheckHeap2(queue));\
79 \
80  if (queue->nnodes == queue->maxnodes) \
81  return 0;\
82 \
83  ASSERT2(FPRFX ## CheckHeap2(queue));\
84 \
85  i = queue->nnodes++;\
86  while (i > 0) {\
87  j = (i-1)>>1;\
88  if (KEY_LT(key, keys[j])) {\
89  keys[i] = keys[j];\
90  vals[i] = vals[j];\
91  i = j;\
92  }\
93  else\
94  break;\
95  }\
96  ASSERT(i >= 0);\
97  keys[i] = key;\
98  vals[i] = val;\
99 \
100  ASSERT2(FPRFX ## CheckHeap2(queue));\
101 \
102  return 1;\
103 }\
104 \
105 \
106 /*************************************************************************/\
107 \
109 /**************************************************************************/\
110 int FPRFX ## GetTop2(PQT *queue, VT *r_val)\
111 {\
112  ssize_t i, j;\
113  KT key, *keys=queue->keys;\
114  VT val, *vals=queue->vals;\
115 \
116  ASSERT2(FPRFX ## CheckHeap2(queue));\
117 \
118  if (queue->nnodes == 0)\
119  return 0;\
120 \
121  queue->nnodes--;\
122 \
123  *r_val = vals[0];\
124 \
125  if ((i = queue->nnodes) > 0) {\
126  key = keys[i];\
127  val = vals[i];\
128  i = 0;\
129  while ((j=2*i+1) < queue->nnodes) {\
130  if (KEY_LT(keys[j], key)) {\
131  if (j+1 < queue->nnodes && KEY_LT(keys[j+1], keys[j]))\
132  j = j+1;\
133  keys[i] = keys[j];\
134  vals[i] = vals[j];\
135  i = j;\
136  }\
137  else if (j+1 < queue->nnodes && KEY_LT(keys[j+1], key)) {\
138  j = j+1;\
139  keys[i] = keys[j];\
140  vals[i] = vals[j];\
141  i = j;\
142  }\
143  else\
144  break;\
145  }\
146 \
147  keys[i] = key;\
148  vals[i] = val;\
149  }\
150 \
151  ASSERT2(FPRFX ## CheckHeap2(queue));\
152 \
153  return 1;\
154 }\
155 \
156 \
157 /*************************************************************************/\
158 \
160 /**************************************************************************/\
161 int FPRFX ## SeeTopVal2(PQT *queue, VT *r_val)\
162 {\
163  if (queue->nnodes == 0) \
164  return 0;\
165 \
166  *r_val = queue->vals[0];\
167 \
168  return 1;\
169 }\
170 \
171 \
172 /*************************************************************************/\
173 \
175 /**************************************************************************/\
176 KT FPRFX ## SeeTopKey2(PQT *queue)\
177 {\
178  return (queue->nnodes == 0 ? KMAX : queue->keys[0]);\
179 }\
180 \
181 \
182 /*************************************************************************/\
183 \
184 /**************************************************************************/\
185 int FPRFX ## CheckHeap2(PQT *queue)\
186 {\
187  ssize_t i;\
188  KT *keys=queue->keys;\
189 \
190  if (queue->nnodes == 0)\
191  return 1;\
192 \
193  for (i=1; i<queue->nnodes; i++) {\
194  ASSERT(!KEY_LT(keys[i], keys[(i-1)/2]));\
195  }\
196  for (i=1; i<queue->nnodes; i++)\
197  ASSERT(!KEY_LT(keys[i], keys[0]));\
198 \
199  return 1;\
200 }\
201 
202 
203 #define GK_MKPQUEUE2_PROTO(FPRFX, PQT, KT, VT)\
204  PQT * FPRFX ## Create2(ssize_t maxnodes);\
205  void FPRFX ## Reset2(PQT *queue);\
206  void FPRFX ## Destroy2(PQT **r_queue);\
207  size_t FPRFX ## Length2(PQT *queue);\
208  int FPRFX ## Insert2(PQT *queue, VT node, KT key);\
209  int FPRFX ## GetTop2(PQT *queue, VT *r_val);\
210  int FPRFX ## SeeTopVal2(PQT *queue, VT *r_val);\
211  KT FPRFX ## SeeTopKey2(PQT *queue);\
212  int FPRFX ## CheckHeap2(PQT *queue);\
213 
214 
215 #endif


gtsam
Author(s):
autogenerated on Tue Jul 4 2023 02:34:18