counter_lu_metadata.hpp revision 256281
164562Sgshapiro// -*- C++ -*- 2261370Sgshapiro 390792Sgshapiro// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 490792Sgshapiro// 590792Sgshapiro// This file is part of the GNU ISO C++ Library. This library is free 690792Sgshapiro// software; you can redistribute it and/or modify it under the terms 790792Sgshapiro// of the GNU General Public License as published by the Free Software 890792Sgshapiro// Foundation; either version 2, or (at your option) any later 9261370Sgshapiro// version. 1090792Sgshapiro 1190792Sgshapiro// This library is distributed in the hope that it will be useful, but 1264562Sgshapiro// WITHOUT ANY WARRANTY; without even the implied warranty of 1364562Sgshapiro// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 1464562Sgshapiro// General Public License for more details. 1564562Sgshapiro 1664562Sgshapiro// You should have received a copy of the GNU General Public License 1764562Sgshapiro// along with this library; see the file COPYING. If not, write to 1890792Sgshapiro// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 1990792Sgshapiro// MA 02111-1307, USA. 2064562Sgshapiro 2164562Sgshapiro// As a special exception, you may use this file as part of a free 2264562Sgshapiro// software library without restriction. Specifically, if other files 2364562Sgshapiro// instantiate templates or use macros or inline functions from this 2464562Sgshapiro// file, or you compile this file and link it with other files to 2564562Sgshapiro// produce an executable, this file does not by itself cause the 26110560Sgshapiro// resulting executable to be covered by the GNU General Public 2764562Sgshapiro// License. This exception does not however invalidate any other 2864562Sgshapiro// reasons why the executable file might be covered by the GNU General 2964562Sgshapiro// Public License. 3090792Sgshapiro 3164562Sgshapiro// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 3290792Sgshapiro 3364562Sgshapiro// Permission to use, copy, modify, sell, and distribute this software 3464562Sgshapiro// is hereby granted without fee, provided that the above copyright 3564562Sgshapiro// notice appears in all copies, and that both that copyright notice 3690792Sgshapiro// and this permission notice appear in supporting documentation. None 3790792Sgshapiro// of the above authors, nor IBM Haifa Research Laboratories, make any 3890792Sgshapiro// representation about the suitability of this software for any 3990792Sgshapiro// purpose. It is provided "as is" without express or implied 4064562Sgshapiro// warranty. 4190792Sgshapiro 4290792Sgshapiro/** 4364562Sgshapiro * @file counter_lu_metadata.hpp 4464562Sgshapiro * Contains implementation of a lu counter policy's metadata. 4564562Sgshapiro */ 4664562Sgshapiro 4771345Sgshapironamespace pb_ds 4864562Sgshapiro{ 4964562Sgshapiro namespace detail 5090792Sgshapiro { 5164562Sgshapiro template<typename Size_Type> 5264562Sgshapiro class counter_lu_policy_base; 5364562Sgshapiro 5464562Sgshapiro // A list-update metadata type that moves elements to the front of 5564562Sgshapiro // the list based on the counter algorithm. 5664562Sgshapiro template<typename Size_Type = size_t> 5764562Sgshapiro class counter_lu_metadata 5864562Sgshapiro { 5990792Sgshapiro public: 6064562Sgshapiro typedef Size_Type size_type; 6164562Sgshapiro 6264562Sgshapiro private: 6390792Sgshapiro counter_lu_metadata(size_type init_count) : m_count(init_count) 6464562Sgshapiro { } 6564562Sgshapiro 6664562Sgshapiro friend class counter_lu_policy_base<size_type>; 6764562Sgshapiro 6864562Sgshapiro mutable size_type m_count; 6964562Sgshapiro }; 7064562Sgshapiro 7164562Sgshapiro template<typename Size_Type> 7264562Sgshapiro class counter_lu_policy_base 7364562Sgshapiro { 7464562Sgshapiro protected: 7590792Sgshapiro typedef Size_Type size_type; 7664562Sgshapiro 7790792Sgshapiro counter_lu_metadata<size_type> 7864562Sgshapiro operator()(size_type max_size) const 7964562Sgshapiro { return counter_lu_metadata<Size_Type>(rand() % max_size); } 8090792Sgshapiro 8164562Sgshapiro template<typename Metadata_Reference> 8264562Sgshapiro bool 8364562Sgshapiro operator()(Metadata_Reference r_data, size_type m_max_count) const 8464562Sgshapiro { 8564562Sgshapiro if (++r_data.m_count != m_max_count) 8664562Sgshapiro return false; 8764562Sgshapiro r_data.m_count = 0; 8864562Sgshapiro return true; 8964562Sgshapiro } 9090792Sgshapiro }; 9164562Sgshapiro } // namespace detail 9264562Sgshapiro} // namespace pb_ds 9364562Sgshapiro