1172838Sjulian// -*- C++ -*- 2172838Sjulian 3172838Sjulian// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 4172838Sjulian// 5172838Sjulian// This file is part of the GNU ISO C++ Library. This library is free 6172838Sjulian// software; you can redistribute it and/or modify it under the terms 7172838Sjulian// of the GNU General Public License as published by the Free Software 8172838Sjulian// Foundation; either version 2, or (at your option) any later 9172838Sjulian// version. 10172838Sjulian 11172838Sjulian// This library is distributed in the hope that it will be useful, but 12172838Sjulian// WITHOUT ANY WARRANTY; without even the implied warranty of 13172838Sjulian// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14172838Sjulian// General Public License for more details. 15172838Sjulian 16172838Sjulian// You should have received a copy of the GNU General Public License 17172838Sjulian// along with this library; see the file COPYING. If not, write to 18172838Sjulian// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19172838Sjulian// MA 02111-1307, USA. 20172838Sjulian 21172838Sjulian// As a special exception, you may use this file as part of a free 22172838Sjulian// software library without restriction. Specifically, if other files 23172838Sjulian// instantiate templates or use macros or inline functions from this 24172838Sjulian// file, or you compile this file and link it with other files to 25172838Sjulian// produce an executable, this file does not by itself cause the 26172838Sjulian// resulting executable to be covered by the GNU General Public 27172838Sjulian// License. This exception does not however invalidate any other 28172838Sjulian// reasons why the executable file might be covered by the GNU General 29172838Sjulian// Public License. 30172838Sjulian 31172838Sjulian// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32172838Sjulian 33172838Sjulian// Permission to use, copy, modify, sell, and distribute this software 34172838Sjulian// is hereby granted without fee, provided that the above copyright 35172838Sjulian// notice appears in all copies, and that both that copyright notice 36172838Sjulian// and this permission notice appear in supporting documentation. None 37172838Sjulian// of the above authors, nor IBM Haifa Research Laboratories, make any 38172838Sjulian// representation about the suitability of this software for any 39173030Sjulian// purpose. It is provided "as is" without express or implied 40172838Sjulian// warranty. 41172838Sjulian 42172838Sjulian/** 43172838Sjulian * @file insert_store_hash_fn_imps.hpp 44172838Sjulian * Contains implementations of gp_ht_map_'s find related functions, 45172838Sjulian * when the hash value is stored. 46172838Sjulian */ 47173030Sjulian 48173030SjulianPB_DS_CLASS_T_DEC 49173030Sjulianinline typename PB_DS_CLASS_C_DEC::comp_hash 50173030SjulianPB_DS_CLASS_C_DEC:: 51173030Sjulianfind_ins_pos(const_key_reference r_key, true_type) 52172838Sjulian{ 53172838Sjulian _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) 54172838Sjulian comp_hash pos_hash_pair = ranged_probe_fn_base::operator()(r_key); 55172838Sjulian 56172838Sjulian size_type i; 57172838Sjulian 58172838Sjulian /* The insertion position is initted to a non-legal value to indicate 59172838Sjulian * that it has not been initted yet. 60178682Sjulian */ 61178682Sjulian size_type ins_pos = m_num_e; 62178682Sjulian resize_base::notify_insert_search_start(); 63178682Sjulian for (i = 0; i < m_num_e; ++i) 64178682Sjulian { 65178682Sjulian const size_type pos = ranged_probe_fn_base::operator()(r_key, pos_hash_pair.second, i); 66172838Sjulian 67196450Sjulian entry* const p_e = m_entries + pos; 68196450Sjulian switch(p_e->m_stat) 69196450Sjulian { 70196450Sjulian case empty_entry_status: 71196450Sjulian { 72196450Sjulian resize_base::notify_insert_search_end(); 73196450Sjulian _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key);) 74196450Sjulian 75196450Sjulian return ((ins_pos == m_num_e) ? 76196450Sjulian std::make_pair(pos, pos_hash_pair.second) : 77196450Sjulian std::make_pair(ins_pos, pos_hash_pair.second)); 78196450Sjulian } 79196450Sjulian break; 80233648Seadler case erased_entry_status: 81233648Seadler if (ins_pos == m_num_e) 82196450Sjulian ins_pos = pos; 83196450Sjulian break; 84196450Sjulian case valid_entry_status: 85196450Sjulian if (hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), p_e->m_hash, 86196450Sjulian r_key, pos_hash_pair.second)) 87196450Sjulian { 88196450Sjulian resize_base::notify_insert_search_end(); 89172838Sjulian _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key);) 90172838Sjulian return std::make_pair(pos, pos_hash_pair.second); 91172838Sjulian } 92172838Sjulian break; 93173030Sjulian default: 94173030Sjulian _GLIBCXX_DEBUG_ASSERT(0); 95173030Sjulian }; 96173030Sjulian resize_base::notify_insert_search_collision(); 97173030Sjulian } 98172838Sjulian resize_base::notify_insert_search_end(); 99172838Sjulian if (ins_pos == m_num_e) 100172838Sjulian __throw_insert_error(); 101172838Sjulian return std::make_pair(ins_pos, pos_hash_pair.second); 102172838Sjulian} 103173030Sjulian 104172838SjulianPB_DS_CLASS_T_DEC 105172838Sjulianinline std::pair<typename PB_DS_CLASS_C_DEC::point_iterator, bool> 106172838SjulianPB_DS_CLASS_C_DEC:: 107173030Sjulianinsert_imp(const_reference r_val, true_type) 108173030Sjulian{ 109173030Sjulian const_key_reference r_key = PB_DS_V2F(r_val); 110172838Sjulian comp_hash pos_hash_pair = find_ins_pos(r_key, 111172838Sjulian traits_base::m_store_extra_indicator); 112172838Sjulian 113172838Sjulian _GLIBCXX_DEBUG_ASSERT(pos_hash_pair.first < m_num_e); 114172838Sjulian entry_pointer p_e =& m_entries[pos_hash_pair.first]; 115172838Sjulian if (p_e->m_stat == valid_entry_status) 116173030Sjulian { 117172838Sjulian _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key)); 118172838Sjulian return std::make_pair(&p_e->m_value, false); 119172838Sjulian } 120172838Sjulian 121172838Sjulian _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key)); 122173030Sjulian return std::make_pair(insert_new_imp(r_val, pos_hash_pair), true); 123172838Sjulian} 124172838Sjulian 125172838Sjulian