This is o_map.m in view mode; [Download] [Up]
/* A map table implementation.
* Copyright (C) 1993, 1994, 1995, 1996 Free Software Foundation, Inc.
*
* Author: Albin L. Jones <Albin.L.Jones@Dartmouth.EDU>
* Created: ??? ??? ?? ??:??:?? ??? 1993
* Updated: Tue Mar 12 02:12:37 EST 1996
* Serial: 96.03.12.25
*
* This file is part of the GNUstep Base Library.
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Library General Public
* License as published by the Free Software Foundation; either
* version 2 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Library General Public License for more details.
*
* You should have received a copy of the GNU Library General Public
* License along with this library; if not, write to the Free
* Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */
/**** Included Headers *******************************************************/
#include <Foundation/NSZone.h>
#include <gnustep/base/o_cbs.h>
#include <gnustep/base/o_hash.h>
#include <gnustep/base/o_map.h>
/**** Function Implementations ***********************************************/
/** Background functions **/
static inline o_map_bucket_t *
_o_map_pick_bucket_for_key(o_map_t *map,
o_map_bucket_t *buckets,
size_t bucket_count,
const void *key)
{
return buckets + (o_hash(o_map_key_callbacks(map),
key, map)
% bucket_count);
}
static inline o_map_bucket_t *
_o_map_pick_bucket_for_node(o_map_t *map,
o_map_bucket_t *buckets,
size_t bucket_count,
o_map_node_t *node)
{
return buckets + (o_hash(o_map_key_callbacks(map),
node->key, map)
% bucket_count);
}
static inline o_map_bucket_t *
_o_map_bucket_for_key(o_map_t *map, const void *key)
{
return _o_map_pick_bucket_for_key(map, map->buckets,
map->bucket_count, key);
}
static inline o_map_bucket_t *
_o_map_bucket_for_node(o_map_t *map, o_map_node_t *node)
{
return _o_map_pick_bucket_for_node(map, map->buckets,
map->bucket_count, node);
}
static inline void
_o_map_link_node_into_bucket(o_map_bucket_t *bucket,
o_map_node_t *node)
{
if (bucket->first_node != 0)
bucket->first_node->prev_in_bucket = node;
node->next_in_bucket = bucket->first_node;
bucket->first_node = node;
return;
}
static inline void
_o_map_unlink_node_from_its_bucket(o_map_node_t *node)
{
if (node == node->bucket->first_node)
node->bucket->first_node = node->next_in_bucket;
if (node->prev_in_bucket != 0)
node->prev_in_bucket->next_in_bucket = node->next_in_bucket;
if (node->next_in_bucket != 0)
node->next_in_bucket->prev_in_bucket = node->prev_in_bucket;
node->prev_in_bucket = node->next_in_bucket = 0;
return;
}
static inline void
_o_map_link_node_into_map(o_map_t *map,
o_map_node_t *node)
{
if (map->first_node != 0)
map->first_node->prev_in_map = node;
node->next_in_map = map->first_node;
map->first_node = node;
return;
}
static inline void
_o_map_unlink_node_from_its_map(o_map_node_t *node)
{
if (node == node->map->first_node)
node->map->first_node = node->next_in_map;
if (node->prev_in_map != 0)
node->prev_in_map->next_in_map = node->next_in_map;
if (node->next_in_map != 0)
node->next_in_map->prev_in_map = node->prev_in_map;
node->prev_in_map = node->next_in_map = 0;
return;
}
static inline void
_o_map_add_node_to_bucket(o_map_bucket_t *bucket,
o_map_node_t *node)
{
if (bucket != 0)
{
_o_map_link_node_into_bucket(bucket, node);
node->bucket = bucket;
bucket->node_count += 1;
bucket->element_count += 1;
}
return;
}
static inline void
_o_map_add_node_to_its_bucket(o_map_t *map,
o_map_node_t *node)
{
_o_map_add_node_to_bucket(_o_map_bucket_for_node(map, node),
node);
return;
}
static inline void
_o_map_add_node_to_map(o_map_t *map, o_map_node_t *node)
{
if (map != 0)
{
_o_map_add_node_to_its_bucket(map, node);
_o_map_link_node_into_map(map, node);
node->map = map;
map->node_count += 1;
map->element_count += 1;
}
return;
}
static inline void
_o_map_remove_node_from_its_bucket(o_map_node_t *node)
{
if (node->bucket != 0)
{
node->bucket->node_count -= 1;
node->bucket->element_count -= 1;
_o_map_unlink_node_from_its_bucket(node);
}
return;
}
static inline void
_o_map_remove_node_from_its_map(o_map_node_t *node)
{
if (node->map != 0)
{
node->map->node_count -= 1;
node->map->element_count -= 1;
_o_map_unlink_node_from_its_map(node);
}
_o_map_remove_node_from_its_bucket(node);
return;
}
static inline o_map_bucket_t *
_o_map_new_buckets(o_map_t *map, size_t bucket_count)
{
return (o_map_bucket_t *)NSZoneCalloc(o_map_zone(map),
bucket_count,
sizeof(o_map_bucket_t));
}
static inline void
_o_map_free_buckets(o_map_t *map, o_map_bucket_t *buckets)
{
if (buckets != 0)
NSZoneFree(o_map_zone(map), buckets);
return;
}
static inline void
_o_map_remangle_buckets(o_map_t *map,
o_map_bucket_t *old_buckets,
size_t old_bucket_count,
o_map_bucket_t *new_buckets,
size_t new_bucket_count)
{
size_t i;
o_map_node_t *node;
for (i = 0; i < old_bucket_count; i++)
{
while ((node = old_buckets[i].first_node) != 0)
{
_o_map_remove_node_from_its_bucket(node);
_o_map_add_node_to_bucket(_o_map_pick_bucket_for_node(map,
new_buckets,
new_bucket_count,
node),
node);
}
}
/* And that's that. */
return;
}
static inline o_map_node_t *
_o_map_new_node(o_map_t *map, const void *key, const void *value)
{
o_map_node_t *node;
/* Allocate the space for a new node. */
node = (o_map_node_t *)NSZoneMalloc(o_map_zone(map),
sizeof(o_map_node_t));
if (node != 0)
{
/* Retain KEY and VALUE. (They're released below in
* `_o_map_free_node()'.) */
o_retain(o_map_key_callbacks(map), key, map);
o_retain(o_map_value_callbacks(map), value, map);
/* Remember KEY and VALUE. */
node->key = key;
node->value = value;
/* Zero out the various pointers. */
node->map = 0;
node->bucket = 0;
node->next_in_bucket = 0;
node->next_in_map = 0;
node->prev_in_bucket = 0;
node->prev_in_map = 0;
}
return node;
}
static inline void
_o_map_free_node(o_map_node_t *node)
{
if (node != 0)
{
o_map_t *map;
/* Remember NODE's map. */
map = node->map;
/* Release KEY and VALUE. (They're retained above in
* `_o_map_new_node()'.) */
o_release(o_map_key_callbacks(map),
(void *)node->key, map);
o_release(o_map_value_callbacks(map),
(void *)node->value, map);
/* Actually free the space map aside for NODE. */
NSZoneFree(o_map_zone(map), node);
}
/* And just return. */
return;
}
static inline o_map_node_t *
_o_map_node_for_key(o_map_t *map, const void *key)
{
o_map_bucket_t *bucket;
o_map_node_t *node;
/* Find the bucket in which the node for KEY would be. */
bucket = _o_map_bucket_for_key(map, key);
/* Run through the nodes in BUCKET until we find one whose element
* matches ELEMENT. */
for (node = bucket->first_node;
(node != 0) && !o_is_equal(o_map_key_callbacks(map),
key,
node->key,
map);
node = node->next_in_bucket);
/* Note that if none of the nodes' elements matches ELEMENT, then we
* naturally return `0'. */
return node;
}
/* A non--static-inline version for use in NSObject.
xxx Figure out if this change should be generalized. */
o_map_node_t *
o_map_node_for_key (o_map_t *map, const void *key)
{
return _o_map_node_for_key (map, key);
}
/* A non--static-inline version for use in NSObject.
xxx Figure out if this change should be generalized. */
void
o_map_remove_node (o_map_node_t *node)
{
_o_map_remove_node_from_its_map (node);
_o_map_free_node(node);
}
/** Callbacks... **/
/* Return a hash index for MAP. Needed for the callbacks below. */
size_t
_o_map_hash(o_map_t *map)
{
/* One might be tempted to do something simple here, but remember:
* If two map tables are equal they *must* hash to the same value! */
/* FIXME: Code this. */
return 0;
}
/* An (inefficient, but necessary) "retaining" function for map tables. */
o_map_t *
_o_map_retain(o_map_t *map, o_map_t *in_map)
{
/* Note that this works only because all the structures (hash, map
* list, array) look alike at first...so we can get the zone of
* one just like we can get the zone of any of them. */
return o_map_copy_with_zone(map, o_map_zone(in_map));
}
/* Returns a collection of callbacks for use with map tables. */
o_callbacks_t
o_callbacks_for_map(void)
{
o_callbacks_t map_callbacks =
{
(o_hash_func_t) _o_map_hash,
(o_compare_func_t) 0,
(o_is_equal_func_t) o_map_is_equal_to_map,
(o_retain_func_t) _o_map_retain,
(o_release_func_t) o_map_dealloc,
(o_describe_func_t) o_map_description,
0
};
return map_callbacks;
}
/** Resizing **/
size_t
o_map_resize(o_map_t *map, size_t new_capacity)
{
o_map_bucket_t *new_buckets;
/* Round NEW_CAPACITY up to the next power of two. */
new_capacity = _o_next_power_of_two(new_capacity);
/* Make a new map of buckets. */
new_buckets = _o_map_new_buckets(map, new_capacity);
if (new_buckets != 0)
{
_o_map_remangle_buckets(map,
map->buckets,
map->bucket_count,
new_buckets,
new_capacity);
_o_map_free_buckets(map, map->buckets);
map->buckets = new_buckets;
map->bucket_count = new_capacity;
}
/* Return the new capacity. */
return map->bucket_count;
}
size_t
o_map_rightsize(o_map_t *map)
{
/* FIXME: Now, this is a guess, based solely on my intuition. If anyone
* knows of a better ratio (or other test, for that matter) and can
* provide evidence of its goodness, please get in touch with me, Albin
* L. Jones <Albin.L.Jones@Dartmouth.EDU>. */
if (3 * map->node_count > 4 * map->bucket_count)
{
return o_map_resize(map, map->bucket_count + 1);
}
else
{
return map->bucket_count;
}
}
/** Statistics... **/
/* Returns the number of key/value pairs in MAP. */
size_t
o_map_count(o_map_t *map)
{
return map->element_count;
}
/* Returns some (inexact) measure of how many key/value pairs
* MAP can comfortably hold without resizing. */
size_t
o_map_capacity(o_map_t *map)
{
return map->bucket_count;
}
/* Performs an internal consistency check, returns 'true' if
* everything is OK, 'false' otherwise. Really useful only
* for debugging. */
int
o_map_check(o_map_t *map)
{
/* FIXME: Code this. */
return 1;
}
int
o_map_is_empty(o_map_t *map)
{
return o_map_count(map) == 0;
}
/** Searching **/
/* Returns 'true' if and only if some key in MAP is equal
* (in the sense of the key callbacks of MAP) to KEY. */
int
o_map_contains_key(o_map_t *map, const void *key)
{
if (_o_map_node_for_key(map, key) != 0)
return 1;
else
return 0;
}
/* Returns 'true' if and only if some value in MAP is equal
* (in the sense of the value callbacks of MAP) to VALUE. */
/* WARNING: This is rather inefficient. Not to be used lightly. */
int
o_map_contains_value(o_map_t *map, const void *value)
{
o_map_enumerator_t me;
const void *v = 0;
/* ME is an enumerator for MAP. */
me = o_map_enumerator_for_map(map);
/* Enumerate, and check. */
while (o_map_enumerator_next_value(&me, &v))
if (o_is_equal(o_map_value_callbacks(map), value, v, map))
return 1;
/* If we made it this far, then VALUE isn't in MAP. */
return 0;
}
/* If KEY is in MAP, then the following three things happen:
* (1) 'true' is returned;
* (2) if OLD_KEY is non-zero, then the key in MAP
* equal to KEY is placed there;
* (3) if VALUE is non-zero, then the value in MAP
* mapped to by KEY is placed there.
* If KEY is not in MAP, then the following three things happen:
* (1) 'false' is returned;
* (2) if OLD_KEY is non-zero, then the "not a key marker"
* for MAP is placed there;
* (3) if VALUE is non-zero, then the the "not a value marker"
* for MAP is placed there. */
inline int
o_map_key_and_value_at_key(o_map_t *map,
const void **old_key,
const void **value,
const void *key)
{
o_map_node_t *node;
/* Try and find the node for KEY. */
node = _o_map_node_for_key(map, key);
if (node != 0)
{
if (old_key != 0)
*old_key = node->key;
if (value != 0)
*value = node->value;
return 1;
}
else /* (node == 0) */
{
if (old_key != 0)
*old_key = o_map_not_a_key_marker(map);
if (value != 0)
*value = o_map_not_a_value_marker(map);
return 0;
}
}
/* If KEY is in MAP, then the key of MAP which is equal to KEY
* is returned. Otherwise, the "not a key marker" for MAP is returned. */
const void *
o_map_key_at_key(o_map_t *map, const void *key)
{
const void *old_key;
/* Use the grandfather function above... */
o_map_key_and_value_at_key(map, &old_key, 0, key);
return old_key;
}
/* If KEY is in MAP, then the value of MAP which to which KEY maps
* is returned. Otherwise, the "not a value marker" for MAP is returned. */
const void *
o_map_value_at_key(o_map_t *map, const void *key)
{
const void *value;
/* Use the grandfather function above... */
o_map_key_and_value_at_key(map, 0, &value, key);
return value;
}
const void **
o_map_all_keys_and_values(o_map_t *map)
{
size_t j;
const void **array;
o_map_enumerator_t enumerator;
/* Allocate space for ARRAY. Remember that it is the programmer's
* responsibility to free this by calling
* `NSZoneFree(o_map_zone(MAP), ARRAY)' */
array = (const void **)NSZoneCalloc(o_map_zone(map),
2 * (o_map_count(map) + 1),
sizeof(void *));
/* ENUMERATOR is an enumerator for MAP. */
enumerator = o_map_enumerator_for_map(map);
/* Now we enumerate through the elements of MAP, adding them one-by-one
* to ARRAY. Note that this automagically puts the ``not a key/value
* markers'' at the end of ARRAY. */
for (j = 0;
o_map_enumerator_next_key_and_value(&enumerator,
array + j,
array + j + 1);
j += 2);
/* And we're done. */
return array;
}
const void **
o_map_all_keys(o_map_t *map)
{
size_t j;
const void **array;
o_map_enumerator_t enumerator;
/* FIXME: Morally, deallocating this space shouldn't be the
* programmer's responsibility. Maybe we should be returning
* an NSArray? */
/* Allocate space for ARRAY. Remember that it is the programmer's
* responsibility to free this by calling
* `NSZoneFree(o_map_zone(MAP), ARRAY)' */
array = (const void **)NSZoneCalloc(o_map_zone(map),
o_map_count(map) + 1,
sizeof(void *));
/* ENUMERATOR is an enumerator for MAP. */
enumerator = o_map_enumerator_for_map(map);
/* Now we enumerate through the elements of MAP, adding them one-by-one
* to ARRAY. Note that this automagically puts the ``not a key marker''
* at the end of ARRAY. */
for (j = 0; o_map_enumerator_next_key(&enumerator, array + j); j++);
/* And we're done. */
return array;
}
const void **
o_map_all_values(o_map_t *map)
{
size_t j;
const void **array;
o_map_enumerator_t enumerator;
/* FIXME: Morally, deallocating this space shouldn't be the
* programmer's responsibility. Maybe we should be returning
* an NSArray? */
/* Allocate space for ARRAY. Remember that it is the programmer's
* responsibility to free this by calling
* `NSZoneFree(o_map_zone(MAP), ARRAY)' */
array = (const void **)NSZoneCalloc(o_map_zone(map),
o_map_count(map) + 1,
sizeof(void *));
/* ENUMERATOR is an enumerator for MAP. */
enumerator = o_map_enumerator_for_map(map);
/* Now we enumerate through the elements of MAP, adding them one-by-one
* to ARRAY. Note that this automagically puts the ``not a value
* marker'' at the end of ARRAY. */
for (j = 0; o_map_enumerator_next_value(&enumerator, array + j); j++);
/* And we're done. */
return array;
}
/** Enumerating **/
/* WARNING: You should not alter a map while an enumeration is
* in progress. The results of doing so are reasonably unpremapable.
* With that in mind, read the following warnings carefully. But
* remember, DON'T MESS WITH A MAP WHILE YOU'RE ENUMERATING IT. */
/* IMPORTANT WARNING: Map enumerators, as I have map them up, have a
* wonderous property. Namely, that, while enumerating, one may add
* new elements (i.e., new nodes) to the map while an enumeration is
* in progress (i.e., after `o_map_enumerator_for_map()' has been
* called), and the enumeration remains the same. */
/* WARNING: The above warning should not, in any way, be taken as
* assurance that this property of map enumerators will be preserved
* in future editions of the library. I'm still thinking about
* this. */
/* IMPORTANT WARNING: Enumerators have yet another wonderous property.
* Once a node has been returned by `_map_next_node()', it may be
* removed from the map without effecting the rest of the current
* enumeration. For example, to clean all of the nodes out of a map,
* the following code would work:
*
* void
* empty_my_map(o_map_t *map)
* {
* o_map_enuemrator_t enumerator = o_map_enumerator_for_map(map);
* o_map_node_t *node;
*
* while ((node = _o_map_next_node(&enumerator)) != 0)
* {
* _o_map_remove_node_from_its_map(node);
* _o_map_free_node(node);
* }
*
* return;
* }
*
* (In fact, this is the code currently being used below in the
* function `map_delete_all_elements()'.) But again, this is not to be
* taken as an assurance that this behaviour will persist in future
* versions of the library. */
/* EXTREMELY IMPORTANT WARNING: The purpose of this warning is point
* out that, at this time, various (i.e., many) functions depend on
* the behaviours outlined above. So be prepared for some serious
* breakage when you go fudging around with these things. */
o_map_enumerator_t
o_map_enumerator_for_map(o_map_t *map)
{
o_map_enumerator_t enumerator;
/* Make sure ENUMERATOR knows its mapionary. */
enumerator.map = map;
/* Start ENUMERATOR at MAP's first node. */
enumerator.node = map->first_node;
return enumerator;
}
o_map_node_t *
_o_map_enumerator_next_node(o_map_enumerator_t *enumerator)
{
o_map_node_t *node;
/* Remember ENUMERATOR's current node. */
node = enumerator->node;
/* If NODE is a real node, then we need to increment ENUMERATOR's
* current node to the next node in ENUMERATOR's map. */
if (node != 0)
enumerator->node = enumerator->node->next_in_map;
/* Send back NODE. */
return node;
}
int
o_map_enumerator_next_key_and_value(o_map_enumerator_t *enumerator,
const void **key,
const void **value)
{
o_map_node_t *node;
/* Try and get the next node in the enumeration represented by
* ENUMERATOR. */
node = _o_map_enumerator_next_node(enumerator);
if (node != 0)
{
/* If NODE is real, then return the key and value it contains. */
if (key != 0)
*key = node->key;
if (value != 0)
*value = node->value;
/* Indicate that the enumeration continues. */
return 1;
}
else
{
/* If NODE isn't real, then we return the ``bogus'' indicators. */
if (key != 0)
*key = o_map_not_a_key_marker(enumerator->map);
if (value != 0)
*value = o_map_not_a_value_marker(enumerator->map);
/* Indicate that the enumeration is over. */
return 0;
}
}
int
o_map_enumerator_next_key(o_map_enumerator_t *enumerator,
const void **key)
{
return o_map_enumerator_next_key_and_value(enumerator, key, 0);
}
int
o_map_enumerator_next_value(o_map_enumerator_t *enumerator,
const void **value)
{
return o_map_enumerator_next_key_and_value(enumerator, 0, value);
}
/** Adding **/
/* FIXME: Make this check for invalidity and abort or raise an exception! */
const void *
o_map_at_key_put_value_known_absent(o_map_t *map,
const void *key,
const void *value)
{
o_map_node_t *node;
/* Resize MAP if needed. */
o_map_rightsize(map);
/* Make NODE a node which holds KEY and VALUE. */
node = _o_map_new_node(map, key, value);
if (node != 0)
{
/* NODE is real, so stick it in MAP. */
_o_map_add_node_to_map(map, node);
/* Return ELEMENT, just in case someone wants to look at it. */
return key;
}
else
{
/* NODE would be `0' only if an allocation failed, but it's worth
* checking and returning an error if appropriate, I guess. It just
* seems like the kind thing to do. */
return o_map_not_a_key_marker(map);
}
}
const void *
o_map_at_key_put_value(o_map_t *map,
const void *key,
const void *value)
{
o_map_node_t *node;
/* First, we check for KEY in MAP. */
node = _o_map_node_for_key(map, key);
if (node != 0)
{
o_retain(o_map_value_callbacks(map), value, map);
o_release(o_map_value_callbacks(map),
(void *)node->value, map);
node->value = value;
return node->key;
}
else
{
/* KEY isn't in MAP, so we can add it with impunity. */
return o_map_at_key_put_value_known_absent(map, key, value);
}
}
const void *
o_map_at_key_put_value_if_absent(o_map_t *map,
const void *key,
const void *value)
{
o_map_node_t *node;
/* Look for a node with KEY in it. */
node = _o_map_node_for_key(map, key);
if (node != 0)
{
/* If NODE is real, then KEY is already in MAP. So we return the
* member key of MAP which is ``equal to'' KEY. */
return node->key;
}
else
{
/* If NODE isn't real, then we may add KEY (and VALUE) to MAP without
* worrying too much. */
return o_map_at_key_put_value_known_absent(map, key, value);
}
}
/** Removing **/
void
o_map_remove_key(o_map_t *map, const void *key)
{
o_map_node_t *node;
/* Look for a node with KEY in it. */
node = _o_map_node_for_key(map, key);
if (node != 0)
{
/* If NODE is real, then we've got something to remove. */
_o_map_remove_node_from_its_map(node);
_o_map_free_node(node);
}
return;
}
/** Emptying **/
void
o_map_empty(o_map_t *map)
{
o_map_enumerator_t enumerator;
o_map_node_t *node;
/* Get an element enumerator for MAP. */
enumerator = o_map_enumerator_for_map(map);
/* Just step through the nodes of MAP and wipe them out, one after
* another. Don't try this at home, kids! */
while ((node = _o_map_enumerator_next_node(&enumerator)) != 0)
{
_o_map_remove_node_from_its_map(node);
_o_map_free_node(node);
}
/* And return. */
return;
}
/** Creating **/
o_map_t *
o_map_alloc_with_zone(NSZone * zone)
{
o_map_t *map;
map = _o_map_alloc_with_zone(zone);
return map;
}
o_map_t *
o_map_alloc(void)
{
return o_map_alloc_with_zone(0);
}
o_map_t *
o_map_with_zone(NSZone * zone)
{
return o_map_init(o_map_alloc_with_zone(zone));
}
o_map_t *
o_map_with_zone_with_callbacks(NSZone * zone,
o_callbacks_t key_callbacks,
o_callbacks_t value_callbacks)
{
return o_map_init_with_callbacks(o_map_alloc_with_zone(zone),
key_callbacks,
value_callbacks);
}
o_map_t *
o_map_with_callbacks(o_callbacks_t key_callbacks,
o_callbacks_t value_callbacks)
{
return o_map_init_with_callbacks(o_map_alloc(),
key_callbacks,
value_callbacks);
}
o_map_t *
o_map_of_char_p(void)
{
return o_map_with_callbacks(o_callbacks_for_char_p,
o_callbacks_for_char_p);
}
o_map_t *
o_map_of_char_p_to_int(void)
{
return o_map_with_callbacks(o_callbacks_for_char_p,
o_callbacks_for_int);
}
o_map_t *
o_map_of_char_p_to_non_owned_void_p(void)
{
return o_map_with_callbacks(o_callbacks_for_char_p,
o_callbacks_for_non_owned_void_p);
}
o_map_t *
o_map_of_char_p_to_id(void)
{
return o_map_with_callbacks(o_callbacks_for_char_p,
o_callbacks_for_id);
}
o_map_t *
o_map_of_non_owned_void_p(void)
{
return o_map_with_callbacks(o_callbacks_for_non_owned_void_p,
o_callbacks_for_non_owned_void_p);
}
o_map_t *
o_map_of_int(void)
{
return o_map_with_callbacks(o_callbacks_for_int,
o_callbacks_for_int);
}
o_map_t *
o_map_of_int_to_char_p(void)
{
return o_map_with_callbacks(o_callbacks_for_int,
o_callbacks_for_char_p);
}
o_map_t *
o_map_of_int_to_non_owned_void_p(void)
{
return o_map_with_callbacks(o_callbacks_for_int,
o_callbacks_for_non_owned_void_p);
}
o_map_t *
o_map_of_int_to_id(void)
{
return o_map_with_callbacks(o_callbacks_for_int,
o_callbacks_for_id);
}
o_map_t *
o_map_of_id(void)
{
return o_map_with_callbacks(o_callbacks_for_id,
o_callbacks_for_id);
}
o_map_t *
o_map_of_id_to_int(void)
{
return o_map_with_callbacks(o_callbacks_for_id,
o_callbacks_for_int);
}
o_map_t *
o_map_of_id_to_char_p(void)
{
return o_map_with_callbacks(o_callbacks_for_id,
o_callbacks_for_char_p);
}
o_map_t *
o_map_of_id_to_non_owned_void_p(void)
{
return o_map_with_callbacks(o_callbacks_for_id,
o_callbacks_for_non_owned_void_p);
}
/** Initializing **/
o_map_t *
o_map_init_with_callbacks(o_map_t *map,
o_callbacks_t key_callbacks,
o_callbacks_t value_callbacks)
{
if (map != 0)
{
size_t capacity = 10;
/* Make a note of the callbacks for MAP. */
map->key_callbacks = o_callbacks_standardize(key_callbacks);
map->value_callbacks = o_callbacks_standardize(value_callbacks);
/* Zero out the various counts. */
map->node_count = 0;
map->bucket_count = 0;
map->element_count = 0;
/* Zero out the pointers. */
map->first_node = 0;
map->buckets = 0;
/* Resize MAP to the given CAPACITY. */
o_map_resize(map, capacity);
}
/* Return the newly initialized MAP. */
return map;
}
o_map_t *
o_map_init(o_map_t *map)
{
return o_map_init_with_callbacks(map,
o_callbacks_standard(),
o_callbacks_standard());
}
o_map_t *
o_map_init_from_map(o_map_t *map, o_map_t *old_map)
{
o_map_enumerator_t enumerator;
const void *key;
const void *value;
/* Initialize MAP. */
o_map_init_with_callbacks(map,
o_map_key_callbacks(old_map),
o_map_value_callbacks(old_map));
o_map_resize(map, o_map_capacity(old_map));
/* Get an enumerator for OLD_MAP. */
enumerator = o_map_enumerator_for_map(old_map);
/* Step through the pairs of OLD_MAP, adding each in turn to MAP. */
while (o_map_enumerator_next_key_and_value(&enumerator, &key, &value))
o_map_at_key_put_value(map, key, value);
/* Return the newly initialized MAP. */
return map;
}
/** Destroying... **/
/* Releases all the keys and values of MAP, and then
* deallocates MAP itself. */
void
o_map_dealloc(o_map_t *map)
{
if (map != 0)
{
/* Remove all of MAP's elements. */
o_map_empty(map);
/* Free up the bucket array. */
_o_map_free_buckets(map, map->buckets);
/* And finally, free up the space that MAP itself takes up. */
_o_map_dealloc(map);
}
return;
}
/** Replacing **/
void
o_map_replace_key(o_map_t *map,
const void *key)
{
o_map_node_t *node;
/* Look up the node (if any) for KEY in MAP. */
node = _o_map_node_for_key(map, key);
if (node != 0)
{
/* Remember: First retain, then release;
* just in case they're the same. */
o_retain(o_map_key_callbacks(map), key, map);
o_release(o_map_key_callbacks(map),
(void *)(node->key), map);
/* Because "equality" is suppossedly transitive, we needn't
* worry about having duplicate keys in MAP after this. */
node->key = key;
}
return;
}
/** Comparing **/
/* Returns 'true' if every key/value pair of MAP2 is also a key/value pair
* of MAP1. Otherwise, returns 'false'. */
int
o_map_contains_map(o_map_t *map1, o_map_t *map2)
{
o_map_enumerator_t enumerator;
const void *key = 0;
const void *value = 0;
/* ENUMERATOR is a key/value enumerator for MAP2. */
enumerator = o_map_enumerator_for_map(map2);
while (o_map_enumerator_next_key_and_value(&enumerator, &key, &value))
{
o_map_node_t *node;
/* Try an get MAP1's node for KEY. */
node = _o_map_node_for_key(map1, key);
/* If MAP1 doesn't even have KEY as a key, then we're done. */
if (node == 0)
return 0;
/* If MAP1 has K as a key, but doesn't map
* KEY to VALUE, then we're done. */
if (o_compare(o_map_value_callbacks(map1), node->value,
value, map1))
return 0;
}
return 1;
}
/* Returns 'true' iff some key/value pair of MAP1 if also
* a key/value pair of MAP2. */
int
o_map_intersects_map(o_map_t *map1, o_map_t *map2)
{
o_map_enumerator_t enumerator;
const void *key = 0;
const void *value = 0;
/* ENUMERATOR is a key/value enumerator for MAP2. */
enumerator = o_map_enumerator_for_map(map2);
while (o_map_enumerator_next_key_and_value(&enumerator, &key, &value))
{
o_map_node_t *node;
/* Try an get MAP1's node for KEY. */
node = _o_map_node_for_key(map1, key);
/* If MAP1 doesn't even have KEY as a key, then we're done. */
if (node != 0)
/* If MAP1 has KEY as a key, and maps KEY
* to VALUE, then we're done. Yippee! */
if (o_is_equal(o_map_value_callbacks(map1),
node->value, value, map1))
return 1;
}
return 0;
}
int
o_map_is_equal_to_map(o_map_t *map1, o_map_t *map2)
{
/* Check the counts. */
if (o_map_count(map1) != o_map_count(map2))
return 0;
/* If the counts match, then we do an pair by pair check. */
if (!o_map_contains_map(map1, map2)
|| !o_map_contains_map(map2, map1))
return 0;
/* If we made it this far, MAP1 and MAP2 are the same. */
return 1;
}
/* Returns 'true' iff every key of MAP2 is a key of MAP1. */
int
o_map_keys_contain_keys_of_map(o_map_t *map1, o_map_t *map2)
{
o_map_enumerator_t enumerator;
const void *key;
enumerator = o_map_enumerator_for_map(map2);
if (o_map_count(map1) < o_map_count(map2))
return 0;
while (o_map_enumerator_next_key(&enumerator, &key))
if (!o_map_contains_key(map1, key))
return 0;
return 1;
}
/* Returns 'true' iff some key of MAP1 if also a key of MAP2. */
int
o_map_keys_intersect_keys_of_map(o_map_t *map1,
o_map_t *map2)
{
o_map_enumerator_t enumerator;
const void *key;
enumerator = o_map_enumerator_for_map(map1);
while (o_map_enumerator_next_key(&enumerator, &key))
if (o_map_contains_key(map2, key))
return 1;
return 0;
}
/* Returns 'true' if MAP1 and MAP2 have the same number of key/value pairs,
* MAP1 contains every key of MAP2, and MAP2 contains every key of MAP1.
* Otherwise, returns 'false'. */
int
o_map_keys_are_equal_to_keys_of_map(o_map_t *map1,
o_map_t *map2);
/** Copying **/
o_map_t *
o_map_copy_with_zone(o_map_t *old_map, NSZone * zone)
{
o_map_t *new_map;
/* Alloc the NEW_MAP. */
new_map = _o_map_copy_with_zone(old_map, zone);
/* Initialize the NEW_MAP. */
o_map_init_from_map(new_map, old_map);
/* And return the copy. */
return new_map;
}
o_map_t *
o_map_copy(o_map_t *old_map)
{
return o_map_copy_with_zone(old_map, 0);
}
/** Describing... **/
/* Returns a string describing (the contents of) MAP. */
NSString *
o_map_description(o_map_t *map)
{
/* FIXME: Code this. */
return nil;
}
/** Mapping **/
o_map_t *
o_map_map_keys(o_map_t *map,
const void *(*fcn)(const void *, void *),
void *user_data)
{
o_map_enumerator_t enumerator;
o_map_node_t *node;
enumerator = o_map_enumerator_for_map(map);
while ((node = _o_map_enumerator_next_node(&enumerator)) != 0)
{
const void *key;
key = (*fcn)(node->key, user_data);
o_retain(o_map_key_callbacks(map), key, map);
o_release(o_map_key_callbacks(map),
(void *)(node->key), map);
node->key = key;
}
return map;
}
o_map_t *
o_map_map_values(o_map_t *map,
const void *(*fcn) (const void *, void *),
void *user_data)
{
o_map_enumerator_t enumerator;
o_map_node_t *node;
enumerator = o_map_enumerator_for_map(map);
while ((node = _o_map_enumerator_next_node(&enumerator)) != 0)
{
const void *value;
value = (*fcn)(node->value, user_data);
o_retain(o_map_value_callbacks(map), value, map);
o_release(o_map_value_callbacks(map),
(void *)(node->value), map);
node->value = value;
}
return map;
}
/** Miscellaneous **/
o_map_t *
o_map_intersect_map(o_map_t *map, o_map_t *other_map)
{
o_map_enumerator_t enumerator;
const void *key;
enumerator = o_map_enumerator_for_map(map);
while (o_map_enumerator_next_key(&enumerator, &key))
if (!o_map_contains_key(other_map, key))
o_map_remove_key(map, key);
return map;
}
o_map_t *
o_map_minus_map(o_map_t *map, o_map_t *other_map)
{
o_map_enumerator_t enumerator;
const void *key;
enumerator = o_map_enumerator_for_map(other_map);
while (o_map_enumerator_next_key(&enumerator, &key))
{
o_map_remove_key(map, key);
}
return map;
}
o_map_t *
o_map_union_map(o_map_t *map, o_map_t *other_map)
{
o_map_enumerator_t enumerator;
const void *key;
const void *value;
enumerator = o_map_enumerator_for_map(other_map);
while (o_map_enumerator_next_key_and_value(&enumerator, &key, &value))
{
o_map_at_key_put_value_if_absent(map, key, value);
}
return map;
}
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.