trunk/src/prunex.c

/***************************************
 Data pruning functions.

 Part of the Routino routing software.
 ******************/ /******************
 This file Copyright 2011-2012 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 <stdlib.h>
#include <assert.h>

#include "typesx.h"
#include "nodesx.h"
#include "segmentsx.h"
#include "waysx.h"

#include "prunex.h"

#include "files.h"
#include "logging.h"


/* Local functions */

static void prune_segment(SegmentsX *segmentsx,SegmentX *segmentx);
static void modify_segment(SegmentsX *segmentsx,SegmentX *segmentx,index_t newnode1,index_t newnode2);

static void unlink_segment_node_refs(SegmentsX *segmentsx,SegmentX *segmentx,index_t node);


/*++++++++++++++++++++++++++++++++++++++
  Initialise the data structures needed for pruning.

  NodesX *nodesx The set of nodes to use.

  SegmentsX *segmentsx The set of segments to use.

  WaysX *waysx The set of ways to use.
  ++++++++++++++++++++++++++++++++++++++*/

void StartPruning(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx)
{
 SegmentX segmentx;
 index_t index=0,lastnode1=NO_NODE;

 /* Print the start message */

 printf_first("Adding Extra Segment Indexes: Segments=0");

 /* Allocate the array of next segment */

 segmentsx->next1=(index_t*)calloc(segmentsx->number,sizeof(index_t));

 assert(segmentsx->next1); /* Check malloc() worked */

 /* Open the file read-only */

 segmentsx->fd=ReOpenFile(segmentsx->filename);

 /* Read the on-disk image */

 while(!ReadFile(segmentsx->fd,&segmentx,sizeof(SegmentX)))
   {
    index_t node1=segmentx.node1;

    if(index==0)
       ;
    else if(lastnode1==node1)
       segmentsx->next1[index-1]=index;
    else
       segmentsx->next1[index-1]=NO_SEGMENT;

    lastnode1=node1;
    index++;

    if(!(index%10000))
       printf_middle("Added Extra Segment Indexes: Segments=%"Pindex_t,index);
   }

 segmentsx->next1[index-1]=NO_SEGMENT;

 /* Close the file */

 segmentsx->fd=CloseFile(segmentsx->fd);

 /* Print the final message */

 printf_last("Added Extra Segment Indexes: Segments=%"Pindex_t,segmentsx->number);
}


/*++++++++++++++++++++++++++++++++++++++
  Delete the data structures needed for pruning.

  NodesX *nodesx The set of nodes to use.

  SegmentsX *segmentsx The set of segments to use.

  WaysX *waysx The set of ways to use.
  ++++++++++++++++++++++++++++++++++++++*/

void FinishPruning(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx)
{
 index_t i,pruned=0;
 int fd;


 /* Delete the pruned segments */

 free(segmentsx->next1);
 segmentsx->next1=NULL;

 SortSegmentList(segmentsx,1);

 IndexSegments(segmentsx,nodesx);


 /* Delete the pruned nodes */

 printf_first("Marking Pruned Nodes: Nodes=0 Pruned=0");

 /* Re-open the file read-only and a new file writeable */

 nodesx->fd=ReOpenFile(nodesx->filename);

 DeleteFile(nodesx->filename);

 fd=OpenFileNew(nodesx->filename);

 /* Modify the on-disk image */

 for(i=0;i<nodesx->number;i++)
   {
    NodeX nodex;

    ReadFile(nodesx->fd,&nodex,sizeof(NodeX));

    if(segmentsx->firstnode[i]==NO_SEGMENT)
      {
       pruned++;
       nodex.latitude=NO_LATLONG;
       nodex.longitude=NO_LATLONG;
      }

    WriteFile(fd,&nodex,sizeof(NodeX));

    if(!((i+1)%10000))
       printf_middle("Marking Pruned Nodes: Nodes=%"Pindex_t" Pruned=%"Pindex_t,i+1,pruned);
   }

 /* Close the files */

 nodesx->fd=CloseFile(nodesx->fd);
 CloseFile(fd);

 /* Print the final message */

 printf_last("Marked Pruned Nodes: Nodes=%"Pindex_t" Pruned=%"Pindex_t,nodesx->number,pruned);
}


/*++++++++++++++++++++++++++++++++++++++
  Prune out any groups of nodes and segments whose total length is less than a
  specified minimum.

  NodesX *nodesx The set of nodes to use.

  SegmentsX *segmentsx The set of segments to use.

  WaysX *waysx The set of ways to use.

  distance_t minimum The minimum distance to keep.
  ++++++++++++++++++++++++++++++++++++++*/

void PruneIsolatedRegions(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,distance_t minimum)
{
 index_t i,j;
 index_t nregions=0,npruned=0;
 BitMask *connected,*region;
 index_t *regionsegments,*othersegments;
 int nallocregionsegments,nallocothersegments;

 if(nodesx->number==0 || segmentsx->number==0)
    return;

 /* Print the start message */

 printf_first("Pruning Isolated Regions: Segments=0 Pruned=0");

 /* Map into memory / open the files */

#if !SLIM
 nodesx->data=MapFileWriteable(nodesx->filename);
 segmentsx->data=MapFileWriteable(segmentsx->filename);
 waysx->data=MapFile(waysx->filename);
#else
 nodesx->fd=ReOpenFileWriteable(nodesx->filename);
 segmentsx->fd=ReOpenFileWriteable(segmentsx->filename);
 waysx->fd=ReOpenFile(waysx->filename);
#endif

 connected=AllocBitMask(segmentsx->number);
 region   =AllocBitMask(segmentsx->number);

 assert(connected); /* Check AllocBitMask() worked */
 assert(region);    /* Check AllocBitMask() worked */

 regionsegments=(index_t*)malloc((nallocregionsegments=1024)*sizeof(index_t));
 othersegments =(index_t*)malloc((nallocothersegments =1024)*sizeof(index_t));

 assert(regionsegments); /* Check malloc() worked */
 assert(othersegments);  /* Check malloc() worked */

 /* Loop through the segments and find the disconnected ones */

 for(i=0;i<segmentsx->number;i++)
   {
    if(!IsBitSet(connected,i))
      {
       int nregionsegments=0,nothersegments=0;
       distance_t total=0;

       othersegments[nothersegments++]=i;
       SetBit(region,i);

       do
         {
          SegmentX *segmentx;
          index_t thissegment,nodes[2];
          WayX *wayx;

          thissegment=othersegments[--nothersegments];

          if(nregionsegments==nallocregionsegments)
             regionsegments=(index_t*)realloc(regionsegments,(nallocregionsegments+=1024)*sizeof(index_t));

          regionsegments[nregionsegments++]=thissegment;

          segmentx=LookupSegmentX(segmentsx,thissegment,1);

          nodes[0]=segmentx->node1;
          nodes[1]=segmentx->node2;
          total+=DISTANCE(segmentx->distance);

          wayx=LookupWayX(waysx,segmentx->way,1);

          for(j=0;j<2;j++)
            {
             NodeX *nodex=LookupNodeX(nodesx,nodes[j],1);

             if(!(nodex->allow&wayx->way.allow)) /* some type of traffic must be allowed */
                continue;

             segmentx=FirstSegmentX(segmentsx,nodes[j],1);

             while(segmentx)
               {
                index_t segment=IndexSegmentX(segmentsx,segmentx);

                if(segment!=thissegment)
                  {
                   WayX *way2x=LookupWayX(waysx,segmentx->way,2);

                   if(wayx->way.allow&way2x->way.allow) /* some type of traffic must be allowed */
                     {
                      /* Already connected - finish */

                      if(IsBitSet(connected,segment))
                        {
                         total=minimum;
                         goto foundconnection;
                        }

                      /* Not in region - add to list */

                      if(!IsBitSet(region,segment))
                        {
                         if(nothersegments==nallocothersegments)
                            othersegments=(index_t*)realloc(othersegments,(nallocothersegments+=1024)*sizeof(index_t));

                         othersegments[nothersegments++]=segment;
                         SetBit(region,segment);
                        }
                     }
                  }

                segmentx=NextSegmentX(segmentsx,segmentx,nodes[j]);
               }
            }
         }
       while(nothersegments>0 && total<minimum);

      foundconnection:

       /* Prune the segments or mark them as connected */

       if(total<minimum)
         {
          nregions++;

          for(j=0;j<nregionsegments;j++)
            {
             SegmentX *segmentx=LookupSegmentX(segmentsx,regionsegments[j],1);

             SetBit(connected,regionsegments[j]);

             prune_segment(segmentsx,segmentx);

             npruned++;
            }
         }
       else
         {
          for(j=0;j<nregionsegments;j++)
            {
             SetBit(connected,regionsegments[j]);
             ClearBit(region,regionsegments[j]);
            }

          for(j=0;j<nothersegments;j++)
            {
             SetBit(connected,othersegments[j]);
             ClearBit(region,othersegments[j]);
            }
         }
      }

    if(!((i+1)%10000))
       printf_middle("Pruning Isolated Regions: Segments=%"Pindex_t" Pruned=%"Pindex_t" (%"Pindex_t" Regions)",i+1,npruned,nregions);
   }

 /* Unmap from memory / close the files */

 free(region);
 free(connected);

 free(regionsegments);
 free(othersegments);

#if !SLIM
 nodesx->data=UnmapFile(nodesx->filename);
 segmentsx->data=UnmapFile(segmentsx->filename);
 waysx->data=UnmapFile(waysx->filename);
#else
 nodesx->fd=CloseFile(nodesx->fd);
 segmentsx->fd=CloseFile(segmentsx->fd);
 waysx->fd=CloseFile(waysx->fd);
#endif

 /* Print the final message */

 printf_last("Pruned Isolated Regions: Segments=%"Pindex_t" Pruned=%"Pindex_t" (%"Pindex_t" Regions)",segmentsx->number,npruned,nregions);
}


/*++++++++++++++++++++++++++++++++++++++
  Prune a segment; unused nodes and ways will get marked for pruning later.

  SegmentsX *segmentsx The set of segments to use.

  SegmentX *segmentx The segment to be pruned.
  ++++++++++++++++++++++++++++++++++++++*/

static void prune_segment(SegmentsX *segmentsx,SegmentX *segmentx)
{
 unlink_segment_node_refs(segmentsx,segmentx,segmentx->node1);
 unlink_segment_node_refs(segmentsx,segmentx,segmentx->node2);

 segmentx->node1=NO_NODE;
 segmentx->node2=NO_NODE;
 segmentx->next2=NO_SEGMENT;

 PutBackSegmentX(segmentsx,segmentx);
}


/*++++++++++++++++++++++++++++++++++++++
  Modify a segment's nodes; unused nodes will get marked for pruning later.

  SegmentsX *segmentsx The set of segments to use.

  SegmentX *segmentx The segment to be modified.

  index_t newnode1 The new value of node1.

  index_t newnode2 The new value of node2.
  ++++++++++++++++++++++++++++++++++++++*/

static void modify_segment(SegmentsX *segmentsx,SegmentX *segmentx,index_t newnode1,index_t newnode2)
{
 index_t thissegment=IndexSegmentX(segmentsx,segmentx);

 if(newnode1!=segmentx->node1)
   {
    unlink_segment_node_refs(segmentsx,segmentx,segmentx->node1);

    segmentx->node1=newnode1;

    segmentsx->next1[thissegment]=segmentsx->firstnode[newnode1];
    segmentsx->firstnode[newnode1]=thissegment;
   }

 if(newnode1!=segmentx->node1)
   {
    unlink_segment_node_refs(segmentsx,segmentx,segmentx->node2);

    segmentx->node2=newnode2;

    segmentx->next2=segmentsx->firstnode[newnode2];
    segmentsx->firstnode[newnode2]=thissegment;
   }

 PutBackSegmentX(segmentsx,segmentx);
}


/*++++++++++++++++++++++++++++++++++++++
  Unlink one node from a segment by modifying the linked list type arrangement of node references.

  SegmentsX *segmentsx The set of segments to use.

  SegmentX *segmentx The segment to be pruned.

  index_t node The node index of the end of the segment being modified here.
  ++++++++++++++++++++++++++++++++++++++*/

static void unlink_segment_node_refs(SegmentsX *segmentsx,SegmentX *segmentx,index_t node)
{
 index_t thissegment=IndexSegmentX(segmentsx,segmentx);
 index_t segment=segmentsx->firstnode[node];

 if(segment==NO_SEGMENT)
    return;

 if(segment==thissegment)
   {
    if(segmentx->node1==node)
       segmentsx->firstnode[node]=segmentsx->next1[thissegment];
    else
       segmentsx->firstnode[node]=segmentx->next2;
   }
 else
   {
    index_t nextsegment;

    do
      {
       SegmentX *segx=LookupSegmentX(segmentsx,segment,2);

       if(segx->node1==node)
         {
          nextsegment=segmentsx->next1[segment];

          if(thissegment==nextsegment)
            {
             if(segmentx->node1==node)
                segmentsx->next1[segment]=segmentsx->next1[thissegment];
             else
                segmentsx->next1[segment]=segmentx->next2;
            }
         }
       else
         {
          nextsegment=segx->next2;

          if(thissegment==nextsegment)
            {
             if(segmentx->node1==node)
                segx->next2=segmentsx->next1[thissegment];
             else
                segx->next2=segmentx->next2;

             PutBackSegmentX(segmentsx,segx);
            }
         }

       segment=nextsegment;
      }
    while(segment!=thissegment && segment!=NO_SEGMENT);
   }
}
1	/***************************************
2	Data pruning functions.
3
4	Part of the Routino routing software.
5	****************/ /****************
6	This file Copyright 2011-2012 Andrew M. Bishop
7
8	This program is free software: you can redistribute it and/or modify
9	it under the terms of the GNU Affero General Public License as published by
10	the Free Software Foundation, either version 3 of the License, or
11	(at your option) any later version.
12
13	This program is distributed in the hope that it will be useful,
14	but WITHOUT ANY WARRANTY; without even the implied warranty of
15	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16	GNU Affero General Public License for more details.
17
18	You should have received a copy of the GNU Affero General Public License
19	along with this program. If not, see <http://www.gnu.org/licenses/>.
20	***************************************/
21
22
23	#include <stdlib.h>
24	#include <assert.h>
25
26	#include "typesx.h"
27	#include "nodesx.h"
28	#include "segmentsx.h"
29	#include "waysx.h"
30
31	#include "prunex.h"
32
33	#include "files.h"
34	#include "logging.h"
35
36
37	/* Local functions */
38
39	static void prune_segment(SegmentsX segmentsx,SegmentX segmentx);
40	static void modify_segment(SegmentsX segmentsx,SegmentX segmentx,index_t newnode1,index_t newnode2);
41
42	static void unlink_segment_node_refs(SegmentsX segmentsx,SegmentX segmentx,index_t node);
43
44
45	/*++++++++++++++++++++++++++++++++++++++
46	Initialise the data structures needed for pruning.
47
48	NodesX *nodesx The set of nodes to use.
49
50	SegmentsX *segmentsx The set of segments to use.
51
52	WaysX *waysx The set of ways to use.
53	++++++++++++++++++++++++++++++++++++++*/
54
55	void StartPruning(NodesX nodesx,SegmentsX segmentsx,WaysX *waysx)
56	{
57	SegmentX segmentx;
58	index_t index=0,lastnode1=NO_NODE;
59
60	/* Print the start message */
61
62	printf_first("Adding Extra Segment Indexes: Segments=0");
63
64	/* Allocate the array of next segment */
65
66	segmentsx->next1=(index_t*)calloc(segmentsx->number,sizeof(index_t));
67
68	assert(segmentsx->next1); /* Check malloc() worked */
69
70	/* Open the file read-only */
71
72	segmentsx->fd=ReOpenFile(segmentsx->filename);
73
74	/* Read the on-disk image */
75
76	while(!ReadFile(segmentsx->fd,&segmentx,sizeof(SegmentX)))
77	{
78	index_t node1=segmentx.node1;
79
80	if(index==0)
81	;
82	else if(lastnode1==node1)
83	segmentsx->next1[index-1]=index;
84	else
85	segmentsx->next1[index-1]=NO_SEGMENT;
86
87	lastnode1=node1;
88	index++;
89
90	if(!(index%10000))
91	printf_middle("Added Extra Segment Indexes: Segments=%"Pindex_t,index);
92	}
93
94	segmentsx->next1[index-1]=NO_SEGMENT;
95
96	/* Close the file */
97
98	segmentsx->fd=CloseFile(segmentsx->fd);
99
100	/* Print the final message */
101
102	printf_last("Added Extra Segment Indexes: Segments=%"Pindex_t,segmentsx->number);
103	}
104
105
106	/*++++++++++++++++++++++++++++++++++++++
107	Delete the data structures needed for pruning.
108
109	NodesX *nodesx The set of nodes to use.
110
111	SegmentsX *segmentsx The set of segments to use.
112
113	WaysX *waysx The set of ways to use.
114	++++++++++++++++++++++++++++++++++++++*/
115
116	void FinishPruning(NodesX nodesx,SegmentsX segmentsx,WaysX *waysx)
117	{
118	index_t i,pruned=0;
119	int fd;
120
121
122	/* Delete the pruned segments */
123
124	free(segmentsx->next1);
125	segmentsx->next1=NULL;
126
127	SortSegmentList(segmentsx,1);
128
129	IndexSegments(segmentsx,nodesx);
130
131
132	/* Delete the pruned nodes */
133
134	printf_first("Marking Pruned Nodes: Nodes=0 Pruned=0");
135
136	/* Re-open the file read-only and a new file writeable */
137
138	nodesx->fd=ReOpenFile(nodesx->filename);
139
140	DeleteFile(nodesx->filename);
141
142	fd=OpenFileNew(nodesx->filename);
143
144	/* Modify the on-disk image */
145
146	for(i=0;i<nodesx->number;i++)
147	{
148	NodeX nodex;
149
150	ReadFile(nodesx->fd,&nodex,sizeof(NodeX));
151
152	if(segmentsx->firstnode[i]==NO_SEGMENT)
153	{
154	pruned++;
155	nodex.latitude=NO_LATLONG;
156	nodex.longitude=NO_LATLONG;
157	}
158
159	WriteFile(fd,&nodex,sizeof(NodeX));
160
161	if(!((i+1)%10000))
162	printf_middle("Marking Pruned Nodes: Nodes=%"Pindex_t" Pruned=%"Pindex_t,i+1,pruned);
163	}
164
165	/* Close the files */
166
167	nodesx->fd=CloseFile(nodesx->fd);
168	CloseFile(fd);
169
170	/* Print the final message */
171
172	printf_last("Marked Pruned Nodes: Nodes=%"Pindex_t" Pruned=%"Pindex_t,nodesx->number,pruned);
173	}
174
175
176	/*++++++++++++++++++++++++++++++++++++++
177	Prune out any groups of nodes and segments whose total length is less than a
178	specified minimum.
179
180	NodesX *nodesx The set of nodes to use.
181
182	SegmentsX *segmentsx The set of segments to use.
183
184	WaysX *waysx The set of ways to use.
185
186	distance_t minimum The minimum distance to keep.
187	++++++++++++++++++++++++++++++++++++++*/
188
189	void PruneIsolatedRegions(NodesX nodesx,SegmentsX segmentsx,WaysX *waysx,distance_t minimum)
190	{
191	index_t i,j;
192	index_t nregions=0,npruned=0;
193	BitMask connected,region;
194	index_t regionsegments,othersegments;
195	int nallocregionsegments,nallocothersegments;
196
197	if(nodesx->number==0 \|\| segmentsx->number==0)
198	return;
199
200	/* Print the start message */
201
202	printf_first("Pruning Isolated Regions: Segments=0 Pruned=0");
203
204	/* Map into memory / open the files */
205
206	#if !SLIM
207	nodesx->data=MapFileWriteable(nodesx->filename);
208	segmentsx->data=MapFileWriteable(segmentsx->filename);
209	waysx->data=MapFile(waysx->filename);
210	#else
211	nodesx->fd=ReOpenFileWriteable(nodesx->filename);
212	segmentsx->fd=ReOpenFileWriteable(segmentsx->filename);
213	waysx->fd=ReOpenFile(waysx->filename);
214	#endif
215
216	connected=AllocBitMask(segmentsx->number);
217	region =AllocBitMask(segmentsx->number);
218
219	assert(connected); /* Check AllocBitMask() worked */
220	assert(region); /* Check AllocBitMask() worked */
221
222	regionsegments=(index_t)malloc((nallocregionsegments=1024)sizeof(index_t));
223	othersegments =(index_t)malloc((nallocothersegments =1024)sizeof(index_t));
224
225	assert(regionsegments); /* Check malloc() worked */
226	assert(othersegments); /* Check malloc() worked */
227
228	/* Loop through the segments and find the disconnected ones */
229
230	for(i=0;i<segmentsx->number;i++)
231	{
232	if(!IsBitSet(connected,i))
233	{
234	int nregionsegments=0,nothersegments=0;
235	distance_t total=0;
236
237	othersegments[nothersegments++]=i;
238	SetBit(region,i);
239
240	do
241	{
242	SegmentX *segmentx;
243	index_t thissegment,nodes[2];
244	WayX *wayx;
245
246	thissegment=othersegments[--nothersegments];
247
248	if(nregionsegments==nallocregionsegments)
249	regionsegments=(index_t)realloc(regionsegments,(nallocregionsegments+=1024)sizeof(index_t));
250
251	regionsegments[nregionsegments++]=thissegment;
252
253	segmentx=LookupSegmentX(segmentsx,thissegment,1);
254
255	nodes[0]=segmentx->node1;
256	nodes[1]=segmentx->node2;
257	total+=DISTANCE(segmentx->distance);
258
259	wayx=LookupWayX(waysx,segmentx->way,1);
260
261	for(j=0;j<2;j++)
262	{
263	NodeX *nodex=LookupNodeX(nodesx,nodes[j],1);
264
265	if(!(nodex->allow&wayx->way.allow)) /* some type of traffic must be allowed */
266	continue;
267
268	segmentx=FirstSegmentX(segmentsx,nodes[j],1);
269
270	while(segmentx)
271	{
272	index_t segment=IndexSegmentX(segmentsx,segmentx);
273
274	if(segment!=thissegment)
275	{
276	WayX *way2x=LookupWayX(waysx,segmentx->way,2);
277
278	if(wayx->way.allow&way2x->way.allow) /* some type of traffic must be allowed */
279	{
280	/* Already connected - finish */
281
282	if(IsBitSet(connected,segment))
283	{
284	total=minimum;
285	goto foundconnection;
286	}
287
288	/* Not in region - add to list */
289
290	if(!IsBitSet(region,segment))
291	{
292	if(nothersegments==nallocothersegments)
293	othersegments=(index_t)realloc(othersegments,(nallocothersegments+=1024)sizeof(index_t));
294
295	othersegments[nothersegments++]=segment;
296	SetBit(region,segment);
297	}
298	}
299	}
300
301	segmentx=NextSegmentX(segmentsx,segmentx,nodes[j]);
302	}
303	}
304	}
305	while(nothersegments>0 && total<minimum);
306
307	foundconnection:
308
309	/* Prune the segments or mark them as connected */
310
311	if(total<minimum)
312	{
313	nregions++;
314
315	for(j=0;j<nregionsegments;j++)
316	{
317	SegmentX *segmentx=LookupSegmentX(segmentsx,regionsegments[j],1);
318
319	SetBit(connected,regionsegments[j]);
320
321	prune_segment(segmentsx,segmentx);
322
323	npruned++;
324	}
325	}
326	else
327	{
328	for(j=0;j<nregionsegments;j++)
329	{
330	SetBit(connected,regionsegments[j]);
331	ClearBit(region,regionsegments[j]);
332	}
333
334	for(j=0;j<nothersegments;j++)
335	{
336	SetBit(connected,othersegments[j]);
337	ClearBit(region,othersegments[j]);
338	}
339	}
340	}
341
342	if(!((i+1)%10000))
343	printf_middle("Pruning Isolated Regions: Segments=%"Pindex_t" Pruned=%"Pindex_t" (%"Pindex_t" Regions)",i+1,npruned,nregions);
344	}
345
346	/* Unmap from memory / close the files */
347
348	free(region);
349	free(connected);
350
351	free(regionsegments);
352	free(othersegments);
353
354	#if !SLIM
355	nodesx->data=UnmapFile(nodesx->filename);
356	segmentsx->data=UnmapFile(segmentsx->filename);
357	waysx->data=UnmapFile(waysx->filename);
358	#else
359	nodesx->fd=CloseFile(nodesx->fd);
360	segmentsx->fd=CloseFile(segmentsx->fd);
361	waysx->fd=CloseFile(waysx->fd);
362	#endif
363
364	/* Print the final message */
365
366	printf_last("Pruned Isolated Regions: Segments=%"Pindex_t" Pruned=%"Pindex_t" (%"Pindex_t" Regions)",segmentsx->number,npruned,nregions);
367	}
368
369
370	/*++++++++++++++++++++++++++++++++++++++
371	Prune a segment; unused nodes and ways will get marked for pruning later.
372
373	SegmentsX *segmentsx The set of segments to use.
374
375	SegmentX *segmentx The segment to be pruned.
376	++++++++++++++++++++++++++++++++++++++*/
377
378	static void prune_segment(SegmentsX segmentsx,SegmentX segmentx)
379	{
380	unlink_segment_node_refs(segmentsx,segmentx,segmentx->node1);
381	unlink_segment_node_refs(segmentsx,segmentx,segmentx->node2);
382
383	segmentx->node1=NO_NODE;
384	segmentx->node2=NO_NODE;
385	segmentx->next2=NO_SEGMENT;
386
387	PutBackSegmentX(segmentsx,segmentx);
388	}
389
390
391	/*++++++++++++++++++++++++++++++++++++++
392	Modify a segment's nodes; unused nodes will get marked for pruning later.
393
394	SegmentsX *segmentsx The set of segments to use.
395
396	SegmentX *segmentx The segment to be modified.
397
398	index_t newnode1 The new value of node1.
399
400	index_t newnode2 The new value of node2.
401	++++++++++++++++++++++++++++++++++++++*/
402
403	static void modify_segment(SegmentsX segmentsx,SegmentX segmentx,index_t newnode1,index_t newnode2)
404	{
405	index_t thissegment=IndexSegmentX(segmentsx,segmentx);
406
407	if(newnode1!=segmentx->node1)
408	{
409	unlink_segment_node_refs(segmentsx,segmentx,segmentx->node1);
410
411	segmentx->node1=newnode1;
412
413	segmentsx->next1[thissegment]=segmentsx->firstnode[newnode1];
414	segmentsx->firstnode[newnode1]=thissegment;
415	}
416
417	if(newnode1!=segmentx->node1)
418	{
419	unlink_segment_node_refs(segmentsx,segmentx,segmentx->node2);
420
421	segmentx->node2=newnode2;
422
423	segmentx->next2=segmentsx->firstnode[newnode2];
424	segmentsx->firstnode[newnode2]=thissegment;
425	}
426
427	PutBackSegmentX(segmentsx,segmentx);
428	}
429
430
431	/*++++++++++++++++++++++++++++++++++++++
432	Unlink one node from a segment by modifying the linked list type arrangement of node references.
433
434	SegmentsX *segmentsx The set of segments to use.
435
436	SegmentX *segmentx The segment to be pruned.
437
438	index_t node The node index of the end of the segment being modified here.
439	++++++++++++++++++++++++++++++++++++++*/
440
441	static void unlink_segment_node_refs(SegmentsX segmentsx,SegmentX segmentx,index_t node)
442	{
443	index_t thissegment=IndexSegmentX(segmentsx,segmentx);
444	index_t segment=segmentsx->firstnode[node];
445
446	if(segment==NO_SEGMENT)
447	return;
448
449	if(segment==thissegment)
450	{
451	if(segmentx->node1==node)
452	segmentsx->firstnode[node]=segmentsx->next1[thissegment];
453	else
454	segmentsx->firstnode[node]=segmentx->next2;
455	}
456	else
457	{
458	index_t nextsegment;
459
460	do
461	{
462	SegmentX *segx=LookupSegmentX(segmentsx,segment,2);
463
464	if(segx->node1==node)
465	{
466	nextsegment=segmentsx->next1[segment];
467
468	if(thissegment==nextsegment)
469	{
470	if(segmentx->node1==node)
471	segmentsx->next1[segment]=segmentsx->next1[thissegment];
472	else
473	segmentsx->next1[segment]=segmentx->next2;
474	}
475	}
476	else
477	{
478	nextsegment=segx->next2;
479
480	if(thissegment==nextsegment)
481	{
482	if(segmentx->node1==node)
483	segx->next2=segmentsx->next1[thissegment];
484	else
485	segx->next2=segmentx->next2;
486
487	PutBackSegmentX(segmentsx,segx);
488	}
489	}
490
491	segment=nextsegment;
492	}
493	while(segment!=thissegment && segment!=NO_SEGMENT);
494	}
495	}