polar-hash-table.c

/* Internal API: hash table type for polar-objc.
   Copyright (C) 2022-2025 Michael Malicoat <[email protected]>
 
   This file is part of polar-objc.
 
   polar-objc is free software; you can redistribute it and/or modify it under the terms of the GNU General Public
   License as published by the Free Software Foundation; either version 3, or (at your option) any later version.
 
   polar-objc 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 General Public License for more
   details.
 
   You should have received a copy of the GNU General Public License along with this program; see the file LICENSE.  If
   not, see <http://www.gnu.org/licenses/>.
*/
 
// polar_hash_table ****************************************************************************************************
// Private =============================================================================================================
 
// This variable is initialized in polar_hash_table_get_type()
static polar_hash_table_class class_polar_hash_table;
 
// This variable is initialized in _polar_hash_table_class_init()
static polar_runtime_object_class *superclass_polar_hash_table = NULL;
 
// ---------------------------------------------------------------------------------------------------------------------
 
static inline void
polar_hash_table_insert_node( polar_hash_table *self, polar_hash_table_node *node_new )
{
  assert( POLAR_IS_HASH_TABLE(self) );
 
  POLAR_HASH_TABLE_GET_CLASS(self)->insert_node(self, node_new);
}
 
static inline BOOL
polar_hash_table_must_grow( polar_hash_table *self )
{
  assert( POLAR_IS_HASH_TABLE(self) );
 
  // Return YES if the table is filled to ~75% capacity or more; NO otherwise
  return ( (self->count_entries + ((self->mask_buckets + 1) >> 2)) >= (self->mask_buckets + 1) );
}
 
static inline void
polar_hash_table_maybe_free_buckets( polar_hash_table *self )
{
  assert( POLAR_IS_HASH_TABLE(self) );
 
  if( self->count_entries > 0 )
    ;
 
  else
  {
    polar_runtime_object_free( (polar_runtime_object *)(self->array_buckets) );
    self->array_buckets = NULL;
  }
}
 
static inline polar_hash_table_node *
polar_hash_table_get_bucket( polar_hash_table *self, intptr_t idx_bucket )
{
  assert( POLAR_IS_HASH_TABLE(self) );
  assert( idx_bucket >= 0 );
 
  if( (self->array_buckets != NULL) && (idx_bucket <= self->mask_buckets) )
    return (polar_hash_table_node *)polar_paged_array_get_element(self->array_buckets, idx_bucket);
 
  return NULL;
}
 
static inline polar_hash_table_node *
polar_hash_table_swap_bucket( polar_hash_table *self, intptr_t idx_bucket, polar_hash_table_node *node_new )
{
  assert( idx_bucket >= 0 );
  
  if( self->array_buckets != NULL )
    return (polar_hash_table_node *)polar_paged_array_swap_element(self->array_buckets, idx_bucket, node_new);
 
  else if ( (idx_bucket <= self->mask_buckets) && (node_new != NULL) )
  {
    self->array_buckets = polar_paged_array_new(NULL);
    polar_paged_array_set_element(self->array_buckets, idx_bucket, node_new);
  }
 
  return NULL;
}
 
POLAR_FUNCTION_INTERNAL void
polar_hash_table_set_bucket( polar_hash_table *self, intptr_t idx_bucket, polar_hash_table_node *node_new )
{
  polar_paged_array *array_buckets_new;
 
  assert( POLAR_IS_HASH_TABLE(self) );
  assert( idx_bucket >= 0 );
 
  if( idx_bucket <= self->mask_buckets )
    ;
 
  else
    return;
 
  if( self->array_buckets != NULL )
    ;
 
  else if( POLAR_IS_HASH_TABLE_NODE(node_new) )
    self->array_buckets = polar_paged_array_new(NULL);
 
  else
    return;
 
  ( (polar_list_node *)node_new )->node_next = (polar_list_node *)
    polar_paged_array_swap_element(self->array_buckets, idx_bucket, node_new);
}
 
POLAR_FUNCTION_INTERNAL void
polar_hash_table_empty_bucket( polar_hash_table *self, intptr_t idx_bucket )
{
  polar_list_node *node_current;
 
  assert( POLAR_IS_HASH_TABLE(self) );
  assert( idx_bucket >= 0 );
  assert( idx_bucket <= self->mask_buckets );
 
  if( self->array_buckets != NULL )
  {
    node_current = (polar_list_node *)polar_paged_array_swap_element(self->array_buckets, idx_bucket, NULL);
    self->count_entries -= polar_list_node_list_free( &node_current );
  }
}
 
POLAR_FUNCTION_INTERNAL void
polar_hash_table_grow( polar_hash_table *self )
{
  intptr_t count_buckets_new, mask_buckets_new;
  polar_paged_array *array_buckets_new;
  intptr_t i;
  polar_hash_table_node *node_current, *node_next;
  intptr_t idx_new;
 
  assert( POLAR_IS_HASH_TABLE(self) );
 
  if( self->array_buckets != NULL )
    ;
 
  else
    return;
 
  count_buckets_new = ( (self->mask_buckets + 1) << 1 );
  mask_buckets_new = ( count_buckets_new - 1 );
 
  array_buckets_new = polar_paged_array_new(NULL);
 
  for( i = 0; i <= self->mask_buckets; i++ )
  {
    node_current = (polar_hash_table_node *)polar_paged_array_get_element(self->array_buckets, i);
 
    while( node_current != NULL )
    {
      node_next = (polar_hash_table_node *)( POLAR_LIST_NODE(node_current)->node_next );
 
      idx_new = ( polar_hash_table_node_get_hash_value(node_current) & mask_buckets_new );
 
      ( (polar_list_node *)node_current )->node_next = (polar_list_node *)
        polar_paged_array_swap_element(array_buckets_new, idx_new, node_current);
 
      node_current = node_next;
    }
  }
 
  polar_runtime_object_free( (polar_runtime_object *)(self->array_buckets) );
 
  self->array_buckets = array_buckets_new;
  self->mask_buckets = mask_buckets_new;
}
 
// ---------------------------------------------------------------------------------------------------------------------
 
POLAR_FUNCTION_INTERNAL polar_hash_table *
_polar_hash_table_init( polar_hash_table *self )
{
  // Chain up first
  self = (polar_hash_table *)
    POLAR_RUNTIME_OBJECT_CLASS(superclass_polar_hash_table)->init( (polar_runtime_object *)self );
 
  if( self != NULL )
  {
    self->id_node_type = POLAR_TYPE_HASH_TABLE_NODE;
  }
 
  return self;
}
 
POLAR_FUNCTION_INTERNAL polar_runtime_object *
_polar_hash_table_finalize( polar_hash_table *self )
{
  polar_hash_table_clear(self);
 
  // Chain up
  return POLAR_RUNTIME_OBJECT_CLASS(superclass_polar_hash_table)->finalize( (polar_runtime_object *)self );
}
 
POLAR_FUNCTION_INTERNAL void
_polar_hash_table_insert_node( polar_hash_table *self, polar_hash_table_node *node_new )
{
  intptr_t idx_bucket;
 
  assert( POLAR_IS_HASH_TABLE_NODE(node_new) );
  assert( polar_hash_table_has_node(self, polar_hash_table_node_get_key(node_new)) == NO );
 
  if( polar_hash_table_must_grow(self) == NO )
    ;
 
  else
    polar_hash_table_grow(self);
 
  idx_bucket = ( polar_hash_table_node_get_hash_value(node_new) & self->mask_buckets );
  polar_hash_table_set_bucket(self, idx_bucket, node_new);
 
  self->count_entries++;
}
 
POLAR_FUNCTION_INTERNAL void
_polar_hash_table_class_init( polar_hash_table_class *self )
{
  // Acquire our superclass
  superclass_polar_hash_table = POLAR_RUNTIME_OBJECT_CLASS(self)->class_superclass;
 
  // Establish our virtual methods
  ( (polar_runtime_object_class *)self )->init = (polar_func_runtime_object_lifecycle)_polar_hash_table_init;
  ( (polar_runtime_object_class *)self )->finalize = (polar_func_runtime_object_lifecycle)_polar_hash_table_finalize;
 
  self->insert_node = _polar_hash_table_insert_node;
}
 
static struct polar_internal_type_info pti_polar_hash_table =
{
  .name_type          = "polar_hash_table",
  .size_type_instance = sizeof(polar_hash_table),
  .size_type_class    = sizeof(polar_hash_table_class),
  .type_class_init    = (polar_func_runtime_object_class_lifecycle)_polar_hash_table_class_init
};
 
// Public ==============================================================================================================
 
POLAR_FUNCTION_INTERNAL OBJC_FUNCTION_CONSTANT polar_internal_type
polar_hash_table_get_type( void )
{
  static polar_internal_type pt_polar_hash_table = POLAR_INTERNAL_TYPE_INVALID;
 
  if( pt_polar_hash_table != POLAR_INTERNAL_TYPE_INVALID )
    return pt_polar_hash_table;
 
  pt_polar_hash_table = polar_internal_type_init( POLAR_TYPE_RUNTIME_OBJECT, &class_polar_hash_table,
                                                  &pti_polar_hash_table );
 
  return pt_polar_hash_table;
}
 
POLAR_FUNCTION_INTERNAL OBJC_RETURNS_VALID_POINTER polar_hash_table *
polar_hash_table_new( intptr_t count_buckets_initial, polar_internal_type id_node_type )
{
  polar_hash_table *result;
 
  assert( count_buckets_initial >= 2 );
  assert( (count_buckets_initial & (count_buckets_initial - 1)) == 0 );
  assert( polar_internal_type_is_a(id_node_type, POLAR_TYPE_HASH_TABLE_NODE) );
 
  result = (polar_hash_table *)polar_runtime_object_new(POLAR_TYPE_HASH_TABLE);
  result->mask_buckets = ( count_buckets_initial - 1 );
  result->id_node_type = id_node_type;
 
  return result;
}
 
POLAR_FUNCTION_INTERNAL OBJC_FUNCTION_HOTSPOT polar_hash_table_node *
polar_hash_table_get_node( polar_hash_table *self, void *key_desired )
{
  polar_hash_table_node *result;
  polar_hash_table_node *node_with_key_desired;
  intptr_t idx_bucket;
  char node_memory[512];  // Cheating here and not using alloca() or the heap
 
  assert( POLAR_IS_HASH_TABLE(self) );
 
  node_with_key_desired = (polar_hash_table_node *)
    polar_runtime_object_preallocated_init( &node_memory[0], self->id_node_type, YES );
 
  polar_hash_table_node_set_key(node_with_key_desired, key_desired);
 
  idx_bucket = ( polar_hash_table_node_get_hash_value(node_with_key_desired) & self->mask_buckets );
 
  result = polar_hash_table_get_bucket(self, idx_bucket);
  while( result != NULL )
  {
    if( polar_hash_table_node_is_equal_to(result, node_with_key_desired) == NO )
      result = (polar_hash_table_node *)( ((polar_list_node *)(result))->node_next );
 
    else
      break;
  }
 
  polar_runtime_object_preallocated_finalize(node_with_key_desired);
 
  return result;
}
 
POLAR_FUNCTION_INTERNAL polar_hash_table_node *
polar_hash_table_add_node( polar_hash_table *self, void *key_desired )
{
  polar_hash_table_node *result;
 
  result = (polar_hash_table_node *)polar_runtime_object_new(self->id_node_type);
  polar_hash_table_node_set_key(result, key_desired);
 
  polar_hash_table_insert_node(self, result);
  return result;
}
 
POLAR_FUNCTION_INTERNAL polar_hash_table_node *
polar_hash_table_remove_node( polar_hash_table *self, void *key_desired )
{
  polar_hash_table_node *result, *node_with_key_desired, *node_previous;
  intptr_t idx_bucket;
 
  assert( POLAR_IS_HASH_TABLE(self) );
 
  node_with_key_desired = (polar_hash_table_node *)alloca( polar_internal_type_get_instance_size(self->id_node_type) );
  polar_runtime_object_preallocated_init(node_with_key_desired, self->id_node_type, YES);
  polar_hash_table_node_set_key(node_with_key_desired, key_desired);
 
  node_previous = NULL;
  idx_bucket = ( polar_hash_table_node_get_hash_value(node_with_key_desired) & self->mask_buckets );
 
  result = polar_hash_table_get_bucket(self, idx_bucket);
  while( result != NULL )
  {
    if( polar_hash_table_node_is_equal_to(result, node_with_key_desired) == NO )
    {
      node_previous = result;
      result = (polar_hash_table_node *)( POLAR_LIST_NODE(result)->node_next );
    }
 
    else
    {
      if( node_previous != NULL )
        POLAR_LIST_NODE(node_previous)->node_next = POLAR_LIST_NODE(result)->node_next;
 
      else
        polar_paged_array_set_element(self->array_buckets, idx_bucket, ((polar_list_node *)result)->node_next);
 
      POLAR_LIST_NODE(result)->node_next = NULL;
      self->count_entries--;
 
      polar_hash_table_maybe_free_buckets(self);
      break;
    }
  }
 
  polar_runtime_object_preallocated_finalize(node_with_key_desired);
 
  return result;
}
 
POLAR_FUNCTION_INTERNAL void
polar_hash_table_clear( polar_hash_table *self )
{
  intptr_t i;
 
  assert( POLAR_IS_HASH_TABLE(self) );
 
  if( self->count_entries > 0 )
  {
    for( i = 0; i <= self->mask_buckets; i++ )
      polar_hash_table_empty_bucket(self, i);
 
    self->count_entries = 0;
  }
 
  polar_hash_table_maybe_free_buckets(self);
}