James Hawkins : msi: Use a hash table for reordering rows in a WHERE query to conserve space.
Module: wine Branch: master Commit: 80bbf583780cb5f275b6bb111e5dfd2c71b9ca88 URL: http://source.winehq.org/git/wine.git/?a=commit;h=80bbf583780cb5f275b6bb111e... Author: James Hawkins <truiken(a)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); }
participants (1)
-
Alexandre Julliard