/*
 * Copyright (c) 2018 The Fuchsia Authors.
 *
 * Permission to use, copy, modify, and/or distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */
#ifndef GARNET_DRIVERS_WLAN_THIRD_PARTY_ATHEROS_ATH10K_SPARSE_ARRAY_H_
#define GARNET_DRIVERS_WLAN_THIRD_PARTY_ATHEROS_ATH10K_SPARSE_ARRAY_H_

#include <stddef.h>
#include <sys/types.h>

// A sparse array provides an association between index values and payloads.
// The operations available and their time complexity are:
//   add: add a new element, returning the index into which it was stored, O(1)
//   get: return the value associated with an index, O(1)
//   remove: remove the value associated with an index, O(1)
//   for_each: call a function for each value in the used list, O(n), where n
//             is the number of indices in use

// Note that concurrent accesses are unsupported, so the caller must provide
// their own mutex if it's needed.

struct sparse_array;
typedef struct sparse_array* sparse_array_t;

// Allocate a new sparse array into *psa. Sets to NULL if memory allocation fails.
void sa_init(sparse_array_t* psa, size_t size);

// Deallocate a sparse array.
void sa_free(sparse_array_t sa);

// Add an element to a sparse array, returns the index or -1 if no entries are available.
ssize_t sa_add(sparse_array_t sa, void* payload);

// Get the element at the specified index, which must be in the used list.
void* sa_get(sparse_array_t sa, ssize_t ndx);

// Remove an element from a sparse array, which must be in the used list.
void sa_remove(sparse_array_t sa, ssize_t ndx);

// Call a function on each element in a sparse array.
void sa_for_each(sparse_array_t sa, void (*fn)(ssize_t ndx, void* ptr, void* ctx), void* ctx);

#endif  // GARNET_DRIVERS_WLAN_THIRD_PARTY_ATHEROS_ATH10K_SPARSE_ARRAY_H_