*
* Copyright 2002-2004, Mike McCormack for CodeWeavers
* Copyright 2007 Robert Shearman for CodeWeavers
+ * Copyright 2010 Hans Leidekker for CodeWeavers
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
WINE_DEFAULT_DEBUG_CHANNEL(msidb);
-#define HASH_SIZE 0x101
-#define LONG_STR_BYTES 3
-
typedef struct _msistring
{
- int hash_next;
- UINT persistent_refcount;
- UINT nonpersistent_refcount;
+ USHORT persistent_refcount;
+ USHORT nonpersistent_refcount;
LPWSTR str;
} msistring;
UINT maxcount; /* the number of strings */
UINT freeslot;
UINT codepage;
- int hash[HASH_SIZE];
- msistring *strings; /* an array of strings (in the tree) */
+ UINT sortcount;
+ msistring *strings; /* an array of strings */
+ UINT *sorted; /* index */
};
-static UINT msistring_makehash( const WCHAR *str )
-{
- UINT hash = 0;
-
- if (str==NULL)
- return hash;
-
- while( *str )
- {
- hash ^= *str++;
- hash *= 53;
- hash = (hash<<5) | (hash>>27);
- }
- return hash % HASH_SIZE;
-}
-
static string_table *init_stringtable( int entries, UINT codepage )
{
string_table *st;
- int i;
if (codepage != CP_ACP && !IsValidCodePage(codepage))
{
return NULL;
if( entries < 1 )
entries = 1;
+
st->strings = msi_alloc_zero( sizeof (msistring) * entries );
if( !st->strings )
{
msi_free( st );
return NULL;
}
+
+ st->sorted = msi_alloc( sizeof (UINT) * entries );
+ if( !st->sorted )
+ {
+ msi_free( st->strings );
+ msi_free( st );
+ return NULL;
+ }
+
st->maxcount = entries;
st->freeslot = 1;
st->codepage = codepage;
-
- for( i=0; i<HASH_SIZE; i++ )
- st->hash[i] = -1;
+ st->sortcount = 0;
return st;
}
msi_free( st->strings[i].str );
}
msi_free( st->strings );
+ msi_free( st->sorted );
msi_free( st );
}
static int st_find_free_entry( string_table *st )
{
- UINT i, sz;
+ UINT i, sz, *s;
msistring *p;
TRACE("%p\n", st);
p = msi_realloc_zero( st->strings, sz*sizeof(msistring) );
if( !p )
return -1;
+
+ s = msi_realloc( st->sorted, sz*sizeof(UINT) );
+ if( !s )
+ {
+ msi_free( p );
+ return -1;
+ }
+
st->strings = p;
+ st->sorted = s;
+
st->freeslot = st->maxcount;
st->maxcount = sz;
if( st->strings[st->freeslot].persistent_refcount ||
return st->freeslot;
}
-static void set_st_entry( string_table *st, UINT n, LPWSTR str, UINT refcount, enum StringPersistence persistence )
+static int find_insert_index( const string_table *st, UINT string_id )
{
- UINT hash = msistring_makehash( str );
+ int i, c, low = 0, high = st->sortcount - 1;
+
+ while (low <= high)
+ {
+ i = (low + high) / 2;
+ c = lstrcmpW( st->strings[string_id].str, st->strings[st->sorted[i]].str );
+ if (c < 0)
+ high = i - 1;
+ else if (c > 0)
+ low = i + 1;
+ else
+ return -1; /* already exists */
+ }
+ return high + 1;
+}
+
+static void insert_string_sorted( string_table *st, UINT string_id )
+{
+ int i;
+
+ i = find_insert_index( st, string_id );
+ if (i == -1)
+ return;
+
+ memmove( &st->sorted[i] + 1, &st->sorted[i], (st->sortcount - i) * sizeof(UINT) );
+ st->sorted[i] = string_id;
+ st->sortcount++;
+}
+
+static void set_st_entry( string_table *st, UINT n, LPWSTR str, USHORT refcount, enum StringPersistence persistence )
+{
if (persistence == StringPersistent)
{
st->strings[n].persistent_refcount = refcount;
st->strings[n].str = str;
- st->strings[n].hash_next = st->hash[hash];
- st->hash[hash] = n;
+ insert_string_sorted( st, n );
if( n < st->maxcount )
st->freeslot = n + 1;
return r;
}
-static int msi_addstring( string_table *st, UINT n, const CHAR *data, int len, UINT refcount, enum StringPersistence persistence )
+static int msi_addstring( string_table *st, UINT n, const CHAR *data, int len, USHORT refcount, enum StringPersistence persistence )
{
LPWSTR str;
int sz;
return n;
}
-int msi_addstringW( string_table *st, UINT n, const WCHAR *data, int len, UINT refcount, enum StringPersistence persistence )
+int msi_addstringW( string_table *st, const WCHAR *data, int len, USHORT refcount, enum StringPersistence persistence )
{
+ UINT n;
LPWSTR str;
- /* TRACE("[%2d] = %s\n", string_no, debugstr_an(data,len) ); */
-
if( !data )
return 0;
if( !data[0] )
return 0;
- if( n > 0 )
- {
- if( st->strings[n].persistent_refcount ||
- st->strings[n].nonpersistent_refcount )
- return -1;
- }
- else
+
+ if( msi_string2idW( st, data, &n ) == ERROR_SUCCESS )
{
- if( ERROR_SUCCESS == msi_string2idW( st, data, &n ) )
- {
- if (persistence == StringPersistent)
- st->strings[n].persistent_refcount += refcount;
- else
- st->strings[n].nonpersistent_refcount += refcount;
- return n;
- }
- n = st_find_free_entry( st );
- if( n == -1 )
- return -1;
+ if (persistence == StringPersistent)
+ st->strings[n].persistent_refcount += refcount;
+ else
+ st->strings[n].nonpersistent_refcount += refcount;
+ return n;
}
- if( n < 1 )
- {
- ERR("invalid index adding %s (%d)\n", debugstr_w( data ), n );
+ n = st_find_free_entry( st );
+ if( n == -1 )
return -1;
- }
/* allocate a new string */
if(len<0)
*/
UINT msi_string2idW( const string_table *st, LPCWSTR str, UINT *id )
{
- UINT n, hash = msistring_makehash( str );
- msistring *se = st->strings;
+ int i, c, low = 0, high = st->sortcount - 1;
- for (n = st->hash[hash]; n != -1; n = st->strings[n].hash_next )
+ while (low <= high)
{
- if ((str == se[n].str) || !lstrcmpW(str, se[n].str))
+ i = (low + high) / 2;
+ c = lstrcmpW( str, st->strings[st->sorted[i]].str );
+
+ if (c < 0)
+ high = i - 1;
+ else if (c > 0)
+ low = i + 1;
+ else
{
- *id = n;
+ *id = st->sorted[i];
return ERROR_SUCCESS;
}
}
return st;
}
-UINT msi_save_string_table( const string_table *st, IStorage *storage )
+UINT msi_save_string_table( const string_table *st, IStorage *storage, UINT *bytes_per_strref )
{
UINT i, datasize = 0, poolsize = 0, sz, used, r, codepage, n;
UINT ret = ERROR_FUNCTION_FAILED;
used = 0;
codepage = st->codepage;
- pool[0]=codepage&0xffff;
- pool[1]=(codepage>>16);
+ pool[0] = codepage & 0xffff;
+ pool[1] = codepage >> 16;
+ if (st->maxcount > 0xffff)
+ {
+ pool[1] |= 0x8000;
+ *bytes_per_strref = LONG_STR_BYTES;
+ }
+ else
+ *bytes_per_strref = sizeof(USHORT);
+
n = 1;
for( i=1; i<st->maxcount; i++ )
{
projects / reactos.git / blobdiff