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 void node_bucket_clear(pbqp_node_bucket *bucket)
  53 {
  54         ARR_SHRINKLEN(*bucket, 0);
  55 }
  56
  57 int node_bucket_contains(pbqp_node_bucket bucket, pbqp_node *node)
  58 {
  59         assert(node);
  60
  61         return node->bucket_index < node_bucket_get_length(bucket)
  62                         && bucket[node->bucket_index] == node;
  63 }
  64
  65 void node_bucket_copy(pbqp_node_bucket *dst, pbqp_node_bucket *src)
  66 {
  67         unsigned src_index;
  68         unsigned src_length = node_bucket_get_length(*src);
  69
  70         for (src_index = 0; src_index < src_length; ++src_index) {
  71                 node_bucket_insert(dst, (*src)[src_index]);
  72         }
  73 }
  74
  75 void node_bucket_free(pbqp_node_bucket *bucket)
  76 {
  77         DEL_ARR_F(*bucket);
  78         *bucket = NULL;
  79 }
  80
  81 unsigned node_bucket_get_length(pbqp_node_bucket bucket)
  82 {
  83         return ARR_LEN(bucket);
  84 }
  85
  86 void node_bucket_init(pbqp_node_bucket *bucket)
  87 {
  88         *bucket = NEW_ARR_F(pbqp_node *, 0);
  89 }
  90
  91 void node_bucket_insert(pbqp_node_bucket *bucket, pbqp_node *node)
  92 {
  93         node->bucket_index = node_bucket_get_length(*bucket);
  94         ARR_APP1(pbqp_node *, *bucket, node);
  95 }
  96
  97 pbqp_node *node_bucket_pop(pbqp_node_bucket *bucket)
  98 {
  99         unsigned   bucket_len = node_bucket_get_length(*bucket);
 100         pbqp_node *node;
 101
 102         assert(bucket_len > 0);
 103
 104         node = (*bucket)[bucket_len - 1];
 105         assert(node);
 106
 107         ARR_SHRINKLEN(*bucket, (int)bucket_len - 1);
 108         node->bucket_index = UINT_MAX;
 109
 110         return node;
 111 }
 112
 113 void node_bucket_remove(pbqp_node_bucket *bucket, pbqp_node *node)
 114 {
 115         unsigned   bucket_len = node_bucket_get_length(*bucket);
 116         unsigned   node_index;
 117         pbqp_node *other;
 118
 119         assert(node);
 120         assert(node_bucket_contains(*bucket, node));
 121         assert(bucket_len > 0);
 122
 123         node_index            = node->bucket_index;
 124         other                 = (*bucket)[bucket_len - 1];
 125         other->bucket_index   = node_index;
 126         (*bucket)[node_index] = other;
 127
 128         ARR_SHRINKLEN(*bucket, (int)bucket_len - 1);
 129         node->bucket_index = UINT_MAX;
 130 }
 131
 132 pbqp_node_bucket *node_bucket_deep_copy(pbqp_node_bucket bucket)
 133 {
 134         pbqp_node_bucket *copy;
 135         unsigned          bucket_index;
 136         unsigned          bucket_length;
 137
 138         node_bucket_init(copy);
 139         bucket_length = node_bucket_get_length(bucket);
 140
 141         for (bucket_index = 0; bucket_index < bucket_length; ++bucket_index) {
 142                 node_bucket_insert(copy, pbqp_node_deep_copy(bucket[bucket_index]));
 143         }
 144
 145         return copy;
 146 }