tests/collections_random.c

   1 /*
   2 * Copyright (c) 2020 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.h>
  25 #include <stdio.h>
  26 #include <string.h>
  27 #include <unistd.h>
  28 #include <darwintest.h>
  29 #include <stdlib.h>
  30
  31 #define RANDOM_COUNT 256
  32
  33
  34 // Returns a random 32 bit integer
  35 static uint32_t random_32() {
  36         uint32_t result = rand();
  37         return result;
  38 }
  39
  40 // Returns a random 64 bit integer thats not 0 or ~0
  41 static uint64_t random_64() {
  42         return (uint64_t)random_32() | ((uint64_t)random_32() << 32);
  43 }
  44
  45 static bool array_contains(uint32_t *array, int size, uint32_t entry) {
  46         for (int i = 0; i < size; i++) {
  47                 if(array[i] == entry) {
  48                         return true;
  49                 }
  50         }
  51         return false;
  52 }
  53
  54 // Returns a random 32 bit integer thats not in the array
  55 static uint32_t random_32_not_in_array(uint32_t *array, int size) {
  56         uint32_t candidate;
  57         do {
  58                 candidate = random_32();
  59         } while (array_contains(array, size, candidate));
  60         return candidate;
  61 }
  62
  63 #define RUN_MAP_RANDOM(MAP, KEY_CONV)                                           \
  64 {                                                                               \
  65         T_LOG("Start run map for " #MAP);                                       \
  66                                                                                 \
  67         uint32_t keys[RANDOM_COUNT];                                            \
  68         void *vals[RANDOM_COUNT];                                               \
  69                                                                                 \
  70         os_map_init(&MAP, NULL);                                                \
  71                                                                                 \
  72         /* Insert random values for sequential keys to the map */               \
  73         for (int i = 0; i < RANDOM_COUNT; i++) {                                \
  74                 uint32_t key = random_32_not_in_array(keys, i);                 \
  75                 void *val = (void *)random_64();                                \
  76                 T_LOG("Inserting 0x%x, 0x%llx", key, (unsigned long long)val);  \
  77                 os_map_insert(&MAP, KEY_CONV(key), val);                        \
  78                 keys[i] = key;                                                  \
  79                 vals[i] = val;                                                  \
  80         }                                                                       \
  81                                                                                 \
  82         /* Find all the values */                                               \
  83         for (int i = 0; i < RANDOM_COUNT; i++) {                                \
  84                 uint32_t key = keys[i];                                         \
  85                 void *expected_val = vals[i];                                   \
  86                 void *actual_val = os_map_find(&MAP, KEY_CONV(key));            \
  87                 if (expected_val == actual_val) {                               \
  88                         T_PASS("Found 0x%x, 0x%llx", key,                       \
  89                                 (unsigned long long)expected_val);              \
  90                 } else {                                                        \
  91                         T_FAIL("Incorrect find for 0x%x, Expected 0x%llx but got 0x%llx", \
  92                                 key, (unsigned long long)expected_val,          \
  93                                 (unsigned long long)actual_val);                \
  94                 }                                                               \
  95         }                                                                       \
  96                                                                                 \
  97         /* Find some nonexistant values */                                      \
  98         for (int i = 0; i < RANDOM_COUNT; i++) {                                \
  99                 uint32_t key =  random_32_not_in_array(keys, RANDOM_COUNT);     \
 100                 void *val = os_map_find(&MAP, KEY_CONV(key));                   \
 101                 if (val == NULL) {                                              \
 102                         T_PASS("Did not find value for nonexistant key 0x%x",   \
 103                                 key);                                           \
 104                 } else {                                                        \
 105                         T_FAIL("Found value for nonexistant key 0x%x (0x%llx)", \
 106                                 key, (unsigned long long)val);                  \
 107                 }                                                               \
 108         }                                                                       \
 109                                                                                 \
 110         /* Remove half of the values */                                         \
 111         for (int i = 0; i < RANDOM_COUNT; i+=2) {                               \
 112                 uint32_t key = keys[i];                                         \
 113                 os_map_delete(&MAP, KEY_CONV(key));                             \
 114                 vals[i] == NULL;                                                \
 115         }                                                                       \
 116                                                                                 \
 117         /* Find the half that are still there */                                \
 118         for (int i = 1; i < RANDOM_COUNT; i+=2) {                               \
 119                 uint32_t key = keys[i];                                         \
 120                 void *expected_val = vals[i];                                   \
 121                 void *actual_val = os_map_find(&MAP, KEY_CONV(key));            \
 122                 if (expected_val == actual_val) {                               \
 123                         T_PASS("Found 0x%x, 0x%llx", key,                       \
 124                                 (unsigned long long)expected_val);              \
 125                 } else {                                                        \
 126                         T_FAIL("Incorrect find for 0x%x, Expected 0x%llx but got 0x%llx", \
 127                                 key, (unsigned long long)expected_val,          \
 128                                 (unsigned long long)actual_val);                \
 129                 }                                                               \
 130         }                                                                       \
 131                                                                                 \
 132         /* Find the half that aren't there */                                   \
 133         for (int i = 0; i < RANDOM_COUNT; i+=2) {                               \
 134                 uint32_t key = keys[i];                                         \
 135                 void *val = os_map_find(&MAP, KEY_CONV(key));                   \
 136                 if (val == NULL) {                                              \
 137                         T_PASS("Did not find value for nonexistant key 0x%x",   \
 138                                 key);                                           \
 139                 } else {                                                        \
 140                         T_FAIL("Found value for nonexistant key 0x%x (0x%llx)", \
 141                                 key, (unsigned long long)val);                  \
 142                 }                                                               \
 143         }                                                                       \
 144                                                                                 \
 145         os_map_destroy(&MAP);                                                   \
 146 }
 147
 148 uint64_t key_conv_32_to_64(uint32_t key) {
 149         return (uint64_t)key | ((uint64_t)key << 32);
 150 }
 151
 152 uint32_t key_conv_32_to_32(uint32_t key) {
 153         return key;
 154 }
 155
 156 const char *key_conv_32_to_string(uint32_t key) {
 157         // TODO: Make this not leak
 158         char *output;
 159         assert(asprintf(&output, "0x%x", key) > 0);
 160         return (const char *)output;
 161 }
 162
 163 T_DECL(map_random_64,
 164        "Make sure 64 bit map works for a bunch of random entries",
 165         T_META("owner", "Core Darwin Daemons & Tools"))
 166 {
 167         os_map_64_t random_64_map;
 168
 169         RUN_MAP_RANDOM(random_64_map, key_conv_32_to_64);
 170 }
 171
 172 T_DECL(map_random_32,
 173        "Make sure 32 bit map works for a bunch of random entries",
 174         T_META("owner", "Core Darwin Daemons & Tools"))
 175 {
 176         os_map_32_t random_32_map;
 177
 178         RUN_MAP_RANDOM(random_32_map, key_conv_32_to_32);
 179
 180 }
 181
 182 T_DECL(map_random_string,
 183        "Make sure string map works for a bunch of random entries",
 184         T_META("owner", "Core Darwin Daemons & Tools"),
 185         T_META_CHECK_LEAKS(false))
 186 {
 187
 188         os_map_str_t random_s_map;
 189
 190         RUN_MAP_RANDOM(random_s_map, key_conv_32_to_string);
 191
 192 }
 193