Libc-1439.100.3.tar.gz

[apple/libc.git] / collections / PublicHeader / collections_map.h

/*
* Copyright (c) 2019 Apple Inc. All rights reserved.
*
* @APPLE_LICENSE_HEADER_START@
*
* This file contains Original Code and/or Modifications of Original Code
* as defined in and that are subject to the Apple Public Source License
* Version 2.0 (the 'License'). You may not use this file except in
* compliance with the License. Please obtain a copy of the License at
* http://www.opensource.apple.com/apsl/ and read it before using this
* file.
*
* The Original Code and all software distributed under the License are
* distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
* Please see the License for the specific language governing rights and
* limitations under the License.
*
* @APPLE_LICENSE_HEADER_END@
*/

#ifndef _OS_COLLECTIONS_MAP_H
#define _OS_COLLECTIONS_MAP_H

#include <os/base.h>
#include <stdint.h>
#include <stdbool.h>
#include <TargetConditionals.h>
#include <sys/types.h>

OS_ASSUME_NONNULL_BEGIN

struct os_map_config_s
{
	const char *name; // Only used when DEBUG is set
	uint32_t initial_size; // If 0, default will be used
};

// Increment this when changing os_map_config_s
#define OS_MAP_CONFIG_S_VERSION 1

typedef struct os_map_config_s os_map_config_t;


// *** HASH MAPS ***
// Stores values for keys. Not safe for concurrent use.


struct os_map_128_key_s {
	uint64_t x[2];
};

typedef struct os_map_128_key_s os_map_128_key_t;

#if TARGET_RT_64_BIT
#define OPAQUE_MAP_SIZE 3
#else
#define OPAQUE_MAP_SIZE 4
#endif

struct _os_opaque_str_map_s {
	void *data[OPAQUE_MAP_SIZE];
};

struct _os_opaque_32_map_s {
	void *data[OPAQUE_MAP_SIZE];
};

struct _os_opaque_64_map_s {
	void *data[OPAQUE_MAP_SIZE];
};

struct _os_opaque_128_map_s {
	void *data[OPAQUE_MAP_SIZE];
};

// Map with string keys and void * values
// Keys must be valid pointers.
typedef struct _os_opaque_str_map_s os_map_str_t ;
// Map with uint32_t keys and void * values
typedef struct _os_opaque_32_map_s os_map_32_t ;
// Map with uint64_t keys and void * values
typedef struct _os_opaque_64_map_s os_map_64_t ;
// Map with os_map_128_key_t keys and void * values
typedef struct _os_opaque_128_map_s os_map_128_t ;

/*!
* @function os_map_init
* Initialize a map.
*
* @param t
* The table to initialize
*
* @param config
* The configuration to use for this table
*
* @discussion
* An initialized map will use additional memory which can be freed with
* os_map_destroy.
*/
OS_OVERLOADABLE OS_ALWAYS_INLINE
static inline void
os_map_init(os_map_64_t *m, os_map_config_t * _Nullable config);

/*!
* @function os_map_destroy
* Destroy a map.
*
* @param t
* The table to destroy.
*
* @discussion
* This will free all memory used by the map, but will not take any action
* on the keys/values that were in the map at the time.
*/
OS_OVERLOADABLE OS_ALWAYS_INLINE
static inline void
os_map_destroy(os_map_64_t *m);

/*!
* @function os_map_insert
* Insert an element into a map.
*
* @param t
* The table to initialize
*
* @param key
* The key to insert the value at
*
* @param val
* The value to insert; cannot be NULL (use os_map_delete to remove entries)
*
* @discussion
* This will insert an element into the map, growing the map if needed. Does not
* support replacing an existing key, so inserting twice without a remove will
* cause undefined behavior.
*/
OS_OVERLOADABLE OS_ALWAYS_INLINE
static inline void
os_map_insert(os_map_64_t *m, uint64_t key, void *val);

/*!
* @function os_map_find
* Find an element in a map.
*
* @param t
* The map to search
*
* @param key
* The key to search for
*
* @result
* The value stored at key, or NULL if no value is present.
*
*/
OS_OVERLOADABLE OS_ALWAYS_INLINE
static inline void * _Nullable
os_map_find(os_map_64_t *m, uint64_t key);

/*!
* @function os_map_delete
* Remove an element from a map.
*
* @param t
* The map to remove the element from
*
* @param key
* The key of the element to be removed
*
* @result
* The value stored at key, or NULL if no value is present.
*
* @discussion
* Has no effect if the key is not present
*/
OS_OVERLOADABLE OS_ALWAYS_INLINE
static inline void * _Nullable
os_map_delete(os_map_64_t *m, uint64_t key);

typedef bool (^os_map_64_payload_handler_t) (uint64_t, void *);

/*!
* @function os_map_clear
* Removes all elements from a map.
*
* @param t
* The map to remove the elements from
*
* @param handler
* A handler that will be called for all elements in the table. Handler may be
* NULL.
*
* @discussion
* Has no effect if the key is not present
*/
OS_OVERLOADABLE OS_ALWAYS_INLINE
static inline void
os_map_clear(os_map_64_t *m,
		  OS_NOESCAPE os_map_64_payload_handler_t _Nullable handler);

/*!
* @function os_map_count
* Gets the number of items present in a map
*
* @param t
* The map to get the count of
*
* @result
* Returns the number of items present in the map
*/
OS_OVERLOADABLE OS_ALWAYS_INLINE
static inline size_t
os_map_count(os_map_64_t *m);

/*!
* @function os_map_foreach
*Iterate over the key/value pairs in a map.
*
* @param t
* The map to iterate over
*
* @param handler
* The handler to call for each entry in the map.
*
* @discussion
* Will invoke handler for each key/value pair in the map. Modifying the map
* during this iteration is not permitted. The handler may be called on the
* entries in any order.
*/
OS_OVERLOADABLE OS_ALWAYS_INLINE
static inline void
os_map_foreach(os_map_64_t *m,
		 OS_NOESCAPE os_map_64_payload_handler_t handler);

/*!
* @function os_map_entry
* Gets the exact entry, if present, for a given key and NULL otherwise.
*
* @param t
* The map to search
*
* @param key
* The key to search for
*
* @discussion
* Only available for os_map_str_t.
* Gets the exact entry, if present, for a given key and NULL otherwise. So, for
* two equal strings a, b where a != b. We guarentee that
* os_map_entry(t, a) == os_map_entry(t, b)
*/
OS_OVERLOADABLE OS_ALWAYS_INLINE
static inline const char *
os_map_entry(os_map_str_t *m, const char *key);

OS_ASSUME_NONNULL_END

#include <os/_collections_map.h>

#endif /* _OS_COLLECTIONS_MAP_H */