hashmap.h

#️⃣ hashmap.h

Implementasi hashmap satu header sederhana untuk C/C++.

Penggunaan

Cukup #include "hashmap.h" dalam kode Anda!

Kompiler yang didukung saat ini adalah gcc, clang dan msvc.

Platform yang didukung saat ini adalah Linux, macOS dan Windows.

Desain Dasar

Peta hash dibuat untuk bekerja dengan kunci data apa pun - Anda cukup memberikan penunjuk dan ukuran, dan data tersebut akan di-hash. Hasher default adalah varian crc32 yang menggunakan intrinsik perangkat keras jika memungkinkan, dan pembanding default hanya menggunakan memcmp , jadi disarankan untuk menghilangkan padding apa pun di kunci struct.

Buat Peta Hash

Untuk membuat hashmap, panggil fungsi hashmap_create :

 const unsigned initial_size = 2 ;
struct hashmap_s hashmap ;
if ( 0 != hashmap_create ( initial_size , & hashmap )) {
  // error!
}

Parameter initial_size hanya menetapkan ukuran awal peta hash - yang dapat bertambah jika beberapa kunci menekan entri hash yang sama. Ukuran peta hash dibulatkan ke pangkat dua terdekat di atas initial_size yang disediakan.

Ada juga fungsi pembuatan yang diperluas hashmap_create_ex :

 struct hashmap_s hashmap ;
struct hashmap_create_options_s options ;
memset ( & options , 0 , sizeof ( options ));

// You can set a custom hasher that the hashmap should use.
options . hasher = & my_hasher ;

// You can set a custom comparer that the hashmap should for comparing keys.
options . comparer = & my_comparer ;

// You can also specify the initial capacity of the hashmap.
options . initial_capacity = 42 ;

if ( 0 != hashmap_create_ex ( options , & hashmap )) {
  // error!
}

Masukkan Sesuatu ke dalam Hashmap

Untuk memasukkan item ke dalam hashmap gunakan fungsi hashmap_put :

 int meaning_of_life = 42 ;
char question = 6 * 8 ;

if ( 0 != hashmap_put ( & hashmap , "life" , strlen ( "life" ), & meaning_of_life )) {
  // error!
}

if ( 0 != hashmap_put ( & hashmap , "?" , strlen ( "?" ), & question )) {
  // error!
}

Perhatikan bahwa beberapa entri dengan tipe berbeda bisa ada di peta hash yang sama. Hashmap tidak diketik - ia dapat menyimpan data void* apa pun sebagai nilai kunci.

Dapatkan Sesuatu dari Hashmap

Untuk mendapatkan entri dari hashmap gunakan fungsi hashmap_get :

 void * const element = hashmap_get ( & hashmap , "x" , strlen ( "x" ));
if ( NULL == element ) {
  // error!
}

Fungsi ini akan mengembalikan NULL jika elemen tidak ditemukan. Perhatikan bahwa kunci yang digunakan untuk mendapatkan elemen tidak harus berupa penunjuk yang sama dengan yang digunakan untuk meletakkan elemen di peta hash - tetapi potongan string harus cocok agar hit dapat terjadi.

Hapus Sesuatu dari Hashmap

Untuk menghapus entri dari hashmap gunakan fungsi hashmap_remove :

 if ( 0 != hashmap_remove ( & hashmap , "x" , strlen ( "x" ))) {
  // error!
}

Fungsi ini akan mengembalikan nilai bukan nol jika elemen tidak ditemukan. Perhatikan bahwa kunci yang digunakan untuk mendapatkan elemen tidak harus berupa penunjuk yang sama dengan yang digunakan untuk meletakkan elemen di peta hash - tetapi potongan string harus cocok agar hit dapat terjadi.

Ulangi Hashmap

Anda dapat mengulangi semua elemen yang disimpan dalam hashmap dengan fungsi hashmap_iterate :

 static int iterate ( void * const context , void * const value ) {
  // If the value is 42...
  if ( 42 == * ( int * ) value ) {
    // Store into our user-provided context the value.
    * ( void * * ) context = value ;

    // Return 0 to tell the iteration to stop here.
    return 0 ;
  }

  // Otherwise tell the iteration to keep going.
  return 1 ;
}

int * value ;
if ( 0 != hashmap_iterate ( & hashmap , iterate , & value )) {
  if ( * value != 42 ) {
    // error!
  }
} else {
  // if we got here it means we never found 42 in the hashmap
}

Anda dapat keluar lebih awal dari iterasi peta hash dengan mengembalikan bukan nol dari fungsi panggilan balik Anda - mungkin Anda ingin memproses dan menghapus semua elemen dari peta hash atau mencari nilai tertentu saja. Jika tidak, jika nol dikembalikan dari panggilan balik Anda maka iterasi akan mencakup seluruh peta hash.

Iterator Alternatif untuk Pasangan Nilai Kunci

Dalam beberapa aplikasi, seperti kebutuhan untuk mencetak konten peta hash, Anda perlu memiliki akses ke kunci dan panjang kunci selain nilainya. Untuk tujuan itu, iterator kedua telah ditambahkan bernama hashmap_iterate_pairs .

Selain itu, mengembalikan -1 dari fungsi panggilan balik memungkinkan penghapusan item saat ini secara otomatis. Hal ini sangat berguna ketika menyimpan objek yang dialokasikan secara dinamis ke peta dan perlu mengosongkan memori saat menghancurkan peta.

 int log_and_free_all ( void * const context , struct hashmap_element_s * const e ) {
  int counter ;
  for ( counter = 0 ; counter < e -> key_len ; counter ++ ) {
    fputc ( e -> key [ counter ], ( FILE ) context );
  }
  fprintf (( FILE ) context , "=%s pair has been freedn" , ( char * ) e -> data );
  free ( e -> data );
  return -1 ;
}

void shut_down () {
  if ( 0 != hashmap_iterate_pairs ( & hash , log_and_free_all , ( void * ) log )) {
    fprintf ( stderr , "failed to deallocate hashmap entriesn" );
  }
  fclose ( log );
  hashmap_destroy ( & hash );
}

Dapatkan Jumlah Entri dalam Hashmap

Untuk mendapatkan jumlah entri yang telah dimasukkan ke dalam hashmap gunakan fungsi hashmap_num_entries :

 unsigned num_entries = hashmap_num_entries ( & hashmap );

Dapatkan Kapasitas Hashmap

Untuk mendapatkan jumlah aktual keranjang yang dialokasikan dalam hashmap (kapasitas) gunakan fungsi hashmap_capacity :

 unsigned num_entries = hashmap_capacity ( & hashmap );

Hancurkan Hashmap

Untuk menghancurkan hashmap setelah Anda selesai menggunakannya, gunakan fungsi hashmap_destroy :

 hashmap_destroy ( & hashmap );

Kepemilikan Kode

Kode ini hampir seluruhnya ditulis oleh Pete Warden yang mengagumkan, berdasarkan postingan blog Elliott Back yang sekarang sudah tidak ada lagi. Penulis telah menerapkan perubahan lebih lanjut berikut ini:

• Menggabungkan .c / .h untuk membuat satu header (artinya integrasi lebih mudah dengan proyek eksternal).
• Menggunakan lisensi domain publik secara eksplisit untuk kodenya - tidak berlisensi.
• Mengubah API untuk mengambil penunjuk dan panjang data sewenang-wenang (awalnya hanya untuk potongan string UTF-8).
• Melakukan izin untuk membersihkan komentar dan tanda tangan fungsi.
• Menambahkan iterator kedua, tes dan dokumentasi. (Samuel D. Gagak)

Lisensi

Ini adalah perangkat lunak gratis dan tidak terbebani yang dirilis ke domain publik.

Siapa pun bebas menyalin, memodifikasi, menerbitkan, menggunakan, menyusun, menjual, atau mendistribusikan perangkat lunak ini, baik dalam bentuk kode sumber atau sebagai biner terkompilasi, untuk tujuan apa pun, komersial atau non-komersial, dan dengan cara apa pun.

Di wilayah hukum yang mengakui undang-undang hak cipta, pembuat perangkat lunak ini mendedikasikan setiap dan seluruh kepentingan hak cipta dalam perangkat lunak tersebut ke domain publik. Pengabdian ini kami lakukan demi kemaslahatan masyarakat luas dan merugikan ahli waris serta penerus kami. Kami bermaksud dedikasi ini menjadi tindakan pelepasan yang terang-terangan untuk selamanya atas semua hak saat ini dan di masa depan atas perangkat lunak ini berdasarkan undang-undang hak cipta.

PERANGKAT LUNAK INI DISEDIAKAN "APA ADANYA", TANPA JAMINAN APA PUN, TERSURAT MAUPUN TERSIRAT, TERMASUK NAMUN TIDAK TERBATAS PADA JAMINAN KELAYAKAN UNTUK DIPERDAGANGKAN, KESESUAIAN UNTUK TUJUAN TERTENTU, DAN TIDAK ADA PELANGGARAN. DALAM KEADAAN APA PUN PENULIS TIDAK BERTANGGUNG JAWAB ATAS KLAIM, KERUSAKAN ATAU TANGGUNG JAWAB LAINNYA, BAIK DALAM TINDAKAN KONTRAK, HUKUM ATAU LAINNYA, YANG TIMBUL DARI, DARI ATAU SEHUBUNGAN DENGAN PERANGKAT LUNAK ATAU PENGGUNAAN ATAU HAL-HAL LAIN DALAM PERANGKAT LUNAK.

Untuk informasi lebih lanjut, silakan merujuk ke http://unlicense.org/