James Hawkins : msi: Use a hash table for reordering rows in a WHERE query to conserve space.
Alexandre Julliard
julliard at winehq.org
Mon Dec 3 09:17:51 CST 2007
Module: wine
Branch: master
Commit: 80bbf583780cb5f275b6bb111e5dfd2c71b9ca88
URL: http://source.winehq.org/git/wine.git/?a=commit;h=80bbf583780cb5f275b6bb111e5dfd2c71b9ca88
Author: James Hawkins <truiken at gmail.com>
Date: Sun Dec 2 20:42:25 2007 -0600
msi: Use a hash table for reordering rows in a WHERE query to conserve space.
---
dlls/msi/where.c | 117 +++++++++++++++++++++++++++++++++++++++++++++---------
1 files changed, 98 insertions(+), 19 deletions(-)
diff --git a/dlls/msi/where.c b/dlls/msi/where.c
index 26e4c8f..4029a7f 100644
--- a/dlls/msi/where.c
+++ b/dlls/msi/where.c
@@ -35,6 +35,14 @@
WINE_DEFAULT_DEBUG_CHANNEL(msidb);
+#define MSI_HASH_TABLE_SIZE 37
+
+typedef struct tagMSIHASHENTRY
+{
+ struct tagMSIHASHENTRY *next;
+ UINT value;
+ UINT row;
+} MSIHASHENTRY;
/* below is the query interface to a table */
@@ -44,14 +52,78 @@ typedef struct tagMSIWHEREVIEW
MSIDATABASE *db;
MSIVIEW *table;
UINT row_count;
- UINT *reorder;
+ MSIHASHENTRY **reorder;
struct expr *cond;
UINT rec_index;
} MSIWHEREVIEW;
+static void free_hash_table(MSIHASHENTRY **table)
+{
+ MSIHASHENTRY *new, *old;
+ int i;
+
+ if (!table)
+ return;
+
+ for (i = 0; i < MSI_HASH_TABLE_SIZE; i++)
+ {
+ new = table[i];
+
+ while (new)
+ {
+ old = new;
+ new = old->next;
+ msi_free(old);
+ }
+
+ table[i] = NULL;
+ }
+
+ msi_free(table);
+}
+
+static UINT find_entry_in_hash(MSIHASHENTRY **table, UINT row, UINT *val)
+{
+ MSIHASHENTRY *entry;
+
+ if (!(entry = table[row % MSI_HASH_TABLE_SIZE]))
+ {
+ ERR("Row not found in hash table!\n");
+ return ERROR_FUNCTION_FAILED;
+ }
+
+ while (entry && entry->row != row)
+ entry = entry->next;
+
+ if (entry) *val = entry->value;
+ return ERROR_SUCCESS;
+}
+
+static UINT add_entry_to_hash(MSIHASHENTRY **table, UINT row, UINT val)
+{
+ MSIHASHENTRY *new = msi_alloc(sizeof(MSIHASHENTRY));
+ MSIHASHENTRY *prev;
+
+ if (!new)
+ return ERROR_OUTOFMEMORY;
+
+ new->next = NULL;
+ new->value = val;
+ new->row = row;
+
+ prev = table[row % MSI_HASH_TABLE_SIZE];
+ if (prev)
+ new->next = prev;
+
+ table[row % MSI_HASH_TABLE_SIZE] = new;
+
+ return ERROR_SUCCESS;
+}
+
static UINT WHERE_fetch_int( struct tagMSIVIEW *view, UINT row, UINT col, UINT *val )
{
MSIWHEREVIEW *wv = (MSIWHEREVIEW*)view;
+ UINT r;
TRACE("%p %d %d %p\n", wv, row, col, val );
@@ -61,7 +133,9 @@ static UINT WHERE_fetch_int( struct tagMSIVIEW *view, UINT row, UINT col, UINT *
if( row > wv->row_count )
return ERROR_NO_MORE_ITEMS;
- row = wv->reorder[ row ];
+ r = find_entry_in_hash(wv->reorder, row, &row);
+ if (r != ERROR_SUCCESS)
+ return r;
return wv->table->ops->fetch_int( wv->table, row, col, val );
}
@@ -69,6 +143,7 @@ static UINT WHERE_fetch_int( struct tagMSIVIEW *view, UINT row, UINT col, UINT *
static UINT WHERE_fetch_stream( struct tagMSIVIEW *view, UINT row, UINT col, IStream **stm )
{
MSIWHEREVIEW *wv = (MSIWHEREVIEW*)view;
+ UINT r;
TRACE("%p %d %d %p\n", wv, row, col, stm );
@@ -78,7 +153,9 @@ static UINT WHERE_fetch_stream( struct tagMSIVIEW *view, UINT row, UINT col, ISt
if( row > wv->row_count )
return ERROR_NO_MORE_ITEMS;
- row = wv->reorder[ row ];
+ r = find_entry_in_hash(wv->reorder, row, &row);
+ if (r != ERROR_SUCCESS)
+ return r;
return wv->table->ops->fetch_stream( wv->table, row, col, stm );
}
@@ -86,6 +163,7 @@ static UINT WHERE_fetch_stream( struct tagMSIVIEW *view, UINT row, UINT col, ISt
static UINT WHERE_get_row( struct tagMSIVIEW *view, UINT row, MSIRECORD **rec )
{
MSIWHEREVIEW *wv = (MSIWHEREVIEW *)view;
+ UINT r;
TRACE("%p %d %p\n", wv, row, rec );
@@ -95,7 +173,9 @@ static UINT WHERE_get_row( struct tagMSIVIEW *view, UINT row, MSIRECORD **rec )
if (row > wv->row_count)
return ERROR_NO_MORE_ITEMS;
- row = wv->reorder[row];
+ r = find_entry_in_hash(wv->reorder, row, &row);
+ if (r != ERROR_SUCCESS)
+ return r;
return wv->table->ops->get_row(view, row, rec);
}
@@ -103,6 +183,7 @@ static UINT WHERE_get_row( struct tagMSIVIEW *view, UINT row, MSIRECORD **rec )
static UINT WHERE_set_row( struct tagMSIVIEW *view, UINT row, MSIRECORD *rec, UINT mask )
{
MSIWHEREVIEW *wv = (MSIWHEREVIEW*)view;
+ UINT r;
TRACE("%p %d %p %08x\n", wv, row, rec, mask );
@@ -112,7 +193,9 @@ static UINT WHERE_set_row( struct tagMSIVIEW *view, UINT row, MSIRECORD *rec, UI
if( row > wv->row_count )
return ERROR_NO_MORE_ITEMS;
- row = wv->reorder[ row ];
+ r = find_entry_in_hash(wv->reorder, row, &row);
+ if (r != ERROR_SUCCESS)
+ return r;
return wv->table->ops->set_row( wv->table, row, rec, mask );
}
@@ -264,7 +347,6 @@ static UINT WHERE_evaluate( MSIWHEREVIEW *wv, UINT row,
}
return ERROR_SUCCESS;
-
}
static UINT WHERE_execute( struct tagMSIVIEW *view, MSIRECORD *record )
@@ -287,10 +369,10 @@ static UINT WHERE_execute( struct tagMSIVIEW *view, MSIRECORD *record )
if( r != ERROR_SUCCESS )
return r;
- msi_free( wv->reorder );
- wv->reorder = msi_alloc( count*sizeof(UINT) );
+ free_hash_table(wv->reorder);
+ wv->reorder = msi_alloc_zero(MSI_HASH_TABLE_SIZE * sizeof(MSIHASHENTRY *));
if( !wv->reorder )
- return ERROR_FUNCTION_FAILED;
+ return ERROR_OUTOFMEMORY;
wv->row_count = 0;
if (wv->cond->type == EXPR_STRCMP)
@@ -327,7 +409,7 @@ static UINT WHERE_execute( struct tagMSIVIEW *view, MSIRECORD *record )
{
r = table->ops->find_matching_rows(table, col, value, &row, &handle);
if (r == ERROR_SUCCESS)
- wv->reorder[ wv->row_count ++ ] = row;
+ add_entry_to_hash(wv->reorder, wv->row_count++, row);
} while (r == ERROR_SUCCESS);
if (r == ERROR_NO_MORE_ITEMS)
@@ -346,7 +428,7 @@ static UINT WHERE_execute( struct tagMSIVIEW *view, MSIRECORD *record )
if( r != ERROR_SUCCESS )
return r;
if( val )
- wv->reorder[ wv->row_count ++ ] = i;
+ add_entry_to_hash( wv->reorder, wv->row_count++, i );
}
return ERROR_SUCCESS;
@@ -359,10 +441,7 @@ static UINT WHERE_close( struct tagMSIVIEW *view )
TRACE("%p\n", wv );
if( !wv->table )
- return ERROR_FUNCTION_FAILED;
-
- msi_free( wv->reorder );
- wv->reorder = NULL;
+ return ERROR_FUNCTION_FAILED;
return wv->table->ops->close( wv->table );
}
@@ -422,7 +501,7 @@ static UINT WHERE_delete( struct tagMSIVIEW *view )
wv->table->ops->delete( wv->table );
wv->table = 0;
- msi_free( wv->reorder );
+ free_hash_table(wv->reorder);
wv->reorder = NULL;
wv->row_count = 0;
@@ -444,13 +523,13 @@ static UINT WHERE_find_matching_rows( struct tagMSIVIEW *view, UINT col,
return ERROR_FUNCTION_FAILED;
r = wv->table->ops->find_matching_rows( wv->table, col, val, row, handle );
+ if (r != ERROR_SUCCESS)
+ return r;
if( *row > wv->row_count )
return ERROR_NO_MORE_ITEMS;
- *row = wv->reorder[ *row ];
-
- return r;
+ return find_entry_in_hash(wv->reorder, *row, row);
}
More information about the wine-cvs
mailing list