Better understanding the LRU algorithm

I need to implement a LRU algorithm in a 3D renderer for texture caching. I write the code in C++ on Linux.

In my case I will use texture caching to store "tiles" of image data (16x16 pixels block). Now imagine that I do a lookup in the cache, get a hit (tile is in the cache). How do I return the content of the "cache" for that entry to the function caller? I explain. I imagine that when I load a tile in the cache memory, I allocate the memory to store 16x16 pixels for example, then load the image data for that tile. Now there's two solutions to pass the content of the cache entry to the function caller:
1) either as pointer to the tile data (fast, memory efficient),
```
TileData *tileData = cache->lookup(tileId); // not safe?
```
2) or I need to recopy the tile data from the cache within a memory space allocated by the function caller (copy can be slow).
```
void Cache::lookup(int tileId, float *&tileData)
{
   // find tile in cache, if not in cache load from disk add to cache, ...
   ...
   // now copy tile data, safe but ins't that slow?
   memcpy((char*)tileData, tileDataFromCache, sizeof(float) * 3 * 16 * 16);
}
float *tileData = new float[3 * 16 * 16]; // need to allocate the memory for that tile
// get tile data from cache, requires a copy
cache->lookup(tileId, tileData);
```
I would go with 1) but the problem is, what happens if the tile gets deleted from the cache just after the lookup, and that the function tries to access the data using the return pointer? The only solution I see to this, is to use a form of referencing counting (auto_ptr) where the data is actually only deleted when it's not used anymore?
the application might access more than 1 texture. I can't seem to find of a way of creating a key which is unique to each texture and each tile of a texture. For example I may have tile 1 from file1 and tile1 from file2 in the cache, so making the search on tildId=1 is not enough... but I can't seem to find a way of creating the key that accounts for the file name and the tileID. I can build a string that would contain the file name and the tileID (FILENAME_TILEID) but wouldn't a string used as a key be much slower than an integer?
Finally I have a question regarding time stamp. Many papers suggest to use a time stamp for ordering the entry in the cache. What is a good function to use a time stamp? the time() function, clock()? Is there a better way than using time stamps?

Sorry I realise it's a very long message, but LRU doesn't seem as simple to implement than it sounds.

Solution

Answers to your questions:

1) Return a shared_ptr (or something logically equivalent to it). Then all of the "when-is-it-safe-to-delete-this-object" issues pretty much go away.

2) I'd start by using a string as a key, and see if it actually is too slow or not. If the strings aren't too long (e.g. your filenames aren't too long) then you may find it's faster than you expect. If you do find out that string-keys aren't efficient enough, you could try something like computing a hashcode for the string and adding the tile ID to it... that would probably work in practice although there would always be the possibility of a hash-collision. But you could have a collision-check routine run at startup that would generate all of the possible filename+tileID combinations and alert you if map to the same key value, so that at least you'd know immediately during your testing when there is a problem and could do something about it (e.g. by adjusting your filenames and/or your hashcode algorithm). This assumes that what all the filenames and tile IDs are going to be known in advance, of course.

3) I wouldn't recommend using a timestamp, it's unnecessary and fragile. Instead, try something like this (pseudocode):

typedef shared_ptr<TileData *> TileDataPtr;   // automatic memory management!

linked_list<TileDataPtr> linkedList;
hash_map<data_key_t, TileDataPtr> hashMap;

// This is the method the calling code would call to get its tile data for a given key
TileDataPtr GetData(data_key_t theKey)
{
   if (hashMap.contains_key(theKey))
   {
      // The desired data is already in the cache, great!  Just move it to the head
      // of the LRU list (to reflect its popularity) and then return it.
      TileDataPtr ret = hashMap.get(theKey);
      linkedList.remove(ret);     // move this item to the head
      linkedList.push_front(ret); // of the linked list -- this is O(1)/fast
      return ret;
   }
   else
   {
      // Oops, the requested object was not in our cache, load it from disk or whatever
      TileDataPtr ret = LoadDataFromDisk(theKey);
      linkedList.push_front(ret);
      hashMap.put(theKey, ret);

      // Don't let our cache get too large -- delete
      // the least-recently-used item if necessary
      if (linkedList.size() > MAX_LRU_CACHE_SIZE)
      {
         TileDataPtr dropMe = linkedList.tail();
         hashMap.remove(dropMe->GetKey());
         linkedList.remove(dropMe);
      }
      return ret;
   }
}