trunk/src/results.c

/***************************************
 $Header: /home/amb/CVS/routino/src/results.c,v 1.20 2009-11-13 19:24:11 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 <sys/types.h>
#include <string.h>
#include <stdlib.h>

#include "results.h"

/*+ The size of the increment for the Results data structure. +*/
#define RESULTS_INCREMENT    16


/*++++++++++++++++++++++++++++++++++++++
  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;
 uint32_t 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 i,c=(results->number-1)/(results->nbins*RESULTS_INCREMENT);

 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 *InsertResult 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;
 uint32_t 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;
 results->point[bin][results->count[bin]-1]->queued=NOT_QUEUED;

 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 *FindResult 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 i,j=0,c=(results->number-1)/(results->nbins*RESULTS_INCREMENT);

 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]);
}
1	amb	29	/***************************************
2	amb	302	$Header: /home/amb/CVS/routino/src/results.c,v 1.20 2009-11-13 19:24:11 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	amb	214	#include <sys/types.h>
26	amb	29	#include <string.h>
27			#include <stdlib.h>
28
29			#include "results.h"
30
31	amb	228	/+ The size of the increment for the Results data structure. +/
32			#define RESULTS_INCREMENT 16
33	amb	29
34	amb	67
35	amb	29	/*++++++++++++++++++++++++++++++++++++++
36			Allocate a new results list.
37
38			Results *NewResultsList Returns the results list.
39	amb	71
40			int nbins The number of bins in the results array.
41	amb	29	++++++++++++++++++++++++++++++++++++++*/
42
43	amb	71	Results *NewResultsList(int nbins)
44	amb	29	{
45			Results *results;
46	amb	214	uint32_t i;
47	amb	29
48			results=(Results*)malloc(sizeof(Results));
49
50	amb	71	results->nbins=1;
51			results->mask=~0;
52
53			while(nbins>>=1)
54			{
55			results->mask<<=1;
56			results->nbins<<=1;
57			}
58
59			results->mask=~results->mask;
60
61			results->alloced=RESULTS_INCREMENT;
62	amb	45	results->number=0;
63	amb	29
64	amb	79	results->count=(uint32_t)malloc(results->nbinssizeof(uint32_t));
65			results->point=(Result**)malloc(results->nbinssizeof(Result**));
66	amb	71
67			for(i=0;i<results->nbins;i++)
68	amb	29	{
69	amb	79	results->count[i]=0;
70	amb	45
71	amb	79	results->point[i]=(Result*)malloc(results->allocedsizeof(Result*));
72	amb	29	}
73	amb	45
74	amb	79	results->data=(Result*)malloc(1sizeof(Result*));
75			results->data[0]=(Result)malloc(results->nbinsRESULTS_INCREMENT*sizeof(Result));
76	amb	45
77	amb	176	results->start=NO_NODE;
78			results->finish=NO_NODE;
79	amb	165
80	amb	29	return(results);
81			}
82
83
84			/*++++++++++++++++++++++++++++++++++++++
85			Allocate a new results list.
86
87			Results *results The results list to be destroyed.
88			++++++++++++++++++++++++++++++++++++++*/
89
90			void FreeResultsList(Results *results)
91			{
92	amb	214	int i,c=(results->number-1)/(results->nbins*RESULTS_INCREMENT);
93	amb	29
94	amb	79	for(i=c;i>=0;i--)
95			free(results->data[i]);
96	amb	71
97	amb	79	free(results->data);
98
99	amb	71	for(i=0;i<results->nbins;i++)
100	amb	79	free(results->point[i]);
101	amb	71
102	amb	79	free(results->point);
103	amb	29
104	amb	79	free(results->count);
105
106	amb	29	free(results);
107			}
108
109
110			/*++++++++++++++++++++++++++++++++++++++
111			Insert a new result into the results data structure in the right order.
112
113	amb	228	Result *InsertResult Returns the result that has been inserted.
114	amb	29
115			Results *results The results structure to insert into.
116
117	amb	116	index_t node The node that is to be inserted into the results.
118	amb	29	++++++++++++++++++++++++++++++++++++++*/
119
120	amb	116	Result InsertResult(Results results,index_t node)
121	amb	29	{
122	amb	71	int bin=node&results->mask;
123	amb	214	uint32_t i;
124	amb	29
125			/* Check that the arrays have enough space. */
126
127	amb	79	if(results->count[bin]==results->alloced)
128	amb	29	{
129	amb	71	results->alloced+=RESULTS_INCREMENT;
130	amb	29
131	amb	71	for(i=0;i<results->nbins;i++)
132	amb	79	results->point[i]=(Result*)realloc((void)results->point[i],results->allocedsizeof(Result));
133			}
134	amb	29
135	amb	79	if(results->number && (results->number%RESULTS_INCREMENT)==0 && (results->number%(RESULTS_INCREMENT*results->nbins))==0)
136			{
137			int c=results->number/(results->nbins*RESULTS_INCREMENT);
138
139			results->data=(Result*)realloc((void)results->data,(c+1)sizeof(Result));
140			results->data[c]=(Result)malloc(results->nbinsRESULTS_INCREMENT*sizeof(Result));
141	amb	45	}
142	amb	29
143			/* Insert the new entry */
144
145	amb	111	results->point[bin][results->count[bin]]=&results->data[results->number/(results->nbinsRESULTS_INCREMENT)][results->number%(results->nbinsRESULTS_INCREMENT)];
146	amb	29
147	amb	45	results->number++;
148	amb	29
149	amb	79	results->count[bin]++;
150	amb	45
151	amb	166	results->point[bin][results->count[bin]-1]->node=node;
152	amb	302	results->point[bin][results->count[bin]-1]->queued=NOT_QUEUED;
153	amb	166
154	amb	111	return(results->point[bin][results->count[bin]-1]);
155	amb	29	}
156
157
158			/*++++++++++++++++++++++++++++++++++++++
159	amb	166	Zero the values in a result structure.
160
161			Result *result The result to modify.
162			++++++++++++++++++++++++++++++++++++++*/
163
164			void ZeroResult(Result *result)
165			{
166	amb	176	result->prev=NO_NODE;
167			result->next=NO_NODE;
168	amb	166
169			result->score=0;
170	amb	170	result->sortby=0;
171	amb	166
172	amb	170	result->segment=NULL;
173	amb	166	}
174
175
176			/*++++++++++++++++++++++++++++++++++++++
177	amb	111	Find a result; search by node.
178	amb	29
179	amb	228	Result *FindResult Returns the result that has been found.
180	amb	29
181			Results *results The results structure to search.
182
183	amb	116	index_t node The node that is to be found.
184	amb	29	++++++++++++++++++++++++++++++++++++++*/
185
186	amb	116	Result FindResult(Results results,index_t node)
187	amb	29	{
188	amb	71	int bin=node&results->mask;
189	amb	111	int i;
190	amb	29
191	amb	111	for(i=results->count[bin]-1;i>=0;i--)
192			if(results->point[bin][i]->node==node)
193			return(results->point[bin][i]);
194	amb	29
195			return(NULL);
196			}
197	amb	67
198
199			/*++++++++++++++++++++++++++++++++++++++
200	amb	79	Find a result from a set of results.
201	amb	67
202	amb	79	Result *FirstResult Returns the first results from a set of results.
203
204	amb	67	Results *results The set of results.
205	amb	79	++++++++++++++++++++++++++++++++++++++*/
206	amb	67
207	amb	79	Result FirstResult(Results results)
208			{
209			return(&results->data[0][0]);
210			}
211
212
213			/*++++++++++++++++++++++++++++++++++++++
214			Find a result from a set of results.
215
216			Result *NextResult Returns the next result from a set of results.
217
218			Results *results The set of results.
219
220			Result *result The previous result.
221			++++++++++++++++++++++++++++++++++++++*/
222
223			Result NextResult(Results results,Result *result)
224			{
225	amb	214	int i,j=0,c=(results->number-1)/(results->nbins*RESULTS_INCREMENT);
226	amb	79
227			for(i=0;i<=c;i++)
228			{
229	amb	214	j=result-results->data[i];
230	amb	79
231			if(j>=0 && j<(results->nbins*RESULTS_INCREMENT))
232			break;
233			}
234
235			if(++j>=(results->nbins*RESULTS_INCREMENT))
236			{i++;j=0;}
237
238			if((i(results->nbinsRESULTS_INCREMENT)+j)>=results->number)
239			return(NULL);
240
241			return(&results->data[i][j]);
242			}