pqueue_base.h

Go to the documentation of this file.

/*
 * Copyright (c) 2014, Volkan Yazıcı <volkan.yazici@gmail.com>
 * 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 SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
 * ANY EXPRESS 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 THE COPYRIGHT OWNER OR CONTRIBUTORS 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.
 *
 * Modified by Marten Lohstroh (May, 2019).
 * Changes:
 * - Require implementation of a pqueue_eq_elem_f function to determine
 *   whether two elements are equal or not; and
 * - The provided pqueue_eq_elem_f implementation is used to test and
 *   search for equal elements present in the queue; and
 * - Removed capability to reassign priorities.
 *
 * Modified by Byeonggil Jun (Apr, 2024).
 * Changes:
 * - Made the pqueue_cmp_pri_f function return do the three-way comparison
 *   rather than the two-way comparison.
 * - The changed pqueue_cmp_pri_f function is used to check the equality of
 *   two elements in the pqueue_find_equal_same_priority function.
 * - Remove the pqueue_find_equal function.
 *
 * @brief Priority Queue function declarations used as a base for Lingua Franca priority queues.
 *
 * @{
 */
 
#ifndef PQUEUE_BASE_H
#define PQUEUE_BASE_H
 
#include <stddef.h>
 
typedef unsigned long long pqueue_pri_t;
 
typedef pqueue_pri_t (*pqueue_get_pri_f)(void* a);
 
typedef int (*pqueue_cmp_pri_f)(pqueue_pri_t next, pqueue_pri_t curr);
 
typedef int (*pqueue_eq_elem_f)(void* next, void* curr);
 
typedef size_t (*pqueue_get_pos_f)(void* a);
 
typedef void (*pqueue_set_pos_f)(void* a, size_t pos);
 
typedef void (*pqueue_print_entry_f)(void* a);
 
typedef struct pqueue_t {
  size_t size;              
  size_t avail;             
  size_t step;              
  pqueue_cmp_pri_f cmppri;  
  pqueue_get_pri_f getpri;  
  pqueue_get_pos_f getpos;  
  pqueue_set_pos_f setpos;  
  pqueue_eq_elem_f eqelem;  
  pqueue_print_entry_f prt; 
  void** d;                 
} pqueue_t;
 
pqueue_t* pqueue_init(size_t n, pqueue_cmp_pri_f cmppri, pqueue_get_pri_f getpri, pqueue_get_pos_f getpos,
                      pqueue_set_pos_f setpos, pqueue_eq_elem_f eqelem, pqueue_print_entry_f prt);
 
void pqueue_free(pqueue_t* q);
 
size_t pqueue_size(pqueue_t* q);
 
int pqueue_insert(pqueue_t* q, void* d);
 
void pqueue_change_priority(pqueue_t* q, pqueue_pri_t new_pri, void* d);
 
void* pqueue_pop(pqueue_t* q);
 
void pqueue_empty_into(pqueue_t** dest, pqueue_t** src);
 
void* pqueue_find_same_priority(pqueue_t* q, void* e);
 
void* pqueue_find_equal_same_priority(pqueue_t* q, void* e);
 
int pqueue_remove(pqueue_t* q, void* e);
 
void* pqueue_peek(pqueue_t* q);
 
void pqueue_print(pqueue_t* q, pqueue_print_entry_f print);
 
void pqueue_dump(pqueue_t* q, pqueue_print_entry_f print);
 
int pqueue_is_valid(pqueue_t* q);
 
#endif /* PQUEUE_BASE_H */