reactos/dll/appcompat/apphelp/sdbstringtable.c

   1 /*
   2  * Copyright 2016 Mark Jansen
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Lesser General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2.1 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Lesser General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Lesser General Public
  15  * License along with this library; if not, write to the Free Software
  16  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
  17  */
  18
  19 #if !defined(SDBWRITE_HOSTTOOL)
  20 #define WIN32_NO_STATUS
  21 #include "windows.h"
  22 #include "sdbtypes.h"
  23 #include "sdbpapi.h"
  24 #else /* !defined(SDBWRITE_HOSTTOOL) */
  25 #include <typedefs.h>
  26 #include <guiddef.h>
  27 #include "sdbtypes.h"
  28 #include "sdbpapi.h"
  29 #endif /* !defined(SDBWRITE_HOSTTOOL) */
  30
  31 #include "sdbstringtable.h"
  32
  33 #if !defined(offsetof)
  34 #if defined(__GNUC__)
  35 #define offsetof(TYPE, MEMBER) __builtin_offsetof (TYPE, MEMBER)
  36 #else
  37 #define offsetof(TYPE, MEMBER) ((size_t)&(((TYPE *)0)->MEMBER))
  38 #endif
  39 #endif // !defined(offsetof)
  40
  41 #define DEFAULT_TABLE_SIZE    0x100
  42
  43 typedef struct SdbHashEntry
  44 {
  45     struct SdbHashEntry* Next;
  46     TAGID Tagid;
  47     WCHAR Name[1];
  48 } SdbHashEntry;
  49
  50 struct SdbStringHashTable
  51 {
  52     DWORD Size;
  53     struct SdbHashEntry** Entries;
  54 };
  55
  56
  57 static struct SdbStringHashTable* HashCreate(void)
  58 {
  59     struct SdbStringHashTable* tab = SdbAlloc(sizeof(*tab));
  60     if (!tab)
  61     {
  62         SHIM_ERR("Failed to allocate 8 bytes.\r\n");
  63         return tab;
  64     }
  65     tab->Size = DEFAULT_TABLE_SIZE;
  66     tab->Entries = SdbAlloc(tab->Size * sizeof(*tab->Entries));
  67     return tab;
  68 }
  69
  70
  71 void SdbpTableDestroy(struct SdbStringHashTable** pTable)
  72 {
  73     struct SdbStringHashTable* table = *pTable;
  74     struct SdbHashEntry* entry, *next;
  75     DWORD n, depth = 0, once = 1;
  76
  77     *pTable = NULL;
  78     for (n = 0; n < table->Size; ++n)
  79     {
  80         depth = 0;
  81         entry = next = table->Entries[n];
  82         while (entry)
  83         {
  84             next = entry->Next;
  85             SdbFree(entry);
  86             entry = next;
  87             depth++;
  88         }
  89         if (once && depth > 3)
  90         {
  91             // warn
  92             once = 0;
  93         }
  94     }
  95     SdbFree(table->Entries);
  96     SdbFree(table);
  97 }
  98
  99 /* Based on RtlHashUnicodeString */
 100 static DWORD StringHash(const WCHAR* str)
 101 {
 102     DWORD hash = 0;
 103     for (; *str; str++)
 104     {
 105         hash = ((65599 * hash) + (ULONG)(*str));
 106     }
 107     return hash;
 108 }
 109
 110 int Sdbwcscmp(const WCHAR* s1, const WCHAR* s2)
 111 {
 112     while (*s1 == *s2)
 113     {
 114         if (*s1 == 0)
 115             return 0;
 116         s1++;
 117         s2++;
 118     }
 119     return *s1 - *s2;
 120 }
 121
 122
 123 // implementation taken from reactos/sdk/lib/crt/string/wcs.c
 124 INT Sdbwcscpy(WCHAR* wcDest, size_t numElement, const WCHAR *wcSrc)
 125 {
 126     size_t size = 0;
 127     if(!wcDest || !numElement)
 128         return 22;  /* EINVAL */
 129
 130     wcDest[0] = 0;
 131
 132     if(!wcSrc)
 133         return 22;  /* EINVAL */
 134
 135     size = SdbpStrlen(wcSrc) + 1;
 136
 137     if(size > numElement)
 138         return 34;  /* ERANGE */
 139
 140     memcpy(wcDest, wcSrc, size * sizeof(WCHAR));
 141
 142     return 0;
 143 }
 144
 145 static struct SdbHashEntry** TableFindPtr(struct SdbStringHashTable* table, const WCHAR* str)
 146 {
 147     DWORD hash = StringHash(str);
 148     struct SdbHashEntry** entry = &table->Entries[hash % table->Size];
 149     while (*entry)
 150     {
 151         if (!Sdbwcscmp((*entry)->Name, str))
 152             return entry;
 153         entry = &(*entry)->Next;
 154     }
 155     return entry;
 156 }
 157
 158 static BOOL HashAddString(struct SdbStringHashTable* table, struct SdbHashEntry** position, const WCHAR* str, TAGID tagid)
 159 {
 160     struct SdbHashEntry* entry;
 161     SIZE_T size, len;
 162
 163     if (!position)
 164         position = TableFindPtr(table, str);
 165
 166     len = SdbpStrlen(str) + 1;
 167     size = offsetof(struct SdbHashEntry, Name[len]);
 168     entry = (*position) = SdbAlloc(size);
 169     if (!entry)
 170     {
 171         SHIM_ERR("Failed to allocate %u bytes.", size);
 172         return FALSE;
 173     }
 174     entry->Tagid = tagid;
 175     Sdbwcscpy(entry->Name, len, str);
 176     return TRUE;
 177 }
 178
 179
 180 BOOL SdbpAddStringToTable(struct SdbStringHashTable** table, const WCHAR* str, TAGID* tagid)
 181 {
 182     struct SdbHashEntry** entry;
 183
 184     if (!*table)
 185     {
 186         *table = HashCreate();
 187         if (!*table)
 188         {
 189             SHIM_ERR("Error creating hash table\n");
 190             return FALSE;
 191         }
 192     }
 193
 194     entry = TableFindPtr(*table, str);
 195     if (*entry)
 196     {
 197         *tagid = (*entry)->Tagid;
 198         return FALSE;
 199     }
 200     return HashAddString(*table, entry, str, *tagid);
 201 }
 202