Debian Codegraph @

src/libsphinxbase/util/priority_queue.c

raw
1 /* -*- c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 /* ====================================================================
3 * Copyright (c) 2015 Carnegie Mellon University. All rights
4 * reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 *
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in
15 * the documentation and/or other materials provided with the
16 * distribution.
17 *
18 * This work was supported in part by funding from the Defense Advanced
19 * Research Projects Agency and the National Science Foundation of the
20 * United States of America, and the CMU Sphinx Speech Consortium.
21 *
22 * THIS SOFTWARE IS PROVIDED BY CARNEGIE MELLON UNIVERSITY ``AS IS'' AND
23 * ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
24 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
25 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY
26 * NOR ITS EMPLOYEES BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
27 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
28 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
29 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
30 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
31 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
32 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
33 *
34 * ====================================================================
35 *
36 */
37
38 #ifdef HAVE_CONFIG_H
39 #include <config.h>
40 #endif
41
42 #include <sphinxbase/priority_queue.h>
43 #include <sphinxbase/ckd_alloc.h>
44 #include <sphinxbase/err.h>
45
46 struct priority_queue_s {
47 void **pointers;
48 size_t alloc_size;
49 size_t size;
50 void *max_element;
51 int (*compare)(const void *a, const void *b);
52 };
53
54 priority_queue_t* priority_queue_create(size_t len, int (*compare)(const void *a, const void *b))
55 {
56 priority_queue_t* queue;
57
58 queue = (priority_queue_t *)ckd_calloc(1, sizeof(*queue));
59 queue->alloc_size = len;
60 queue->pointers = (void **)ckd_calloc(len, sizeof(*queue->pointers));
61 queue->size = 0;
62 queue->max_element = NULL;
63 queue->compare = compare;
64
65 return queue;
66 }
67
68 void* priority_queue_poll(priority_queue_t *queue)
69 {
70
71 size_t i;
72 void *res;
73
74 if (queue->size == 0) {
75 E_WARN("Trying to poll from empty queue\n");
76 return NULL;
77 }
78 if (queue->max_element == NULL) {
79 E_ERROR("Trying to poll from queue and max element is undefined\n");
80 return NULL;
81 }
82 res = queue->max_element;
83 for (i = 0; i < queue->alloc_size; i++) {
84 if (queue->pointers[i] == queue->max_element) {
85 queue->pointers[i] = NULL;
86 break;
87 }
88 }
89 queue->max_element = NULL;
90 for (i = 0; i < queue->alloc_size; i++) {
91 if (queue->pointers[i] == 0)
92 continue;
93 if (queue->max_element == NULL) {
94 queue->max_element = queue->pointers[i];
95 } else {
96 if (queue->compare(queue->pointers[i], queue->max_element) < 0)
97 queue->max_element = queue->pointers[i];
98 }
99 }
100 queue->size--;
101 return res;
102 }
103
104 void priority_queue_add(priority_queue_t *queue, void *element)
105 {
106 size_t i;
107 if (queue->size == queue->alloc_size) {
108 E_ERROR("Trying to add element into full queue\n");
109 return;
110 }
111 for (i = 0; i < queue->alloc_size; i++) {
112 if (queue->pointers[i] == NULL) {
113 queue->pointers[i] = element;
114 break;
115 }
116 }
117
118 if (queue->max_element == NULL || queue->compare(element, queue->max_element) < 0) {
119 queue->max_element = element;
120 }
121 queue->size++;
122 }
123
124 size_t priority_queue_size(priority_queue_t *queue)
125 {
126 return queue->size;
127 }
128
129 void priority_queue_free(priority_queue_t *queue, void (*free_ptr)(void *a))
130 {
131 size_t i;
132
133 for (i = 0; i < queue->alloc_size; i++) {
134 if (queue->pointers[i] != NULL) {
135 if (free_ptr == NULL) {
136 ckd_free(queue->pointers[i]);
137 } else {
138 free_ptr(queue->pointers[i]);
139 }
140 }
141 }
142 ckd_free(queue->pointers);
143 ckd_free(queue);
144 }