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  * @version $Id$
  26  */
  27 #include "config.h"
  28
  29 #include "adt/array.h"
  30
  31 #include "bucket.h"
  32 #include "pbqp_edge_t.h"
  33 #include "pbqp_node.h"
  34 #include "pbqp_node_t.h"
  35
  36 int edge_bucket_contains(pbqp_edge_bucket_t bucket, pbqp_edge_t *edge)
  37 {
  38         return edge->bucket_index < edge_bucket_get_length(bucket)
  39                         && bucket[edge->bucket_index] == edge;
  40 }
  41
  42 void edge_bucket_free(pbqp_edge_bucket_t *bucket)
  43 {
  44         DEL_ARR_F(*bucket);
  45         *bucket = NULL;
  46 }
  47
  48 unsigned edge_bucket_get_length(pbqp_edge_bucket_t bucket)
  49 {
  50         return ARR_LEN(bucket);
  51 }
  52
  53 void edge_bucket_init(pbqp_edge_bucket_t *bucket)
  54 {
  55         *bucket = NEW_ARR_F(pbqp_edge_t *, 0);
  56 }
  57
  58 void edge_bucket_insert(pbqp_edge_bucket_t *bucket, pbqp_edge_t *edge)
  59 {
  60         edge->bucket_index = edge_bucket_get_length(*bucket);
  61         ARR_APP1(pbqp_edge_t *, *bucket, edge);
  62 }
  63
  64 pbqp_edge_t *edge_bucket_pop(pbqp_edge_bucket_t *bucket)
  65 {
  66         unsigned     bucket_len = edge_bucket_get_length(*bucket);
  67         pbqp_edge_t *edge;
  68
  69         assert(bucket_len > 0);
  70
  71         edge = (*bucket)[bucket_len - 1];
  72
  73         ARR_SHRINKLEN(*bucket, (int)bucket_len - 1);
  74         edge->bucket_index = UINT_MAX;
  75
  76         return edge;
  77 }
  78
  79 void node_bucket_shrink(pbqp_node_bucket_t *bucket, unsigned len)
  80 {
  81         ARR_SHRINKLEN(*bucket, (int)len);
  82 }
  83
  84 int node_bucket_contains(pbqp_node_bucket_t bucket, pbqp_node_t *node)
  85 {
  86         return node->bucket_index < node_bucket_get_length(bucket)
  87                         && bucket[node->bucket_index] == node;
  88 }
  89
  90 void node_bucket_copy(pbqp_node_bucket_t *dst, pbqp_node_bucket_t src)
  91 {
  92         unsigned src_index;
  93         unsigned src_length = node_bucket_get_length(src);
  94
  95         for (src_index = 0; src_index < src_length; ++src_index) {
  96                 node_bucket_insert(dst, src[src_index]);
  97         }
  98 }
  99
 100 void node_bucket_update(pbqp_t *pbqp, pbqp_node_bucket_t bucket)
 101 {
 102         unsigned index;
 103         unsigned length = node_bucket_get_length(bucket);
 104
 105         for (index = 0; index < length; ++index) {
 106                 pbqp->nodes[bucket[index]->index] = bucket[index];
 107         }
 108 }
 109
 110 void node_bucket_free(pbqp_node_bucket_t *bucket)
 111 {
 112         DEL_ARR_F(*bucket);
 113         *bucket = NULL;
 114 }
 115
 116 unsigned node_bucket_get_length(pbqp_node_bucket_t bucket)
 117 {
 118         return ARR_LEN(bucket);
 119 }
 120
 121 void node_bucket_init(pbqp_node_bucket_t *bucket)
 122 {
 123         *bucket = NEW_ARR_F(pbqp_node_t*, 0);
 124 }
 125
 126 void node_bucket_insert(pbqp_node_bucket_t *bucket, pbqp_node_t *node)
 127 {
 128         node->bucket_index = node_bucket_get_length(*bucket);
 129         ARR_APP1(pbqp_node_t *, *bucket, node);
 130 }
 131
 132 pbqp_node_t *node_bucket_pop(pbqp_node_bucket_t *bucket)
 133 {
 134         unsigned     bucket_len = node_bucket_get_length(*bucket);
 135         pbqp_node_t *node;
 136
 137         assert(bucket_len > 0);
 138
 139         node = (*bucket)[bucket_len - 1];
 140
 141         ARR_SHRINKLEN(*bucket, (int)bucket_len - 1);
 142         node->bucket_index = UINT_MAX;
 143
 144         return node;
 145 }
 146
 147 void node_bucket_remove(pbqp_node_bucket_t *bucket, pbqp_node_t *node)
 148 {
 149         unsigned     bucket_len = node_bucket_get_length(*bucket);
 150         unsigned     node_index;
 151         pbqp_node_t *other;
 152
 153         assert(node_bucket_contains(*bucket, node));
 154
 155         node_index            = node->bucket_index;
 156         other                 = (*bucket)[bucket_len - 1];
 157         other->bucket_index   = node_index;
 158         (*bucket)[node_index] = other;
 159
 160         ARR_SHRINKLEN(*bucket, (int)bucket_len - 1);
 161         node->bucket_index = UINT_MAX;
 162 }
 163
 164 void node_bucket_deep_copy(pbqp_t *pbqp, pbqp_node_bucket_t *dst,
 165                            pbqp_node_bucket_t src)
 166 {
 167         unsigned bucket_index;
 168         unsigned bucket_length;
 169
 170         bucket_length = node_bucket_get_length(src);
 171
 172         for (bucket_index = 0; bucket_index < bucket_length; ++bucket_index) {
 173                 node_bucket_insert(dst, pbqp_node_deep_copy(pbqp, *dst, src[bucket_index]));
 174         }
 175 }