note description: "History used for cache remembering system, so that element% %accessed more often are kept as much as possible." legal: "See notice at end of class." status: "See notice at end of class." date: "$Date$" revision: "$Revision$" class CACHE_HISTORY [G] create make feature {NONE} -- Initialization make (n: INTEGER) -- Create an history of size n local i: INTEGER int_array: SPECIAL [INTEGER] l_default: detachable G do create area.make_filled (l_default, n) create next.make_filled (0, n) create previous.make_filled (0, n) create free_cells.make_filled (0, n) from int_array := free_cells until i = n loop int_array.put (i, i) i := i + 1 end size := n younger := -1 older := -1 end feature -- Access next: SPECIAL [INTEGER] -- Position of the next element in the history -- Understand next arrived previous: SPECIAL [INTEGER] -- Position of the previous element in the history -- Understand previously arrived free_cells: SPECIAL [INTEGER] -- Record of the cells still free in the history feature -- Status Report size: INTEGER -- Size of the history count: INTEGER -- Number of elements in the history capacity: INTEGER -- Maximum number of elements in the history do Result := area.capacity end older: INTEGER -- Index of the older element in the history younger: INTEGER -- Index of the younger element in the history to_remove: G -- Last element removed from the history -- by the force function feature -- Element change add (e: G) -- Add a new element in the history require non_void_arguement: e /= Void local new_one: INTEGER l_default: G do if count < size then new_one := free_cells.item (count) count := count + 1 if younger /= -1 then next.put (new_one, younger) else check went_from_empty_to_one: count = 1 end older := new_one end next.put (-1, new_one) previous.put (younger, new_one) younger := new_one area.put (e, new_one) to_remove := l_default else -- we are full: the older must leave new_one := older older := next.item (new_one) previous.put (-1, older) previous.put (younger, new_one) next.put (new_one, younger) next.put (-1, new_one) younger := new_one to_remove := area.item (new_one) area.put (e, new_one) end end make_younger (i: INTEGER) -- Make the element of index i younger -- as it is accessed in the cache require out_of_bound: i <= capacity local next_i, previous_i: INTEGER do if younger /= i then previous_i := previous.item (i) next_i := next.item (i) if i = older then older := next_i previous.put (-1, next_i) else next.put (next_i, previous_i) previous.put (previous_i, next_i) end previous.put (younger, i) next.put (-1, i) next.put (i, younger) younger := i end end remove (i: INTEGER) -- Remove the item of index i from the -- history -- Do not check if i is really a used cell require out_of_bound: i <= capacity local previous_i, next_i: INTEGER l_default: G do area.put (l_default, i) if count > 1 then previous_i := previous.item (i) next_i := next.item (i) if i = older then older := next_i previous.put (-1, next_i) elseif i = younger then younger := previous_i next.put (-1, previous_i) else next.put (next_i, previous_i) previous.put (previous_i, next_i) end count := count - 1 free_cells.put (i, count) else older := -1 younger := -1 count := 0 free_cells.put (i, 0) end end wipe_out, clear_all local int_array: SPECIAL [INTEGER] i: INTEGER l_default: G do count := 0 younger := -1 older := -1 from int_array := free_cells until i = size loop int_array.put (i, i) i := i + 1 end to_remove := l_default next.fill_with (0, 0, next.upper) previous.fill_with (0, 0, previous.upper) end set_item (e: G; i: INTEGER) -- change the item at the index i do area.put (e, i) end valid_content: BOOLEAN -- Is content valid? local l_free_positions: SEARCH_TABLE [INTEGER] i, nb, l_found: INTEGER l_area: like area l_free_cells: like free_cells l_previous: like previous l_next: like next do l_area := area l_free_cells := free_cells nb := capacity create l_free_positions.make (nb - count) from i := count Result := True until i = nb or not Result loop -- add + 1 because 0 cannot be hashed with the old HASH_TABLE. if l_free_positions.has (l_free_cells.item (i) + 1) then Result := False else l_free_positions.put (l_free_cells.item (i) + 1) end i := i + 1 end if Result then from l_previous := previous i := l_previous.lower nb := l_previous.upper l_found := 0 until i > nb loop if not l_free_positions.has (i + 1) then if l_previous.item (i) = -1 then l_found := l_found + 1 end end i := i + 1 end Result := l_found <= 1 if Result then from l_next := next i := l_next.lower nb := l_next.upper l_found := 0 until i > nb loop if not l_free_positions.has (i + 1) then if l_next.item (i) = -1 then l_found := l_found + 1 end end i := i + 1 end Result := l_found <= 1 end end end feature {NONE} -- Implementation area: SPECIAL [G] -- Storage for history invariant consistent_area: area.capacity = area.count older_good: older >= -1 and older <= size younger_good: younger >= -1 and younger <= size count_good: count >= 0 and count <= size valid_content: valid_content note copyright: "Copyright (c) 1984-2011, Eiffel Software" license: "GPL version 2 (see http://www.eiffel.com/licensing/gpl.txt)" licensing_options: "http://www.eiffel.com/licensing" copying: "[ This file is part of Eiffel Software's Eiffel Development Environment. Eiffel Software's Eiffel Development Environment is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2 of the License (available at the URL listed under "license" above). Eiffel Software's Eiffel Development Environment is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with Eiffel Software's Eiffel Development Environment; if not, write to the Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA ]" source: "[ Eiffel Software 5949 Hollister Ave., Goleta, CA 93117 USA Telephone 805-685-1006, Fax 805-685-6869 Website http://www.eiffel.com Customer support http://support.eiffel.com ]" end