GCC Wikia
Advertisement

このページを編集する際は,編集に関する方針に従ってください.[]

概要[]

  • gcc-4.1.0/libiberty/hashtab.cにて定義
  • 与えられた要素と等しいエントリを含んでいるハッシュテーブルスロットを捜す

引数[]

実装[]

  578: /* This function searches for a hash table slot containing an entry
  579:    equal to the given element.  To delete an entry, call this with
  580:    insert=NO_INSERT, then call htab_clear_slot on the slot returned
  581:    (possibly after doing some checks).  To insert an entry, call this
  582:    with insert=INSERT, then write the value you want into the returned
  583:    slot.  When inserting an entry, NULL may be returned if memory
  584:    allocation fails.  */
  この関数は、与えられたelementと等しいエントリを含んでいるハッシュテーブルスロットを捜します。
  エントリを削除するときは、insert=NO_INSERTでこれを呼んでください、
  そして、スロットの上の呼び出しhtab_clear_slotは帰りました
  (おそらく、いくらかのチェックをした後に)。
  エントリを挿入するときは、insert=INSERTでこれを呼んでください、
  そして、あなたが返されたスロットに望む価値を書いてください。
  エントリを挿入するとき、メモリアロケーションが失敗するならば、NULLは返されるかもしれません。
585: 
586: PTR *
587: htab_find_slot_with_hash (htab_t htab, const PTR element,
588:                           hashval_t hash, enum insert_option insert)
589: {
590:   PTR *first_deleted_slot;
591:   hashval_t index, hash2;
592:   size_t size;
593:   PTR entry;
594: 

~
*テーブルが小さいときテーブルの大きさを変更する

595:   size = htab_size (htab);
596:   if (insert == [[INSERT>enum insert_option]] && size * 3 <= htab->n_elements * 4)
597:     {
598:       if (htab_expand (htab) == 0)
599:         return NULL;
600:       size = htab_size (htab);
601:     }
602: 

~

603:   index = htab_mod (hash, htab);
604: 
605:   htab->searches++;
606:   first_deleted_slot = NULL;
607: 
608:   entry = htab->entries[index];
609:   if (entry == HTAB_EMPTY_ENTRY)
610:     goto empty_entry;
611:   else if (entry == HTAB_DELETED_ENTRY)
612:     first_deleted_slot = &htab->entries[index];

*見つかった

613:   else if ((*htab->eq_f) (entry, element))
614:     return &htab->entries[index];
615:       

~

616:   hash2 = htab_mod_m2 (hash, htab);
617:   for (;;)
618:     {
619:       htab->collisions++;
620:       index += hash2;
621:       if (index >= size)
622:         index -= size;
623:       
624:       entry = htab->entries[index];
625:       if (entry == HTAB_EMPTY_ENTRY)
626:         goto empty_entry;
627:       else if (entry == HTAB_DELETED_ENTRY)
628:         {
629:           if (!first_deleted_slot)
630:             first_deleted_slot = &htab->entries[index];
631:         }

*見つかった

632:       else if ((*htab->eq_f) (entry, element))
633:         return &htab->entries[index];
634:     }

~
*elementと一致するエントリがない

635: 
636:  empty_entry:
637:   if (insert == [[NO_INSERT>enum insert_option]])
638:     return NULL;
639: 
640:   if (first_deleted_slot)
641:     {
642:       htab->n_deleted--;
643:       *first_deleted_slot = HTAB_EMPTY_ENTRY;
644:       return first_deleted_slot;
645:     }
646: 
647:   htab->n_elements++;
648:   return &htab->entries[index];
649: }


リンク元

Advertisement