Bernhard Loos : msi: Use an array instead of a hashtable for WHEREVIEW.
Alexandre Julliard
julliard at winehq.org
Thu Aug 25 13:00:16 CDT 2011
Module: wine
Branch: master
Commit: 3bd0acf1ba233ff7deb370c7f198a71e29b15799
URL: http://source.winehq.org/git/wine.git/?a=commit;h=3bd0acf1ba233ff7deb370c7f198a71e29b15799
Author: Bernhard Loos <bernhardloos at googlemail.com>
Date: Wed Aug 24 16:42:53 2011 +0200
msi: Use an array instead of a hashtable for WHEREVIEW.
---
dlls/msi/where.c | 150 ++++++++++++++++++++++++------------------------------
1 files changed, 67 insertions(+), 83 deletions(-)
diff --git a/dlls/msi/where.c b/dlls/msi/where.c
index ae31e81..c29c883 100644
--- a/dlls/msi/where.c
+++ b/dlls/msi/where.c
@@ -36,14 +36,10 @@
WINE_DEFAULT_DEBUG_CHANNEL(msidb);
-#define MSI_HASH_TABLE_SIZE 37
-
-typedef struct tagMSIHASHENTRY
+typedef struct tagMSIROWENTRY
{
- struct tagMSIHASHENTRY *next;
UINT value;
- UINT row;
-} MSIHASHENTRY;
+} MSIROWENTRY;
/* below is the query interface to a table */
@@ -53,73 +49,84 @@ typedef struct tagMSIWHEREVIEW
MSIDATABASE *db;
MSIVIEW *table;
UINT row_count;
- MSIHASHENTRY **reorder;
+ MSIROWENTRY **reorder;
+ UINT reorder_size; /* number of entries available in reorder */
struct expr *cond;
UINT rec_index;
} MSIWHEREVIEW;
-static void free_hash_table(MSIHASHENTRY **table)
-{
- MSIHASHENTRY *new, *old;
- int i;
-
- if (!table)
- return;
+#define INITIAL_REORDER_SIZE 16
- for (i = 0; i < MSI_HASH_TABLE_SIZE; i++)
- {
- new = table[i];
+static UINT init_reorder(MSIWHEREVIEW *wv)
+{
+ MSIROWENTRY **new = msi_alloc_zero(sizeof(MSIROWENTRY *) * INITIAL_REORDER_SIZE);
+ if (!new)
+ return ERROR_OUTOFMEMORY;
- while (new)
- {
- old = new;
- new = old->next;
- msi_free(old);
- }
+ if (wv->reorder)
+ msi_free(wv->reorder);
- table[i] = NULL;
- }
+ wv->reorder = new;
+ wv->reorder_size = INITIAL_REORDER_SIZE;
+ wv->row_count = 0;
- msi_free(table);
+ return ERROR_SUCCESS;
}
-static UINT find_entry_in_hash(MSIHASHENTRY **table, UINT row, UINT *val)
+static void free_reorder(MSIWHEREVIEW *wv)
{
- MSIHASHENTRY *entry;
+ UINT i;
- if (!table)
- return ERROR_SUCCESS;
+ if (!wv->reorder)
+ return;
+
+ for (i = 0; i < wv->row_count; i++)
+ msi_free(wv->reorder[i]);
+
+ msi_free( wv->reorder );
+ wv->reorder = NULL;
+ wv->reorder_size = 0;
+ wv->row_count = 0;
+}
- if (!(entry = table[row % MSI_HASH_TABLE_SIZE]))
+static inline UINT find_row(MSIWHEREVIEW *wv, UINT row, UINT *value)
+{
+ if (row >= wv->row_count)
{
- WARN("Row not found in hash table!\n");
- return ERROR_FUNCTION_FAILED;
+ *value = -2;
+ return ERROR_NO_MORE_ITEMS;
}
- while (entry && entry->row != row)
- entry = entry->next;
+ *value = wv->reorder[row]->value;
- if (entry) *val = entry->value;
return ERROR_SUCCESS;
}
-static UINT add_entry_to_hash(MSIHASHENTRY **table, UINT row, UINT val)
+static UINT add_row(MSIWHEREVIEW *wv, UINT val)
{
- MSIHASHENTRY *new = msi_alloc(sizeof(MSIHASHENTRY));
- MSIHASHENTRY *prev;
+ MSIROWENTRY *new;
+
+ if (wv->reorder_size <= wv->row_count)
+ {
+ MSIROWENTRY **new_reorder;
+ UINT newsize = wv->reorder_size * 2;
+
+ new_reorder = msi_realloc_zero(wv->reorder, sizeof(MSIROWENTRY *) * newsize);
+ if (!new_reorder)
+ return ERROR_OUTOFMEMORY;
+
+ wv->reorder = new_reorder;
+ wv->reorder_size = newsize;
+ }
+
+ new = msi_alloc(sizeof(MSIROWENTRY));
if (!new)
return ERROR_OUTOFMEMORY;
- new->next = NULL;
- new->value = val;
- new->row = row;
+ wv->reorder[wv->row_count++] = new;
- prev = table[row % MSI_HASH_TABLE_SIZE];
- if (prev)
- new->next = prev;
-
- table[row % MSI_HASH_TABLE_SIZE] = new;
+ new->value = val;
return ERROR_SUCCESS;
}
@@ -134,10 +141,7 @@ static UINT WHERE_fetch_int( struct tagMSIVIEW *view, UINT row, UINT col, UINT *
if( !wv->table )
return ERROR_FUNCTION_FAILED;
- if( row > wv->row_count )
- return ERROR_NO_MORE_ITEMS;
-
- r = find_entry_in_hash(wv->reorder, row, &row);
+ r = find_row(wv, row, &row);
if (r != ERROR_SUCCESS)
return r;
@@ -154,10 +158,7 @@ static UINT WHERE_fetch_stream( struct tagMSIVIEW *view, UINT row, UINT col, ISt
if( !wv->table )
return ERROR_FUNCTION_FAILED;
- if( row > wv->row_count )
- return ERROR_NO_MORE_ITEMS;
-
- r = find_entry_in_hash(wv->reorder, row, &row);
+ r = find_row(wv, row, &row);
if (r != ERROR_SUCCESS)
return r;
@@ -174,10 +175,7 @@ static UINT WHERE_get_row( struct tagMSIVIEW *view, UINT row, MSIRECORD **rec )
if (!wv->table)
return ERROR_FUNCTION_FAILED;
- if (row > wv->row_count)
- return ERROR_NO_MORE_ITEMS;
-
- r = find_entry_in_hash(wv->reorder, row, &row);
+ r = find_row(wv, row, &row);
if (r != ERROR_SUCCESS)
return r;
@@ -194,10 +192,7 @@ static UINT WHERE_set_row( struct tagMSIVIEW *view, UINT row, MSIRECORD *rec, UI
if( !wv->table )
return ERROR_FUNCTION_FAILED;
- if( row > wv->row_count )
- return ERROR_NO_MORE_ITEMS;
-
- r = find_entry_in_hash(wv->reorder, row, &row);
+ r = find_row(wv, row, &row);
if (r != ERROR_SUCCESS)
return r;
@@ -214,10 +209,7 @@ static UINT WHERE_delete_row(struct tagMSIVIEW *view, UINT row)
if ( !wv->table )
return ERROR_FUNCTION_FAILED;
- if ( row > wv->row_count )
- return ERROR_NO_MORE_ITEMS;
-
- r = find_entry_in_hash( wv->reorder, row, &row );
+ r = find_row( wv, row, &row );
if ( r != ERROR_SUCCESS )
return r;
@@ -396,12 +388,9 @@ static UINT WHERE_execute( struct tagMSIVIEW *view, MSIRECORD *record )
if( r != ERROR_SUCCESS )
return r;
- free_hash_table(wv->reorder);
- wv->reorder = msi_alloc_zero(MSI_HASH_TABLE_SIZE * sizeof(MSIHASHENTRY *));
- if( !wv->reorder )
- return ERROR_OUTOFMEMORY;
-
- wv->row_count = 0;
+ r = init_reorder(wv);
+ if( r != ERROR_SUCCESS )
+ return r;
if (0) /* disable optimization, there's no guarantee that strings are in the string table */
{
@@ -439,7 +428,7 @@ if (0) /* disable optimization, there's no guarantee that strings are in the str
{
r = table->ops->find_matching_rows(table, col, value, &row, &handle);
if (r == ERROR_SUCCESS)
- add_entry_to_hash(wv->reorder, wv->row_count++, row);
+ add_row(wv, row);
} while (r == ERROR_SUCCESS);
if (r == ERROR_NO_MORE_ITEMS)
@@ -459,7 +448,7 @@ if (0) /* disable optimization, there's no guarantee that strings are in the str
if( r != ERROR_SUCCESS )
return r;
if( val )
- add_entry_to_hash( wv->reorder, wv->row_count++, i );
+ add_row( wv, i );
}
return ERROR_SUCCESS;
@@ -517,7 +506,7 @@ static UINT WHERE_modify( struct tagMSIVIEW *view, MSIMODIFY eModifyMode,
TRACE("%p %d %p\n", wv, eModifyMode, rec);
- find_entry_in_hash(wv->reorder, row - 1, &row);
+ find_row(wv, row - 1, &row);
row++;
return wv->table->ops->modify( wv->table, eModifyMode, rec, row );
@@ -533,9 +522,7 @@ static UINT WHERE_delete( struct tagMSIVIEW *view )
wv->table->ops->delete( wv->table );
wv->table = 0;
- free_hash_table(wv->reorder);
- wv->reorder = NULL;
- wv->row_count = 0;
+ free_reorder(wv);
msiobj_release( &wv->db->hdr );
msi_free( wv );
@@ -558,10 +545,7 @@ static UINT WHERE_find_matching_rows( struct tagMSIVIEW *view, UINT col,
if (r != ERROR_SUCCESS)
return r;
- if( *row > wv->row_count )
- return ERROR_NO_MORE_ITEMS;
-
- return find_entry_in_hash(wv->reorder, *row, row);
+ return find_row(wv, *row, row);
}
static UINT WHERE_sort(struct tagMSIVIEW *view, column_info *columns)
More information about the wine-cvs
mailing list