| 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 |