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>
43 #include <sphinxbase/ckd_alloc.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 
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 }
#define ckd_calloc(n, sz)
Macros to simplify the use of above functions.
Definition: ckd_alloc.h:248
#define E_ERROR(...)
Print error message to error log.
Definition: err.h:104
Sphinx&#39;s memory allocation/deallocation routines.
SPHINXBASE_EXPORT void ckd_free(void *ptr)
Test and free a 1-D array.
Definition: ckd_alloc.c:244
Implementation of logging routines.
#define E_WARN(...)
Print warning message to error log.
Definition: err.h:109