SphinxBase 5prealpha
priority_queue.c
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>
44#include <sphinxbase/err.h>
45
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
54priority_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
68void* 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
104void 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
124size_t priority_queue_size(priority_queue_t *queue)
125{
126 return queue->size;
127}
128
129void 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}
Sphinx's memory allocation/deallocation routines.
SPHINXBASE_EXPORT void ckd_free(void *ptr)
Test and free a 1-D array.
Definition: ckd_alloc.c:244
#define ckd_calloc(n, sz)
Macros to simplify the use of above functions.
Definition: ckd_alloc.h:248
Implementation of logging routines.
#define E_ERROR(...)
Print error message to error log.
Definition: err.h:104
#define E_WARN(...)
Print warning message to error log.
Definition: err.h:109