pqueue.c 3.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158
  1. /*
  2. * Copyright 2005-2018 The OpenSSL Project Authors. All Rights Reserved.
  3. *
  4. * Licensed under the Apache License 2.0 (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_local.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. SSLerr(SSL_F_PITEM_NEW, ERR_R_MALLOC_FAILURE);
  20. return NULL;
  21. }
  22. memcpy(item->priority, prio64be, sizeof(item->priority));
  23. item->data = data;
  24. item->next = NULL;
  25. return item;
  26. }
  27. void pitem_free(pitem *item)
  28. {
  29. OPENSSL_free(item);
  30. }
  31. pqueue *pqueue_new(void)
  32. {
  33. pqueue *pq = OPENSSL_zalloc(sizeof(*pq));
  34. if (pq == NULL)
  35. SSLerr(SSL_F_PQUEUE_NEW, ERR_R_MALLOC_FAILURE);
  36. return pq;
  37. }
  38. void pqueue_free(pqueue *pq)
  39. {
  40. OPENSSL_free(pq);
  41. }
  42. pitem *pqueue_insert(pqueue *pq, pitem *item)
  43. {
  44. pitem *curr, *next;
  45. if (pq->items == NULL) {
  46. pq->items = item;
  47. return item;
  48. }
  49. for (curr = NULL, next = pq->items;
  50. next != NULL; curr = next, next = next->next) {
  51. /*
  52. * we can compare 64-bit value in big-endian encoding with memcmp:-)
  53. */
  54. int cmp = memcmp(next->priority, item->priority, 8);
  55. if (cmp > 0) { /* next > item */
  56. item->next = next;
  57. if (curr == NULL)
  58. pq->items = item;
  59. else
  60. curr->next = item;
  61. return item;
  62. }
  63. else if (cmp == 0) /* duplicates not allowed */
  64. return NULL;
  65. }
  66. item->next = NULL;
  67. curr->next = item;
  68. return item;
  69. }
  70. pitem *pqueue_peek(pqueue *pq)
  71. {
  72. return pq->items;
  73. }
  74. pitem *pqueue_pop(pqueue *pq)
  75. {
  76. pitem *item = pq->items;
  77. if (pq->items != NULL)
  78. pq->items = pq->items->next;
  79. return item;
  80. }
  81. pitem *pqueue_find(pqueue *pq, unsigned char *prio64be)
  82. {
  83. pitem *next;
  84. pitem *found = NULL;
  85. if (pq->items == NULL)
  86. return NULL;
  87. for (next = pq->items; next->next != NULL; next = next->next) {
  88. if (memcmp(next->priority, prio64be, 8) == 0) {
  89. found = next;
  90. break;
  91. }
  92. }
  93. /* check the one last node */
  94. if (memcmp(next->priority, prio64be, 8) == 0)
  95. found = next;
  96. if (!found)
  97. return NULL;
  98. return found;
  99. }
  100. pitem *pqueue_iterator(pqueue *pq)
  101. {
  102. return pqueue_peek(pq);
  103. }
  104. pitem *pqueue_next(piterator *item)
  105. {
  106. pitem *ret;
  107. if (item == NULL || *item == NULL)
  108. return NULL;
  109. /* *item != NULL */
  110. ret = *item;
  111. *item = (*item)->next;
  112. return ret;
  113. }
  114. size_t pqueue_size(pqueue *pq)
  115. {
  116. pitem *item = pq->items;
  117. size_t count = 0;
  118. while (item != NULL) {
  119. count++;
  120. item = item->next;
  121. }
  122. return count;
  123. }