nsz Git - libfirm/blob - ir/kaps/bucket.c

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief   Buckets for nodes and edges.
  23  * @date    30.11.2008
  24  * @author  Sebastian Buchwald
  25  */
  26 #include "config.h"
  27
  28 #include "adt/array.h"
  29
  30 #include "bucket.h"
  31 #include "pbqp_edge_t.h"
  32 #include "pbqp_node.h"
  33 #include "pbqp_node_t.h"
  34
  35 int edge_bucket_contains(pbqp_edge_bucket_t bucket, pbqp_edge_t *edge)
  36 {
  37         return edge->bucket_index < edge_bucket_get_length(bucket)
  38                         && bucket[edge->bucket_index] == edge;
  39 }
  40
  41 void edge_bucket_free(pbqp_edge_bucket_t *bucket)
  42 {
  43         DEL_ARR_F(*bucket);
  44         *bucket = NULL;
  45 }
  46
  47 unsigned edge_bucket_get_length(pbqp_edge_bucket_t bucket)
  48 {
  49         return ARR_LEN(bucket);
  50 }
  51
  52 void edge_bucket_init(pbqp_edge_bucket_t *bucket)
  53 {
  54         *bucket = NEW_ARR_F(pbqp_edge_t *, 0);
  55 }
  56
  57 void edge_bucket_insert(pbqp_edge_bucket_t *bucket, pbqp_edge_t *edge)
  58 {
  59         edge->bucket_index = edge_bucket_get_length(*bucket);
  60         ARR_APP1(pbqp_edge_t *, *bucket, edge);
  61 }
  62
  63 pbqp_edge_t *edge_bucket_pop(pbqp_edge_bucket_t *bucket)
  64 {
  65         unsigned     bucket_len = edge_bucket_get_length(*bucket);
  66         pbqp_edge_t *edge;
  67
  68         assert(bucket_len > 0);
  69
  70         edge = (*bucket)[bucket_len - 1];
  71
  72         ARR_SHRINKLEN(*bucket, (int)bucket_len - 1);
  73         edge->bucket_index = UINT_MAX;
  74
  75         return edge;
  76 }
  77
  78 void node_bucket_shrink(pbqp_node_bucket_t *bucket, unsigned len)
  79 {
  80         ARR_SHRINKLEN(*bucket, (int)len);
  81 }
  82
  83 int node_bucket_contains(pbqp_node_bucket_t bucket, pbqp_node_t *node)
  84 {
  85         return node->bucket_index < node_bucket_get_length(bucket)
  86                         && bucket[node->bucket_index] == node;
  87 }
  88
  89 void node_bucket_copy(pbqp_node_bucket_t *dst, pbqp_node_bucket_t src)
  90 {
  91         unsigned src_index;
  92         unsigned src_length = node_bucket_get_length(src);
  93
  94         for (src_index = 0; src_index < src_length; ++src_index) {
  95                 node_bucket_insert(dst, src[src_index]);
  96         }
  97 }
  98
  99 void node_bucket_update(pbqp_t *pbqp, pbqp_node_bucket_t bucket)
 100 {
 101         unsigned index;
 102         unsigned length = node_bucket_get_length(bucket);
 103
 104         for (index = 0; index < length; ++index) {
 105                 pbqp->nodes[bucket[index]->index] = bucket[index];
 106         }
 107 }
 108
 109 void node_bucket_free(pbqp_node_bucket_t *bucket)
 110 {
 111         DEL_ARR_F(*bucket);
 112         *bucket = NULL;
 113 }
 114
 115 unsigned node_bucket_get_length(pbqp_node_bucket_t bucket)
 116 {
 117         return ARR_LEN(bucket);
 118 }
 119
 120 void node_bucket_init(pbqp_node_bucket_t *bucket)
 121 {
 122         *bucket = NEW_ARR_F(pbqp_node_t*, 0);
 123 }
 124
 125 void node_bucket_insert(pbqp_node_bucket_t *bucket, pbqp_node_t *node)
 126 {
 127         node->bucket_index = node_bucket_get_length(*bucket);
 128         ARR_APP1(pbqp_node_t *, *bucket, node);
 129 }
 130
 131 pbqp_node_t *node_bucket_pop(pbqp_node_bucket_t *bucket)
 132 {
 133         unsigned     bucket_len = node_bucket_get_length(*bucket);
 134         pbqp_node_t *node;
 135
 136         assert(bucket_len > 0);
 137
 138         node = (*bucket)[bucket_len - 1];
 139
 140         ARR_SHRINKLEN(*bucket, (int)bucket_len - 1);
 141         node->bucket_index = UINT_MAX;
 142
 143         return node;
 144 }
 145
 146 void node_bucket_remove(pbqp_node_bucket_t *bucket, pbqp_node_t *node)
 147 {
 148         unsigned     bucket_len = node_bucket_get_length(*bucket);
 149         unsigned     node_index;
 150         pbqp_node_t *other;
 151
 152         assert(node_bucket_contains(*bucket, node));
 153
 154         node_index            = node->bucket_index;
 155         other                 = (*bucket)[bucket_len - 1];
 156         other->bucket_index   = node_index;
 157         (*bucket)[node_index] = other;
 158
 159         ARR_SHRINKLEN(*bucket, (int)bucket_len - 1);
 160         node->bucket_index = UINT_MAX;
 161 }
 162
 163 void node_bucket_deep_copy(pbqp_t *pbqp, pbqp_node_bucket_t *dst,
 164                            pbqp_node_bucket_t src)
 165 {
 166         unsigned bucket_index;
 167         unsigned bucket_length;
 168
 169         bucket_length = node_bucket_get_length(src);
 170
 171         for (bucket_index = 0; bucket_index < bucket_length; ++bucket_index) {
 172                 node_bucket_insert(dst, pbqp_node_deep_copy(pbqp, *dst, src[bucket_index]));
 173         }
 174 }