aboutsummaryrefslogtreecommitdiff
path: root/bfd/arange-set.c
blob: 0a6c2f0cccd092f742aa4b2f99d7dba73ba4e647 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
/* DWARF 2 Arange-Set.
   Copyright 2007 Free Software Foundation, Inc.
   Contributed by Doug Kwan, Google Inc.
 
   This file is part of BFD.

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU 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
   General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
   MA 02110-1301, USA.  */

#include "sysdep.h"
#include "bfd.h"
#include "libiberty.h"
#include "libbfd.h"
#include "arange-set.h"
#include "splay-tree.h"

/* Implementation of an arange-set.  The set is implemented using the
   splay tree support in libiberty.  The advantage of using this is
   that it has been well tested and is relatively simple to use.  The
   disadvantage is that it is too general and it does not fit our design
   exactly.  So we waste a bit of memory for unneeded generality and work
   around for mis-match between the splay tree API and the arange-set
   internals.  A specialized implentation of a balanced tree type for
   arange-set exclusively may speed up things a little and reduce memory
   consumption.  Until there is a pressing need, we stick to the splay
   tree in libiberty.  */

struct arange_set_s
{
  /* Splay tree containing aranges.  */
  splay_tree ranges;

  /* Lowest address in set.  If set is empty, it is ~0.  */
  bfd_vma lower_bound;

  /* Highest address in set.  If set is empty, it is 0.  */
  bfd_vma upper_bound;

  /* TRUE if aranges in this set have values.  */
  bfd_boolean value_p;

  /* Function to compare arange values.  */
  arange_value_equal_fn value_equal_fn;

  /* Function to copy an arange value.  */
  arange_value_copy_fn value_copy_fn;

  /* Function to combine arange values.  */
  arange_value_combine_fn value_combine_fn;

  /* Function to delete an arange value.  */
  arange_value_delete_fn value_delete_fn;

  /* Function to allocate a piece of memory.  */
  arange_set_allocate_fn allocate_fn;

  /* Function to deallocate a piece of memory.  */
  arange_set_deallocate_fn deallocate_fn;

  /* Call back data shared by all callbacks.  */
  void *data;
};

/* Structure for aranges with a value attached.  Since a splay tree
   node can only hold one value,  we need to use the container struct
   to store data associated with an arange and have the splay tree value
   to be a pointer to this struct. */

typedef struct
{
  /* High-pc of an arange.  This is different from the DWARF2 semantics that
     the high-pc is really the last location in an arange.  */
  bfd_vma high;

  /* We need to store a pointer to the set because splay_tree_value_delete
     only takes a pointer to the value deleted.  If we use a deallocator
     that need extra information like a pointer to the memory pool, we need to
     look up via the set pointer.  This adds one extra pointer per arange. */
  arange_set set;

  /* Value associated with this arange.  */
  arange_value_type value;

} arange_value_container_t;



static void
arange_set_delete_value (arange_set set, arange_value_type value)
{
  if (set->value_delete_fn)
    (set->value_delete_fn) (value, set->data);
}

/* Compare two VMAs as keys of splay tree nodes.  */

static int
splay_tree_compare_bfd_vmas (splay_tree_key k1, splay_tree_key k2)
{
  if ((bfd_vma) k1 < (bfd_vma) k2)
    return -1;
  else if ((bfd_vma) k1 > (bfd_vma) k2)
    return 1;

  return 0;
}

/* Default memory allocator and deallocator.  */

void *
arange_set_allocate (arange_set set, int size)
{
  if (set->allocate_fn)
    return (set->allocate_fn) (size, set->data); 

  return xmalloc (size);
}

void
arange_set_deallocate (arange_set set, void *object)
{
  if (set->deallocate_fn)
    (set->deallocate_fn) (object, set->data); 
  else
    free (object);
}

static void
arange_set_delete_value_container (splay_tree_value value)
{
  arange_value_container_t *container;

  container = (arange_value_container_t*) value;
  arange_set_delete_value (container->set, container->value);
  arange_set_deallocate (container->set, container);
}

/* Create an arange set.  Return the new set of NULL if there is any
   error.  

   allocate_fn is the memory allocator function of this arange set. If
   it is NULL, the default allocator will be used.

   deallocate_fn is the memory deallocator function of this arange set. If
   it is NULL, the default allocator will be used.

   value_p specifies whether an arange set supports values.  If it is
   TURE.  Each arange can be associated with a value of type arange_value_type.
   If it is FALSE, the following parameters value_equal_fn, value_copy_fn,
   value_combine_fn and value_delete_fn will be ignored.

   value_equal_fn is the value equality function.  An arange uses it to
   check if two values are the same.  If it is NULL, the default bit-wise
   equality function will be used.

   value_copy_fn is the value copy function.  An arange uses it to copy
   values of type arange_value_type.  If it is NULL, the default bit-wise
   copy function will be used.

   value_combine_fn is the value combine function. An arange uses it to
   combine values of two identical arange.  If it is NULL, the default
   constant zero function will be used.

   value_delete_fn is the value deletion function. If it is not NULL,
   it will be called when an arange deletes a value.

   data is pointer to an object, which will be passed to all allocate_fn,
   deallocate_fn, value_equal_fn, value_copy_fn, value_combine_fn and
   value_delete_fn.  */

arange_set
arange_set_new (arange_set_allocate_fn allocate_fn,
		arange_set_deallocate_fn deallocate_fn,
		bfd_boolean value_p,
		arange_value_equal_fn value_equal_fn,
		arange_value_copy_fn value_copy_fn,
		arange_value_combine_fn value_combine_fn,
		arange_value_delete_fn value_delete_fn,
		void *data)
{
  arange_set set;
  splay_tree sp;
  splay_tree_delete_value_fn fn;

  /* Allocate space for arange structure.  */
  set = (arange_set)
    (*allocate_fn) (sizeof (struct arange_set_s), data);
  if (!set)
    return set;
  
  fn = value_p ? arange_set_delete_value_container : NULL;
  sp = splay_tree_new_with_allocator (splay_tree_compare_bfd_vmas, NULL,
				      fn, allocate_fn, deallocate_fn,
				      data);
  if (!sp)
    {
      (deallocate_fn) (set, data);
      return NULL;
    }

  set->ranges = sp;
  set->lower_bound = ~0;
  set->upper_bound = 0;
  set->value_p = value_p;
  set->allocate_fn = allocate_fn;
  set->deallocate_fn = deallocate_fn;
  set->value_equal_fn = value_equal_fn;
  set->value_copy_fn = value_copy_fn;
  set->value_combine_fn = value_combine_fn;
  set->value_delete_fn = value_delete_fn;
  set->data = data;
  return set;
}

/*  Delete an arange set.  */

void
arange_set_delete (arange_set set)
{
  splay_tree_delete (set->ranges);
  (*set->deallocate_fn) (set, set->data);
}

/* Return TRUE if and only if arange set is empty.  */

bfd_boolean
arange_set_empty_p (arange_set set)
{
  return set->lower_bound > set->upper_bound;
}

/* Accessors for low and high of an arange.
 
   There is no arange_set_node_set_low since the low address is the
   key of the splay tree node.  */

/* Get the high VMA address of a node.  */

static bfd_vma
arange_set_node_high (arange_set set, splay_tree_node node)
{
  arange_value_container_t *container;

  if (set->value_p)
    {
      container = (arange_value_container_t*) node->value;
      return container->high;
    }

  return (bfd_vma) node->value;
}

/* Set the high VMA address of a node.  */

static void
arange_set_node_set_high (arange_set set, splay_tree_node node, bfd_vma address)
{
  arange_value_container_t *container;

  if (set->value_p)
    {
      container = (arange_value_container_t*) node->value;
      container->high = address;
    }
  else
    node->value = (splay_tree_value) address;
}

/* Get the low VMA address of a node.  */

static bfd_vma
arange_set_node_low (splay_tree_node node)
{
  return (bfd_vma) node->key;
}

/* If arange set supports values, return value of an arange; otheriwse
   always return 0 so that it appears that all aranges have the same value.  */

static arange_value_type
arange_set_node_value (arange_set set, splay_tree_node node)
{
  arange_value_container_t *container;

  if (set->value_p)
    {
      container = (arange_value_container_t*) node->value;
      return container->value;
    }

  return 0;
}

/* If arange set supports values, return value of an arange; otheriwse
   always return 0 so that it appears that all aranges have the same value.  */

static void
arange_set_node_set_value (arange_set set,
			   splay_tree_node node,
			   arange_value_type value)
{
  arange_value_container_t *container;

  if (set->value_p)
    {
      container = (arange_value_container_t*) node->value;
      container->value = value;
    }
}

/* Return TRUE if and only if arange set supports values.  */

bfd_boolean
arange_set_has_values_p (arange_set set)
{
  return set->value_p;
}

/* Copy a value using the value copying function of an arange set.  If
   the set does not support values or if there is not value copying
   function specified, it simply returns the input value.  */

arange_value_type
arange_set_copy_value (arange_set set, arange_value_type value)
{
  /* If no copy function is specified or set does not support values,
     default is bit-wise copy.  */
  if (set->value_p && set->value_copy_fn)
    return (set->value_copy_fn) (value, set->data);

  return value;
}

static arange_value_type
arange_set_combine_value (arange_set set,
			  arange_value_type value1,
			  arange_value_type value2)
{
  /* If no combine function is specified or set does not support values,
     default is returning 0.  */
  if (set->value_p && set->value_combine_fn)
    return (set->value_combine_fn) (value1, value2, set->data);

  return (arange_value_type) 0;
}

/* Compares two values for equality.  If the arange set does not support values
   or if no value equality function is specified, this function simply does
   a bit-wise comparison.  */

bfd_boolean
arange_set_value_equal_p (arange_set set,
			  arange_value_type value1,
			  arange_value_type value2)
{
  /* If no equality function is specified or set does not support values,
     default is bit-wise comparison.  */
  if (set->value_p && set->value_equal_fn)
    return (set->value_equal_fn) (value1, value2, set->data);

  return value1 == value2;
}

/* Check to see if a given address is in an arange set.  Return TRUE if the
   address is inside one of the aranges. If low_ptr, high_ptr and value_ptr are
   used to return lower address, upper address and value associated with a
   found arounge.  If anyone of them is NULL, the corresponding information
   is not returned.  For arange set without values, no information is returned
   through the pointer value_ptr.  */

bfd_boolean
arange_set_lookup_address (arange_set set, bfd_vma address,
			   bfd_vma *low_ptr, bfd_vma *high_ptr,
			   arange_value_type *value_ptr)
{
  splay_tree_node pred, node;

  if (address < set->lower_bound || address > set->upper_bound)
    return FALSE;

  /* Find immediate predecessor.  */
  pred = splay_tree_predecessor (set->ranges, (splay_tree_key) address);
  if (pred
      && arange_set_node_high (set, pred) >= address)
    node = pred;
  else
    /* If the predecessor range does not cover this address, the address
       is in the arange set only if itself starts an arange.  */
    node = splay_tree_lookup (set->ranges, (splay_tree_key) address);

  if (node)
    {
      /* Also return arange boundaries if caller supplies pointers.  */
      if (low_ptr)
	*low_ptr = arange_set_node_low (node);
      if (high_ptr)
	*high_ptr = arange_set_node_high (set, node);
      if (set->value_p && value_ptr)
	*value_ptr = arange_set_node_value (set, node);
      return TRUE;
    }

  return FALSE;
}

/* Insert an arange [low, high] into a set's splay tree.  If the set supports
   value, also insert with the given value.  Return the inserted node if there
   is no error or NULL otherwise.  */

static splay_tree_node
arange_set_splay_tree_insert (arange_set set,
			      bfd_vma low,
			      bfd_vma high,
			      arange_value_type value)
{
  splay_tree_value sp_value;
  arange_value_container_t *container;
   
  if (set->value_p)
    {
      int size = sizeof (arange_value_container_t);
      void *data = set->ranges->allocate_data;

      container =
	(arange_value_container_t*) (*set->ranges->allocate) (size, data);
      if (!container)
	return NULL;
      container->high = high;

      /* Due to the design of splay tree API, there is no way of passing
	 callback data to the splay tree value delete function.  Hence we need
	 to store a pointer to set in every containier!  */
      container->set = set;

      container->value = value;
      sp_value = (splay_tree_value) container;
    }
  else
    sp_value = (splay_tree_value) high;	

  /* Currently splay_tree_insert does not return any status to tell if there
     is an error.  */
  return splay_tree_insert (set->ranges, (splay_tree_key) low, sp_value);
}

/* Split [low, high] to [low, address) & [address, high].  */

static bfd_boolean
arange_set_split_node (arange_set set, splay_tree_node node, bfd_vma address)
{
  splay_tree_node node2;
  arange_value_type value;
  bfd_vma low, high;

  low = arange_set_node_low (node);
  high = arange_set_node_high (set, node);

  BFD_ASSERT (low < address && address <= high);
  
  value = arange_set_copy_value (set, arange_set_node_value (set, node));
  node2 = arange_set_splay_tree_insert (set, address, high, value);
  if (!node2)
    return FALSE;

  arange_set_node_set_high (set, node, address - 1);
  return TRUE;
}

static splay_tree_node
arange_set_maybe_merge_with_predecessor (arange_set set, splay_tree_node node)
{
  splay_tree_node pred;
  bfd_vma low, high;

  low = arange_set_node_low (node);
  high = arange_set_node_high (set, node);

  pred = splay_tree_predecessor (set->ranges, low);
  if (! pred)
    return node;

  if (arange_set_node_high (set, pred) + 1 == low
      && arange_set_value_equal_p (set,
				   arange_set_node_value (set, pred),
				   arange_set_node_value (set, node)))
    {
      splay_tree_remove (set->ranges, arange_set_node_low (node));
      arange_set_node_set_high (set, pred, high);
      return arange_set_maybe_merge_with_predecessor (set, pred);	
    }

  return node;
}

/* Insert an arange [low,high] into a set. Return TRUE if and only if there
   is no error.  Note that the address high is also included where as in
   DWARF2 an address range between low & high means [low,high).

   This only handles sets with values. For the simpler case of sets without
   value, it is handled in arange_set_insert().  This function is
   tail-recurive.  It is guaranteed to terminate because it only recurses
   with a smaller range than it is given.  */

static bfd_boolean
arange_set_insert_value (arange_set set,
			 bfd_vma low,
			 bfd_vma high,
			 arange_value_type value)
{
  splay_tree_node succ, pred, node;
  bfd_vma succ_high, succ_low;
  arange_value_type combined, old_value;

  if (low > high)
    {
      arange_set_delete_value (set, value);
      return FALSE;
    }

  pred = splay_tree_predecessor (set->ranges, low);
  if (pred && arange_set_node_high (set, pred) >= low)
    arange_set_split_node (set, pred, low);

  node = splay_tree_lookup (set->ranges, low);
  if (node)
    {
      /* Split node if its arange is larger than inserted arange. */
      if (arange_set_node_high (set, node) > high)
	arange_set_split_node (set, node, high + 1);

      old_value = arange_set_node_value (set, node);
      combined = arange_set_combine_value (set, old_value, value); 
      arange_set_node_set_value (set, node, combined);
      node = arange_set_maybe_merge_with_predecessor (set, node);
      arange_set_delete_value (set, old_value);

      /* Insert remaining arange by tail-recursion.  */
      if (high > arange_set_node_high (set, node))
	return arange_set_insert_value (set,
					arange_set_node_high (set, node) + 1,
					high, value);
      else
	{
	  /* Node must cover exactly the range. */
	  BFD_ASSERT (high == arange_set_node_high (set, node));
	  arange_set_delete_value (set, value);
	  succ = splay_tree_successor (set->ranges, arange_set_node_low (node));
	  if (succ)
	    succ = arange_set_maybe_merge_with_predecessor (set, succ);	
	  return TRUE;
	}
    }
  
  succ = splay_tree_successor (set->ranges, low);
  if (succ)
    {
      succ_low = arange_set_node_low (succ);	
      succ_high = arange_set_node_high (set, succ);

      if (succ_low <= high)
	{
	  node = arange_set_splay_tree_insert (set, low, succ_low - 1, value); 
	  if (!node)
	    return FALSE;

	  /* Update set lower bound only after insertion is successful.  */
	  if (low < set->lower_bound)
	    set->lower_bound = low;

	  node = arange_set_maybe_merge_with_predecessor (set, node);

	  /* Recurse to handle rest of insertion.  Note that we have to copy
	     value here since it has already been used in the node above.  */
	  return arange_set_insert_value (set, succ_low, high,
					  arange_set_copy_value (set, value));
	}
     }
  
  node = arange_set_splay_tree_insert (set, low, high, value);
  if (!node)
    return FALSE;

  /* Update set boundaries only after insertion is successful.  */
  if (low < set->lower_bound)
    set->lower_bound = low;
  if (high > set->upper_bound)
    set->upper_bound = high;

  node = arange_set_maybe_merge_with_predecessor (set, node);

  succ = splay_tree_successor (set->ranges, arange_set_node_low (node));
  if (succ)
    succ = arange_set_maybe_merge_with_predecessor (set, succ);	

  return TRUE;
}

bfd_boolean
arange_set_insert (arange_set set,
		   bfd_vma low,
		   bfd_vma high,
		   arange_value_type value)
{
  splay_tree tree = set->ranges;
  splay_tree_node pred, succ, node = NULL;
  bfd_vma pred_high, node_low;

  if (set->value_p)
    return arange_set_insert_value (set, low, high, value);

  if (low > high)
    return FALSE;

  pred = splay_tree_predecessor (tree, low);
  if (pred)
    {
      pred_high = arange_set_node_high (set, pred);

      /* Nothing to be done if predecessor contains new aranges.  */ 
      if (pred_high >= high)
	return TRUE;

      /* If we can expand predecessor, do so.  Test for the case in which
	 predecessor does not contain new arange but touches it.  */
      if (pred_high >= low || pred_high + 1 == low)
	{
	  node = pred;
	  arange_set_node_set_high (set, node, high);
	}
    }

  /* Try to see if [low,something] is already in splay tree.  */ 
  if (node == NULL)
    {
      node = splay_tree_lookup (tree, low); 	
      if (node)
	{
	  /* Nothing to be done if node contains new aranges.  */ 
	  if (arange_set_node_high (set, node) >= high)
	    return TRUE;

	  arange_set_node_set_high (set, node, high);
	}
    }

  if (node == NULL)
    {
      node = arange_set_splay_tree_insert (set, low, high, 0);
      if (!node)
	return FALSE;
    }

  BFD_ASSERT (node
	      && arange_set_node_low (node) <= low
	      && arange_set_node_high (set, node) >= high);

  /* Update set upper and lower bounds.  */
  if (low < set->lower_bound)
    set->lower_bound = low;
  if (high > set->upper_bound)
    set->upper_bound = high;

  /* Merge successor if it overlaps or touches node.  */
  node_low = arange_set_node_low (node);
  while ((succ = splay_tree_successor (tree, node_low)) != NULL
	 && ((arange_set_node_high (set, node) >= arange_set_node_low (succ))
	     || (arange_set_node_high (set, node) + 1
		 == arange_set_node_low (succ))))
    {
      if (arange_set_node_high (set, succ) > high)
        arange_set_node_set_high (set, node, arange_set_node_high (set, succ));
      splay_tree_remove (tree, arange_set_node_low (succ));
    }
  return TRUE;
}

struct arange_set_foreach_adapter_data
{
  void *data;
  arange_set set;
  arange_set_foreach_fn foreach_fn;
};

/* Adaptor to make arange_set_foreach works with splay_tree_foreach.  */

static int
arange_set_foreach_adapter (splay_tree_node node, void *data)
{
  struct arange_set_foreach_adapter_data *adapter_data;
  arange_set set;

  adapter_data = data;
  set = adapter_data->set;
  return (adapter_data->foreach_fn) (arange_set_node_low (node),
				     arange_set_node_high (set, node),
				     arange_set_node_value (set, node),
				     adapter_data->data);
}

/* Traverse aranges in a set.  For each arange in ascending order of
   low addresses, call foreach_fn with arange boundaries and data.
   If any invocation of foreach_fn returns a non-zero value, stop traversal
   and return that value. Otherwise, return 0.  */

int
arange_set_foreach (arange_set set,
		    arange_set_foreach_fn foreach_fn,
		    void *data)
{
  struct arange_set_foreach_adapter_data adapter_data;

  adapter_data.data = data;
  adapter_data.foreach_fn = foreach_fn;
  adapter_data.set = set;
  return splay_tree_foreach (set->ranges, arange_set_foreach_adapter,
			     (void *) &adapter_data);
}