collections/Source/collections_map.c

   1 /*
   2 * Copyright (c) 2019 Apple Inc. All rights reserved.
   3 *
   4 * @APPLE_LICENSE_HEADER_START@
   5 *
   6 * This file contains Original Code and/or Modifications of Original Code
   7 * as defined in and that are subject to the Apple Public Source License
   8 * Version 2.0 (the 'License'). You may not use this file except in
   9 * compliance with the License. Please obtain a copy of the License at
  10 * http://www.opensource.apple.com/apsl/ and read it before using this
  11 * file.
  12 *
  13 * The Original Code and all software distributed under the License are
  14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  18 * Please see the License for the specific language governing rights and
  19 * limitations under the License.
  20 *
  21 * @APPLE_LICENSE_HEADER_END@
  22 */
  23
  24 #include <os/collections_map.h>
  25
  26 #include <os/base_private.h>
  27 #include <stdlib.h>
  28 #include <string.h>
  29 #include <sys/types.h>
  30 #include <assert.h>
  31
  32 static inline bool
  33 os_map_str_key_equals(const char * a, const char *b)
  34 {
  35         return a == b || strcmp(a, b) == 0;
  36 }
  37
  38 static inline uint32_t
  39 os_map_str_hash(const char *key)
  40 {
  41         uint32_t hash = 0;
  42
  43         for (; *key; key++) {
  44                 hash += (unsigned char)(*key);
  45                 hash += (hash << 10);
  46                 hash ^= (hash >> 6);
  47         }
  48
  49         hash += (hash << 3);
  50         hash ^= (hash >> 11);
  51         hash += (hash << 15);
  52
  53         return hash;
  54 }
  55
  56 static inline bool
  57 os_map_32_key_equals(uint32_t a, uint32_t b)
  58 {
  59         return a == b;
  60 }
  61
  62 static inline uint32_t
  63 os_map_32_hash(uint32_t x)
  64 {
  65         x = ((x >> 16) ^ x) * 0x45d9f3b;
  66         x = ((x >> 16) ^ x) * 0x45d9f3b;
  67         x = (x >> 16) ^ x;
  68         return (uint32_t)x;
  69 }
  70
  71 static inline bool
  72 os_map_64_key_equals(uint64_t a, uint64_t b)
  73 {
  74         return a == b;
  75 }
  76
  77 static inline uint32_t
  78 os_map_64_hash(uint64_t key)
  79 {
  80         return os_map_32_hash((uint32_t)key ^ (uint32_t)(key >> 32));
  81 }
  82
  83 static inline bool
  84 os_map_128_key_equals(os_map_128_key_t a, os_map_128_key_t b)
  85 {
  86     return a.x[0] == b.x[0] &&
  87         a.x[1] == b.x[1];
  88 }
  89
  90 static inline uint32_t
  91 os_map_128_hash(os_map_128_key_t key)
  92 {
  93     return os_map_64_hash(key.x[0] ^ key.x[1]);
  94 }
  95
  96 // The following symbols are required for each include of collections_map.in.c
  97 // IN_MAP(, _t)
  98 //      EXAMPLE: os_map_64_t
  99 //      The opaque representation of the map.
 100 // IN_MAP(, _hash)
 101 //      EXAMPLE: os_map_64_hash
 102 //      The default hash function for the map
 103 // IN_MAP(,_key_equals)
 104 //      Example: os_map_64_key_equals
 105 //      The equality check for this map
 106
 107 #define IN_MAP(PREFIX, SUFFIX) PREFIX ## os_map_str ## SUFFIX
 108 #define os_map_key_t const char *
 109 #define MAP_SUPPORTS_ENTRY
 110 #include "collections_map.in.c"
 111 #undef IN_MAP
 112 #undef os_map_key_t
 113 #undef MAP_SUPPORTS_ENTRY
 114
 115 #define IN_MAP(PREFIX, SUFFIX) PREFIX ## os_map_32 ## SUFFIX
 116 #define os_map_key_t uint32_t
 117 #include "collections_map.in.c"
 118 #undef IN_MAP
 119 #undef os_map_key_t
 120
 121 #define IN_MAP(PREFIX, SUFFIX) PREFIX ## os_map_64 ## SUFFIX
 122 #define os_map_key_t uint64_t
 123 #include "collections_map.in.c"
 124 #undef IN_MAP
 125 #undef os_map_key_t
 126
 127 #define IN_MAP(PREFIX, SUFFIX) PREFIX ## os_map_128 ## SUFFIX
 128 #define os_map_key_t os_map_128_key_t
 129 #include "collections_map.in.c"
 130 #undef IN_MAP
 131 #undef os_map_key_t