Index: trunk/lib/Makefile
===================================================================
--- trunk/lib/Makefile	(revision 107)
+++ trunk/lib/Makefile	(revision 108)
@@ -3,5 +3,5 @@
 ################################################################################
 
-FILES=regfi.o smb_deps.o void_stack.o range_list.o
+FILES=regfi.o smb_deps.o void_stack.o range_list.o lru_cache.o
 
 all: $(FILES)
@@ -19,4 +19,7 @@
 	$(CC) $(CFLAGS) $(OPTS) $(INC) -c -o $@ range_list.c
 
+lru_cache.o: lru_cache.c
+	$(CC) $(CFLAGS) $(OPTS) $(INC) -c -o $@ lru_cache.c
+
 clean:
 	rm -f $(FILES)
Index: trunk/lib/lru_cache.c
===================================================================
--- trunk/lib/lru_cache.c	(revision 108)
+++ trunk/lib/lru_cache.c	(revision 108)
@@ -0,0 +1,361 @@
+/*
+ * Copyright (C) 2008 Timothy D. Morgan
+ *
+ * This program 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 3 of the License.
+ * 
+ * This program 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 this program; if not, write to the Free Software
+ * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  
+ *
+ * $Id: $
+ */
+
+#include "../include/lru_cache.h"
+
+
+#define LRU_CACHE_DEBUG 0
+
+/* XXX: really should replace this with a real universal hash or other
+ *      fast HMAC.
+ */ 
+static uint32_t lru_cache_compute_hash(uint32_t num_buckets,
+				       uint32_t secret,
+				       const void* buf,
+				       uint32_t buf_len)
+{
+  uint32_t i;
+  uint32_t ret_val = 0x243f6a88;
+  unsigned char* s = (unsigned char*)&secret;
+  const unsigned char* b = (unsigned char*)buf;
+
+  for(i=0; i<buf_len; i++)
+    ret_val = (ret_val+(i^s[i%4])*b[i]) % num_buckets;
+  
+  return ret_val;
+}
+
+/* Returns approximately floor(log_2(n)) (log base 2 of n, floored) 
+ * If n == 0, returns 0
+ */
+static uint32_t lru_cache_floor_log2(uint32_t n)
+{
+  uint32_t ret_val;
+  
+  for(ret_val=31; ret_val > 1; ret_val--)
+    if((n & (1 << ret_val)) != 0)
+      return ret_val;
+
+  return 0;
+}
+
+
+static void lru_cache_print(lru_cache* ht)
+{
+  uint32_t i;
+  lru_cache_element* cur;
+
+  printf("from newest to oldest:\n");
+  for(cur=ht->newest; cur != NULL; cur=cur->older)
+  {
+    /*    write(STDOUT_FILENO, cur->index, cur->index_len);*/
+    printf("%p", (void*)cur);
+    printf("\n");
+    if(cur->older == ht->newest)
+    {
+      printf("??? Loop in LRU list!!");
+      break;
+    }
+  }
+  printf("\n");
+
+  printf("table:\n");
+  for(i=0; i<ht->num_buckets; i++)
+  {
+    printf("%.8X: ", i);
+    for(cur=ht->table[i]; cur != NULL; cur=cur->next)
+    {
+      /*      write(STDOUT_FILENO, cur->index, cur->index_len);*/
+      printf("%p", (void*)cur);
+      printf("|");
+
+      if(cur->next == ht->table[i])
+      {
+	printf("??? Loop in table chain!!");
+	break;
+      }
+    }
+    printf("\n");
+  }
+}
+
+
+lru_cache* lru_cache_create(uint32_t max_keys, uint32_t secret, bool free_data)
+{
+  lru_cache* ret_val;
+
+  if(max_keys < 2)
+    return NULL;
+
+  ret_val = (lru_cache*)malloc(sizeof(lru_cache));
+  if(ret_val == NULL)
+    return NULL;
+
+  ret_val->num_buckets = max_keys/lru_cache_floor_log2(max_keys);
+  if(ret_val->num_buckets < 1)
+    ret_val->num_buckets = 1;
+  
+  ret_val->table 
+    = (lru_cache_element**)malloc(sizeof(lru_cache_element*) 
+				  * ret_val->num_buckets);
+  if(ret_val->table == NULL)
+  {
+    free(ret_val);
+    return NULL;
+  }
+  
+  ret_val->oldest = NULL;
+  ret_val->newest = NULL;
+  ret_val->max_keys = max_keys;
+  ret_val->secret = secret;
+  ret_val->free_data = free_data;
+  ret_val->num_keys = 0;
+  memset(ret_val->table, 0, ret_val->num_buckets*sizeof(lru_cache_element*));
+
+  return ret_val;
+}
+
+
+void lru_cache_destroy(lru_cache* ht)
+{
+  lru_cache_element* cur;
+  lru_cache_element* last = NULL;
+  
+  for(cur=ht->oldest; cur != NULL; last=cur,cur=cur->newer)
+  {
+    if(last != NULL)
+    {
+      if(ht->free_data)
+	free(last->data);
+      free(last->index);
+      free(last);
+    }
+  }
+  free(ht->table);
+  ht->secret = 0;
+  free(ht);
+}
+
+
+
+bool lru_cache_update(lru_cache* ht, const void* index, 
+		      uint32_t index_len, void* data)
+{
+  uint32_t hash, lru_hash;
+  lru_cache_element* cur;
+  lru_cache_element* last = NULL;
+  lru_cache_element* e = NULL;
+  void* tmp_index;
+
+  hash = lru_cache_compute_hash(ht->num_buckets, ht->secret, index, index_len);
+  for(cur = ht->table[hash]; cur != NULL && e == NULL; cur=cur->next)
+  {
+    if((index_len == cur->index_len) 
+       && memcmp(cur->index, index, index_len) == 0)
+    { e = cur; }
+  }
+  
+  if(e != NULL)
+  { /* We found the index, so we're going to overwrite the data.
+     * We also need to reposition the element to the newest position,
+     * so remove it from the list for now.
+     */
+    if(ht->free_data)
+      free(e->data);
+
+    if(e->newer == NULL)
+      ht->newest = e->older;
+    else
+      e->newer->older = e->older;
+
+    if(e->older == NULL)
+      ht->oldest = e->newer;
+    else
+      e->older->newer = e->newer;
+  }
+  else
+  { /* We didn't find an identical index. */
+    
+    if(ht->num_keys >= ht->max_keys)
+    { /* Eliminate the least recently used item, but reuse the element
+       * structure to minimize reallocation. 
+       */
+      e = ht->oldest;
+      if(ht->newest == ht->oldest)
+      {
+	ht->newest = NULL;
+	ht->oldest = NULL;
+      }
+      else
+      {
+	ht->oldest = e->newer;
+	e->newer->older = NULL;
+      }
+      e->newer = NULL;
+      e->older = NULL;
+
+      last = NULL;
+      lru_hash = lru_cache_compute_hash(ht->num_buckets, ht->secret, 
+					e->index, e->index_len);
+      for(cur = ht->table[lru_hash]; cur != e && cur != NULL; 
+	  last=cur, cur=cur->next)
+      {	continue; }
+
+      if(last == NULL)
+	ht->table[lru_hash] = e->next;
+      else
+	last->next = e->next;
+      e->next = NULL;
+
+      if(ht->free_data)
+	free(e->data);
+
+      tmp_index = realloc(e->index, index_len);
+      if(tmp_index == NULL)
+      {
+	free(e->index);
+	free(e);
+	return false;
+      }
+    }
+    else
+    { /* Brand new element because we have room to spare. */
+
+      e = (lru_cache_element*)malloc(sizeof(lru_cache_element));
+      if(e == NULL)
+	return false;
+      
+      e->index = malloc(index_len);
+      if(e->index == NULL)
+      {
+	free(e);
+	return false;
+      }
+      
+      /* New entry, increment counters. */
+      ht->num_keys++;
+    }
+    memcpy(e->index, index, index_len);
+    e->index_len = index_len;
+
+    /* Insert at beginning of chain, in a vaguely LRU style */
+    e->next = ht->table[hash];
+    ht->table[hash] = e;
+  }
+  e->data = data;
+
+  /* Finally, let's insert the element to the newest position in the LRU list.*/
+  if(ht->newest != NULL)
+    ht->newest->newer = e;
+  e->newer = NULL;
+  e->older = ht->newest;
+  ht->newest = e;
+  if(ht->oldest == NULL)
+    ht->oldest = e;
+
+  return true;
+}
+
+
+void* lru_cache_find(lru_cache* ht, const void* index,
+		     uint32_t index_len)
+{
+  uint32_t hash;
+  lru_cache_element* cur;
+
+  hash = lru_cache_compute_hash(ht->num_buckets, ht->secret, index, index_len);
+  for(cur = ht->table[hash]; (cur != NULL); cur = cur->next)
+  {
+    if((index_len == cur->index_len)
+       && memcmp(cur->index, index, index_len) == 0)
+    { break; }
+  }
+  
+  if(cur != NULL && cur->newer != NULL)
+  { /* Need to move this element up to the newest slot. */
+
+    cur->newer->older = cur->older;
+
+    if(cur->older == NULL)
+      ht->oldest = cur->newer;
+    else
+      cur->older->newer = cur->newer;
+
+    cur->newer = NULL;
+    cur->older = ht->newest;
+    ht->newest->newer = cur;
+    ht->newest = cur;
+  }
+
+  if(cur != NULL)
+    return cur->data;
+  else
+    return NULL;
+}
+
+
+
+bool lru_cache_remove(lru_cache* ht, const void* index, 
+		      uint32_t index_len)
+{
+  uint32_t hash;
+  lru_cache_element* cur;
+  lru_cache_element* last = NULL;
+
+  hash = lru_cache_compute_hash(ht->num_buckets, ht->secret,
+				index, index_len);
+  for(cur=ht->table[hash]; (cur != NULL);
+      last=cur, cur=cur->next)
+  {
+    if((index_len == cur->index_len) 
+       && memcmp(cur->index, index, index_len) == 0)
+    { break; }
+  }
+
+  if(cur == NULL)
+    return false;
+
+  if(ht->free_data)
+    free(cur->data);
+
+  /* Detach from list */
+  if(cur->newer == NULL)
+    ht->newest = cur->older;
+  else
+    cur->newer->older = cur->older;
+  
+  if(cur->older == NULL)
+    ht->oldest = cur->newer;
+  else
+    cur->older->newer = cur->newer;
+
+  /* Detach from hash table */
+  if(last == NULL)
+    ht->table[hash] = cur->next;
+  else
+    last->next = cur->next;
+
+  free(cur->index);
+  free(cur);
+  
+  /* Removing entry, decrement counters. */
+  ht->num_keys--;
+  
+  return true;
+}
Index: trunk/lib/regfi.c
===================================================================
--- trunk/lib/regfi.c	(revision 107)
+++ trunk/lib/regfi.c	(revision 108)
@@ -682,20 +682,5 @@
 
 /*******************************************************************
- *******************************************************************/
-static REGF_SK_REC* find_sk_record_by_offset( REGF_FILE *file, uint32 offset )
-{
-  REGF_SK_REC *p_sk;
-  
-  for ( p_sk=file->sec_desc_list; p_sk; p_sk=p_sk->next ) {
-    if ( p_sk->sk_off == offset ) 
-      return p_sk;
-  }
-  
-  return NULL;
-}
-
-
-/*******************************************************************
- *******************************************************************/
+
 static REGF_SK_REC* find_sk_record_by_sec_desc( REGF_FILE *file, SEC_DESC *sd )
 {
@@ -707,9 +692,8 @@
   }
 
-  /* failure */
 
   return NULL;
 }
-
+ *******************************************************************/
 
 /*******************************************************************
@@ -798,5 +782,6 @@
   /* get the security descriptor.  First look if we have already parsed it */
   if((nk->sk_off!=REGF_OFFSET_NONE)
-     && !(nk->sec_desc = find_sk_record_by_offset( file, nk->sk_off )))
+     && !(nk->sec_desc = (REGF_SK_REC*)lru_cache_find(file->sk_recs, 
+						      &nk->sk_off, 4)))
   {
     sub_hbin = hbin;
@@ -826,7 +811,5 @@
     nk->sec_desc->sk_off = nk->sk_off;
     
-    /* add to the list of security descriptors (ref_count has been read from the files) */
-    /* XXX: this kind of caching needs to be re-evaluated */
-    DLIST_ADD( file->sec_desc_list, nk->sec_desc );
+    lru_cache_update(file->sk_recs, &nk->sk_off, 4, nk->sec_desc);
   }
   
@@ -919,4 +902,7 @@
     return NULL;
   }
+  
+  /* TODO: come up with a better secret. */
+  rb->sk_recs = lru_cache_create(127, 0xDEADBEEF, true);
 
   rla = true;
@@ -955,4 +941,6 @@
     free(range_list_get(file->unalloc_cells, i)->data);
   range_list_free(file->unalloc_cells);
+
+  lru_cache_destroy(file->sk_recs);
 
   free(file);
