trunk/src/results.c

/***************************************
 $Header: /home/amb/CVS/routino/src/results.c,v 1.6 2009-01-30 19:57:09 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 RESULTS_INCREMENT   16
#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. +*/
 Result  **xqueue;              /*+ An array of pointers to parts of the results structure. +*/
}
 Queue;

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


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

  Results *NewResultsList Returns the results list.

  int nbins The number of bins in the results array.
  ++++++++++++++++++++++++++++++++++++++*/

Results *NewResultsList(int nbins)
{
 Results *results;
 int i;

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

 results->nbins=1;
 results->mask=~0;

 while(nbins>>=1)
   {
    results->mask<<=1;
    results->nbins<<=1;
   }

 results->mask=~results->mask;

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

 results->count=(uint32_t*)malloc(results->nbins*sizeof(uint32_t));
 results->point=(Result***)malloc(results->nbins*sizeof(Result**));

 for(i=0;i<results->nbins;i++)
   {
    results->count[i]=0;

    results->point[i]=(Result**)malloc(results->alloced*sizeof(Result*));
   }

 results->data=(Result**)malloc(1*sizeof(Result*));
 results->data[0]=(Result*)malloc(results->nbins*RESULTS_INCREMENT*sizeof(Result));

 return(results);
}


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

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

void FreeResultsList(Results *results)
{
 int c=(results->number-1)/(results->nbins*RESULTS_INCREMENT);
 int i;

 for(i=c;i>=0;i--)
    free(results->data[i]);

 free(results->data);

 for(i=0;i<results->nbins;i++)
    free(results->point[i]);

 free(results->point);

 free(results->count);

 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)
{
 int bin=node&results->mask;
 int start=0;
 int end=results->count[bin]-1;
 int i;
 int mid;
 int insert=-1;

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

 if(results->count[bin]==results->alloced)
   {
    results->alloced+=RESULTS_INCREMENT;

    for(i=0;i<results->nbins;i++)
       results->point[i]=(Result**)realloc((void*)results->point[i],results->alloced*sizeof(Result*));
   }

 if(results->number && (results->number%RESULTS_INCREMENT)==0 && (results->number%(RESULTS_INCREMENT*results->nbins))==0)
   {
    int c=results->number/(results->nbins*RESULTS_INCREMENT);

    results->data=(Result**)realloc((void*)results->data,(c+1)*sizeof(Result*));
    results->data[c]=(Result*)malloc(results->nbins*RESULTS_INCREMENT*sizeof(Result));
   }

 /* 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->point[bin][start]->node) /* Check key is not before start */
    insert=start;
 else if(node>results->point[bin][end]->node)   /* Check key is not after end */
    insert=end+1;
 else
   {
    do
      {
       mid=(start+end)/2;                           /* Choose mid point */

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

    insert=end;
   }

 /* Shuffle the array up */

 if(insert!=results->count[bin])
    memmove(&results->point[bin][insert+1],&results->point[bin][insert],(results->count[bin]-insert)*sizeof(Result*));

 /* Insert the new entry */

 results->point[bin][insert]=&results->data[results->number/(results->nbins*RESULTS_INCREMENT)][results->number%(results->nbins*RESULTS_INCREMENT)];

 results->number++;

 results->count[bin]++;

 return(results->point[bin][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)
{
 int bin=node&results->mask;
 int start=0;
 int end=results->count[bin]-1;
 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->point[bin][start]->node) /* Check key is not before start */
    return(NULL);
 else if(node>results->point[bin][end]->node)   /* Check key is not after end */
    return(NULL);
 else
   {
    do
      {
       mid=(start+end)/2;                           /* Choose mid point */

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

    if(results->point[bin][start]->node==node)      /* Start is correct */
       return(results->point[bin][start]);

    if(results->point[bin][end]->node==node)        /* End is correct */
       return(results->point[bin][end]);
   }

 return(NULL);
}


/*++++++++++++++++++++++++++++++++++++++
  Find a result from a set of results.

  Result *FirstResult Returns the first results from a set of results.

  Results *results The set of results.
  ++++++++++++++++++++++++++++++++++++++*/

Result *FirstResult(Results *results)
{
 return(&results->data[0][0]);
}


/*++++++++++++++++++++++++++++++++++++++
  Find a result from a set of results.

  Result *NextResult Returns the next result from a set of results.

  Results *results The set of results.

  Result *result The previous result.
  ++++++++++++++++++++++++++++++++++++++*/

Result *NextResult(Results *results,Result *result)
{
 int c=(results->number-1)/(results->nbins*RESULTS_INCREMENT);
 int i,j=0;

 for(i=0;i<=c;i++)
   {
    j=(result-results->data[i]);

    if(j>=0 && j<(results->nbins*RESULTS_INCREMENT))
       break;
   }

 if(++j>=(results->nbins*RESULTS_INCREMENT))
   {i++;j=0;}

 if((i*(results->nbins*RESULTS_INCREMENT)+j)>=results->number)
    return(NULL);

 return(&results->data[i][j]);
}


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

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

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

 /* Check that the array is allocated. */

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

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

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

 /* 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>queue.xqueue[start]->shortest.distance) /* Check key is not before start */
    insert=start;
 else if(result->shortest.distance<queue.xqueue[end]->shortest.distance)   /* Check key is not after end */
    insert=end+1;
 else
   {
    do
      {
       mid=(start+end)/2;                                                     /* Choose mid point */

       if(queue.xqueue[mid]->shortest.distance>result->shortest.distance)      /* Mid point is too low */
          start=mid;
       else if(queue.xqueue[mid]->shortest.distance<result->shortest.distance) /* Mid point is too high */
          end=mid;
       else                                                                   /* Mid point is correct */
         {
          if(queue.xqueue[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.xqueue[insert+1],&queue.xqueue[insert],(queue.number-insert)*sizeof(Result*));

 /* Insert the new entry */

 queue.xqueue[insert]=result;

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