calqueue.c File Reference

Calendar Queue Implementation. More...

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <core/core.h>
#include <datatypes/calqueue.h>
#include <mm/mm.h>

Include dependency graph for calqueue.c:

Go to the source code of this file.

Functions
static calqueue_node *	calqueue_deq (void)
static void	localinit (int qbase, int nbucks, double bwidth, double startprio)
static double	new_width (void)
static void	resize (int newsize)
void	calqueue_init (void)
void	calqueue_put (double timestamp, void *payload)
void *	calqueue_get (void)

Variables
static calqueue_node *	calq [CALQSPACE]
static calqueue_node **	calendar
static int	firstsub
static int	nbuckets
static int	qsize
static int	lastbucket
static bool	resize_enabled
static double	top_threshold
static double	bot_threshold
static double	lastprio
static double	buckettop
static double	cwidth

Detailed Description

Calendar Queue Implementation.

Classical Calendar Queue implementation. It is an array of lists of events which reorganizes itself upon each insertion/deletion, ensuring amortized O(1) operations.

Due to the nature of the calendar queue, you cannot insert events which "happen before" the last extracted events, otherwise the list breaks and starts returning dummy events.

For a thorough description of the algorithm, refer to:

R. Brown “Calendar Queues: A Fast 0(1) Priority Queue Implementation for the Simulation Event Set Problem” CACM, Vol. 31, No. 10, pp. 1220-1227, Oct. 1988.

Copyright

Copyright (C) 2008-2019 HPDCS Group https://hpdcs.github.io

This file is part of ROOT-Sim (ROme OpTimistic Simulator).

ROOT-Sim is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; only version 3 of the License applies.

ROOT-Sim is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with ROOT-Sim; if not, write to the Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA

Author

R. Brown

Definition in file calqueue.c.