trunk/src/results.c

/***************************************
 $Header: /home/amb/CVS/routino/src/results.c,v 1.2 2009-01-17 17:49:58 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"


/*++++++++++++++++++++++++++++++++++++++
  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);
}
1	amb	29	/***************************************
2	amb	45	$Header: /home/amb/CVS/routino/src/results.c,v 1.2 2009-01-17 17:49:58 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			/*++++++++++++++++++++++++++++++++++++++
23			Allocate a new results list.
24
25			Results *NewResultsList Returns the results list.
26			++++++++++++++++++++++++++++++++++++++*/
27
28			Results *NewResultsList(void)
29			{
30			Results *results;
31			#if NBINS_RESULTS
32			int i;
33			#endif
34
35			results=(Results*)malloc(sizeof(Results));
36
37			results->alloced=INCREMENT_RESULTS;
38	amb	45	results->number=0;
39	amb	29
40			#if NBINS_RESULTS
41			for(i=0;i<NBINS_RESULTS;i++)
42			{
43	amb	45	results->numbin[i]=0;
44
45			results->offsets[i]=(uint32_t)malloc(results->allocedsizeof(uint32_t));
46	amb	29	}
47	amb	45
48			results->results=(Result)malloc(results->allocedNBINS_RESULTS*sizeof(Result));
49	amb	29	#else
50	amb	45	results->offsets=(uint32_t)malloc(results->allocedsizeof(uint32_t));
51
52			results->data=(Result)malloc(results->allocedsizeof(Result));
53	amb	29	#endif
54
55			return(results);
56			}
57
58
59			/*++++++++++++++++++++++++++++++++++++++
60			Allocate a new results list.
61
62			Results *results The results list to be destroyed.
63			++++++++++++++++++++++++++++++++++++++*/
64
65			void FreeResultsList(Results *results)
66			{
67			#if NBINS_RESULTS
68			int i;
69			#endif
70
71			#if NBINS_RESULTS
72			for(i=0;i<NBINS_RESULTS;i++)
73	amb	45	free(results->offsets[i]);
74	amb	29	#else
75	amb	45	free(results->offsets);
76	amb	29	#endif
77
78	amb	45	free(results->results);
79
80	amb	29	free(results);
81			}
82
83
84			/*++++++++++++++++++++++++++++++++++++++
85			Insert a new result into the results data structure in the right order.
86
87			Result *insert_result Returns the result that has been inserted.
88
89			Results *results The results structure to insert into.
90
91			node_t node The node that is to be inserted into the results.
92			++++++++++++++++++++++++++++++++++++++*/
93
94			Result InsertResult(Results results,node_t node)
95			{
96			#ifdef NBINS_RESULTS
97			int bin=node%NBINS_RESULTS;
98			int start=0;
99	amb	45	int end=results->numbin[bin]-1;
100			uint32_t *offsetsp=results->offsets[bin];
101	amb	29	int i;
102			#else
103			int start=0;
104			int end=results->number-1;
105	amb	45	uint32_t *offsetsp=results->offsets;
106	amb	29	#endif
107			int mid;
108			int insert=-1;
109
110			/* Check that the arrays have enough space. */
111
112	amb	45	#ifdef NBINS_RESULTS
113			if(results->numbin[bin]==results->alloced)
114	amb	29	{
115			results->alloced+=INCREMENT_RESULTS;
116
117			for(i=0;i<NBINS_RESULTS;i++)
118	amb	45	results->offsets[i]=(uint32_t)realloc((void)results->offsets[i],results->alloced*sizeof(uint32_t));
119	amb	29
120	amb	45	offsetsp=results->offsets[bin];
121
122			results->results=(Result)realloc((void)results->results,results->allocedNBINS_RESULTSsizeof(Result));
123			}
124	amb	29	#else
125	amb	45	if(results->number==results->alloced)
126			{
127			results->alloced+=INCREMENT_RESULTS;
128	amb	29
129	amb	45	results->offsets=(uint32_t)realloc((void)results->offsets[i],results->alloced*sizeof(uint32_t));
130
131			offsetsp=results->offsets;
132
133			results->results=(Result)realloc((void)results->results,results->alloced*sizeof(Result));
134			}
135	amb	29	#endif
136
137			/* Binary search - search key may not match, if not then insertion point required
138			*
139			* # <- start \| Check mid and move start or end if it doesn't match
140			* # \|
141			* # \| Since there may not be an exact match we must set end=mid
142			* # <- mid \| or start=mid because we know that mid doesn't match.
143			* # \|
144			* # \| Eventually end=start+1 and the insertion point is before
145			* # <- end \| end (since it cannot be before the initial start or end).
146			*/
147
148	amb	45	if(end<start) /* There are no results */
149	amb	29	insert=start;
150	amb	45	else if(node<results->results[offsetsp[start]].node) /* Check key is not before start */
151	amb	29	insert=start;
152	amb	45	else if(node>results->results[offsetsp[end]].node) /* Check key is not after end */
153	amb	29	insert=end+1;
154			else
155			{
156			do
157			{
158	amb	45	mid=(start+end)/2; /* Choose mid point */
159	amb	29
160	amb	45	if(results->results[offsetsp[mid]].node<node) /* Mid point is too low */
161	amb	29	start=mid;
162	amb	45	else if(results->results[offsetsp[mid]].node>node) /* Mid point is too high */
163	amb	29	end=mid;
164			else
165			assert(0);
166			}
167			while((end-start)>1);
168
169			insert=end;
170			}
171
172			/* Shuffle the array up */
173
174	amb	45	#ifdef NBINS_RESULTS
175			if(insert!=results->numbin[bin])
176			memmove(&offsetsp[insert+1],&offsetsp[insert],(results->numbin[bin]-insert)*sizeof(uint32_t));
177			#else
178			if(insert!=results->number)
179			memmove(&offsetsp[insert+1],&offsetsp[insert],(results->number-insert)*sizeof(uint32_t));
180			#endif
181	amb	29
182			/* Insert the new entry */
183
184	amb	45	offsetsp[insert]=results->number;
185	amb	29
186	amb	45	results->number++;
187	amb	29
188	amb	45	#ifdef NBINS_RESULTS
189			results->numbin[bin]++;
190			#endif
191
192			return(&results->results[offsetsp[insert]]);
193	amb	29	}
194
195
196			/*++++++++++++++++++++++++++++++++++++++
197			Find a result, ordered by node.
198
199			Result *insert_result Returns the result that has been found.
200
201			Results *results The results structure to search.
202
203			node_t node The node that is to be found.
204			++++++++++++++++++++++++++++++++++++++*/
205
206			Result FindResult(Results results,node_t node)
207			{
208			#ifdef NBINS_RESULTS
209			int bin=node%NBINS_RESULTS;
210			int start=0;
211	amb	45	int end=results->numbin[bin]-1;
212			uint32_t *offsetsp=results->offsets[bin];
213	amb	29	#else
214			int start=0;
215			int end=results->number-1;
216	amb	45	uint32_t *offsetsp=results->offsets;
217	amb	29	#endif
218			int mid;
219
220			/* Binary search - search key exact match only is required.
221			*
222			* # <- start \| Check mid and move start or end if it doesn't match
223			* # \|
224			* # \| Since an exact match is wanted we can set end=mid-1
225			* # <- mid \| or start=mid+1 because we know that mid doesn't match.
226			* # \|
227			* # \| Eventually either end=start or end=start+1 and one of
228			* # <- end \| start or end is the wanted one.
229			*/
230
231	amb	45	if(end<start) /* There are no results */
232	amb	29	return(NULL);
233	amb	45	else if(node<results->results[offsetsp[start]].node) /* Check key is not before start */
234	amb	29	return(NULL);
235	amb	45	else if(node>results->results[offsetsp[end]].node) /* Check key is not after end */
236	amb	29	return(NULL);
237			else
238			{
239			do
240			{
241	amb	45	mid=(start+end)/2; /* Choose mid point */
242	amb	29
243	amb	45	if(results->results[offsetsp[mid]].node<node) /* Mid point is too low */
244	amb	29	start=mid+1;
245	amb	45	else if(results->results[offsetsp[mid]].node>node) /* Mid point is too high */
246	amb	29	end=mid-1;
247	amb	45	else /* Mid point is correct */
248			return(&results->results[offsetsp[mid]]);
249	amb	29	}
250			while((end-start)>1);
251
252	amb	45	if(results->results[offsetsp[start]].node==node) /* Start is correct */
253			return(&results->results[offsetsp[start]]);
254	amb	29
255	amb	45	if(results->results[offsetsp[end]].node==node) /* End is correct */
256			return(&results->results[offsetsp[end]]);
257	amb	29	}
258
259			return(NULL);
260			}