1 files changed, 204 insertions, 0 deletions

diff --git a/baseline/source/dijkstra/dijkstra.c b/baseline/source/dijkstra/dijkstra.c
new file mode 100644
index 0000000..af86ea6
--- /dev/null
+++ b/baseline/source/dijkstra/dijkstra.c
@@ -0,0 +1,204 @@
+/*
+
+  This program is part of the TACLeBench benchmark suite.
+  Version V 2.0
+
+  Name: dijkstra
+
+  Author: unknown
+
+  Function: dijkstra finds the shortest path between nodes in a graph
+
+  Source: network section of MiBench
+
+  Changes: Made some variables local, compute checksum
+
+  License: GPL
+
+*/
+
+#include "../extra.h"
+#include "input.h"
+
+/*
+  Definitions of symbolic constants
+*/
+#define NONE 9999
+#define OUT_OF_MEMORY -1
+#define QUEUE_SIZE 1000
+
+/*
+  Type declarations
+*/
+struct _NODE {
+  int dist;
+  int prev;
+};
+
+struct _QITEM {
+  int node;
+  int dist;
+  int prev;
+  struct _QITEM *next;
+};
+
+/*
+  Global variable definitions
+*/
+struct _NODE dijkstra_rgnNodes[NUM_NODES];
+
+int dijkstra_queueCount;
+int dijkstra_queueNext;
+struct _QITEM *dijkstra_queueHead;
+struct _QITEM dijkstra_queueItems[QUEUE_SIZE];
+
+int dijkstra_checksum = 0;
+
+/*
+  Forward declaration of functions
+*/
+void dijkstra_init( void );
+int dijkstra_return( void );
+int dijkstra_enqueue( int node, int dist, int prev );
+void dijkstra_dequeue( int *node, int *dist, int *prev );
+int dijkstra_qcount( void );
+int dijkstra_find( int chStart, int chEnd );
+void dijkstra_main( void );
+//int main( void );
+
+void dijkstra_init( void )
+{
+  int i, k;
+  volatile int x = 0;
+  _Pragma( "loopbound min 100 max 100" )
+  for ( i = 0; i < NUM_NODES; i++ ) {
+    _Pragma( "loopbound min 100 max 100" )
+    for ( k = 0; k < NUM_NODES; k++ ) {
+      dijkstra_AdjMatrix[i][k] ^= x;
+    }
+  }
+
+  dijkstra_queueCount = 0;
+  dijkstra_queueNext = 0;
+  dijkstra_queueHead = ( struct _QITEM * )0;
+
+  dijkstra_checksum = 0;
+}
+
+int dijkstra_return( void )
+{
+  return ( ( dijkstra_checksum == 25 ) ? 0 : -1 );
+}
+
+int dijkstra_enqueue( int node, int dist, int prev )
+{
+  struct _QITEM *newItem = &dijkstra_queueItems[dijkstra_queueNext];
+  struct _QITEM *last = dijkstra_queueHead;
+
+  if ( ++dijkstra_queueNext >= QUEUE_SIZE )
+    return OUT_OF_MEMORY;
+  newItem->node = node;
+  newItem->dist = dist;
+  newItem->prev = prev;
+  newItem->next = 0;
+
+  if ( !last )
+    dijkstra_queueHead = newItem;
+  else {
+    /* TODO: where does this magic loop bound come from? */
+    _Pragma( "loopbound min 0 max 313" )
+    while ( last->next )
+      last = last->next;
+    last->next = newItem;
+  }
+  dijkstra_queueCount++;
+  return 0;
+}
+
+void dijkstra_dequeue( int *node, int *dist, int *prev )
+{
+  if ( dijkstra_queueHead ) {
+    *node = dijkstra_queueHead->node;
+    *dist = dijkstra_queueHead->dist;
+    *prev = dijkstra_queueHead->prev;
+    dijkstra_queueHead = dijkstra_queueHead->next;
+    dijkstra_queueCount--;
+  }
+}
+
+int dijkstra_qcount( void )
+{
+  return ( dijkstra_queueCount );
+}
+
+int dijkstra_find( int chStart, int chEnd )
+{
+  int ch;
+  int prev, node;
+  int cost, dist;
+  int i;
+
+  _Pragma( "loopbound min 100 max 100" )
+  for ( ch = 0; ch < NUM_NODES; ch++ ) {
+    dijkstra_rgnNodes[ch].dist = NONE;
+    dijkstra_rgnNodes[ch].prev = NONE;
+  }
+
+  if ( chStart == chEnd ) {
+  } else {
+    dijkstra_rgnNodes[chStart].dist = 0;
+    dijkstra_rgnNodes[chStart].prev = NONE;
+
+    if ( dijkstra_enqueue ( chStart, 0, NONE ) == OUT_OF_MEMORY )
+      return OUT_OF_MEMORY;
+
+    /* TODO: where does this magic loop bound come from? */
+    _Pragma( "loopbound min 618 max 928" )
+    while ( dijkstra_qcount() > 0 ) {
+      dijkstra_dequeue ( &node, &dist, &prev );
+      _Pragma( "loopbound min 100 max 100" )
+      for ( i = 0; i < NUM_NODES; i++ ) {
+        if ( ( cost = dijkstra_AdjMatrix[node][i] ) != NONE ) {
+          if ( ( NONE == dijkstra_rgnNodes[i].dist ) ||
+               ( dijkstra_rgnNodes[i].dist > ( cost + dist ) ) ) {
+            dijkstra_rgnNodes[i].dist = dist + cost;
+            dijkstra_rgnNodes[i].prev = node;
+            if ( dijkstra_enqueue ( i, dist + cost, node ) == OUT_OF_MEMORY )
+              return OUT_OF_MEMORY;
+          }
+        }
+      }
+    }
+  }
+  return 0;
+}
+
+void _Pragma( "entrypoint" ) dijkstra_main( void )
+{
+  int i, j;
+
+  /* finds 20 shortest paths between nodes */
+  _Pragma( "loopbound min 20 max 20" )
+  for ( i = 0, j = NUM_NODES / 2; i < 20; i++, j++ ) {
+    j = j % NUM_NODES;
+    if ( dijkstra_find( i, j ) == OUT_OF_MEMORY ) {
+      dijkstra_checksum += OUT_OF_MEMORY;
+      return;
+    } else
+      dijkstra_checksum += dijkstra_rgnNodes[j].dist;
+    dijkstra_queueNext = 0;
+  }
+}
+
+int main(int argc, char** argv )
+{
+        SET_UP
+        for(jobsComplete=-1; jobsComplete<maxJobs; jobsComplete++){
+                START_LOOP
+                dijkstra_init();
+                dijkstra_main();
+                STOP_LOOP
+        }
+        WRITE_TO_FILE
+  return ( dijkstra_return() );
+}