indexing
	description: "An advertisement LRU cache"
	license: "MIT license (see ../license.txt)"
	author: "Beat Strasser <beat@stradax.net>"
	date: "$Date$"
	revision: "$Revision$"

class
	P2P_ADVERTISEMENTS_LRUCACHE [G -> P2P_ADVERTISEMENT]

inherit
	DT_SHARED_SYSTEM_CLOCK
		export
			{NONE} all
		end

create
	make,
	make_without_capacity_limit

feature {NONE} -- Initialization

	make (a_capacity: like capacity) is
			-- Create a LRU cache
		require
			Capacity_valid: a_capacity > 0
		do
			expiry_check_valid_until := utc_system_clock.date_time_now
			expiry_check_valid_until.add_seconds (expiry_check_interval)
			create lock.make
			create list.make
			capacity := a_capacity
		ensure
			Capacity_set: capacity = a_capacity
		end

	make_without_capacity_limit is
			-- Create a LRU cache without capacity limit
		do
			expiry_check_valid_until := utc_system_clock.date_time_now
			expiry_check_valid_until.add_seconds (expiry_check_interval)
			create lock.make
			create list.make
			capacity := capacity_unlimited
		end

feature -- Access

	capacity: INTEGER

	Capacity_unlimited: INTEGER is -1

	count: INTEGER is
			-- Number of stored advertisements
		do
			remove_expired_advertisements
			Result := list.count
		end

	is_full: BOOLEAN is
			-- Is list full?
		do
			remove_expired_advertisements
			Result := list.count = capacity
		end

	find_all (a_max_count: INTEGER): DS_LIST [G] is
			-- Maximal `a_max_count' number of advertisements. If `a_max_count' is negative, all entries.
		require
			Max_valid: a_max_count /= 0
		local
			equality_tester: KL_EQUALITY_TESTER [G]
			cursor: DS_LINKED_LIST_CURSOR [G]
		do
			remove_expired_advertisements
			lock.lock
			if a_max_count < 0 or a_max_count >= list.count then
				create {DS_ARRAYED_LIST [G]} Result.make_from_linear (list)
			else
				create {DS_ARRAYED_LIST [G]} Result.make (a_max_count)
				from
					cursor := list.new_cursor
					cursor.start
				until
					Result.count = a_max_count or cursor.after
				loop
					Result.put_last (cursor.item)
					cursor.forth
				end
			end
			lock.unlock
			create equality_tester
			Result.set_equality_tester (equality_tester)
		ensure
			Result_set: Result /= Void and (a_max_count < 0 or Result.count <= a_max_count)
		end

	find_matches (a_key, a_value: STRING): DS_LIST [G] is
			-- Matching advertisements
		require
			Key_valid: a_key /= Void and not a_key.is_empty
		local
			cursor: DS_LINKED_LIST_CURSOR [G]
			cur: G
		do
			remove_expired_advertisements
			lock.lock
			create {DS_ARRAYED_LIST [G]} Result.make (list.count)
			-- find matching advertisements
			from
				cursor := list.new_cursor
				cursor.start
			until
				cursor.after
			loop
				cur := cursor.item
				if cur.match (a_key, a_value) then
					Result.put_last (cur)
					-- mark advertisement as recently used (move to head)
					cursor.remove -- also move our cursor forth
					list.put_first (cur)
				else
					cursor.forth
				end
			end
			lock.unlock
		ensure
			Result_set: Result /= Void
		end

	find_advertisement (a_unique_id: STRING): G is
			-- Advertisement with `a_unique_id'
		require
			Unique_id_valid: a_unique_id /= Void
		local
			cursor: DS_LINKED_LIST_CURSOR [G]
		do
			remove_expired_advertisements
			lock.lock
			from
				cursor := list.new_cursor
				cursor.start
			until
				cursor.after
			loop
				if a_unique_id.is_equal (cursor.item.unique_id) then
					Result := cursor.item
					-- mark advertisement as recently used (move to head)
					cursor.remove -- also move forth
					list.put_first (Result)
					cursor.go_after
				else
					cursor.forth
				end
			end
			lock.unlock
		end

	has (an_entry: G): BOOLEAN is
			-- Is the unique id of `an_entry' available in the list? Don't mark found entry as recently used.
		require
			Entry_valid: an_entry /= Void and an_entry.unique_id /= Void
		local
			cursor: DS_LINKED_LIST_CURSOR [G]
		do
			lock.lock
			from
				cursor := list.new_cursor
				cursor.start
			until
				Result or cursor.after
			loop
				if cursor.item.has_expired then
					-- remove expired advertisement
					cursor.remove  -- and move forth
				elseif an_entry.unique_id.is_equal (cursor.item.unique_id) then
					Result := True
				else
					cursor.forth
				end
			end
			if not Result then
				-- we traversed the entire list, so we did a full expiry check
				expiry_check_valid_until := utc_system_clock.date_time_now
				expiry_check_valid_until.add_seconds (expiry_check_interval)
			end
			lock.unlock
		end

	srdi_entries (changed_since: DT_DATE_TIME): DS_LIST [TUPLE [STRING, INTEGER_64, STRING]] is
			-- SRDI index entries of all advertisements (or if `changed_since' is set, of all which changed since `changed_since').
			-- Only advertisements with positive `expiration_time' (valid to the public) will get indexed.
		local
			cursor: DS_LINKED_LIST_CURSOR [G]
			cur: G
			adv_srdi: DS_LIST [TUPLE [STRING, STRING]]
			key, value: STRING
		do
			remove_expired_advertisements
			create {DS_LINKED_LIST [TUPLE [STRING, INTEGER_64, STRING]]} Result.make
			lock.lock
			-- iterate through all advertisements
			from
				cursor := list.new_cursor
				cursor.start
			until
				cursor.after
			loop
				cur := cursor.item
				if cur.expiration_time > 0 and (changed_since = Void or cur.is_newer_than (changed_since)) then
					-- push advertisements index entries to the srdi
					adv_srdi := cur.index_elements
					from
						adv_srdi.start
					until
						adv_srdi.after
					loop
						key ?= adv_srdi.item_for_iteration.item (1)
						value ?= adv_srdi.item_for_iteration.item (2)
						Result.put_last ([key, cur.expiration_time, value])
						adv_srdi.forth
					end
				end
				cursor.forth
			end
			lock.unlock
		ensure
			Result_set: Result /= Void
		end

feature -- Element change

	mark_recently_used, put (an_entry: G) is
			-- Update advertisement with same unique id or add `an_entry' to the list and mark it as recently used
		require
			Entry_valid: an_entry /= Void
		local
			cursor: DS_LINKED_LIST_CURSOR [G]
			found: BOOLEAN
		do
			-- only insert not expired advertisements with valid unique ids
			if an_entry.unique_id /= Void and not an_entry.has_expired then
				lock.lock
				-- search for advertisement with same unique_id
				from
					cursor := list.new_cursor
					cursor.start
				until
					found or cursor.after
				loop
					if an_entry.unique_id.is_equal (cursor.item.unique_id) then
						-- entry found: update advertisement and move to head
						-- we don't allow the new advertisement to decrease the lifetime
						if an_entry.lifetime_absolute /= Void and cursor.item.lifetime_absolute /= Void and
								an_entry.lifetime_absolute < cursor.item.lifetime_absolute then
							an_entry.set_lifetime_from (cursor.item)
						end
						cursor.remove
						list.put_first (an_entry)
						found := True
					elseif cursor.item.has_expired then
						cursor.remove
					else
						cursor.forth
					end
				end
				if not found then
					-- entry not found: add advertisement
					list.put_first (an_entry)
					keep_capacity
				end
				lock.unlock
			end
		end

	load (an_entry: G) is
			-- Load `an_entry' into list marking it as not recently used.
			-- If another entry with the same unique id is already available it won't be updated nor marked as recently used.
		require
			Entry_valid: an_entry /= Void
		do
			if an_entry.unique_id /= Void and not an_entry.has_expired and not is_full then
				lock.lock
				if not list.has (an_entry) then
					list.put_last (an_entry)
				end
				lock.unlock
			end
		end

feature -- Removal

	remove (a_unique_id: STRING) is
			-- Remove the entry with `a_unique_id'
		require
			Entry_valid: a_unique_id /= Void
		local
			cursor: DS_LINKED_LIST_CURSOR [G]
		do
			lock.lock
			from
				cursor := list.new_cursor
				cursor.start
			until
				cursor.after
			loop
				if a_unique_id.is_equal (cursor.item.unique_id) then
					cursor.remove
					cursor.go_after
				else
					cursor.forth
				end
			end
			lock.unlock
		end

	remove_expired_advertisements is
			-- Remove expired advertisements
		local
			cursor: DS_LIST_CURSOR [G]
		do
			if utc_system_clock.date_time_now > expiry_check_valid_until then
				lock.lock
				from
					cursor := list.new_cursor
					cursor.start
				until
					cursor.after
				loop
					if cursor.item.has_expired then
						cursor.remove -- and move forth
					else
						cursor.forth
					end
				end
				expiry_check_valid_until := utc_system_clock.date_time_now
				expiry_check_valid_until.add_seconds (expiry_check_interval)
				lock.unlock
			end
		end

feature -- Resizing

	resize (a_capacity: like capacity) is
			-- Resize
		require
			Capacity_valid: a_capacity > 0
		do
			remove_expired_advertisements
			lock.lock
			capacity := a_capacity
			keep_capacity
			lock.unlock
		ensure
			Capacity_set: capacity = a_capacity
		end

feature {NONE} -- Implementation

	list: DS_LINKED_LIST [G]
	lock: MUTEX

	keep_capacity is
			-- Keep first `capacity' entries
		do
			if capacity > 0 and list.count > capacity then
				list.keep_first (capacity)
			end
		end

	expiry_check_valid_until: DT_DATE_TIME
	Expiry_check_interval: INTEGER is 5 -- 5 seconds

end