trunk/src/results.c

/***************************************
 $Header: /home/amb/CVS/routino/src/results.c,v 1.15 2009-07-02 16:33:31 amb Exp $

 Result data type functions.

 Part of the Routino routing software.
 ******************/ /******************
 This file Copyright 2008,2009 Andrew M. Bishop

 This program is free software: you can redistribute it and/or modify
 it under the terms of the GNU Affero General Public License as published by
 the Free Software Foundation, either version 3 of the License, or
 (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU Affero General Public License for more details.

 You should have received a copy of the GNU Affero General Public License
 along with this program.  If not, see <http://www.gnu.org/licenses/>.
 ***************************************/


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

#include "results.h"


#define RESULTS_INCREMENT    16
#define QUEUE_INCREMENT   10240


/*+ 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));

 results->start=NO_NODE;
 results->finish=NO_NODE;

 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.

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

Result *InsertResult(Results *results,index_t node)
{
 int bin=node&results->mask;
 int i;

 /* 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));
   }

 /* Insert the new entry */

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

 results->number++;

 results->count[bin]++;

 results->point[bin][results->count[bin]-1]->node=node;

 return(results->point[bin][results->count[bin]-1]);
}


/*++++++++++++++++++++++++++++++++++++++
  Zero the values in a result structure.

  Result *result The result to modify.
  ++++++++++++++++++++++++++++++++++++++*/

void ZeroResult(Result *result)
{
 result->prev=NO_NODE;
 result->next=NO_NODE;

 result->score=0;
 result->sortby=0;

 result->segment=NULL;
}


/*++++++++++++++++++++++++++++++++++++++
  Find a result; search by node.

  Result *insert_result Returns the result that has been found.

  Results *results The results structure to search.

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

Result *FindResult(Results *results,index_t node)
{
 int bin=node&results->mask;
 int i;

 for(i=results->count[bin]-1;i>=0;i--)
    if(results->point[bin][i]->node==node)
       return(results->point[bin][i]);

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

       if(queue.xqueue[mid]->sortby>result->sortby)      /* Mid point is too low */
          start=mid;
       else if(queue.xqueue[mid]->sortby<result->sortby) /* 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	amb	29	/***************************************
2	amb	213	$Header: /home/amb/CVS/routino/src/results.c,v 1.15 2009-07-02 16:33:31 amb Exp $
3	amb	29
4			Result data type functions.
5	amb	151
6			Part of the Routino routing software.
7	amb	29	****************/ /****************
8	amb	151	This file Copyright 2008,2009 Andrew M. Bishop
9	amb	29
10	amb	151	This program is free software: you can redistribute it and/or modify
11			it under the terms of the GNU Affero General Public License as published by
12			the Free Software Foundation, either version 3 of the License, or
13			(at your option) any later version.
14
15			This program is distributed in the hope that it will be useful,
16			but WITHOUT ANY WARRANTY; without even the implied warranty of
17			MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18			GNU Affero General Public License for more details.
19
20			You should have received a copy of the GNU Affero General Public License
21			along with this program. If not, see <http://www.gnu.org/licenses/>.
22	amb	29	***************************************/
23
24
25			#include <string.h>
26			#include <stdlib.h>
27
28			#include "results.h"
29
30
31	amb	116	#define RESULTS_INCREMENT 16
32			#define QUEUE_INCREMENT 10240
33	amb	67
34	amb	71
35	amb	67	/+ A queue of results. +/
36			typedef struct _Queue
37			{
38	amb	79	uint32_t alloced; /+ The amount of space allocated for results in the array. +/
39			uint32_t number; /+ The number of occupied results in the array. +/
40			Result *xqueue; /+ An array of pointers to parts of the results structure. +*/
41	amb	67	}
42			Queue;
43
44			/+ The queue of nodes. +/
45	amb	113	static Queue queue={0,0,NULL};
46	amb	67
47
48	amb	29	/*++++++++++++++++++++++++++++++++++++++
49			Allocate a new results list.
50
51			Results *NewResultsList Returns the results list.
52	amb	71
53			int nbins The number of bins in the results array.
54	amb	29	++++++++++++++++++++++++++++++++++++++*/
55
56	amb	71	Results *NewResultsList(int nbins)
57	amb	29	{
58			Results *results;
59			int i;
60
61			results=(Results*)malloc(sizeof(Results));
62
63	amb	71	results->nbins=1;
64			results->mask=~0;
65
66			while(nbins>>=1)
67			{
68			results->mask<<=1;
69			results->nbins<<=1;
70			}
71
72			results->mask=~results->mask;
73
74			results->alloced=RESULTS_INCREMENT;
75	amb	45	results->number=0;
76	amb	29
77	amb	79	results->count=(uint32_t)malloc(results->nbinssizeof(uint32_t));
78			results->point=(Result**)malloc(results->nbinssizeof(Result**));
79	amb	71
80			for(i=0;i<results->nbins;i++)
81	amb	29	{
82	amb	79	results->count[i]=0;
83	amb	45
84	amb	79	results->point[i]=(Result*)malloc(results->allocedsizeof(Result*));
85	amb	29	}
86	amb	45
87	amb	79	results->data=(Result*)malloc(1sizeof(Result*));
88			results->data[0]=(Result)malloc(results->nbinsRESULTS_INCREMENT*sizeof(Result));
89	amb	45
90	amb	176	results->start=NO_NODE;
91			results->finish=NO_NODE;
92	amb	165
93	amb	29	return(results);
94			}
95
96
97			/*++++++++++++++++++++++++++++++++++++++
98			Allocate a new results list.
99
100			Results *results The results list to be destroyed.
101			++++++++++++++++++++++++++++++++++++++*/
102
103			void FreeResultsList(Results *results)
104			{
105	amb	79	int c=(results->number-1)/(results->nbins*RESULTS_INCREMENT);
106	amb	29	int i;
107
108	amb	79	for(i=c;i>=0;i--)
109			free(results->data[i]);
110	amb	71
111	amb	79	free(results->data);
112
113	amb	71	for(i=0;i<results->nbins;i++)
114	amb	79	free(results->point[i]);
115	amb	71
116	amb	79	free(results->point);
117	amb	29
118	amb	79	free(results->count);
119
120	amb	29	free(results);
121			}
122
123
124			/*++++++++++++++++++++++++++++++++++++++
125			Insert a new result into the results data structure in the right order.
126
127			Result *insert_result Returns the result that has been inserted.
128
129			Results *results The results structure to insert into.
130
131	amb	116	index_t node The node that is to be inserted into the results.
132	amb	29	++++++++++++++++++++++++++++++++++++++*/
133
134	amb	116	Result InsertResult(Results results,index_t node)
135	amb	29	{
136	amb	71	int bin=node&results->mask;
137	amb	29	int i;
138
139			/* Check that the arrays have enough space. */
140
141	amb	79	if(results->count[bin]==results->alloced)
142	amb	29	{
143	amb	71	results->alloced+=RESULTS_INCREMENT;
144	amb	29
145	amb	71	for(i=0;i<results->nbins;i++)
146	amb	79	results->point[i]=(Result*)realloc((void)results->point[i],results->allocedsizeof(Result));
147			}
148	amb	29
149	amb	79	if(results->number && (results->number%RESULTS_INCREMENT)==0 && (results->number%(RESULTS_INCREMENT*results->nbins))==0)
150			{
151			int c=results->number/(results->nbins*RESULTS_INCREMENT);
152
153			results->data=(Result*)realloc((void)results->data,(c+1)sizeof(Result));
154			results->data[c]=(Result)malloc(results->nbinsRESULTS_INCREMENT*sizeof(Result));
155	amb	45	}
156	amb	29
157			/* Insert the new entry */
158
159	amb	111	results->point[bin][results->count[bin]]=&results->data[results->number/(results->nbinsRESULTS_INCREMENT)][results->number%(results->nbinsRESULTS_INCREMENT)];
160	amb	29
161	amb	45	results->number++;
162	amb	29
163	amb	79	results->count[bin]++;
164	amb	45
165	amb	166	results->point[bin][results->count[bin]-1]->node=node;
166
167	amb	111	return(results->point[bin][results->count[bin]-1]);
168	amb	29	}
169
170
171			/*++++++++++++++++++++++++++++++++++++++
172	amb	166	Zero the values in a result structure.
173
174			Result *result The result to modify.
175			++++++++++++++++++++++++++++++++++++++*/
176
177			void ZeroResult(Result *result)
178			{
179	amb	176	result->prev=NO_NODE;
180			result->next=NO_NODE;
181	amb	166
182			result->score=0;
183	amb	170	result->sortby=0;
184	amb	166
185	amb	170	result->segment=NULL;
186	amb	166	}
187
188
189			/*++++++++++++++++++++++++++++++++++++++
190	amb	111	Find a result; search by node.
191	amb	29
192			Result *insert_result Returns the result that has been found.
193
194			Results *results The results structure to search.
195
196	amb	116	index_t node The node that is to be found.
197	amb	29	++++++++++++++++++++++++++++++++++++++*/
198
199	amb	116	Result FindResult(Results results,index_t node)
200	amb	29	{
201	amb	71	int bin=node&results->mask;
202	amb	111	int i;
203	amb	29
204	amb	111	for(i=results->count[bin]-1;i>=0;i--)
205			if(results->point[bin][i]->node==node)
206			return(results->point[bin][i]);
207	amb	29
208			return(NULL);
209			}
210	amb	67
211
212			/*++++++++++++++++++++++++++++++++++++++
213	amb	79	Find a result from a set of results.
214	amb	67
215	amb	79	Result *FirstResult Returns the first results from a set of results.
216
217	amb	67	Results *results The set of results.
218	amb	79	++++++++++++++++++++++++++++++++++++++*/
219	amb	67
220	amb	79	Result FirstResult(Results results)
221			{
222			return(&results->data[0][0]);
223			}
224
225
226			/*++++++++++++++++++++++++++++++++++++++
227			Find a result from a set of results.
228
229			Result *NextResult Returns the next result from a set of results.
230
231			Results *results The set of results.
232
233			Result *result The previous result.
234			++++++++++++++++++++++++++++++++++++++*/
235
236			Result NextResult(Results results,Result *result)
237			{
238			int c=(results->number-1)/(results->nbins*RESULTS_INCREMENT);
239	amb	92	int i,j=0;
240	amb	79
241			for(i=0;i<=c;i++)
242			{
243			j=(result-results->data[i]);
244
245			if(j>=0 && j<(results->nbins*RESULTS_INCREMENT))
246			break;
247			}
248
249			if(++j>=(results->nbins*RESULTS_INCREMENT))
250			{i++;j=0;}
251
252			if((i(results->nbinsRESULTS_INCREMENT)+j)>=results->number)
253			return(NULL);
254
255			return(&results->data[i][j]);
256			}
257
258
259			/*++++++++++++++++++++++++++++++++++++++
260			Insert an item into the queue in the right order.
261
262	amb	67	Result *result The result to insert into the queue.
263			++++++++++++++++++++++++++++++++++++++*/
264
265	amb	79	void insert_in_queue(Result *result)
266	amb	67	{
267			int start=0;
268			int end=queue.number-1;
269			int mid;
270			int insert=-1;
271
272	amb	79	/* Check that the array is allocated. */
273	amb	67
274	amb	79	if(!queue.xqueue)
275	amb	67	{
276			queue.alloced=QUEUE_INCREMENT;
277			queue.number=0;
278	amb	79	queue.xqueue=(Result*)malloc(queue.allocedsizeof(Result*));
279	amb	67	}
280
281			/* Check that the arrays have enough space. */
282
283			if(queue.number==queue.alloced)
284			{
285			queue.alloced+=QUEUE_INCREMENT;
286	amb	79	queue.xqueue=(Result*)realloc((void)queue.xqueue,queue.allocedsizeof(Result));
287	amb	67	}
288
289			/* Binary search - search key may not match, new insertion point required
290			*
291			* # <- start \| Check mid and move start or end if it doesn't match
292			* # \|
293			* # \| Since there may not be an exact match we must set end=mid
294			* # <- mid \| or start=mid because we know that mid doesn't match.
295			* # \|
296			* # \| Eventually end=start+1 and the insertion point is before
297			* # <- end \| end (since it cannot be before the initial start or end).
298			*/
299
300	amb	116	if(queue.number==0) /* There is nothing in the queue */
301	amb	67	insert=0;
302	amb	116	else if(result->sortby>queue.xqueue[start]->sortby) /* Check key is not before start */
303	amb	67	insert=start;
304	amb	116	else if(result->sortby<queue.xqueue[end]->sortby) /* Check key is not after end */
305	amb	67	insert=end+1;
306	amb	116	else if(queue.number==2) /* Must be between them */
307			insert=1;
308	amb	67	else
309			{
310			do
311			{
312	amb	116	mid=(start+end)/2; /* Choose mid point */
313	amb	67
314	amb	116	if(queue.xqueue[mid]->sortby>result->sortby) /* Mid point is too low */
315	amb	67	start=mid;
316	amb	116	else if(queue.xqueue[mid]->sortby<result->sortby) /* Mid point is too high */
317	amb	67	end=mid;
318	amb	116	else /* Mid point is correct */
319	amb	67	{
320	amb	79	if(queue.xqueue[mid]==result)
321	amb	67	return;
322
323			insert=mid;
324			break;
325			}
326			}
327			while((end-start)>1);
328
329			if(insert==-1)
330			insert=end;
331			}
332
333			/* Shuffle the array up */
334
335			if(insert!=queue.number)
336	amb	79	memmove(&queue.xqueue[insert+1],&queue.xqueue[insert],(queue.number-insert)sizeof(Result));
337	amb	67
338			/* Insert the new entry */
339
340	amb	79	queue.xqueue[insert]=result;
341	amb	67
342			queue.number++;
343			}
344
345
346			/*++++++++++++++++++++++++++++++++++++++
347			Pop an item from the end of the queue.
348
349			Result *pop_from_queue Returns the top item.
350
351			Results *results The set of results that the queue is processing.
352			++++++++++++++++++++++++++++++++++++++*/
353
354	amb	79	Result *pop_from_queue()
355	amb	67	{
356			if(queue.number)
357	amb	79	return(queue.xqueue[--queue.number]);
358	amb	67	else
359	amb	79	return(NULL);
360	amb	67	}