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