polar-sparse-array.c

/* Internal API: sparse array 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_sparse_array **************************************************************************************************
// Private =============================================================================================================
 
// This variable is initialized in polar_sparse_array_get_type()
static polar_sparse_array_class class_polar_sparse_array;
 
// This variable is initialized in _polar_sparse_array_class_init()
static polar_runtime_object_class *superclass_polar_sparse_array = NULL;
 
// ---------------------------------------------------------------------------------------------------------------------
 
POLAR_FUNCTION_INTERNAL void
polar_sparse_array_insert_page( polar_sparse_array *self, polar_sparse_array_page *page_new );
 
static inline polar_sparse_array_page *
polar_sparse_array_next_page_after( polar_sparse_array *self, polar_sparse_array_page *page_current )
{
  assert( POLAR_IS_SPARSE_ARRAY(self) );
 
  return (polar_sparse_array_page *)
    polar_btree_next_node_after( (polar_btree *)self, (polar_btree_node *)page_current );
}
 
POLAR_FUNCTION_INTERNAL void
polar_sparse_array_maybe_replace_root( polar_sparse_array *self, polar_sparse_array_page *page_root_new )
{
  polar_sparse_array_page *page_root_current, *page_current, *page_temp;
  size_t instance_size;
  intptr_t i;
 
  assert( POLAR_IS_SPARSE_ARRAY(self) );
  assert( self->data_inherited.node_root != NULL );
  assert( POLAR_IS_SPARSE_ARRAY_PAGE(page_root_new) );
 
  page_root_current = (polar_sparse_array_page *)( self->data_inherited.node_root );
  if( page_root_current != page_root_new )
    ;
 
  else
    return;
 
  if( polar_sparse_array_page_compare_elements_used(page_root_new, page_root_current, self->value_element_empty) > 0 )
    ;
 
  else
    return;
 
  ( (polar_btree_node *)page_root_new )->branch_right = NULL;
  ( (polar_btree_node *)page_root_new )->branch_left = NULL;
 
  // Exchange our current root node for our new root node
  instance_size = polar_internal_type_get_instance_size( ((polar_btree *)self)->id_node_type );
  page_temp = (polar_sparse_array_page *)polar_memory_duplicate(page_root_current, instance_size);
 
  objc_memcpy(page_root_current, page_root_new, instance_size);
  objc_memcpy(page_root_new, page_temp, instance_size);
 
  polar_memory_free(page_temp, instance_size);
 
  // Re-sort the tree
  page_current = NULL;
  for( i = 0; i < self->data_inherited.count_nodes; i++ )
  {
    page_current = polar_sparse_array_next_page_after(self, page_current);
 
    if( page_current != page_root_current )
    {
      ( (polar_btree_node *)page_current )->branch_right = NULL;
      ( (polar_btree_node *)page_current )->branch_left = NULL;
 
      polar_sparse_array_insert_page(self, page_current);
    }
  }
}
 
POLAR_FUNCTION_INTERNAL polar_sparse_array_page *
polar_sparse_array_new_page( polar_sparse_array **p_array_target )
{
  polar_sparse_array_page *result;
 
  assert( *p_array_target != NULL );
  assert( POLAR_IS_SPARSE_ARRAY(*p_array_target) );
 
  result = (polar_sparse_array_page *)polar_btree_new_node( (polar_btree **)p_array_target );
 
  if( (*p_array_target)->value_element_empty == NULL )
    return result;
 
  polar_sparse_array_page_fill_elements(result, (*p_array_target)->value_element_empty);
  return result;
}
 
POLAR_FUNCTION_INTERNAL OBJC_FUNCTION_HOTSPOT polar_sparse_array_page *
polar_sparse_array_get_page( polar_sparse_array *self, intptr_t idx_page_desired )
{
  polar_sparse_array_page *result;
  intptr_t i;
 
  assert( POLAR_IS_SPARSE_ARRAY(self) );
  assert( idx_page_desired >= 0 );
 
  result = (polar_sparse_array_page *)( self->data_inherited.node_root );
 
  // The compiler optimization code seems to handle a loop with a known quantity better than a while loop
  for( i = 0; i < self->data_inherited.count_nodes; i++ )
  {
    if( (void *)idx_page_desired > ((polar_btree_node *)result)->node_key )
      result = (polar_sparse_array_page *)( ((polar_btree_node *)result)->branch_right );
 
    else if( (void *)idx_page_desired < ((polar_btree_node *)result)->node_key )
      result = (polar_sparse_array_page *)( ((polar_btree_node *)result)->branch_left );
 
    else
      return result;
 
    if( result != NULL )
      ;
 
    else
      return &self->page_empty;
  }
 
  return &self->page_empty;
}
 
POLAR_FUNCTION_INTERNAL void
polar_sparse_array_insert_page( polar_sparse_array *self, polar_sparse_array_page *page_new )
{
  polar_sparse_array_page *page_current, *page_temp;
  polar_btree_node **page_placement;
  size_t instance_size;
  intptr_t idx_logical_max;
 
  assert( POLAR_IS_SPARSE_ARRAY(self) );
 
  if( page_new != NULL )
    assert( POLAR_IS_SPARSE_ARRAY_PAGE(page_new) );
 
  else
    return;
 
  page_current = (polar_sparse_array_page *)( self->data_inherited.node_root );
 
  if( page_current == NULL )
    self->data_inherited.node_root = (polar_btree_node *)page_new;
 
  else if( polar_sparse_array_page_compare_elements_used(page_new, page_current, self->value_element_empty) > 0 )
    polar_sparse_array_maybe_replace_root(self, page_new);
 
  else
  {
    /* The idea here is to find where the new page will be placed, all else being equal, and then to check whether or
       not the new page contains more live data than the one that will serve as its immediate root.  If so, the
       positions of the two pages are swapped, so that pages with more live data are closer to the root node of the
       overall tree.
    */
    page_placement = NULL;
 
    do
    {
      if( ((polar_btree_node *)page_new)->node_key > ((polar_btree_node *)page_current)->node_key )
      {
        if( ((polar_btree_node *)page_current)->branch_right != NULL )
          page_current = (polar_sparse_array_page *)( ((polar_btree_node *)page_current)->branch_right );
 
        else
          page_placement = &( (polar_btree_node *)page_current )->branch_right;
      }
 
      else
      {
        if( ((polar_btree_node *)page_current)->branch_left != NULL )
          page_current = (polar_sparse_array_page *)( ((polar_btree_node *)page_current)->branch_left );
 
        else
          page_placement = &( (polar_btree_node *)page_current )->branch_left;
      }
    } while( page_placement == NULL );
 
    if( polar_sparse_array_page_compare_elements_used(page_new, page_current, self->value_element_empty) > 0 )
    {
      /* Swap `page_new` and `page_current`, so that `page_new` is closer to the root of the tree.  This has the added
         benefit of swapping `page_new` in without the need to update branch links further upstream.  However, it swaps
        `page_current` out of the tree entirely until we put it back, below.
      */
 
      instance_size = polar_internal_type_get_instance_size( ((polar_btree *)self)->id_node_type );
 
      page_temp = (polar_sparse_array_page *)polar_memory_duplicate(page_current, instance_size);
 
      objc_memcpy(page_current, page_new, instance_size);
      objc_memcpy(page_new, page_temp, instance_size);
 
      polar_memory_free(page_temp, instance_size);
 
      page_temp = page_current;
      page_current = page_new;
      page_new = page_temp;
 
      // Place `page_current` back into the tree
      if( ((polar_btree_node *)page_current)->node_key > ((polar_btree_node *)page_new)->node_key )
        ( (polar_btree_node *)page_new )->branch_right = (polar_btree_node *)page_current;
 
      else
        ( (polar_btree_node *)page_new )->branch_left = (polar_btree_node *)page_current;
    }
 
    else
      *page_placement = (polar_btree_node *)page_new;
  }
 
  idx_logical_max = POLAR_MASK_SPARSE_ARRAY +
    ( polar_sparse_array_page_get_page_number(page_new) << POLAR_SHIFT_SPARSE_ARRAY );
 
  if( idx_logical_max > self->idx_logical_max )
    self->idx_logical_max = idx_logical_max;
}
 
// ---------------------------------------------------------------------------------------------------------------------
 
POLAR_FUNCTION_INTERNAL polar_sparse_array *
_polar_sparse_array_init( polar_sparse_array *self )
{
  // Chain up first
  self = (polar_sparse_array *)
    POLAR_RUNTIME_OBJECT_CLASS(superclass_polar_sparse_array)->init( (polar_runtime_object *)self );
 
  if( self != NULL )
  {
    self->data_inherited.id_node_type = POLAR_TYPE_SPARSE_ARRAY_PAGE;
    self->idx_logical_max = -1;
 
    ( (polar_runtime_object *)(&self->page_empty) )->class_pointer = self->data_inherited.id_node_type;
  }
 
  return self;
}
 
POLAR_FUNCTION_INTERNAL void
_polar_sparse_array_class_init( polar_sparse_array_class *self )
{
  // Acquire our superclass
  superclass_polar_sparse_array = POLAR_RUNTIME_OBJECT_CLASS(self)->class_superclass;
 
  // Establish our virtual methods
  ( (polar_runtime_object_class *)self )->init = (polar_func_runtime_object_lifecycle)_polar_sparse_array_init;
}
 
static struct polar_internal_type_info pti_polar_sparse_array =
{
  .name_type          = "polar_sparse_array",
  .size_type_instance = sizeof(polar_sparse_array),
  .size_type_class    = sizeof(polar_sparse_array_class),
  .type_class_init    = (polar_func_runtime_object_class_lifecycle)_polar_sparse_array_class_init
};
 
// Public ==============================================================================================================
 
POLAR_FUNCTION_INTERNAL OBJC_FUNCTION_CONSTANT polar_internal_type
polar_sparse_array_get_type( void )
{
  static polar_internal_type pt_polar_sparse_array = POLAR_INTERNAL_TYPE_INVALID;
 
  if( pt_polar_sparse_array != POLAR_INTERNAL_TYPE_INVALID )
    return pt_polar_sparse_array;
 
  pt_polar_sparse_array = polar_internal_type_init( POLAR_TYPE_BTREE, &class_polar_sparse_array,
                                                    &pti_polar_sparse_array) ;
 
  return pt_polar_sparse_array;
}
 
POLAR_FUNCTION_INTERNAL OBJC_RETURNS_VALID_POINTER polar_sparse_array *
polar_sparse_array_new( void *value_element_empty )
{
  polar_sparse_array *result;
 
  result = (polar_sparse_array *)polar_runtime_object_new(POLAR_TYPE_SPARSE_ARRAY);
  result->value_element_empty = value_element_empty;
 
  if( value_element_empty == NULL )
    ;
 
  else
    polar_sparse_array_page_fill_elements( &result->page_empty, value_element_empty );
 
  return result;
}
 
POLAR_FUNCTION_INTERNAL OBJC_FUNCTION_HOTSPOT void *
polar_sparse_array_get_element( polar_sparse_array *self, intptr_t idx_logical )
{
  intptr_t idx_page, idx_element;
  polar_sparse_array_page *page_target;
 
  assert( POLAR_IS_SPARSE_ARRAY(self) );
  assert( idx_logical >= 0 );
 
  if( idx_logical <= self->idx_logical_max )
  {
    idx_page = ( idx_logical >> POLAR_SHIFT_SPARSE_ARRAY );
    page_target = polar_sparse_array_get_page(self, idx_page);
 
    idx_element = ( idx_logical & POLAR_MASK_SPARSE_ARRAY );
    return polar_sparse_array_page_get_element(page_target, idx_element);
  }
 
  return self->value_element_empty;
}
 
POLAR_FUNCTION_INTERNAL void
polar_sparse_array_set_element( polar_sparse_array **p_array_target, intptr_t idx_logical, void *value_new )
{
  intptr_t idx_page, idx_element;
  polar_sparse_array *array_target;
  polar_sparse_array_page *page_target;
 
  assert( p_array_target != NULL );
  assert( POLAR_IS_SPARSE_ARRAY(*p_array_target) );
  assert( idx_logical >= 0 );
 
  idx_page = ( idx_logical >> POLAR_SHIFT_SPARSE_ARRAY );
  idx_element = ( idx_logical & POLAR_MASK_SPARSE_ARRAY );
  array_target = *p_array_target;
 
  if( idx_logical <= array_target->idx_logical_max )
  {
    page_target = polar_sparse_array_get_page(array_target, idx_page);
 
    if( page_target != &array_target->page_empty )
    {  
      polar_sparse_array_page_set_element(page_target, idx_element, value_new);
      return;
    }  
  }  
 
  if( value_new != array_target->value_element_empty )
  {
    page_target = polar_sparse_array_new_page(p_array_target);
 
    ( (polar_btree_node *)page_target )->node_key = (void *)idx_page;
    polar_sparse_array_page_set_element(page_target, idx_element, value_new);
 
    polar_sparse_array_insert_page(*p_array_target, page_target);
  }
}
 
POLAR_FUNCTION_INTERNAL BOOL
polar_sparse_array_set_element_if_empty( polar_sparse_array **p_array_target, intptr_t idx_logical, void *value_new )
{
  assert( p_array_target != NULL );
  assert( POLAR_IS_SPARSE_ARRAY(*p_array_target) );
  assert( idx_logical >= 0 );
 
  if( polar_sparse_array_test_element_empty(*p_array_target, idx_logical) )
  {
    polar_sparse_array_set_element(p_array_target, idx_logical, value_new);
    return YES;
  }
 
  return NO;
}