OLD | NEW |
1 /* crypto/pqueue/pqueue.c */ | 1 /* crypto/pqueue/pqueue.c */ |
2 /* | 2 /* |
3 * DTLS implementation written by Nagendra Modadugu | 3 * DTLS implementation written by Nagendra Modadugu |
4 * (nagendra@cs.stanford.edu) for the OpenSSL project 2005. | 4 * (nagendra@cs.stanford.edu) for the OpenSSL project 2005. |
5 */ | 5 */ |
6 /* ==================================================================== | 6 /* ==================================================================== |
7 * Copyright (c) 1999-2005 The OpenSSL Project. All rights reserved. | 7 * Copyright (c) 1999-2005 The OpenSSL Project. All rights reserved. |
8 * | 8 * |
9 * Redistribution and use in source and binary forms, with or without | 9 * Redistribution and use in source and binary forms, with or without |
10 * modification, are permitted provided that the following conditions | 10 * modification, are permitted provided that the following conditions |
(...skipping 50 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
61 #include <openssl/bn.h> | 61 #include <openssl/bn.h> |
62 #include "pqueue.h" | 62 #include "pqueue.h" |
63 | 63 |
64 typedef struct _pqueue | 64 typedef struct _pqueue |
65 { | 65 { |
66 pitem *items; | 66 pitem *items; |
67 int count; | 67 int count; |
68 } pqueue_s; | 68 } pqueue_s; |
69 | 69 |
70 pitem * | 70 pitem * |
71 pitem_new(PQ_64BIT priority, void *data) | 71 pitem_new(unsigned char *prio64be, void *data) |
72 { | 72 { |
73 pitem *item = (pitem *) OPENSSL_malloc(sizeof(pitem)); | 73 pitem *item = (pitem *) OPENSSL_malloc(sizeof(pitem)); |
74 if (item == NULL) return NULL; | 74 if (item == NULL) return NULL; |
75 | 75 |
76 » pq_64bit_init(&(item->priority)); | 76 » memcpy(item->priority,prio64be,sizeof(item->priority)); |
77 » pq_64bit_assign(&item->priority, &priority); | |
78 | 77 |
79 item->data = data; | 78 item->data = data; |
80 item->next = NULL; | 79 item->next = NULL; |
81 | 80 |
82 return item; | 81 return item; |
83 } | 82 } |
84 | 83 |
85 void | 84 void |
86 pitem_free(pitem *item) | 85 pitem_free(pitem *item) |
87 { | 86 { |
88 if (item == NULL) return; | 87 if (item == NULL) return; |
89 | 88 |
90 pq_64bit_free(&(item->priority)); | |
91 OPENSSL_free(item); | 89 OPENSSL_free(item); |
92 } | 90 } |
93 | 91 |
94 pqueue_s * | 92 pqueue_s * |
95 pqueue_new() | 93 pqueue_new() |
96 { | 94 { |
97 pqueue_s *pq = (pqueue_s *) OPENSSL_malloc(sizeof(pqueue_s)); | 95 pqueue_s *pq = (pqueue_s *) OPENSSL_malloc(sizeof(pqueue_s)); |
98 if (pq == NULL) return NULL; | 96 if (pq == NULL) return NULL; |
99 | 97 |
100 memset(pq, 0x00, sizeof(pqueue_s)); | 98 memset(pq, 0x00, sizeof(pqueue_s)); |
(...skipping 16 matching lines...) Expand all Loading... |
117 if (pq->items == NULL) | 115 if (pq->items == NULL) |
118 { | 116 { |
119 pq->items = item; | 117 pq->items = item; |
120 return item; | 118 return item; |
121 } | 119 } |
122 | 120 |
123 for(curr = NULL, next = pq->items; | 121 for(curr = NULL, next = pq->items; |
124 next != NULL; | 122 next != NULL; |
125 curr = next, next = next->next) | 123 curr = next, next = next->next) |
126 { | 124 { |
127 » » if (pq_64bit_gt(&(next->priority), &(item->priority))) | 125 » » /* we can compare 64-bit value in big-endian encoding |
| 126 » » * with memcmp:-) */ |
| 127 » » int cmp = memcmp(next->priority, item->priority,8); |
| 128 » » if (cmp > 0)» » /* next > item */ |
128 { | 129 { |
129 item->next = next; | 130 item->next = next; |
130 | 131 |
131 if (curr == NULL) | 132 if (curr == NULL) |
132 pq->items = item; | 133 pq->items = item; |
133 else | 134 else |
134 curr->next = item; | 135 curr->next = item; |
135 | 136 |
136 return item; | 137 return item; |
137 } | 138 } |
138 » » /* duplicates not allowed */ | 139 » » |
139 » » if (pq_64bit_eq(&(item->priority), &(next->priority))) | 140 » » else if (cmp == 0)» /* duplicates not allowed */ |
140 return NULL; | 141 return NULL; |
141 } | 142 } |
142 | 143 |
143 item->next = NULL; | 144 item->next = NULL; |
144 curr->next = item; | 145 curr->next = item; |
145 | 146 |
146 return item; | 147 return item; |
147 } | 148 } |
148 | 149 |
149 pitem * | 150 pitem * |
150 pqueue_peek(pqueue_s *pq) | 151 pqueue_peek(pqueue_s *pq) |
151 { | 152 { |
152 return pq->items; | 153 return pq->items; |
153 } | 154 } |
154 | 155 |
155 pitem * | 156 pitem * |
156 pqueue_pop(pqueue_s *pq) | 157 pqueue_pop(pqueue_s *pq) |
157 { | 158 { |
158 pitem *item = pq->items; | 159 pitem *item = pq->items; |
159 | 160 |
160 if (pq->items != NULL) | 161 if (pq->items != NULL) |
161 pq->items = pq->items->next; | 162 pq->items = pq->items->next; |
162 | 163 |
163 return item; | 164 return item; |
164 } | 165 } |
165 | 166 |
166 pitem * | 167 pitem * |
167 pqueue_find(pqueue_s *pq, PQ_64BIT priority) | 168 pqueue_find(pqueue_s *pq, unsigned char *prio64be) |
168 { | 169 { |
169 » pitem *next, *prev = NULL; | 170 » pitem *next; |
170 pitem *found = NULL; | 171 pitem *found = NULL; |
171 | 172 |
172 if ( pq->items == NULL) | 173 if ( pq->items == NULL) |
173 return NULL; | 174 return NULL; |
174 | 175 |
175 » for ( next = pq->items; next->next != NULL; | 176 » for ( next = pq->items; next->next != NULL; next = next->next) |
176 » » prev = next, next = next->next) | |
177 { | 177 { |
178 » » if ( pq_64bit_eq(&(next->priority), &priority)) | 178 » » if ( memcmp(next->priority, prio64be,8) == 0) |
179 { | 179 { |
180 found = next; | 180 found = next; |
181 break; | 181 break; |
182 } | 182 } |
183 } | 183 } |
184 | 184 |
185 /* check the one last node */ | 185 /* check the one last node */ |
186 » if ( pq_64bit_eq(&(next->priority), &priority)) | 186 » if ( memcmp(next->priority, prio64be,8) ==0) |
187 found = next; | 187 found = next; |
188 | 188 |
189 if ( ! found) | 189 if ( ! found) |
190 return NULL; | 190 return NULL; |
191 | 191 |
192 #if 0 /* find works in peek mode */ | 192 #if 0 /* find works in peek mode */ |
193 if ( prev == NULL) | 193 if ( prev == NULL) |
194 pq->items = next->next; | 194 pq->items = next->next; |
195 else | 195 else |
196 prev->next = next->next; | 196 prev->next = next->next; |
197 #endif | 197 #endif |
198 | 198 |
199 return found; | 199 return found; |
200 } | 200 } |
201 | 201 |
202 #if PQ_64BIT_IS_INTEGER | |
203 void | 202 void |
204 pqueue_print(pqueue_s *pq) | 203 pqueue_print(pqueue_s *pq) |
205 { | 204 { |
206 pitem *item = pq->items; | 205 pitem *item = pq->items; |
207 | 206 |
208 while(item != NULL) | 207 while(item != NULL) |
209 { | 208 { |
210 » » printf("item\t" PQ_64BIT_PRINT "\n", item->priority); | 209 » » printf("item\t%02x%02x%02x%02x%02x%02x%02x%02x\n", |
| 210 » » » item->priority[0],item->priority[1], |
| 211 » » » item->priority[2],item->priority[3], |
| 212 » » » item->priority[4],item->priority[5], |
| 213 » » » item->priority[6],item->priority[7]); |
211 item = item->next; | 214 item = item->next; |
212 } | 215 } |
213 } | 216 } |
214 #endif | |
215 | 217 |
216 pitem * | 218 pitem * |
217 pqueue_iterator(pqueue_s *pq) | 219 pqueue_iterator(pqueue_s *pq) |
218 { | 220 { |
219 return pqueue_peek(pq); | 221 return pqueue_peek(pq); |
220 } | 222 } |
221 | 223 |
222 pitem * | 224 pitem * |
223 pqueue_next(pitem **item) | 225 pqueue_next(pitem **item) |
224 { | 226 { |
(...skipping 16 matching lines...) Expand all Loading... |
241 pitem *item = pq->items; | 243 pitem *item = pq->items; |
242 int count = 0; | 244 int count = 0; |
243 | 245 |
244 while(item != NULL) | 246 while(item != NULL) |
245 { | 247 { |
246 count++; | 248 count++; |
247 item = item->next; | 249 item = item->next; |
248 } | 250 } |
249 return count; | 251 return count; |
250 } | 252 } |
OLD | NEW |