trunk/src/results.c

/***************************************
 $Header: /home/amb/CVS/routino/src/results.c,v 1.3 2009-01-22 19:26:17 amb Exp $

 Result data type functions.
 ******************/ /******************
 Written by Andrew M. Bishop

 This file Copyright 2008,2009 Andrew M. Bishop
 It may be distributed under the GNU Public License, version 2, or
 any higher version.  See section COPYING of the GNU Public license
 for conditions under which this file may be redistributed.
 ***************************************/


#include <assert.h>
#include <string.h>
#include <stdlib.h>

#include "results.h"


#define QUEUE_INCREMENT 1024

/*+ A queue of results. +*/
typedef struct _Queue
{
 uint32_t alloced;              /*+ The amount of space allocated for results in the array. +*/
 uint32_t number;               /*+ The number of occupied results in the array. +*/
 uint32_t *queue;               /*+ An array of offsets into the results array. +*/
}
 Queue;

/*+ The queue of nodes. +*/
static Queue queue={0,0,NULL};


/*++++++++++++++++++++++++++++++++++++++
  Allocate a new results list.

  Results *NewResultsList Returns the results list.
  ++++++++++++++++++++++++++++++++++++++*/

Results *NewResultsList(void)
{
 Results *results;
#if NBINS_RESULTS
 int i;
#endif

 results=(Results*)malloc(sizeof(Results));

 results->alloced=INCREMENT_RESULTS;
 results->number=0;

#if NBINS_RESULTS
 for(i=0;i<NBINS_RESULTS;i++)
   {
    results->numbin[i]=0;

    results->offsets[i]=(uint32_t*)malloc(results->alloced*sizeof(uint32_t));
   }

 results->results=(Result*)malloc(results->alloced*NBINS_RESULTS*sizeof(Result));
#else
 results->offsets=(uint32_t*)malloc(results->alloced*sizeof(uint32_t));

 results->data=(Result*)malloc(results->alloced*sizeof(Result));
#endif

 return(results);
}


/*++++++++++++++++++++++++++++++++++++++
  Allocate a new results list.

  Results *results The results list to be destroyed.
  ++++++++++++++++++++++++++++++++++++++*/

void FreeResultsList(Results *results)
{
#if NBINS_RESULTS
 int i;
#endif

#if NBINS_RESULTS
 for(i=0;i<NBINS_RESULTS;i++)
    free(results->offsets[i]);
#else
 free(results->offsets);
#endif

 free(results->results);

 free(results);
}


/*++++++++++++++++++++++++++++++++++++++
  Insert a new result into the results data structure in the right order.

  Result *insert_result Returns the result that has been inserted.

  Results *results The results structure to insert into.

  node_t node The node that is to be inserted into the results.
  ++++++++++++++++++++++++++++++++++++++*/

Result *InsertResult(Results *results,node_t node)
{
#ifdef NBINS_RESULTS
 int bin=node%NBINS_RESULTS;
 int start=0;
 int end=results->numbin[bin]-1;
 uint32_t *offsetsp=results->offsets[bin];
 int i;
#else
 int start=0;
 int end=results->number-1;
 uint32_t *offsetsp=results->offsets;
#endif
 int mid;
 int insert=-1;

 /* Check that the arrays have enough space. */

#ifdef NBINS_RESULTS
 if(results->numbin[bin]==results->alloced)
   {
    results->alloced+=INCREMENT_RESULTS;

    for(i=0;i<NBINS_RESULTS;i++)
       results->offsets[i]=(uint32_t*)realloc((void*)results->offsets[i],results->alloced*sizeof(uint32_t));

    offsetsp=results->offsets[bin];

    results->results=(Result*)realloc((void*)results->results,results->alloced*NBINS_RESULTS*sizeof(Result));
   }
#else
 if(results->number==results->alloced)
   {
    results->alloced+=INCREMENT_RESULTS;

    results->offsets=(uint32_t*)realloc((void*)results->offsets[i],results->alloced*sizeof(uint32_t));

    offsetsp=results->offsets;

    results->results=(Result*)realloc((void*)results->results,results->alloced*sizeof(Result));
   }
#endif

 /* Binary search - search key may not match, if not then insertion point required
  *
  *  # <- start  |  Check mid and move start or end if it doesn't match
  *  #           |
  *  #           |  Since there may not be an exact match we must set end=mid
  *  # <- mid    |  or start=mid because we know that mid doesn't match.
  *  #           |
  *  #           |  Eventually end=start+1 and the insertion point is before
  *  # <- end    |  end (since it cannot be before the initial start or end).
  */

 if(end<start)                                         /* There are no results */
    insert=start;
 else if(node<results->results[offsetsp[start]].node) /* Check key is not before start */
    insert=start;
 else if(node>results->results[offsetsp[end]].node)   /* Check key is not after end */
    insert=end+1;
 else
   {
    do
      {
       mid=(start+end)/2;                                  /* Choose mid point */

       if(results->results[offsetsp[mid]].node<node)      /* Mid point is too low */
          start=mid;
       else if(results->results[offsetsp[mid]].node>node) /* Mid point is too high */
          end=mid;
       else
          assert(0);
      }
    while((end-start)>1);

    insert=end;
   }

 /* Shuffle the array up */

#ifdef NBINS_RESULTS
 if(insert!=results->numbin[bin])
    memmove(&offsetsp[insert+1],&offsetsp[insert],(results->numbin[bin]-insert)*sizeof(uint32_t));
#else
 if(insert!=results->number)
    memmove(&offsetsp[insert+1],&offsetsp[insert],(results->number-insert)*sizeof(uint32_t));
#endif

 /* Insert the new entry */

 offsetsp[insert]=results->number;

 results->number++;

#ifdef NBINS_RESULTS
 results->numbin[bin]++;
#endif

 return(&results->results[offsetsp[insert]]);
}


/*++++++++++++++++++++++++++++++++++++++
  Find a result, ordered by node.

  Result *insert_result Returns the result that has been found.

  Results *results The results structure to search.

  node_t node The node that is to be found.
  ++++++++++++++++++++++++++++++++++++++*/

Result *FindResult(Results *results,node_t node)
{
#ifdef NBINS_RESULTS
 int bin=node%NBINS_RESULTS;
 int start=0;
 int end=results->numbin[bin]-1;
 uint32_t *offsetsp=results->offsets[bin];
#else
 int start=0;
 int end=results->number-1;
 uint32_t *offsetsp=results->offsets;
#endif
 int mid;

 /* Binary search - search key exact match only is required.
  *
  *  # <- start  |  Check mid and move start or end if it doesn't match
  *  #           |
  *  #           |  Since an exact match is wanted we can set end=mid-1
  *  # <- mid    |  or start=mid+1 because we know that mid doesn't match.
  *  #           |
  *  #           |  Eventually either end=start or end=start+1 and one of
  *  # <- end    |  start or end is the wanted one.
  */

 if(end<start)                                         /* There are no results */
    return(NULL);
 else if(node<results->results[offsetsp[start]].node) /* Check key is not before start */
    return(NULL);
 else if(node>results->results[offsetsp[end]].node)   /* Check key is not after end */
    return(NULL);
 else
   {
    do
      {
       mid=(start+end)/2;                                  /* Choose mid point */

       if(results->results[offsetsp[mid]].node<node)      /* Mid point is too low */
          start=mid+1;
       else if(results->results[offsetsp[mid]].node>node) /* Mid point is too high */
          end=mid-1;
       else                                                /* Mid point is correct */
          return(&results->results[offsetsp[mid]]);
      }
    while((end-start)>1);

    if(results->results[offsetsp[start]].node==node)      /* Start is correct */
       return(&results->results[offsetsp[start]]);

    if(results->results[offsetsp[end]].node==node)        /* End is correct */
       return(&results->results[offsetsp[end]]);
   }

 return(NULL);
}


/*++++++++++++++++++++++++++++++++++++++
  Insert an item into the queue in the right order.

  Results *results The set of results.

  Result *result The result to insert into the queue.
  ++++++++++++++++++++++++++++++++++++++*/

void insert_in_queue(Results *results,Result *result)
{
 int start=0;
 int end=queue.number-1;
 int mid;
 int insert=-1;

 /* Check that the whole thing is allocated. */

 if(!queue.queue)
   {
    queue.alloced=QUEUE_INCREMENT;
    queue.number=0;
    queue.queue=(uint32_t*)malloc(queue.alloced*sizeof(uint32_t));
   }

 /* Check that the arrays have enough space. */

 if(queue.number==queue.alloced)
   {
    queue.alloced+=QUEUE_INCREMENT;
    queue.queue=(uint32_t*)realloc((void*)queue.queue,queue.alloced*sizeof(uint32_t));
   }

 /* Binary search - search key may not match, new insertion point required
  *
  *  # <- start  |  Check mid and move start or end if it doesn't match
  *  #           |
  *  #           |  Since there may not be an exact match we must set end=mid
  *  # <- mid    |  or start=mid because we know that mid doesn't match.
  *  #           |
  *  #           |  Eventually end=start+1 and the insertion point is before
  *  # <- end    |  end (since it cannot be before the initial start or end).
  */

 if(queue.number==0)                                                                       /* There is nothing in the queue */
    insert=0;
 else if(result->shortest.distance>results->results[queue.queue[start]].shortest.distance) /* Check key is not before start */
    insert=start;
 else if(result->shortest.distance<results->results[queue.queue[end]].shortest.distance)   /* Check key is not after end */
    insert=end+1;
 else
   {
    do
      {
       mid=(start+end)/2;                                                                      /* Choose mid point */

       if(results->results[queue.queue[mid]].shortest.distance>result->shortest.distance)      /* Mid point is too low */
          start=mid;
       else if(results->results[queue.queue[mid]].shortest.distance<result->shortest.distance) /* Mid point is too high */
          end=mid;
       else                                                                                    /* Mid point is correct */
         {
          if(&results->results[queue.queue[mid]]==result)
             return;

          insert=mid;
          break;
         }
      }
    while((end-start)>1);

    if(insert==-1)
       insert=end;
   }

 /* Shuffle the array up */

 if(insert!=queue.number)
    memmove(&queue.queue[insert+1],&queue.queue[insert],(queue.number-insert)*sizeof(uint32_t));

 /* Insert the new entry */

 queue.queue[insert]=result-results->results;

 queue.number++;
}


/*++++++++++++++++++++++++++++++++++++++
  Pop an item from the end of the queue.

  Result *pop_from_queue Returns the top item.

  Results *results The set of results that the queue is processing.
  ++++++++++++++++++++++++++++++++++++++*/

Result *pop_from_queue(Results *results)
{
 if(queue.number)
    return LookupResult(results,queue.queue[--queue.number]);
 else
    return NULL;
}
1	amb	29	/***************************************
2	amb	67	$Header: /home/amb/CVS/routino/src/results.c,v 1.3 2009-01-22 19:26:17 amb Exp $
3	amb	29
4			Result data type functions.
5			****************/ /****************
6			Written by Andrew M. Bishop
7
8			This file Copyright 2008,2009 Andrew M. Bishop
9			It may be distributed under the GNU Public License, version 2, or
10			any higher version. See section COPYING of the GNU Public license
11			for conditions under which this file may be redistributed.
12			***************************************/
13
14
15			#include <assert.h>
16			#include <string.h>
17			#include <stdlib.h>
18
19			#include "results.h"
20
21
22	amb	67	#define QUEUE_INCREMENT 1024
23
24			/+ A queue of results. +/
25			typedef struct _Queue
26			{
27			uint32_t alloced; /+ The amount of space allocated for results in the array. +/
28			uint32_t number; /+ The number of occupied results in the array. +/
29			uint32_t queue; /+ An array of offsets into the results array. +*/
30			}
31			Queue;
32
33			/+ The queue of nodes. +/
34			static Queue queue={0,0,NULL};
35
36
37	amb	29	/*++++++++++++++++++++++++++++++++++++++
38			Allocate a new results list.
39
40			Results *NewResultsList Returns the results list.
41			++++++++++++++++++++++++++++++++++++++*/
42
43			Results *NewResultsList(void)
44			{
45			Results *results;
46			#if NBINS_RESULTS
47			int i;
48			#endif
49
50			results=(Results*)malloc(sizeof(Results));
51
52			results->alloced=INCREMENT_RESULTS;
53	amb	45	results->number=0;
54	amb	29
55			#if NBINS_RESULTS
56			for(i=0;i<NBINS_RESULTS;i++)
57			{
58	amb	45	results->numbin[i]=0;
59
60			results->offsets[i]=(uint32_t)malloc(results->allocedsizeof(uint32_t));
61	amb	29	}
62	amb	45
63			results->results=(Result)malloc(results->allocedNBINS_RESULTS*sizeof(Result));
64	amb	29	#else
65	amb	45	results->offsets=(uint32_t)malloc(results->allocedsizeof(uint32_t));
66
67			results->data=(Result)malloc(results->allocedsizeof(Result));
68	amb	29	#endif
69
70			return(results);
71			}
72
73
74			/*++++++++++++++++++++++++++++++++++++++
75			Allocate a new results list.
76
77			Results *results The results list to be destroyed.
78			++++++++++++++++++++++++++++++++++++++*/
79
80			void FreeResultsList(Results *results)
81			{
82			#if NBINS_RESULTS
83			int i;
84			#endif
85
86			#if NBINS_RESULTS
87			for(i=0;i<NBINS_RESULTS;i++)
88	amb	45	free(results->offsets[i]);
89	amb	29	#else
90	amb	45	free(results->offsets);
91	amb	29	#endif
92
93	amb	45	free(results->results);
94
95	amb	29	free(results);
96			}
97
98
99			/*++++++++++++++++++++++++++++++++++++++
100			Insert a new result into the results data structure in the right order.
101
102			Result *insert_result Returns the result that has been inserted.
103
104			Results *results The results structure to insert into.
105
106			node_t node The node that is to be inserted into the results.
107			++++++++++++++++++++++++++++++++++++++*/
108
109			Result InsertResult(Results results,node_t node)
110			{
111			#ifdef NBINS_RESULTS
112			int bin=node%NBINS_RESULTS;
113			int start=0;
114	amb	45	int end=results->numbin[bin]-1;
115			uint32_t *offsetsp=results->offsets[bin];
116	amb	29	int i;
117			#else
118			int start=0;
119			int end=results->number-1;
120	amb	45	uint32_t *offsetsp=results->offsets;
121	amb	29	#endif
122			int mid;
123			int insert=-1;
124
125			/* Check that the arrays have enough space. */
126
127	amb	45	#ifdef NBINS_RESULTS
128			if(results->numbin[bin]==results->alloced)
129	amb	29	{
130			results->alloced+=INCREMENT_RESULTS;
131
132			for(i=0;i<NBINS_RESULTS;i++)
133	amb	45	results->offsets[i]=(uint32_t)realloc((void)results->offsets[i],results->alloced*sizeof(uint32_t));
134	amb	29
135	amb	45	offsetsp=results->offsets[bin];
136
137			results->results=(Result)realloc((void)results->results,results->allocedNBINS_RESULTSsizeof(Result));
138			}
139	amb	29	#else
140	amb	45	if(results->number==results->alloced)
141			{
142			results->alloced+=INCREMENT_RESULTS;
143	amb	29
144	amb	45	results->offsets=(uint32_t)realloc((void)results->offsets[i],results->alloced*sizeof(uint32_t));
145
146			offsetsp=results->offsets;
147
148			results->results=(Result)realloc((void)results->results,results->alloced*sizeof(Result));
149			}
150	amb	29	#endif
151
152			/* Binary search - search key may not match, if not then insertion point required
153			*
154			* # <- start \| Check mid and move start or end if it doesn't match
155			* # \|
156			* # \| Since there may not be an exact match we must set end=mid
157			* # <- mid \| or start=mid because we know that mid doesn't match.
158			* # \|
159			* # \| Eventually end=start+1 and the insertion point is before
160			* # <- end \| end (since it cannot be before the initial start or end).
161			*/
162
163	amb	45	if(end<start) /* There are no results */
164	amb	29	insert=start;
165	amb	45	else if(node<results->results[offsetsp[start]].node) /* Check key is not before start */
166	amb	29	insert=start;
167	amb	45	else if(node>results->results[offsetsp[end]].node) /* Check key is not after end */
168	amb	29	insert=end+1;
169			else
170			{
171			do
172			{
173	amb	45	mid=(start+end)/2; /* Choose mid point */
174	amb	29
175	amb	45	if(results->results[offsetsp[mid]].node<node) /* Mid point is too low */
176	amb	29	start=mid;
177	amb	45	else if(results->results[offsetsp[mid]].node>node) /* Mid point is too high */
178	amb	29	end=mid;
179			else
180			assert(0);
181			}
182			while((end-start)>1);
183
184			insert=end;
185			}
186
187			/* Shuffle the array up */
188
189	amb	45	#ifdef NBINS_RESULTS
190			if(insert!=results->numbin[bin])
191			memmove(&offsetsp[insert+1],&offsetsp[insert],(results->numbin[bin]-insert)*sizeof(uint32_t));
192			#else
193			if(insert!=results->number)
194			memmove(&offsetsp[insert+1],&offsetsp[insert],(results->number-insert)*sizeof(uint32_t));
195			#endif
196	amb	29
197			/* Insert the new entry */
198
199	amb	45	offsetsp[insert]=results->number;
200	amb	29
201	amb	45	results->number++;
202	amb	29
203	amb	45	#ifdef NBINS_RESULTS
204			results->numbin[bin]++;
205			#endif
206
207			return(&results->results[offsetsp[insert]]);
208	amb	29	}
209
210
211			/*++++++++++++++++++++++++++++++++++++++
212			Find a result, ordered by node.
213
214			Result *insert_result Returns the result that has been found.
215
216			Results *results The results structure to search.
217
218			node_t node The node that is to be found.
219			++++++++++++++++++++++++++++++++++++++*/
220
221			Result FindResult(Results results,node_t node)
222			{
223			#ifdef NBINS_RESULTS
224			int bin=node%NBINS_RESULTS;
225			int start=0;
226	amb	45	int end=results->numbin[bin]-1;
227			uint32_t *offsetsp=results->offsets[bin];
228	amb	29	#else
229			int start=0;
230			int end=results->number-1;
231	amb	45	uint32_t *offsetsp=results->offsets;
232	amb	29	#endif
233			int mid;
234
235			/* Binary search - search key exact match only is required.
236			*
237			* # <- start \| Check mid and move start or end if it doesn't match
238			* # \|
239			* # \| Since an exact match is wanted we can set end=mid-1
240			* # <- mid \| or start=mid+1 because we know that mid doesn't match.
241			* # \|
242			* # \| Eventually either end=start or end=start+1 and one of
243			* # <- end \| start or end is the wanted one.
244			*/
245
246	amb	45	if(end<start) /* There are no results */
247	amb	29	return(NULL);
248	amb	45	else if(node<results->results[offsetsp[start]].node) /* Check key is not before start */
249	amb	29	return(NULL);
250	amb	45	else if(node>results->results[offsetsp[end]].node) /* Check key is not after end */
251	amb	29	return(NULL);
252			else
253			{
254			do
255			{
256	amb	45	mid=(start+end)/2; /* Choose mid point */
257	amb	29
258	amb	45	if(results->results[offsetsp[mid]].node<node) /* Mid point is too low */
259	amb	29	start=mid+1;
260	amb	45	else if(results->results[offsetsp[mid]].node>node) /* Mid point is too high */
261	amb	29	end=mid-1;
262	amb	45	else /* Mid point is correct */
263			return(&results->results[offsetsp[mid]]);
264	amb	29	}
265			while((end-start)>1);
266
267	amb	45	if(results->results[offsetsp[start]].node==node) /* Start is correct */
268			return(&results->results[offsetsp[start]]);
269	amb	29
270	amb	45	if(results->results[offsetsp[end]].node==node) /* End is correct */
271			return(&results->results[offsetsp[end]]);
272	amb	29	}
273
274			return(NULL);
275			}
276	amb	67
277
278			/*++++++++++++++++++++++++++++++++++++++
279			Insert an item into the queue in the right order.
280
281			Results *results The set of results.
282
283			Result *result The result to insert into the queue.
284			++++++++++++++++++++++++++++++++++++++*/
285
286			void insert_in_queue(Results results,Result result)
287			{
288			int start=0;
289			int end=queue.number-1;
290			int mid;
291			int insert=-1;
292
293			/* Check that the whole thing is allocated. */
294
295			if(!queue.queue)
296			{
297			queue.alloced=QUEUE_INCREMENT;
298			queue.number=0;
299			queue.queue=(uint32_t)malloc(queue.allocedsizeof(uint32_t));
300			}
301
302			/* Check that the arrays have enough space. */
303
304			if(queue.number==queue.alloced)
305			{
306			queue.alloced+=QUEUE_INCREMENT;
307			queue.queue=(uint32_t)realloc((void)queue.queue,queue.alloced*sizeof(uint32_t));
308			}
309
310			/* Binary search - search key may not match, new insertion point required
311			*
312			* # <- start \| Check mid and move start or end if it doesn't match
313			* # \|
314			* # \| Since there may not be an exact match we must set end=mid
315			* # <- mid \| or start=mid because we know that mid doesn't match.
316			* # \|
317			* # \| Eventually end=start+1 and the insertion point is before
318			* # <- end \| end (since it cannot be before the initial start or end).
319			*/
320
321			if(queue.number==0) /* There is nothing in the queue */
322			insert=0;
323			else if(result->shortest.distance>results->results[queue.queue[start]].shortest.distance) /* Check key is not before start */
324			insert=start;
325			else if(result->shortest.distance<results->results[queue.queue[end]].shortest.distance) /* Check key is not after end */
326			insert=end+1;
327			else
328			{
329			do
330			{
331			mid=(start+end)/2; /* Choose mid point */
332
333			if(results->results[queue.queue[mid]].shortest.distance>result->shortest.distance) /* Mid point is too low */
334			start=mid;
335			else if(results->results[queue.queue[mid]].shortest.distance<result->shortest.distance) /* Mid point is too high */
336			end=mid;
337			else /* Mid point is correct */
338			{
339			if(&results->results[queue.queue[mid]]==result)
340			return;
341
342			insert=mid;
343			break;
344			}
345			}
346			while((end-start)>1);
347
348			if(insert==-1)
349			insert=end;
350			}
351
352			/* Shuffle the array up */
353
354			if(insert!=queue.number)
355			memmove(&queue.queue[insert+1],&queue.queue[insert],(queue.number-insert)*sizeof(uint32_t));
356
357			/* Insert the new entry */
358
359			queue.queue[insert]=result-results->results;
360
361			queue.number++;
362			}
363
364
365			/*++++++++++++++++++++++++++++++++++++++
366			Pop an item from the end of the queue.
367
368			Result *pop_from_queue Returns the top item.
369
370			Results *results The set of results that the queue is processing.
371			++++++++++++++++++++++++++++++++++++++*/
372
373			Result pop_from_queue(Results results)
374			{
375			if(queue.number)
376			return LookupResult(results,queue.queue[--queue.number]);
377			else
378			return NULL;
379			}