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