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