priority_queue.c
/* -*- c-basic-offset: 4; indent-tabs-mode: nil -*- */
/* ====================================================================
* Copyright (c) 2015 Carnegie Mellon University. All rights
* reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* This work was supported in part by funding from the Defense Advanced
* Research Projects Agency and the National Science Foundation of the
* United States of America, and the CMU Sphinx Speech Consortium.
*
* THIS SOFTWARE IS PROVIDED BY CARNEGIE MELLON UNIVERSITY ``AS IS'' AND
* ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
* THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY
* NOR ITS EMPLOYEES BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*
* ====================================================================
*
*/
#ifdef HAVE_CONFIG_H
#include <config.h>
#endif
#include <sphinxbase/priority_queue.h>
#include <sphinxbase/ckd_alloc.h>
#include <sphinxbase/err.h>
struct priority_queue_s {
void **pointers;
size_t alloc_size;
size_t size;
void *max_element;
int (*compare)(const void *a, const void *b);
};
priority_queue_t* priority_queue_create(size_t len, int (*compare)(const void *a, const void *b))
{
priority_queue_t* queue;
queue = (priority_queue_t *)ckd_calloc(1, sizeof(*queue));
queue->alloc_size = len;
queue->pointers = (void **)ckd_calloc(len, sizeof(*queue->pointers));
queue->size = 0;
queue->max_element = NULL;
queue->compare = compare;
return queue;
}
void* priority_queue_poll(priority_queue_t *queue)
{
size_t i;
void *res;
if (queue->size == 0) {
E_WARN("Trying to poll from empty queue\n");
return NULL;
}
if (queue->max_element == NULL) {
E_ERROR("Trying to poll from queue and max element is undefined\n");
return NULL;
}
res = queue->max_element;
for (i = 0; i < queue->alloc_size; i++) {
if (queue->pointers[i] == queue->max_element) {
queue->pointers[i] = NULL;
break;
}
}
queue->max_element = NULL;
for (i = 0; i < queue->alloc_size; i++) {
if (queue->pointers[i] == 0)
continue;
if (queue->max_element == NULL) {
queue->max_element = queue->pointers[i];
} else {
if (queue->compare(queue->pointers[i], queue->max_element) < 0)
queue->max_element = queue->pointers[i];
}
}
queue->size--;
return res;
}
void priority_queue_add(priority_queue_t *queue, void *element)
{
size_t i;
if (queue->size == queue->alloc_size) {
E_ERROR("Trying to add element into full queue\n");
return;
}
for (i = 0; i < queue->alloc_size; i++) {
if (queue->pointers[i] == NULL) {
queue->pointers[i] = element;
break;
}
}
if (queue->max_element == NULL || queue->compare(element, queue->max_element) < 0) {
queue->max_element = element;
}
queue->size++;
}
size_t priority_queue_size(priority_queue_t *queue)
{
return queue->size;
}
void priority_queue_free(priority_queue_t *queue, void (*free_ptr)(void *a))
{
size_t i;
for (i = 0; i < queue->alloc_size; i++) {
if (queue->pointers[i] != NULL) {
if (free_ptr == NULL) {
ckd_free(queue->pointers[i]);
} else {
free_ptr(queue->pointers[i]);
}
}
}
ckd_free(queue->pointers);
ckd_free(queue);
}
ckd_alloc.h
Sphinx's memory allocation/deallocation routines.
ckd_free
SPHINXBASE_EXPORT void ckd_free(void *ptr)
Test and free a 1-D array.
Definition ckd_alloc.c:244
ckd_calloc
#define ckd_calloc(n, sz)
Macros to simplify the use of above functions.
Definition ckd_alloc.h:248
err.h
Implementation of logging routines.
E_ERROR
#define E_ERROR(...)
Print error message to error log.
Definition err.h:104
E_WARN
#define E_WARN(...)
Print warning message to error log.
Definition err.h:109
priority_queue_s
Definition priority_queue.c:46