diff options
Diffstat (limited to 'compiler/kuma/src/IntervalSet.cpp')
-rw-r--r-- | compiler/kuma/src/IntervalSet.cpp | 92 |
1 files changed, 92 insertions, 0 deletions
diff --git a/compiler/kuma/src/IntervalSet.cpp b/compiler/kuma/src/IntervalSet.cpp new file mode 100644 index 000000000..f6790c654 --- /dev/null +++ b/compiler/kuma/src/IntervalSet.cpp @@ -0,0 +1,92 @@ +/* + * Copyright (c) 2020 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "IntervalSet.h" + +#include <cassert> +#include <stdexcept> + +namespace kuma +{ +namespace details +{ + +IntervalSet::IntervalSet(uint32_t len) +{ + // Update _content + _content[len] = len; +} + +void IntervalSet::insert(const IntervalMask &m) +{ + auto s = m.s; + auto e = m.e; + + assert(s <= e); + + if (s == e) + { + // Empty region, nothing to do + return; + } + + // lower_bound() returns an iterator to the first element not less than the given key + auto lb = _content.lower_bound(s); + + // NOTE 1. "lower_bound" ensures "prev_s < s <= curr_e" + // NOTE 2. "e" points to somewhere after "s" + auto curr_s = lb->first - lb->second; + auto curr_e = lb->first; + + if (curr_s < s) + { + // Split the current interval + _content[s] = s - curr_s; + // NOTE The invariant over "_content" is temporarily broken here. + } + + if (e < curr_e) + { + // Adjust the current interval + _content[curr_e] = curr_e - e; + } + else + { + // Remove the current interval + _content.erase(curr_e); + // Check the next interval (e > curr_e) + // + // TODO Remove this recursive call (to prevent stack overflow issue) + insert(mask(curr_e, e)); + } +} + +uint32_t IntervalSet::firstfit(uint32_t len) const +{ + for (auto it = _content.begin(); it != _content.end(); ++it) + { + if (it->second >= len) + { + // Got it! This interval is larger than "len". + return it->first - it->second; + } + } + + throw std::runtime_error{"infeasible"}; +} + +} // namespace details +} // namespace kuma |