summaryrefslogtreecommitdiffstats
path: root/baseline/source/dijkstra
diff options
context:
space:
mode:
Diffstat (limited to 'baseline/source/dijkstra')
-rw-r--r--baseline/source/dijkstra/ChangeLog.txt44
-rw-r--r--baseline/source/dijkstra/dijkstra.c204
-rw-r--r--baseline/source/dijkstra/input.c105
-rw-r--r--baseline/source/dijkstra/input.h8
4 files changed, 361 insertions, 0 deletions
diff --git a/baseline/source/dijkstra/ChangeLog.txt b/baseline/source/dijkstra/ChangeLog.txt
new file mode 100644
index 0000000..f96350b
--- /dev/null
+++ b/baseline/source/dijkstra/ChangeLog.txt
@@ -0,0 +1,44 @@
1File: dijkstra.c
2Original provenience: network section of MiBench
3
42015-11-30:
5- Replaced "NULL" with "0", remove #include of glibc_common.h
6- Removed commented code referring to variable "qKill"
7- Made ch, i, iPrev, iNode, iCost and iDist local variables
8- Stripped (inconsistently applied) Hungarian notation, replaced
9 prefix "q" with prefix "queue" for global variables, renamed
10 "next_in" to "queueNext" and "qNew" to "newItem"
11- Initialize queueHead statically (like queueCount and queueNext)
12- Prefixed all functions and global variables with "dijkstra_",
13 renaming "dijkstra" to "dijkstra_find"
14- Calculate a checksum in dijkstra_main, return its value in new
15 function dijkstra_return
16- Added (empty) function dijkstra_init and a main function
17- Reordered functions in source code: initialization- and
18 return-value-related functions first, followed by algorithm core
19 functions, followed by main functions
20- Added function prototypes
21- Applied code formatting with astyle as in the example
22- Added general TACLeBench header to beginning of source code
23
242016-03-15:
25- Return 0 if checksum is as expected, -1 otherwise
26- Make all initializations explicit
27- Touch input matrix with volatile to rule out optimizations
28- Add entrypoint pragma
29
302016-06-14:
31- Removed cast to make C++ compiler happy
32
33Files: input.h, input.c
34Original provenience: network section of MiBench
35
362015-11-30:
37- Prefix global variable "AdjMatrix" with "dijkstra_"
38- Applied code formatting with astyle as in the example
39
40File: glibc_common.h
41Original provenience: network section of MiBench
42
432015-11-30:
44- Removed file
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 @@
1/*
2
3 This program is part of the TACLeBench benchmark suite.
4 Version V 2.0
5
6 Name: dijkstra
7
8 Author: unknown
9
10 Function: dijkstra finds the shortest path between nodes in a graph
11
12 Source: network section of MiBench
13
14 Changes: Made some variables local, compute checksum
15
16 License: GPL
17
18*/
19
20#include "../extra.h"
21#include "input.h"
22
23/*
24 Definitions of symbolic constants
25*/
26#define NONE 9999
27#define OUT_OF_MEMORY -1
28#define QUEUE_SIZE 1000
29
30/*
31 Type declarations
32*/
33struct _NODE {
34 int dist;
35 int prev;
36};
37
38struct _QITEM {
39 int node;
40 int dist;
41 int prev;
42 struct _QITEM *next;
43};
44
45/*
46 Global variable definitions
47*/
48struct _NODE dijkstra_rgnNodes[NUM_NODES];
49
50int dijkstra_queueCount;
51int dijkstra_queueNext;
52struct _QITEM *dijkstra_queueHead;
53struct _QITEM dijkstra_queueItems[QUEUE_SIZE];
54
55int dijkstra_checksum = 0;
56
57/*
58 Forward declaration of functions
59*/
60void dijkstra_init( void );
61int dijkstra_return( void );
62int dijkstra_enqueue( int node, int dist, int prev );
63void dijkstra_dequeue( int *node, int *dist, int *prev );
64int dijkstra_qcount( void );
65int dijkstra_find( int chStart, int chEnd );
66void dijkstra_main( void );
67//int main( void );
68
69void dijkstra_init( void )
70{
71 int i, k;
72 volatile int x = 0;
73 _Pragma( "loopbound min 100 max 100" )
74 for ( i = 0; i < NUM_NODES; i++ ) {
75 _Pragma( "loopbound min 100 max 100" )
76 for ( k = 0; k < NUM_NODES; k++ ) {
77 dijkstra_AdjMatrix[i][k] ^= x;
78 }
79 }
80
81 dijkstra_queueCount = 0;
82 dijkstra_queueNext = 0;
83 dijkstra_queueHead = ( struct _QITEM * )0;
84
85 dijkstra_checksum = 0;
86}
87
88int dijkstra_return( void )
89{
90 return ( ( dijkstra_checksum == 25 ) ? 0 : -1 );
91}
92
93int dijkstra_enqueue( int node, int dist, int prev )
94{
95 struct _QITEM *newItem = &dijkstra_queueItems[dijkstra_queueNext];
96 struct _QITEM *last = dijkstra_queueHead;
97
98 if ( ++dijkstra_queueNext >= QUEUE_SIZE )
99 return OUT_OF_MEMORY;
100 newItem->node = node;
101 newItem->dist = dist;
102 newItem->prev = prev;
103 newItem->next = 0;
104
105 if ( !last )
106 dijkstra_queueHead = newItem;
107 else {
108 /* TODO: where does this magic loop bound come from? */
109 _Pragma( "loopbound min 0 max 313" )
110 while ( last->next )
111 last = last->next;
112 last->next = newItem;
113 }
114 dijkstra_queueCount++;
115 return 0;
116}
117
118void dijkstra_dequeue( int *node, int *dist, int *prev )
119{
120 if ( dijkstra_queueHead ) {
121 *node = dijkstra_queueHead->node;
122 *dist = dijkstra_queueHead->dist;
123 *prev = dijkstra_queueHead->prev;
124 dijkstra_queueHead = dijkstra_queueHead->next;
125 dijkstra_queueCount--;
126 }
127}
128
129int dijkstra_qcount( void )
130{
131 return ( dijkstra_queueCount );
132}
133
134int dijkstra_find( int chStart, int chEnd )
135{
136 int ch;
137 int prev, node;
138 int cost, dist;
139 int i;
140
141 _Pragma( "loopbound min 100 max 100" )
142 for ( ch = 0; ch < NUM_NODES; ch++ ) {
143 dijkstra_rgnNodes[ch].dist = NONE;
144 dijkstra_rgnNodes[ch].prev = NONE;
145 }
146
147 if ( chStart == chEnd ) {
148 } else {
149 dijkstra_rgnNodes[chStart].dist = 0;
150 dijkstra_rgnNodes[chStart].prev = NONE;
151
152 if ( dijkstra_enqueue ( chStart, 0, NONE ) == OUT_OF_MEMORY )
153 return OUT_OF_MEMORY;
154
155 /* TODO: where does this magic loop bound come from? */
156 _Pragma( "loopbound min 618 max 928" )
157 while ( dijkstra_qcount() > 0 ) {