pqueue.c 2.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154
  1. /*
  2. * Copyright 2005-2017 The OpenSSL Project Authors. All Rights Reserved.
  3. *
  4. * Licensed under the OpenSSL license (the "License"). You may not use
  5. * this file except in compliance with the License. You can obtain a copy
  6. * in the file LICENSE in the source distribution or at
  7. * https://www.openssl.org/source/license.html
  8. */
  9. #include "ssl_locl.h"
  10. #include <openssl/bn.h>
  11. struct pqueue_st {
  12. pitem *items;
  13. int count;
  14. };
  15. pitem *pitem_new(unsigned char *prio64be, void *data)
  16. {
  17. pitem *item = OPENSSL_malloc(sizeof(*item));
  18. if (item == NULL)
  19. return NULL;
  20. memcpy(item->priority, prio64be, sizeof(item->priority));
  21. item->data = data;
  22. item->next = NULL;
  23. return item;
  24. }
  25. void pitem_free(pitem *item)
  26. {
  27. OPENSSL_free(item);
  28. }
  29. pqueue *pqueue_new()
  30. {
  31. pqueue *pq = OPENSSL_zalloc(sizeof(*pq));
  32. return pq;
  33. }
  34. void pqueue_free(pqueue *pq)
  35. {
  36. OPENSSL_free(pq);
  37. }
  38. pitem *pqueue_insert(pqueue *pq, pitem *item)
  39. {
  40. pitem *curr, *next;
  41. if (pq->items == NULL) {
  42. pq->items = item;
  43. return item;
  44. }
  45. for (curr = NULL, next = pq->items;
  46. next != NULL; curr = next, next = next->next) {
  47. /*
  48. * we can compare 64-bit value in big-endian encoding with memcmp:-)
  49. */
  50. int cmp = memcmp(next->priority, item->priority, 8);
  51. if (cmp > 0) { /* next > item */
  52. item->next = next;
  53. if (curr == NULL)
  54. pq->items = item;
  55. else
  56. curr->next = item;
  57. return item;
  58. }
  59. else if (cmp == 0) /* duplicates not allowed */
  60. return NULL;
  61. }
  62. item->next = NULL;
  63. curr->next = item;
  64. return item;
  65. }
  66. pitem *pqueue_peek(pqueue *pq)
  67. {
  68. return pq->items;
  69. }
  70. pitem *pqueue_pop(pqueue *pq)
  71. {
  72. pitem *item = pq->items;
  73. if (pq->items != NULL)
  74. pq->items = pq->items->next;
  75. return item;
  76. }
  77. pitem *pqueue_find(pqueue *pq, unsigned char *prio64be)
  78. {
  79. pitem *next;
  80. pitem *found = NULL;
  81. if (pq->items == NULL)
  82. return NULL;
  83. for (next = pq->items; next->next != NULL; next = next->next) {
  84. if (memcmp(next->priority, prio64be, 8) == 0) {
  85. found = next;
  86. break;
  87. }
  88. }
  89. /* check the one last node */
  90. if (memcmp(next->priority, prio64be, 8) == 0)
  91. found = next;
  92. if (!found)
  93. return NULL;
  94. return found;
  95. }
  96. pitem *pqueue_iterator(pqueue *pq)
  97. {
  98. return pqueue_peek(pq);
  99. }
  100. pitem *pqueue_next(piterator *item)
  101. {
  102. pitem *ret;
  103. if (item == NULL || *item == NULL)
  104. return NULL;
  105. /* *item != NULL */
  106. ret = *item;
  107. *item = (*item)->next;
  108. return ret;
  109. }
  110. size_t pqueue_size(pqueue *pq)
  111. {
  112. pitem *item = pq->items;
  113. size_t count = 0;
  114. while (item != NULL) {
  115. count++;
  116. item = item->next;
  117. }
  118. return count;
  119. }