dlls/setupapi/stringtable.c

   1 /*
   2  * Setupapi string table functions
   3  *
   4  * Copyright 2005 Eric Kohl
   5  * Copyright 2014 Nikolay Sivov for CodeWeavers
   6  *
   7  * This library is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU Lesser General Public
   9  * License as published by the Free Software Foundation; either
  10  * version 2.1 of the License, or (at your option) any later version.
  11  *
  12  * This library is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15  * Lesser General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU Lesser General Public
  18  * License along with this library; if not, write to the Free Software
  19  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
  20  */
  21
  22 #include <stdarg.h>
  23
  24 #include "windef.h"
  25 #include "winbase.h"
  26 #include "winuser.h"
  27 #include "winreg.h"
  28 #include "winnls.h"
  29 #include "setupapi.h"
  30 #include "setupapi_private.h"
  31
  32 #include "wine/debug.h"
  33
  34 WINE_DEFAULT_DEBUG_CHANNEL(setupapi);
  35
  36 DECLARE_HANDLE(HSTRING_TABLE);
  37
  38 struct stringtable {
  39     char     *data;
  40     ULONG     nextoffset;
  41     ULONG     allocated;
  42     DWORD_PTR unk[2];
  43     ULONG     max_extra_size;
  44     LCID      lcid;
  45 };
  46
  47 struct stringentry {
  48     DWORD nextoffset;
  49     WCHAR data[1];
  50 };
  51
  52 #define BUCKET_COUNT 509
  53 #define DEFAULT_ALLOC_SIZE 4096
  54
  55 /*
  56      String table details
  57
  58  Returned string table 'handle' is a pointer to 'struct stringtable' structure.
  59  Data itself is allocated separately, pointer is stored in 'data' field.
  60
  61  Data starts with array of 509 DWORDs - lookup table. Initially all offsets in that
  62  array are set to -1. Right after lookup table goes data itself, stored in linked lists.
  63  Lookup table offset points to first record of 'struct stringentry' type. When more
  64  than one record is present in a bucket, first record links to next one with 'nextoffset'
  65  field. Last record has nextoffset == -1, same when there's only one record. String data
  66  is placed right after offset, and is followed by extra data. Each record has reserved
  67  'max_extra_size' bytes to store extra data, it's not compacted in any way.
  68
  69  A simple hash function is used to determine which bucket a given string belongs to (see below).
  70
  71  All offsets including returned string ids are relative to 'data' pointer. When table
  72  needs to grow 'allocated' size is doubled, but offsets are always valid and preserved.
  73
  74 */
  75
  76 static inline DWORD get_string_hash(const WCHAR *str, BOOL case_sensitive)
  77 {
  78     DWORD hash = 0;
  79
  80     while (*str) {
  81         WCHAR ch = case_sensitive ? *str : towlower(*str);
  82         hash += ch;
  83         if (ch & ~0xff)
  84             hash |= 1;
  85         str++;
  86     }
  87
  88     return hash % BUCKET_COUNT;
  89 }
  90
  91 static inline DWORD *get_bucket_ptr(struct stringtable *table, const WCHAR *string, BOOL case_sensitive)
  92 {
  93     DWORD hash = get_string_hash(string, case_sensitive);
  94     return (DWORD*)(table->data + hash*sizeof(DWORD));
  95 }
  96
  97 static inline WCHAR *get_string_ptr(struct stringtable *table, DWORD id)
  98 {
  99     return (WCHAR*)(table->data + id + sizeof(DWORD));
 100 }
 101
 102 static inline char *get_extradata_ptr(struct stringtable *table, DWORD id)
 103 {
 104     WCHAR *ptrW = get_string_ptr(table, id);
 105     /* skip string itself */
 106     return (char*)(ptrW + lstrlenW(ptrW) + 1);
 107 }
 108
 109 static inline BOOL is_valid_string_id(struct stringtable *table, DWORD id)
 110 {
 111     return (id >= BUCKET_COUNT*sizeof(DWORD)) && (id < table->allocated);
 112 }
 113
 114 static inline int get_aligned16_size(int size)
 115 {
 116     return (size + 15) & ~15;
 117 }
 118
 119 /**************************************************************************
 120  * StringTableInitializeEx [SETUPAPI.@]
 121  *
 122  * Creates a new string table and initializes it.
 123  *
 124  * PARAMS
 125  *     max_extra_size   [I] Maximum extra data size
 126  *     reserved         [I] Unused
 127  *
 128  * RETURNS
 129  *     Success: Handle to the string table
 130  *     Failure: NULL
 131  */
 132 HSTRING_TABLE WINAPI StringTableInitializeEx(ULONG max_extra_size, DWORD reserved)
 133 {
 134     struct stringtable *table;
 135
 136     TRACE("(%ld %lx)\n", max_extra_size, reserved);
 137
 138     table = MyMalloc(sizeof(*table));
 139     if (!table) return NULL;
 140
 141     table->allocated = get_aligned16_size(BUCKET_COUNT*sizeof(DWORD) + DEFAULT_ALLOC_SIZE);
 142     table->data = MyMalloc(table->allocated);
 143     if (!table->data) {
 144         MyFree(table);
 145         return NULL;
 146     }
 147
 148     table->nextoffset = BUCKET_COUNT*sizeof(DWORD);
 149     /* FIXME: actually these two are not zero */
 150     table->unk[0] = table->unk[1] = 0;
 151     table->max_extra_size = max_extra_size;
 152     table->lcid = GetThreadLocale();
 153
 154     /* bucket area is filled with 0xff, actual string data area is zeroed */
 155     memset(table->data, 0xff, table->nextoffset);
 156     memset(table->data + table->nextoffset, 0, table->allocated - table->nextoffset);
 157
 158     return (HSTRING_TABLE)table;
 159 }
 160
 161 /**************************************************************************
 162  * StringTableInitialize [SETUPAPI.@]
 163  *
 164  * Creates a new string table and initializes it.
 165  *
 166  * PARAMS
 167  *     None
 168  *
 169  * RETURNS
 170  *     Success: Handle to the string table
 171  *     Failure: NULL
 172  */
 173 HSTRING_TABLE WINAPI StringTableInitialize(void)
 174 {
 175     return StringTableInitializeEx(0, 0);
 176 }
 177
 178 /**************************************************************************
 179  * StringTableDestroy [SETUPAPI.@]
 180  *
 181  * Destroys a string table.
 182  *
 183  * PARAMS
 184  *     hTable [I] Handle to the string table to be destroyed
 185  *
 186  * RETURNS
 187  *     None
 188  */
 189 void WINAPI StringTableDestroy(HSTRING_TABLE hTable)
 190 {
 191     struct stringtable *table = (struct stringtable*)hTable;
 192
 193     TRACE("%p\n", table);
 194
 195     if (!table)
 196         return;
 197
 198     MyFree(table->data);
 199     MyFree(table);
 200 }
 201
 202 /**************************************************************************
 203  * StringTableDuplicate [SETUPAPI.@]
 204  *
 205  * Duplicates a given string table.
 206  *
 207  * PARAMS
 208  *     hTable [I] Handle to the string table
 209  *
 210  * RETURNS
 211  *     Success: Handle to the duplicated string table
 212  *     Failure: NULL
 213  *
 214  */
 215 HSTRING_TABLE WINAPI StringTableDuplicate(HSTRING_TABLE hTable)
 216 {
 217     struct stringtable *src = (struct stringtable*)hTable, *dest;
 218
 219     TRACE("%p\n", src);
 220
 221     if (!src)
 222         return NULL;
 223
 224     dest = MyMalloc(sizeof(*dest));
 225     if (!dest)
 226         return NULL;
 227
 228     *dest = *src;
 229     dest->data = MyMalloc(src->allocated);
 230     if (!dest->data) {
 231         MyFree(dest);
 232         return NULL;
 233     }
 234
 235     memcpy(dest->data, src->data, src->allocated);
 236     return (HSTRING_TABLE)dest;
 237 }
 238
 239 /**************************************************************************
 240  * StringTableGetExtraData [SETUPAPI.@]
 241  *
 242  * Retrieves extra data from a given string table entry.
 243  *
 244  * PARAMS
 245  *     hTable     [I] Handle to the string table
 246  *     id         [I] String ID
 247  *     extra      [I] Pointer a buffer that receives the extra data
 248  *     extra_size [I] Size of the buffer
 249  *
 250  * RETURNS
 251  *     Success: TRUE
 252  *     Failure: FALSE
 253  */
 254 BOOL WINAPI StringTableGetExtraData(HSTRING_TABLE hTable, ULONG id, void *extra, ULONG extra_size)
 255 {
 256     struct stringtable *table = (struct stringtable*)hTable;
 257     char *extraptr;
 258
 259     TRACE("%p %lu %p %lu\n", table, id, extra, extra_size);
 260
 261     if (!table)
 262         return FALSE;
 263
 264     if (!is_valid_string_id(table, id))
 265         return FALSE;
 266
 267     if (table->max_extra_size > extra_size)
 268     {
 269         ERR("data size is too large\n");
 270         return FALSE;
 271     }
 272
 273     extraptr = get_extradata_ptr(table, id);
 274     memcpy(extra, extraptr, extra_size);
 275     return TRUE;
 276 }
 277
 278 /**************************************************************************
 279  * StringTableLookUpStringEx [SETUPAPI.@]
 280  *
 281  * Searches a string table and extra data for a given string.
 282  *
 283  * PARAMS
 284  *     hTable      [I] Handle to the string table
 285  *     string      [I] String to be searched for
 286  *     flags       [I] Flags
 287  *                        1: case sensitive compare
 288  *     extra       [O] Pointer to the buffer that receives the extra data
 289  *     extra_size  [I/O] Unused
 290  *
 291  * RETURNS
 292  *     Success: String ID
 293  *     Failure: -1
 294  */
 295 DWORD WINAPI StringTableLookUpStringEx(HSTRING_TABLE hTable, LPWSTR string, DWORD flags,
 296     void *extra, ULONG extra_size)
 297 {
 298     struct stringtable *table = (struct stringtable*)hTable;
 299     BOOL case_sensitive = flags & 1;
 300     struct stringentry *entry;
 301     DWORD offset;
 302     int cmp;
 303
 304     TRACE("%p->%p %s %lx %p, %lx\n", table, table->data, debugstr_w(string), flags, extra, extra_size);
 305
 306     if (!table)
 307         return -1;
 308
 309     /* get corresponding offset */
 310     offset = *get_bucket_ptr(table, string, case_sensitive);
 311     if (offset == -1)
 312         return -1;
 313
 314     /* now we're at correct bucket, do linear search for string */
 315     while (1) {
 316         entry = (struct stringentry*)(table->data + offset);
 317         if (case_sensitive)
 318             cmp = wcscmp(entry->data, string);
 319         else
 320             cmp = lstrcmpiW(entry->data, string);
 321         if (!cmp) {
 322             if (extra)
 323                 memcpy(extra, get_extradata_ptr(table, offset), extra_size);
 324             return offset;
 325         }
 326
 327         /* last entry */
 328         if (entry->nextoffset == -1)
 329             return -1;
 330
 331         offset = entry->nextoffset;
 332         if (offset > table->allocated)
 333             return -1;
 334     }
 335 }
 336
 337 /**************************************************************************
 338  * StringTableLookUpString [SETUPAPI.@]
 339  *
 340  * Searches a string table for a given string.
 341  *
 342  * PARAMS
 343  *     hTable  [I] Handle to the string table
 344  *     string  [I] String to be searched for
 345  *     flags   [I] Flags
 346  *                 1: case sensitive compare
 347  *
 348  * RETURNS
 349  *     Success: String ID
 350  *     Failure: -1
 351  */
 352 DWORD WINAPI StringTableLookUpString(HSTRING_TABLE hTable, LPWSTR string, DWORD flags)
 353 {
 354     return StringTableLookUpStringEx(hTable, string, flags, NULL, 0);
 355 }
 356
 357 /**************************************************************************
 358  * StringTableAddStringEx [SETUPAPI.@]
 359  *
 360  * Adds a new string plus extra data to the string table.
 361  *
 362  * PARAMS
 363  *     hTable        [I] Handle to the string table
 364  *     string        [I] String to be added to the string table
 365  *     flags         [I] Flags
 366  *                           1: case sensitive compare
 367  *     extra         [I] Pointer to the extra data
 368  *     extra_size    [I] Size of the extra data
 369  *
 370  * RETURNS
 371  *     Success: String ID
 372  *     Failure: -1
 373  *
 374  * NOTES
 375  *     If the given string already exists in the string table it will not
 376  *     be added again. The ID of the existing string will be returned in
 377  *     this case.
 378  */
 379 DWORD WINAPI StringTableAddStringEx(HSTRING_TABLE hTable, LPWSTR string,
 380                        DWORD flags, void *extra, DWORD extra_size)
 381 {
 382     struct stringtable *table = (struct stringtable*)hTable;
 383     BOOL case_sensitive = flags & 1;
 384     struct stringentry *entry;
 385     DWORD id, *offset;
 386     WCHAR *ptrW;
 387     int len;
 388
 389     TRACE("%p %s %lx %p, %lu\n", hTable, debugstr_w(string), flags, extra, extra_size);
 390
 391     if (!table)
 392         return -1;
 393
 394     id = StringTableLookUpStringEx(hTable, string, flags, NULL, 0);
 395     if (id != -1)
 396         return id;
 397
 398     /* needed space for new record */
 399     len = sizeof(DWORD) + (lstrlenW(string)+1)*sizeof(WCHAR) + table->max_extra_size;
 400     if (table->nextoffset + len >= table->allocated) {
 401         table->allocated <<= 1;
 402         table->data = HeapReAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, table->data, table->allocated);
 403     }
 404
 405     /* hash string */
 406     offset = get_bucket_ptr(table, string, case_sensitive);
 407     if (*offset == -1)
 408         /* bucket used for a very first time */
 409         *offset = table->nextoffset;
 410     else {
 411         entry = (struct stringentry*)(table->data + *offset);
 412         /* link existing last entry to newly added */
 413         while (entry->nextoffset != -1)
 414             entry = (struct stringentry*)(table->data + entry->nextoffset);
 415         entry->nextoffset = table->nextoffset;
 416     }
 417     entry = (struct stringentry*)(table->data + table->nextoffset);
 418     entry->nextoffset = -1;
 419     id = table->nextoffset;
 420
 421     /* copy string */
 422     ptrW = get_string_ptr(table, id);
 423     lstrcpyW(ptrW, string);
 424     if (!case_sensitive)
 425         wcslwr(ptrW);
 426
 427     /* copy extra data */
 428     if (extra)
 429         memcpy(get_extradata_ptr(table, id), extra, extra_size);
 430
 431     table->nextoffset += len;
 432     return id;
 433 }
 434
 435 /**************************************************************************
 436  * StringTableAddString [SETUPAPI.@]
 437  *
 438  * Adds a new string to the string table.
 439  *
 440  * PARAMS
 441  *     hTable     [I] Handle to the string table
 442  *     string     [I] String to be added to the string table
 443  *     flags      [I] Flags
 444  *                        1: case sensitive compare
 445  *
 446  * RETURNS
 447  *     Success: String ID
 448  *     Failure: -1
 449  *
 450  * NOTES
 451  *     If the given string already exists in the string table it will not
 452  *     be added again. The ID of the existing string will be returned in
 453  *     this case.
 454  */
 455 DWORD WINAPI StringTableAddString(HSTRING_TABLE hTable, LPWSTR string, DWORD flags)
 456 {
 457     return StringTableAddStringEx(hTable, string, flags, NULL, 0);
 458 }
 459
 460 /**************************************************************************
 461  * StringTableSetExtraData [SETUPAPI.@]
 462  *
 463  * Sets extra data for a given string table entry.
 464  *
 465  * PARAMS
 466  *     hTable     [I] Handle to the string table
 467  *     id         [I] String ID
 468  *     extra      [I] Pointer to the extra data
 469  *     extra_size [I] Size of the extra data
 470  *
 471  * RETURNS
 472  *     Success: TRUE
 473  *     Failure: FALSE
 474  */
 475 BOOL WINAPI StringTableSetExtraData(HSTRING_TABLE hTable, DWORD id, void *extra, ULONG extra_size)
 476 {
 477     struct stringtable *table = (struct stringtable*)hTable;
 478     char *extraptr;
 479
 480     TRACE("%p %ld %p %lu\n", hTable, id, extra, extra_size);
 481
 482     if (!table)
 483         return FALSE;
 484
 485     if (!is_valid_string_id(table, id))
 486         return FALSE;
 487
 488     if (table->max_extra_size < extra_size)
 489     {
 490         ERR("data size is too large\n");
 491         return FALSE;
 492     }
 493
 494     extraptr = get_extradata_ptr(table, id);
 495     memset(extraptr, 0, table->max_extra_size);
 496     memcpy(extraptr, extra, extra_size);
 497
 498     return TRUE;
 499 }
 500
 501 /**************************************************************************
 502  * StringTableStringFromId [SETUPAPI.@]
 503  *
 504  * Returns a pointer to a string for the given string ID.
 505  *
 506  * PARAMS
 507  *     hTable [I] Handle to the string table.
 508  *     id     [I] String ID
 509  *
 510  * RETURNS
 511  *     Success: Pointer to the string
 512  *     Failure: NULL
 513  */
 514 LPWSTR WINAPI StringTableStringFromId(HSTRING_TABLE hTable, ULONG id)
 515 {
 516     struct stringtable *table = (struct stringtable*)hTable;
 517     static WCHAR empty[] = {0};
 518
 519     TRACE("%p %ld\n", table, id);
 520
 521     if (!table)
 522         return NULL;
 523
 524     if (!is_valid_string_id(table, id))
 525         return empty;
 526
 527     return get_string_ptr(table, id);
 528 }
 529
 530 /**************************************************************************
 531  * StringTableStringFromIdEx [SETUPAPI.@]
 532  *
 533  * Returns a string for the given string ID.
 534  *
 535  * PARAMS
 536  *     hTable   [I] Handle to the string table
 537  *     id       [I] String ID
 538  *     buff     [I] Pointer to string buffer
 539  *     buflen   [I/O] Pointer to the size of the string buffer
 540  *
 541  * RETURNS
 542  *     Success: TRUE
 543  *     Failure: FALSE
 544  */
 545 BOOL WINAPI StringTableStringFromIdEx(HSTRING_TABLE hTable, ULONG id, LPWSTR buff, DWORD *buflen)
 546 {
 547     struct stringtable *table = (struct stringtable*)hTable;
 548     BOOL ret = TRUE;
 549     WCHAR *ptrW;
 550     int len;
 551
 552     TRACE("%p %lx %p %p\n", table, id, buff, buflen);
 553
 554     if (!table) {
 555         *buflen = 0;
 556         return FALSE;
 557     }
 558
 559     if (!is_valid_string_id(table, id)) {
 560         WARN("invalid string id\n");
 561         *buflen = 0;
 562         return FALSE;
 563     }
 564
 565     ptrW = get_string_ptr(table, id);
 566     len = (lstrlenW(ptrW) + 1)*sizeof(WCHAR);
 567     if (len <= *buflen)
 568         lstrcpyW(buff, ptrW);
 569     else
 570         ret = FALSE;
 571
 572     *buflen = len;
 573     return ret;
 574 }
 575
 576 /**************************************************************************
 577  * StringTableTrim [SETUPAPI.@]
 578  *
 579  * ...
 580  *
 581  * PARAMS
 582  *     hTable [I] Handle to the string table
 583  *
 584  * RETURNS
 585  *     None
 586  */
 587 void WINAPI StringTableTrim(HSTRING_TABLE hTable)
 588 {
 589     FIXME("%p\n", hTable);
 590 }