nsz Git - libfirm/blob - bucket.c

   1 #include "adt/array.h"
   2
   3 #include "bucket.h"
   4 #include "pbqp_edge_t.h"
   5 #include "pbqp_node_t.h"
   6
   7 int edge_bucket_contains(pbqp_edge_bucket bucket, pbqp_edge *edge)
   8 {
   9         assert(edge);
  10
  11         return edge->bucket_index < edge_bucket_get_length(bucket)
  12                         && bucket[edge->bucket_index] == edge;
  13 }
  14
  15 void edge_bucket_free(pbqp_edge_bucket *bucket)
  16 {
  17         DEL_ARR_F(*bucket);
  18         *bucket = NULL;
  19 }
  20
  21 unsigned edge_bucket_get_length(pbqp_edge_bucket bucket)
  22 {
  23         return ARR_LEN(bucket);
  24 }
  25
  26 void edge_bucket_init(pbqp_edge_bucket *bucket)
  27 {
  28         *bucket = NEW_ARR_F(pbqp_edge *, 0);
  29 }
  30
  31 void edge_bucket_insert(pbqp_edge_bucket *bucket, pbqp_edge *edge)
  32 {
  33         edge->bucket_index = edge_bucket_get_length(*bucket);
  34         ARR_APP1(pbqp_edge *, *bucket, edge);
  35 }
  36
  37 pbqp_edge *edge_bucket_pop(pbqp_edge_bucket *bucket)
  38 {
  39         unsigned   bucket_len = edge_bucket_get_length(*bucket);
  40         pbqp_edge *edge;
  41
  42         assert(bucket_len > 0);
  43
  44         edge = (*bucket)[bucket_len - 1];
  45
  46         ARR_SHRINKLEN(*bucket, (int)bucket_len - 1);
  47         edge->bucket_index = UINT_MAX;
  48
  49         return edge;
  50 }
  51
  52 int node_bucket_contains(pbqp_node_bucket bucket, pbqp_node *node)
  53 {
  54         assert(node);
  55
  56         return node->bucket_index < node_bucket_get_length(bucket)
  57                         && bucket[node->bucket_index] == node;
  58 }
  59
  60 void node_bucket_free(pbqp_node_bucket *bucket)
  61 {
  62         DEL_ARR_F(*bucket);
  63         *bucket = NULL;
  64 }
  65
  66 unsigned node_bucket_get_length(pbqp_node_bucket bucket)
  67 {
  68         return ARR_LEN(bucket);
  69 }
  70
  71 void node_bucket_init(pbqp_node_bucket *bucket)
  72 {
  73         *bucket = NEW_ARR_F(pbqp_node *, 0);
  74 }
  75
  76 void node_bucket_insert(pbqp_node_bucket *bucket, pbqp_node *node)
  77 {
  78         node->bucket_index = node_bucket_get_length(*bucket);
  79         ARR_APP1(pbqp_node *, *bucket, node);
  80 }
  81
  82 pbqp_node *node_bucket_pop(pbqp_node_bucket *bucket)
  83 {
  84         unsigned   bucket_len = node_bucket_get_length(*bucket);
  85         pbqp_node *node;
  86
  87         assert(bucket_len > 0);
  88
  89         node = (*bucket)[bucket_len - 1];
  90         assert(node);
  91
  92         ARR_SHRINKLEN(*bucket, (int)bucket_len - 1);
  93         node->bucket_index = UINT_MAX;
  94
  95         return node;
  96 }
  97
  98 void node_bucket_remove(pbqp_node_bucket *bucket, pbqp_node *node)
  99 {
 100         unsigned   bucket_len = node_bucket_get_length(*bucket);
 101         unsigned   node_index;
 102         pbqp_node *other;
 103
 104         assert(node);
 105         assert(node_bucket_contains(*bucket, node));
 106         assert(bucket_len > 0);
 107
 108         node_index            = node->bucket_index;
 109         other                 = (*bucket)[bucket_len - 1];
 110         other->bucket_index   = node_index;
 111         (*bucket)[node_index] = other;
 112
 113         ARR_SHRINKLEN(*bucket, (int)bucket_len - 1);
 114         node->bucket_index = UINT_MAX;
 115 }
 116
 117 pbqp_node_bucket *node_bucket_deep_copy(pbqp_node_bucket bucket)
 118 {
 119         pbqp_node_bucket *copy;
 120         unsigned          bucket_index;
 121         unsigned          bucket_length;
 122
 123         node_bucket_init(copy);
 124         bucket_length = node_bucket_get_length(bucket);
 125
 126         for (bucket_index = 0; bucket_index < bucket_length; ++bucket_index) {
 127                 node_bucket_insert(copy, pbqp_node_deep_copy(bucket[bucket_index]));
 128         }
 129
 130         return copy;
 131 }