Changeset 106 for trunk

Timestamp:

04/18/08 00:16:51 (17 years ago)

Author:

tim

Message:

replaced linked list hbin lookup with range_list based binary search

Location:

trunk

Files:

• include/range_list.h (modified) (2 diffs)
• include/regfi.h (modified) (2 diffs)
• lib/range_list.c (modified) (1 diff)
• lib/regfi.c (modified) (13 diffs)

trunk/include/range_list.h

@@ -54 +54 @@
 /* range_list_free(): 
  *  Frees the memory associated with a range_list, including the elements, but
- *  not any data parameters referenced by those elements.
+ *  not any data parameters referenced by those elements.  If rl is NULL, does
+ *  nothing.
  *
  * Arguments:
@@ -82 +83 @@
  *  rl     -- the range list to update
  *  offset -- the starting point for the range
- *  length -- the lenght of the range
+ *  length -- the length of the range
  *  data   -- misc data associated with this range element
  * Returns:

trunk/include/regfi.h

@@ -109 +109 @@
 
 /* HBIN block */
-struct regf_hbin;
 typedef struct regf_hbin 
 {
-  struct regf_hbin* prev;
-  struct regf_hbin* next;
   uint32 file_off;       /* my offset in the registry file */
   uint32 ref_count;      /* how many active records are pointing to this
@@ -260 +257 @@
   uint32 file_length;
   void* mem_ctx;  /* memory context for run-time file access information */
-  REGF_HBIN* block_list; /* list of open hbin blocks */
 
   /* Experimental hbin lists */

trunk/lib/range_list.c

@@ -148 +148 @@
 {
   uint32_t i;
+
+  if(rl == NULL)
+    return;
+
   for(i=0; i < rl->size; i++)
     free(rl->elements[i]);

trunk/lib/regfi.c

@@ -413 +413 @@
 
 /*******************************************************************
- Input a random offset and receive the correpsonding HBIN 
- block for it
-*******************************************************************/
-static bool hbin_contains_offset( REGF_HBIN *hbin, uint32 offset )
-{
-  if ( !hbin )
+ * Given an offset and an hbin, is the offset within that hbin?
+ * The offset is a virtual file offset.
+ *******************************************************************/
+static bool regfi_offset_in_hbin(REGF_HBIN* hbin, uint32 offset)
+{
+  if(!hbin)
     return false;
-        
-  if ( (offset > hbin->first_hbin_off) && (offset < (hbin->first_hbin_off+hbin->block_size)) )
+
+  if((offset > hbin->first_hbin_off) 
+     && (offset < (hbin->first_hbin_off + hbin->block_size)))
     return true;
                 
@@ -428 +429 @@
 
 
+
 /*******************************************************************
- Input a random offset and receive the correpsonding HBIN 
- block for it
-*******************************************************************/
-static REGF_HBIN* lookup_hbin_block( REGF_FILE *file, uint32 offset )
-{
-  REGF_HBIN *hbin = NULL;
-  uint32 block_off;
-
-  /* start with the open list */
-
-  for ( hbin=file->block_list; hbin; hbin=hbin->next ) {
-    /* DEBUG(10,("lookup_hbin_block: address = 0x%x [0x%x]\n", hbin->file_off, (uint32)hbin ));*/
-    if ( hbin_contains_offset( hbin, offset ) )
-      return hbin;
-  }
-        
-  if ( !hbin ) {
-    /* start at the beginning */
-
-    block_off = REGF_BLOCKSIZE;
-    do {
-      hbin = regfi_parse_hbin(file, block_off, true, false);
-
-      if ( hbin ) 
-        block_off = hbin->file_off + hbin->block_size;
-
-    } while ( hbin && !hbin_contains_offset( hbin, offset ) );
-  }
-
-  if ( hbin )
-    /* XXX: this kind of caching needs to be re-evaluated */
-    DLIST_ADD( file->block_list, hbin );
-
-  return hbin;
+ * Given a virtual offset, and receive the correpsonding HBIN 
+ * block for it.  NULL if one doesn't exist.
+ *******************************************************************/
+static REGF_HBIN* regfi_lookup_hbin(REGF_FILE* file, uint32 offset)
+{
+  return (REGF_HBIN*)range_list_find_data(file->hbins, offset+REGF_BLOCKSIZE);
 }
 
@@ -683 +657 @@
     vk_raw_offset = IVAL(buf, i*4);
     
-    sub_hbin = lookup_hbin_block(file, vk_raw_offset);
+    sub_hbin = regfi_lookup_hbin(file, vk_raw_offset);
     if (!sub_hbin)
     {
@@ -740 +714 @@
 
 /*******************************************************************
+ * TODO: Need to add full key and SK record caching using a 
+ *       custom cache structure.
  *******************************************************************/
 REGF_NK_REC* regfi_load_key(REGF_FILE *file, uint32 offset, bool strict)
@@ -748 +724 @@
   uint32 max_length, off;
 
-  hbin = lookup_hbin_block(file, offset-REGF_BLOCKSIZE);
+  hbin = regfi_lookup_hbin(file, offset-REGF_BLOCKSIZE);
   if (hbin == NULL) 
     return NULL;
@@ -761 +737 @@
   {
     sub_hbin = hbin;
-    if(!hbin_contains_offset(hbin, nk->values_off)) 
-      sub_hbin = lookup_hbin_block(file, nk->values_off);
+    if(!regfi_offset_in_hbin(hbin, nk->values_off)) 
+      sub_hbin = regfi_lookup_hbin(file, nk->values_off);
     
     if(sub_hbin == NULL)
@@ -792 +768 @@
   {
     sub_hbin = hbin;
-    if(!hbin_contains_offset(hbin, nk->subkeys_off))
-      sub_hbin = lookup_hbin_block(file, nk->subkeys_off);
+    if(!regfi_offset_in_hbin(hbin, nk->subkeys_off))
+      sub_hbin = regfi_lookup_hbin(file, nk->subkeys_off);
 
     if (sub_hbin == NULL) 
@@ -825 +801 @@
   {
     sub_hbin = hbin;
-    if(!hbin_contains_offset(hbin, nk->sk_off))
-      sub_hbin = lookup_hbin_block(file, nk->sk_off);
+    if(!regfi_offset_in_hbin(hbin, nk->sk_off))
+      sub_hbin = regfi_lookup_hbin(file, nk->sk_off);
 
     if(sub_hbin == NULL)
@@ -910 +886 @@
 {
   REGF_FILE* rb;
+  REGF_HBIN* hbin = NULL;
+  uint32 hbin_off;
   int fd;
   int flags = O_RDONLY;
+  bool rla;
 
   /* open an existing file */
@@ -932 +911 @@
   if((rb->hbins == NULL) || (rb->unalloc_cells == NULL))
   {
+    range_list_free(rb->hbins);
+    range_list_free(rb->unalloc_cells);
     close(fd);
     free(rb);
     return NULL;
+  }
+
+  rla = true;
+  hbin_off = REGF_BLOCKSIZE;
+  hbin = regfi_parse_hbin(rb, hbin_off, true, false);
+  while(hbin && rla)
+  {
+    hbin_off = hbin->file_off + hbin->block_size;
+    rla = range_list_add(rb->hbins, hbin->file_off, hbin->block_size, hbin);
+    hbin = regfi_parse_hbin(rb, hbin_off, true, false); 
   }
 
@@ -947 +938 @@
 {
   int fd;
+  uint32 i;
 
   /* nothing to do if there is no open file */
@@ -954 +946 @@
   fd = file->fd;
   file->fd = -1;
+  for(i=0; i < range_list_size(file->hbins); i++)
+    free(range_list_get(file->hbins, i)->data);
   range_list_free(file->hbins);
+
+  for(i=0; i < range_list_size(file->unalloc_cells); i++)
+    free(range_list_get(file->unalloc_cells, i)->data);
   range_list_free(file->unalloc_cells);
+
   free(file);
 
-  return close( fd );
+  return close(fd);
 }
 
@@ -1321 +1319 @@
 }
 
-
-
-/****************/
-/* Experimental */
-/****************/
-/*
-typedef struct {
-  uint32 offset;
-  uint32 size;
-} REGFI_CELL_INFO;
-
-typedef struct {
-  uint32 count
-  REGFI_CELL_INFO** cells;
-} REGFI_CELL_LIST;
-*/