hashmap.h

#️⃣ hashmap.h

C/C++에 대한 간단한 단일 헤더 해시맵 구현입니다.

용법

코드에 #include "hashmap.h" 하세요!

현재 지원되는 컴파일러는 gcc, clang 및 msvc입니다.

현재 지원되는 플랫폼은 Linux, macOS 및 Windows입니다.

기본 설계

해시맵은 임의의 데이터 키와 함께 작동하도록 만들어졌습니다. 포인터와 크기만 제공하면 해당 데이터가 해시됩니다. 기본 해시는 가능한 경우 하드웨어 내장 함수를 사용하는 crc32 변형이고 기본 비교자는 memcmp 만 사용하므로 구조체 키의 패딩을 0으로 만드는 것이 좋습니다.

해시맵 만들기

해시맵을 생성하려면 hashmap_create 함수를 호출하세요:

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

initial_size 매개변수는 해시맵의 초기 크기만 설정합니다. 이는 여러 키가 동일한 해시 항목에 도달하는 경우 커질 수 있습니다. 해시맵의 크기는 제공된 initial_size 보다 가장 가까운 2의 거듭제곱으로 반올림됩니다.

확장된 생성 함수 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!
}

해시맵에 무언가 넣기

해시맵에 항목을 넣으려면 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!
}

동일한 해시맵에 서로 다른 유형의 여러 항목이 존재할 수 있습니다. 해시맵은 유형이 지정되지 않습니다. void* 데이터를 키 값으로 저장할 수 있습니다.

해시맵에서 무언가 얻기

해시맵에서 항목을 얻으려면 hashmap_get 함수를 사용하세요:

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

요소를 찾을 수 없으면 함수는 NULL 반환합니다. 요소를 가져오는 데 사용되는 키는 해시맵에 요소를 넣는 데 사용되는 포인터와 동일할 필요는 없습니다. 하지만 적중이 발생하려면 문자열 조각이 일치해야 합니다.

해시맵에서 항목 제거

해시맵에서 항목을 제거하려면 hashmap_remove 함수를 사용하세요.

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

요소를 찾을 수 없으면 함수는 0이 아닌 값을 반환합니다. 요소를 가져오는 데 사용되는 키는 해시맵에 요소를 넣는 데 사용되는 포인터와 동일할 필요는 없습니다. 하지만 적중이 발생하려면 문자열 조각이 일치해야 합니다.

해시맵 반복

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
}

콜백 함수에서 0이 아닌 값을 반환하여 해시맵 반복을 조기에 종료할 수 있습니다. 아마도 해시맵에서 모든 요소를 ​​처리하고 제거하거나 특정 값만 검색하기를 원할 것입니다. 그렇지 않고 콜백에서 0이 반환되면 반복은 전체 해시맵을 포함하게 됩니다.

키 값 쌍에 대한 대체 반복자

해시맵의 내용을 인쇄해야 하는 등 일부 애플리케이션에서는 값 외에도 키와 키 길이에 대한 액세스 권한이 필요합니다. 이를 위해 hashmap_iterate_pairs 라는 두 번째 반복자가 추가되었습니다.

또한 콜백 함수에서 -1을 반환하면 현재 항목을 자동으로 제거할 수 있습니다. 이는 동적으로 할당된 객체를 맵에 저장하고 맵을 삭제할 때 메모리를 해제해야 할 때 특히 유용합니다.

 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 );
}

해시맵의 항목 수 가져오기

해시맵에 입력된 항목 수를 얻으려면 hashmap_num_entries 함수를 사용하십시오.

 unsigned num_entries = hashmap_num_entries ( & hashmap );

해시맵의 용량 가져오기

해시맵에 할당된 실제 버킷 수(용량)를 얻으려면 hashmap_capacity 함수를 사용하세요.

 unsigned num_entries = hashmap_capacity ( & hashmap );

해시맵 삭제

해시맵 작업이 끝난 후 해시맵을 삭제하려면 hashmap_destroy 함수를 사용하세요.

 hashmap_destroy ( & hashmap );

코드 소유권

이 코드는 지금은 없어진 Elliott Back의 블로그 게시물을 기반으로 멋진 Pete Warden이 거의 전적으로 작성했습니다. 저자는 다음과 같은 추가 변경 사항을 적용했습니다.

• .c / .h를 병합하여 단일 헤더를 생성했습니다(외부 프로젝트와의 통합이 더 쉬워짐).
• 코드에 대해 명시적인 공개 도메인 라이선스(Unlicense)를 사용했습니다.
• 임의의 데이터 포인터와 길이를 사용하도록 API를 변경했습니다(원래는 UTF-8 문자열 조각 전용이었습니다).
• 주석과 함수 서명을 정리하기 위한 패스를 수행했습니다.
• 두 번째 반복자, 테스트 및 문서가 추가되었습니다. (사무엘 D. 크로우)

특허

이는 공개 도메인으로 출시된 무료이며 제한이 없는 소프트웨어입니다.

누구든지 이 소프트웨어를 소스 코드 형식이나 컴파일된 바이너리로, 상업적 또는 비상업적 목적과 어떤 수단으로든 자유롭게 복사, 수정, 게시, 사용, 컴파일, 판매 또는 배포할 수 있습니다.

저작권법을 인정하는 관할권에서 이 소프트웨어의 작성자는 소프트웨어에 대한 모든 저작권 이익을 공개 도메인에 바칩니다. 우리는 대중의 이익을 위해 그리고 우리의 상속자와 후계자들에게 손해를 끼치기 위해 이러한 헌신을 합니다. 우리는 이러한 헌신이 저작권법에 따라 이 소프트웨어에 대한 현재 및 미래의 모든 권리를 영구적으로 포기하는 명백한 행위가 되도록 의도합니다.

소프트웨어는 상품성, 특정 목적에의 적합성 및 비침해에 대한 보증을 포함하되 이에 국한되지 않고 명시적이든 묵시적이든 어떠한 종류의 보증 없이 "있는 그대로" 제공됩니다. 어떠한 경우에도 작성자는 소프트웨어나 소프트웨어의 사용 또는 기타 거래로 인해 발생하거나 이와 관련하여 발생하는 계약, 불법 행위 또는 기타 모든 청구, 손해 또는 기타 책임에 대해 책임을 지지 않습니다.

자세한 내용은 http://unlicense.org/를 참조하세요.