Line data    Source code

       1           1 : /**
       2             : * @file datatypes/calqueue.h
       3             : *
       4             : * @brief Calendar Queue Implementation
       5             : *
       6             : * Classical Calendar Queue implementation. It is an array of lists of
       7             : * events which reorganizes itself upon each insertion/deletion, ensuring
       8             : * amortized O(1) operations.
       9             : *
      10             : * Due to the nature of the calendar queue, you cannot insert events which
      11             : * "happen before" the last extracted events, otherwise the list breaks
      12             : * and starts returning dummy events.
      13             : *
      14             : * For a thorough description of the algorithm, refer to:
      15             : *
      16             : * R. Brown
      17             : * “Calendar Queues: A Fast 0(1) Priority Queue Implementation for the
      18             : * Simulation Event Set Problem”
      19             : * CACM, Vol. 31, No. 10, pp. 1220-1227, Oct. 1988.
      20             : *
      21             : * @copyright
      22             : * Copyright (C) 2008-2019 HPDCS Group
      23             : * https://hpdcs.github.io
      24             : *
      25             : * This file is part of ROOT-Sim (ROme OpTimistic Simulator).
      26             : *
      27             : * ROOT-Sim is free software; you can redistribute it and/or modify it under the
      28             : * terms of the GNU General Public License as published by the Free Software
      29             : * Foundation; only version 3 of the License applies.
      30             : *
      31             : * ROOT-Sim is distributed in the hope that it will be useful, but WITHOUT ANY
      32             : * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
      33             : * A PARTICULAR PURPOSE. See the GNU General Public License for more details.
      34             : *
      35             : * You should have received a copy of the GNU General Public License along with
      36             : * ROOT-Sim; if not, write to the Free Software Foundation, Inc.,
      37             : * 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
      38             : *
      39             : * @author R. Brown
      40             : */
      41             : 
      42             : #pragma once
      43             : 
      44           0 : #define CALQSPACE 65536         // Calendar array size needed for maximum resize
      45           0 : #define MAXNBUCKETS 32768       // Maximum number of buckets in calendar queue
      46             : 
      47           0 : typedef struct __calqueue_node {
      48           0 :         double timestamp;       // Timestamp associated to the event
      49           0 :         void *payload;          // A pointer to the actual content of the node
      50           0 :         struct __calqueue_node *next;   // Pointers to other nodes
      51           0 : } calqueue_node;
      52             : 
      53           0 : typedef struct __calqueue_node *calendar_queue;
      54             : 
      55           0 : extern void calqueue_init(void);
      56           0 : extern void *calqueue_get(void);
      57           0 : extern void calqueue_put(double, void *);