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