dlls/scrrun/dictionary.c

   1 /*
   2  * Copyright (C) 2012 Alistair Leslie-Hughes
   3  * Copyright 2015 Nikolay Sivov for CodeWeavers
   4  *
   5  * This library is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU Lesser General Public
   7  * License as published by the Free Software Foundation; either
   8  * version 2.1 of the License, or (at your option) any later version.
   9  *
  10  * This library is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * Lesser General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU Lesser General Public
  16  * License along with this library; if not, write to the Free Software
  17  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
  18  */
  19 #define COBJMACROS
  20
  21 #include "config.h"
  22 #include "wine/port.h"
  23
  24 #include <stdarg.h>
  25
  26 #include "windef.h"
  27 #include "winbase.h"
  28 #include "ole2.h"
  29 #include "olectl.h"
  30 #include "dispex.h"
  31 #include "scrrun.h"
  32 #include "scrrun_private.h"
  33
  34 #include "wine/debug.h"
  35 #include "wine/unicode.h"
  36 #include "wine/heap.h"
  37 #include "wine/list.h"
  38
  39 WINE_DEFAULT_DEBUG_CHANNEL(scrrun);
  40
  41 #define BUCKET_COUNT  509
  42 #define DICT_HASH_MOD 1201
  43
  44 /* Implementation details
  45
  46    Dictionary contains one list that links all pairs, this way
  47    order in which they were added is preserved. Each bucket has
  48    its own list to hold all pairs in this bucket. Initially all
  49    bucket lists are zeroed and we init them once we about to add
  50    first pair.
  51
  52    When pair is removed it's unlinked from both lists; if it was
  53    a last pair in a bucket list it stays empty in initialized state.
  54
  55    Preserving pair order is important for enumeration, so far testing
  56    indicates that pairs are not reordered basing on hash value.
  57  */
  58
  59 struct keyitem_pair {
  60     struct  list entry;
  61     struct  list bucket;
  62     DWORD   hash;
  63     VARIANT key;
  64     VARIANT item;
  65 };
  66
  67 typedef struct
  68 {
  69     struct provideclassinfo classinfo;
  70     IDictionary IDictionary_iface;
  71     LONG ref;
  72
  73     CompareMethod method;
  74     LONG count;
  75     struct list pairs;
  76     struct list buckets[BUCKET_COUNT];
  77     struct list notifier;
  78 } dictionary;
  79
  80 struct dictionary_enum {
  81     IEnumVARIANT IEnumVARIANT_iface;
  82     LONG ref;
  83
  84     dictionary *dict;
  85     struct list *cur;
  86     struct list notify;
  87 };
  88
  89 static inline dictionary *impl_from_IDictionary(IDictionary *iface)
  90 {
  91     return CONTAINING_RECORD(iface, dictionary, IDictionary_iface);
  92 }
  93
  94 static inline struct dictionary_enum *impl_from_IEnumVARIANT(IEnumVARIANT *iface)
  95 {
  96     return CONTAINING_RECORD(iface, struct dictionary_enum, IEnumVARIANT_iface);
  97 }
  98
  99 static inline struct list *get_bucket_head(dictionary *dict, DWORD hash)
 100 {
 101     return &dict->buckets[hash % BUCKET_COUNT];
 102 }
 103
 104 static inline BOOL is_string_key(const VARIANT *key)
 105 {
 106     return V_VT(key) == VT_BSTR || V_VT(key) == (VT_BSTR|VT_BYREF);
 107 }
 108
 109 /* Only for VT_BSTR or VT_BSTR|VT_BYREF types */
 110 static inline WCHAR *get_key_strptr(const VARIANT *key)
 111 {
 112     if (V_VT(key) == VT_BSTR)
 113         return V_BSTR(key);
 114
 115     if (V_BSTRREF(key))
 116         return *V_BSTRREF(key);
 117
 118     return NULL;
 119 }
 120
 121 /* should be used only when both keys are of string type, it's not checked */
 122 static inline int strcmp_key(const dictionary *dict, const VARIANT *key1, const VARIANT *key2)
 123 {
 124     const WCHAR *str1, *str2;
 125
 126     str1 = get_key_strptr(key1);
 127     str2 = get_key_strptr(key2);
 128     return dict->method == BinaryCompare ? strcmpW(str1, str2) : strcmpiW(str1, str2);
 129 }
 130
 131 static BOOL is_matching_key(const dictionary *dict, const struct keyitem_pair *pair, const VARIANT *key, DWORD hash)
 132 {
 133     if (is_string_key(key) && is_string_key(&pair->key)) {
 134         if (hash != pair->hash)
 135             return FALSE;
 136
 137         return strcmp_key(dict, key, &pair->key) == 0;
 138     }
 139
 140     if ((is_string_key(key) && !is_string_key(&pair->key)) ||
 141         (!is_string_key(key) && is_string_key(&pair->key)))
 142         return FALSE;
 143
 144     /* for numeric keys only check hash */
 145     return hash == pair->hash;
 146 }
 147
 148 static struct keyitem_pair *get_keyitem_pair(dictionary *dict, VARIANT *key)
 149 {
 150     struct keyitem_pair *pair;
 151     struct list *head, *entry;
 152     VARIANT hash;
 153     HRESULT hr;
 154
 155     hr = IDictionary_get_HashVal(&dict->IDictionary_iface, key, &hash);
 156     if (FAILED(hr))
 157         return NULL;
 158
 159     head = get_bucket_head(dict, V_I4(&hash));
 160     if (!head->next || list_empty(head))
 161         return NULL;
 162
 163     entry = list_head(head);
 164     do {
 165         pair = LIST_ENTRY(entry, struct keyitem_pair, bucket);
 166         if (is_matching_key(dict, pair, key, V_I4(&hash))) return pair;
 167     } while ((entry = list_next(head, entry)));
 168
 169     return NULL;
 170 }
 171
 172 static HRESULT add_keyitem_pair(dictionary *dict, VARIANT *key, VARIANT *item)
 173 {
 174     struct keyitem_pair *pair;
 175     struct list *head;
 176     VARIANT hash;
 177     HRESULT hr;
 178
 179     hr = IDictionary_get_HashVal(&dict->IDictionary_iface, key, &hash);
 180     if (FAILED(hr))
 181         return hr;
 182
 183     pair = heap_alloc(sizeof(*pair));
 184     if (!pair)
 185         return E_OUTOFMEMORY;
 186
 187     pair->hash = V_I4(&hash);
 188     VariantInit(&pair->key);
 189     VariantInit(&pair->item);
 190
 191     hr = VariantCopyInd(&pair->key, key);
 192     if (FAILED(hr))
 193         goto failed;
 194
 195     hr = VariantCopyInd(&pair->item, item);
 196     if (FAILED(hr))
 197         goto failed;
 198
 199     head = get_bucket_head(dict, pair->hash);
 200     if (!head->next)
 201         /* this only happens once per bucket */
 202         list_init(head);
 203
 204     /* link to bucket list and to full list */
 205     list_add_tail(head, &pair->bucket);
 206     list_add_tail(&dict->pairs, &pair->entry);
 207     dict->count++;
 208     return S_OK;
 209
 210 failed:
 211     VariantClear(&pair->key);
 212     VariantClear(&pair->item);
 213     heap_free(pair);
 214     return hr;
 215 }
 216
 217 static void free_keyitem_pair(struct keyitem_pair *pair)
 218 {
 219     VariantClear(&pair->key);
 220     VariantClear(&pair->item);
 221     heap_free(pair);
 222 }
 223
 224 static HRESULT WINAPI dict_enum_QueryInterface(IEnumVARIANT *iface, REFIID riid, void **obj)
 225 {
 226     struct dictionary_enum *This = impl_from_IEnumVARIANT(iface);
 227
 228     TRACE("(%p)->(%s, %p)\n", This, debugstr_guid(riid), obj);
 229
 230     if (IsEqualIID(riid, &IID_IEnumVARIANT) || IsEqualIID(riid, &IID_IUnknown)) {
 231         *obj = iface;
 232         IEnumVARIANT_AddRef(iface);
 233         return S_OK;
 234     }
 235     else {
 236         WARN("interface not supported %s\n", debugstr_guid(riid));
 237         *obj = NULL;
 238         return E_NOINTERFACE;
 239     }
 240 }
 241
 242 static ULONG WINAPI dict_enum_AddRef(IEnumVARIANT *iface)
 243 {
 244     struct dictionary_enum *This = impl_from_IEnumVARIANT(iface);
 245     ULONG ref = InterlockedIncrement(&This->ref);
 246     TRACE("(%p)->(%u)\n", This, ref);
 247     return ref;
 248 }
 249
 250 static ULONG WINAPI dict_enum_Release(IEnumVARIANT *iface)
 251 {
 252     struct dictionary_enum *This = impl_from_IEnumVARIANT(iface);
 253     LONG ref = InterlockedDecrement(&This->ref);
 254
 255     TRACE("(%p)->(%u)\n", This, ref);
 256
 257     if (!ref) {
 258         list_remove(&This->notify);
 259         IDictionary_Release(&This->dict->IDictionary_iface);
 260         heap_free(This);
 261     }
 262
 263     return ref;
 264 }
 265
 266 static HRESULT WINAPI dict_enum_Next(IEnumVARIANT *iface, ULONG count, VARIANT *keys, ULONG *fetched)
 267 {
 268     struct dictionary_enum *This = impl_from_IEnumVARIANT(iface);
 269     struct keyitem_pair *pair;
 270     ULONG i = 0;
 271
 272     TRACE("(%p)->(%u %p %p)\n", This, count, keys, fetched);
 273
 274     if (fetched)
 275         *fetched = 0;
 276
 277     if (!count)
 278         return S_OK;
 279
 280     while (This->cur && i < count) {
 281         pair = LIST_ENTRY(This->cur, struct keyitem_pair, entry);
 282         VariantCopy(&keys[i], &pair->key);
 283         This->cur = list_next(&This->dict->pairs, This->cur);
 284         i++;
 285     }
 286
 287     if (fetched)
 288         *fetched = i;
 289
 290     return i < count ? S_FALSE : S_OK;
 291 }
 292
 293 static HRESULT WINAPI dict_enum_Skip(IEnumVARIANT *iface, ULONG count)
 294 {
 295     struct dictionary_enum *This = impl_from_IEnumVARIANT(iface);
 296
 297     TRACE("(%p)->(%u)\n", This, count);
 298
 299     if (!count)
 300         return S_OK;
 301
 302     if (!This->cur)
 303         return S_FALSE;
 304
 305     while (count--) {
 306         This->cur = list_next(&This->dict->pairs, This->cur);
 307         if (!This->cur) break;
 308     }
 309
 310     return count == 0 ? S_OK : S_FALSE;
 311 }
 312
 313 static HRESULT WINAPI dict_enum_Reset(IEnumVARIANT *iface)
 314 {
 315     struct dictionary_enum *This = impl_from_IEnumVARIANT(iface);
 316
 317     TRACE("(%p)\n", This);
 318
 319     This->cur = list_head(&This->dict->pairs);
 320     return S_OK;
 321 }
 322
 323 static HRESULT create_dict_enum(dictionary*, IUnknown**);
 324
 325 static HRESULT WINAPI dict_enum_Clone(IEnumVARIANT *iface, IEnumVARIANT **cloned)
 326 {
 327     struct dictionary_enum *This = impl_from_IEnumVARIANT(iface);
 328     TRACE("(%p)->(%p)\n", This, cloned);
 329     return create_dict_enum(This->dict, (IUnknown**)cloned);
 330 }
 331
 332 static const IEnumVARIANTVtbl dictenumvtbl = {
 333     dict_enum_QueryInterface,
 334     dict_enum_AddRef,
 335     dict_enum_Release,
 336     dict_enum_Next,
 337     dict_enum_Skip,
 338     dict_enum_Reset,
 339     dict_enum_Clone
 340 };
 341
 342 static HRESULT create_dict_enum(dictionary *dict, IUnknown **ret)
 343 {
 344     struct dictionary_enum *This;
 345
 346     *ret = NULL;
 347
 348     This = heap_alloc(sizeof(*This));
 349     if (!This)
 350         return E_OUTOFMEMORY;
 351
 352     This->IEnumVARIANT_iface.lpVtbl = &dictenumvtbl;
 353     This->ref = 1;
 354     This->cur = list_head(&dict->pairs);
 355     list_add_tail(&dict->notifier, &This->notify);
 356     This->dict = dict;
 357     IDictionary_AddRef(&dict->IDictionary_iface);
 358
 359     *ret = (IUnknown*)&This->IEnumVARIANT_iface;
 360     return S_OK;
 361 }
 362
 363 static void notify_remove_pair(struct list *notifier, struct list *pair)
 364 {
 365     struct dictionary_enum *dict_enum;
 366     struct list *cur;
 367
 368     LIST_FOR_EACH(cur, notifier) {
 369         dict_enum = LIST_ENTRY(cur, struct dictionary_enum, notify);
 370         if (!pair)
 371             dict_enum->cur = list_head(&dict_enum->dict->pairs);
 372         else if (dict_enum->cur == pair) {
 373             dict_enum->cur = list_next(&dict_enum->dict->pairs, dict_enum->cur);
 374         }
 375     }
 376 }
 377
 378 static HRESULT WINAPI dictionary_QueryInterface(IDictionary *iface, REFIID riid, void **obj)
 379 {
 380     dictionary *This = impl_from_IDictionary(iface);
 381     TRACE("(%p)->(%s, %p)\n", This, debugstr_guid(riid), obj);
 382
 383     *obj = NULL;
 384
 385     if(IsEqualIID(riid, &IID_IUnknown) ||
 386        IsEqualIID(riid, &IID_IDispatch) ||
 387        IsEqualIID(riid, &IID_IDictionary))
 388     {
 389         *obj = &This->IDictionary_iface;
 390     }
 391     else if (IsEqualIID(riid, &IID_IProvideClassInfo))
 392     {
 393         *obj = &This->classinfo.IProvideClassInfo_iface;
 394     }
 395     else if ( IsEqualGUID( riid, &IID_IDispatchEx ))
 396     {
 397         TRACE("Interface IDispatchEx not supported - returning NULL\n");
 398         *obj = NULL;
 399         return E_NOINTERFACE;
 400     }
 401     else if ( IsEqualGUID( riid, &IID_IObjectWithSite ))
 402     {
 403         TRACE("Interface IObjectWithSite not supported - returning NULL\n");
 404         *obj = NULL;
 405         return E_NOINTERFACE;
 406     }
 407     else
 408     {
 409         WARN("interface %s not implemented\n", debugstr_guid(riid));
 410         return E_NOINTERFACE;
 411     }
 412
 413     IUnknown_AddRef((IUnknown*)*obj);
 414     return S_OK;
 415 }
 416
 417 static ULONG WINAPI dictionary_AddRef(IDictionary *iface)
 418 {
 419     dictionary *This = impl_from_IDictionary(iface);
 420     ULONG ref = InterlockedIncrement(&This->ref);
 421
 422     TRACE("(%p)->(%u)\n", This, ref);
 423
 424     return ref;
 425 }
 426
 427 static ULONG WINAPI dictionary_Release(IDictionary *iface)
 428 {
 429     dictionary *This = impl_from_IDictionary(iface);
 430     ULONG ref = InterlockedDecrement(&This->ref);
 431
 432     TRACE("(%p)->(%u)\n", This, ref);
 433
 434     if (!ref) {
 435         IDictionary_RemoveAll(iface);
 436         heap_free(This);
 437     }
 438
 439     return ref;
 440 }
 441
 442 static HRESULT WINAPI dictionary_GetTypeInfoCount(IDictionary *iface, UINT *pctinfo)
 443 {
 444     dictionary *This = impl_from_IDictionary(iface);
 445
 446     TRACE("(%p)->(%p)\n", This, pctinfo);
 447
 448     *pctinfo = 1;
 449     return S_OK;
 450 }
 451
 452 static HRESULT WINAPI dictionary_GetTypeInfo(IDictionary *iface, UINT iTInfo, LCID lcid, ITypeInfo **ppTInfo)
 453 {
 454     dictionary *This = impl_from_IDictionary(iface);
 455
 456     TRACE("(%p)->(%u %u %p)\n", This, iTInfo, lcid, ppTInfo);
 457     return get_typeinfo(IDictionary_tid, ppTInfo);
 458 }
 459
 460 static HRESULT WINAPI dictionary_GetIDsOfNames(IDictionary *iface, REFIID riid, LPOLESTR *rgszNames,
 461                 UINT cNames, LCID lcid, DISPID *rgDispId)
 462 {
 463     dictionary *This = impl_from_IDictionary(iface);
 464     ITypeInfo *typeinfo;
 465     HRESULT hr;
 466
 467     TRACE("(%p)->(%s %p %u %u %p)\n", This, debugstr_guid(riid), rgszNames, cNames, lcid, rgDispId);
 468
 469     hr = get_typeinfo(IDictionary_tid, &typeinfo);
 470     if(SUCCEEDED(hr))
 471     {
 472         hr = ITypeInfo_GetIDsOfNames(typeinfo, rgszNames, cNames, rgDispId);
 473         ITypeInfo_Release(typeinfo);
 474     }
 475
 476     return hr;
 477 }
 478
 479 static HRESULT WINAPI dictionary_Invoke(IDictionary *iface, DISPID dispIdMember, REFIID riid,
 480                 LCID lcid, WORD wFlags, DISPPARAMS *pDispParams, VARIANT *pVarResult,
 481                 EXCEPINFO *pExcepInfo, UINT *puArgErr)
 482 {
 483     dictionary *This = impl_from_IDictionary(iface);
 484     ITypeInfo *typeinfo;
 485     HRESULT hr;
 486
 487     TRACE("(%p)->(%d %s %d %d %p %p %p %p)\n", This, dispIdMember, debugstr_guid(riid),
 488            lcid, wFlags, pDispParams, pVarResult, pExcepInfo, puArgErr);
 489
 490     hr = get_typeinfo(IDictionary_tid, &typeinfo);
 491     if(SUCCEEDED(hr))
 492     {
 493         hr = ITypeInfo_Invoke(typeinfo, &This->IDictionary_iface, dispIdMember, wFlags,
 494                 pDispParams, pVarResult, pExcepInfo, puArgErr);
 495         ITypeInfo_Release(typeinfo);
 496     }
 497
 498     return hr;
 499 }
 500
 501 static HRESULT WINAPI dictionary_putref_Item(IDictionary *iface, VARIANT *Key, VARIANT *pRetItem)
 502 {
 503     dictionary *This = impl_from_IDictionary(iface);
 504
 505     FIXME("(%p)->(%p %p)\n", This, Key, pRetItem);
 506
 507     return E_NOTIMPL;
 508 }
 509
 510 static HRESULT WINAPI dictionary_put_Item(IDictionary *iface, VARIANT *key, VARIANT *item)
 511 {
 512     dictionary *This = impl_from_IDictionary(iface);
 513     struct keyitem_pair *pair;
 514
 515     TRACE("(%p)->(%s %s)\n", This, debugstr_variant(key), debugstr_variant(item));
 516
 517     if ((pair = get_keyitem_pair(This, key)))
 518         return VariantCopyInd(&pair->item, item);
 519
 520     return IDictionary_Add(iface, key, item);
 521 }
 522
 523 static HRESULT WINAPI dictionary_get_Item(IDictionary *iface, VARIANT *key, VARIANT *item)
 524 {
 525     dictionary *This = impl_from_IDictionary(iface);
 526     struct keyitem_pair *pair;
 527
 528     TRACE("(%p)->(%s %p)\n", This, debugstr_variant(key), item);
 529
 530     if ((pair = get_keyitem_pair(This, key)))
 531         VariantCopy(item, &pair->item);
 532     else {
 533         VariantInit(item);
 534         return IDictionary_Add(iface, key, item);
 535     }
 536
 537     return S_OK;
 538 }
 539
 540 static HRESULT WINAPI dictionary_Add(IDictionary *iface, VARIANT *key, VARIANT *item)
 541 {
 542     dictionary *This = impl_from_IDictionary(iface);
 543
 544     TRACE("(%p)->(%s %s)\n", This, debugstr_variant(key), debugstr_variant(item));
 545
 546     if (get_keyitem_pair(This, key))
 547         return CTL_E_KEY_ALREADY_EXISTS;
 548
 549     return add_keyitem_pair(This, key, item);
 550 }
 551
 552 static HRESULT WINAPI dictionary_get_Count(IDictionary *iface, LONG *count)
 553 {
 554     dictionary *This = impl_from_IDictionary(iface);
 555
 556     TRACE("(%p)->(%p)\n", This, count);
 557
 558     *count = This->count;
 559     return S_OK;
 560 }
 561
 562 static HRESULT WINAPI dictionary_Exists(IDictionary *iface, VARIANT *key, VARIANT_BOOL *exists)
 563 {
 564     dictionary *This = impl_from_IDictionary(iface);
 565
 566     TRACE("(%p)->(%s %p)\n", This, debugstr_variant(key), exists);
 567
 568     if (!exists)
 569         return CTL_E_ILLEGALFUNCTIONCALL;
 570
 571     *exists = get_keyitem_pair(This, key) != NULL ? VARIANT_TRUE : VARIANT_FALSE;
 572     return S_OK;
 573 }
 574
 575 static HRESULT WINAPI dictionary_Items(IDictionary *iface, VARIANT *items)
 576 {
 577     dictionary *This = impl_from_IDictionary(iface);
 578     struct keyitem_pair *pair;
 579     SAFEARRAYBOUND bound;
 580     SAFEARRAY *sa;
 581     VARIANT *v;
 582     HRESULT hr;
 583     LONG i;
 584
 585     TRACE("(%p)->(%p)\n", This, items);
 586
 587     if (!items)
 588         return S_OK;
 589
 590     bound.lLbound = 0;
 591     bound.cElements = This->count;
 592     sa = SafeArrayCreate(VT_VARIANT, 1, &bound);
 593     if (!sa)
 594         return E_OUTOFMEMORY;
 595
 596     hr = SafeArrayAccessData(sa, (void**)&v);
 597     if (FAILED(hr)) {
 598         SafeArrayDestroy(sa);
 599         return hr;
 600     }
 601
 602     i = 0;
 603     LIST_FOR_EACH_ENTRY(pair, &This->pairs, struct keyitem_pair, entry) {
 604         VariantCopy(&v[i], &pair->item);
 605         i++;
 606     }
 607     SafeArrayUnaccessData(sa);
 608
 609     V_VT(items) = VT_ARRAY|VT_VARIANT;
 610     V_ARRAY(items) = sa;
 611     return S_OK;
 612 }
 613
 614 static HRESULT WINAPI dictionary_put_Key(IDictionary *iface, VARIANT *key, VARIANT *newkey)
 615 {
 616     dictionary *This = impl_from_IDictionary(iface);
 617     struct keyitem_pair *pair;
 618     VARIANT empty;
 619     HRESULT hr;
 620
 621     TRACE("(%p)->(%s %s)\n", This, debugstr_variant(key), debugstr_variant(newkey));
 622
 623     if ((pair = get_keyitem_pair(This, key))) {
 624         /* found existing pair for a key, add new pair with new key
 625            and old item and remove old pair after that */
 626
 627         hr = IDictionary_Add(iface, newkey, &pair->item);
 628         if (FAILED(hr))
 629             return hr;
 630
 631         return IDictionary_Remove(iface, key);
 632     }
 633
 634     VariantInit(&empty);
 635     return IDictionary_Add(iface, newkey, &empty);
 636 }
 637
 638 static HRESULT WINAPI dictionary_Keys(IDictionary *iface, VARIANT *keys)
 639 {
 640     dictionary *This = impl_from_IDictionary(iface);
 641     struct keyitem_pair *pair;
 642     SAFEARRAYBOUND bound;
 643     SAFEARRAY *sa;
 644     VARIANT *v;
 645     HRESULT hr;
 646     LONG i;
 647
 648     TRACE("(%p)->(%p)\n", This, keys);
 649
 650     if (!keys)
 651         return S_OK;
 652
 653     bound.lLbound = 0;
 654     bound.cElements = This->count;
 655     sa = SafeArrayCreate(VT_VARIANT, 1, &bound);
 656     if (!sa)
 657         return E_OUTOFMEMORY;
 658
 659     hr = SafeArrayAccessData(sa, (void**)&v);
 660     if (FAILED(hr)) {
 661         SafeArrayDestroy(sa);
 662         return hr;
 663     }
 664
 665     i = 0;
 666     LIST_FOR_EACH_ENTRY(pair, &This->pairs, struct keyitem_pair, entry) {
 667         VariantCopy(&v[i], &pair->key);
 668         i++;
 669     }
 670     SafeArrayUnaccessData(sa);
 671
 672     V_VT(keys) = VT_ARRAY|VT_VARIANT;
 673     V_ARRAY(keys) = sa;
 674     return S_OK;
 675 }
 676
 677 static HRESULT WINAPI dictionary_Remove(IDictionary *iface, VARIANT *key)
 678 {
 679     dictionary *This = impl_from_IDictionary(iface);
 680     struct keyitem_pair *pair;
 681
 682     TRACE("(%p)->(%s)\n", This, debugstr_variant(key));
 683
 684     if (!(pair = get_keyitem_pair(This, key)))
 685         return CTL_E_ELEMENT_NOT_FOUND;
 686
 687     notify_remove_pair(&This->notifier, &pair->entry);
 688     list_remove(&pair->entry);
 689     list_remove(&pair->bucket);
 690     This->count--;
 691
 692     free_keyitem_pair(pair);
 693     return S_OK;
 694 }
 695
 696 static HRESULT WINAPI dictionary_RemoveAll(IDictionary *iface)
 697 {
 698     dictionary *This = impl_from_IDictionary(iface);
 699     struct keyitem_pair *pair, *pair2;
 700
 701     TRACE("(%p)\n", This);
 702
 703     if (This->count == 0)
 704         return S_OK;
 705
 706     notify_remove_pair(&This->notifier, NULL);
 707     LIST_FOR_EACH_ENTRY_SAFE(pair, pair2, &This->pairs, struct keyitem_pair, entry) {
 708         list_remove(&pair->entry);
 709         list_remove(&pair->bucket);
 710         free_keyitem_pair(pair);
 711     }
 712     This->count = 0;
 713
 714     return S_OK;
 715 }
 716
 717 static HRESULT WINAPI dictionary_put_CompareMode(IDictionary *iface, CompareMethod method)
 718 {
 719     dictionary *This = impl_from_IDictionary(iface);
 720
 721     TRACE("(%p)->(%d)\n", This, method);
 722
 723     if (This->count)
 724         return CTL_E_ILLEGALFUNCTIONCALL;
 725
 726     This->method = method;
 727     return S_OK;
 728 }
 729
 730 static HRESULT WINAPI dictionary_get_CompareMode(IDictionary *iface, CompareMethod *method)
 731 {
 732     dictionary *This = impl_from_IDictionary(iface);
 733
 734     TRACE("(%p)->(%p)\n", This, method);
 735
 736     *method = This->method;
 737     return S_OK;
 738 }
 739
 740 static HRESULT WINAPI dictionary__NewEnum(IDictionary *iface, IUnknown **ret)
 741 {
 742     dictionary *This = impl_from_IDictionary(iface);
 743
 744     TRACE("(%p)->(%p)\n", This, ret);
 745
 746     return create_dict_enum(This, ret);
 747 }
 748
 749 static DWORD get_str_hash(const WCHAR *str, CompareMethod method)
 750 {
 751     DWORD hash = 0;
 752
 753     if (str) {
 754         while (*str) {
 755             WCHAR ch;
 756
 757             ch = (method == TextCompare || method == DatabaseCompare) ? tolowerW(*str) : *str;
 758
 759             hash += (hash << 4) + ch;
 760             str++;
 761         }
 762     }
 763
 764     return hash % DICT_HASH_MOD;
 765 }
 766
 767 static DWORD get_num_hash(FLOAT num)
 768 {
 769     return (*((DWORD*)&num)) % DICT_HASH_MOD;
 770 }
 771
 772 static HRESULT get_flt_hash(FLOAT flt, LONG *hash)
 773 {
 774     if (isinf(flt)) {
 775         *hash = 0;
 776         return S_OK;
 777     }
 778     else if (!isnan(flt)) {
 779         *hash = get_num_hash(flt);
 780         return S_OK;
 781     }
 782
 783     /* NaN case */
 784     *hash = ~0u;
 785     return CTL_E_ILLEGALFUNCTIONCALL;
 786 }
 787
 788 static DWORD get_ptr_hash(void *ptr)
 789 {
 790     return PtrToUlong(ptr) % DICT_HASH_MOD;
 791 }
 792
 793 static HRESULT WINAPI dictionary_get_HashVal(IDictionary *iface, VARIANT *key, VARIANT *hash)
 794 {
 795     dictionary *This = impl_from_IDictionary(iface);
 796
 797     TRACE("(%p)->(%s %p)\n", This, debugstr_variant(key), hash);
 798
 799     V_VT(hash) = VT_I4;
 800     switch (V_VT(key))
 801     {
 802     case VT_BSTR|VT_BYREF:
 803     case VT_BSTR:
 804         V_I4(hash) = get_str_hash(get_key_strptr(key), This->method);
 805         break;
 806     case VT_UI1|VT_BYREF:
 807     case VT_UI1:
 808         V_I4(hash) = get_num_hash(V_VT(key) & VT_BYREF ? *V_UI1REF(key) : V_UI1(key));
 809         break;
 810     case VT_I2|VT_BYREF:
 811     case VT_I2:
 812         V_I4(hash) = get_num_hash(V_VT(key) & VT_BYREF ? *V_I2REF(key) : V_I2(key));
 813         break;
 814     case VT_I4|VT_BYREF:
 815     case VT_I4:
 816         V_I4(hash) = get_num_hash(V_VT(key) & VT_BYREF ? *V_I4REF(key) : V_I4(key));
 817         break;
 818     case VT_UNKNOWN|VT_BYREF:
 819     case VT_DISPATCH|VT_BYREF:
 820     case VT_UNKNOWN:
 821     case VT_DISPATCH:
 822     {
 823         IUnknown *src = (V_VT(key) & VT_BYREF) ? *V_UNKNOWNREF(key) : V_UNKNOWN(key);
 824         IUnknown *unk = NULL;
 825
 826         if (!src) {
 827             V_I4(hash) = 0;
 828             return S_OK;
 829         }
 830
 831         IUnknown_QueryInterface(src, &IID_IUnknown, (void**)&unk);
 832         if (!unk) {
 833             V_I4(hash) = ~0u;
 834             return CTL_E_ILLEGALFUNCTIONCALL;
 835         }
 836         V_I4(hash) = get_ptr_hash(unk);
 837         IUnknown_Release(unk);
 838         break;
 839     }
 840     case VT_DATE|VT_BYREF:
 841     case VT_DATE:
 842         return get_flt_hash(V_VT(key) & VT_BYREF ? *V_DATEREF(key) : V_DATE(key), &V_I4(hash));
 843     case VT_R4|VT_BYREF:
 844     case VT_R4:
 845         return get_flt_hash(V_VT(key) & VT_BYREF ? *V_R4REF(key) : V_R4(key), &V_I4(hash));
 846     case VT_R8|VT_BYREF:
 847     case VT_R8:
 848         return get_flt_hash(V_VT(key) & VT_BYREF ? *V_R8REF(key) : V_R8(key), &V_I4(hash));
 849     case VT_INT:
 850     case VT_UINT:
 851     case VT_I1:
 852     case VT_I8:
 853     case VT_UI2:
 854     case VT_UI4:
 855         V_I4(hash) = ~0u;
 856         return CTL_E_ILLEGALFUNCTIONCALL;
 857     default:
 858         FIXME("not implemented for type %d\n", V_VT(key));
 859         return E_NOTIMPL;
 860     }
 861
 862     return S_OK;
 863 }
 864
 865 static const struct IDictionaryVtbl dictionary_vtbl =
 866 {
 867     dictionary_QueryInterface,
 868     dictionary_AddRef,
 869     dictionary_Release,
 870     dictionary_GetTypeInfoCount,
 871     dictionary_GetTypeInfo,
 872     dictionary_GetIDsOfNames,
 873     dictionary_Invoke,
 874     dictionary_putref_Item,
 875     dictionary_put_Item,
 876     dictionary_get_Item,
 877     dictionary_Add,
 878     dictionary_get_Count,
 879     dictionary_Exists,
 880     dictionary_Items,
 881     dictionary_put_Key,
 882     dictionary_Keys,
 883     dictionary_Remove,
 884     dictionary_RemoveAll,
 885     dictionary_put_CompareMode,
 886     dictionary_get_CompareMode,
 887     dictionary__NewEnum,
 888     dictionary_get_HashVal
 889 };
 890
 891 HRESULT WINAPI Dictionary_CreateInstance(IClassFactory *factory,IUnknown *outer,REFIID riid, void **obj)
 892 {
 893     dictionary *This;
 894
 895     TRACE("(%p, %p, %s, %p)\n", factory, outer, debugstr_guid(riid), obj);
 896
 897     *obj = NULL;
 898
 899     This = heap_alloc(sizeof(*This));
 900     if(!This) return E_OUTOFMEMORY;
 901
 902     This->IDictionary_iface.lpVtbl = &dictionary_vtbl;
 903     This->ref = 1;
 904     This->method = BinaryCompare;
 905     This->count = 0;
 906     list_init(&This->pairs);
 907     list_init(&This->notifier);
 908     memset(This->buckets, 0, sizeof(This->buckets));
 909
 910     init_classinfo(&CLSID_Dictionary, (IUnknown *)&This->IDictionary_iface, &This->classinfo);
 911     *obj = &This->IDictionary_iface;
 912
 913     return S_OK;
 914 }