bean/include/LIST/LIST.c

// C source file with the function definitions to handle lists

// get_lnode() function
// function to create a list node to probably start a list in
lnode * get_lnode(void * src, umax src_size, lnode_data_type type)
{
  // check params
  lnode * new = NULL;
  if (src == NULL || src_size == 0 || type == LNODE_DT_NO_TYPE)
    goto err;
  
  // check if src actually contains what type claims
  // I can only do checks for strings as integers/floats cant be checked
  umax tmp = 0;
  if (type > LNODE_DT_FLT64LE) {
    char_enc old_enc = CHAR_ARR_ENC_STATE;
    set_ch_arr_enc_state(type - LNODE_DT_FLT64LE);
    if ((tmp = check_chenc_arr(src, src_size)) == 0)
      goto err;
    set_ch_arr_enc_state(old_enc);
  }
  
  // allocate space for the node
  new = allocate_memory(1, sizeof(lnode));
  if (new == NULL)
    goto err;
  
  // assign variables
  new -> SRC = src;
  new -> SIZE = tmp == 0 ? src_size : tmp;
  new -> TYPE = type;
  
  // switch time (set print functions)
  switch (type)
  {
    case LNODE_DT_UINT8:    new -> print = print_uint8; break;
    case LNODE_DT_UINT16BE: new -> print = print_uint16be; break;
    case LNODE_DT_UINT16LE: new -> print = print_uint16le; break;
    case LNODE_DT_UINT32BE: new -> print = print_uint32be; break;
    case LNODE_DT_UINT32LE: new -> print = print_uint32le; break;
    case LNODE_DT_SINT8:    new -> print = print_sint8; break;
    case LNODE_DT_SINT16BE: new -> print = print_sint16be; break;
    case LNODE_DT_SINT16LE: new -> print = print_sint16le; break;
    case LNODE_DT_SINT32BE: new -> print = print_sint32be; break;
    case LNODE_DT_SINT32LE: new -> print = print_sint32le; break;
    // floats
    case LNODE_DT_FLT16BE:  new -> print = print_float16be; break;
    case LNODE_DT_FLT16LE:  new -> print = print_float16le; break;
    case LNODE_DT_FLT32BE:  new -> print = print_float32be; break;
    case LNODE_DT_FLT32LE:  new -> print = print_float32le; break;
    case LNODE_DT_FLT64BE:  new -> print = print_float64be; break;
    case LNODE_DT_FLT64LE:  new -> print = print_float64le; break;
    // strings
    case LNODE_DT_STR_ASCII:
    case LNODE_DT_STR_CP1252:
    case LNODE_DT_STR_CP932:
    case LNODE_DT_STR_SHIFT_JIS:
    case LNODE_DT_STR_UTF8:
    case LNODE_DT_STR_UTF16BE:
    case LNODE_DT_STR_UTF16LE:
      new -> print = print_chenc_arr;
      break;
  }
  
  // inconsistent info was provided *somehow*
  if (new -> print == NULL)
    goto err;
  
  // return the new node
  return new;
  // failure
  err:
  free_memory(new);
  return NULL;
}

// find_lnode_behind() function
lnode * find_lnode_behind(lnode * node, umax index)
{
  // check params
  if (node == NULL)
    return NULL;
  
  // search for the required behind node
  for (umax i = 0; i < index; i++)
    if (node -> BEHIND != NULL)
      node = node -> BEHIND;
    else
      break;
  
  // return the result
  return node;
}

// find_lnode_front() function
lnode * find_lnode_front(lnode * node, umax index)
{
  // check params
  if (node == NULL)
    return NULL;
  
  // search for the required front node
  for (umax i = 0; i < index; i++)
    if (node -> FRONT != NULL)
      node = node -> FRONT;
    else
      break;
  
  // return the result
  return node;
}

// find_lnode_parent() function
// function to find the upper level parent needed
lnode * find_lnode_parent(lnode * node, umax index)
{
  // check params
  if (node == NULL)
    return NULL;
  
  // search for the required parent node
  lnode * parent = NULL;
  for (umax i = 0; i < index; i++) {
    // find the most behind node and check if it has a parent
    node = find_lnode_behind(node, (umax) -1);
    if (node -> PARENT != NULL) {
      parent = node -> PARENT;
      node = node -> PARENT;
    }
    else
      break;
  }
    
  // return the result
  return node;
}

// find_lnode_child() function
// function to find the child index needed
lnode * find_lnode_child(lnode * node, umax index)
{
  // check params
  if (node == NULL || node -> CHILD == NULL)
    return NULL;
  
  // otherwise, search for the required child node
  return find_lnode_front(node -> CHILD, index);
}

// add_lnode_front() function
// function to append an element to a node as a new element on the list
// or as a child element (at the end of both lists)
lnode * add_lnode_front(lnode * node, void * src, umax src_size, lnode_data_type type)
{
  // check params
  lnode * front = NULL;
  if (node == NULL || (front = get_lnode(src, src_size, type)) == NULL)
    goto err;
  
  // append the item to the list
  node = find_lnode_front(node, (umax) -1);
  if (node == NULL)
    goto err;
  node -> FRONT = front;
  front -> BEHIND = node;
 
  // return the result
  return front;
  err: // error happened
  free_memory(front);
  return NULL;
}

// add_lnode_child() function
// function to create a child node for a parent node
lnode * add_lnode_child(lnode * node, void * src, umax src_size, lnode_data_type type)
{
  // check params
  lnode * child = NULL;
  if (node == NULL || (child = get_lnode(src, src_size, type)) == NULL)
    goto err;
    
  // add the child node at the end of the child list of the parent
  if (node -> CHILD == NULL) {
    node -> CHILD = child;
    child -> PARENT = node;
  } else /* find the last node child in the list */ {
    node = find_lnode_child(node, (umax) -1);
    if (node == NULL)
      goto err;
    node -> FRONT = child;
    child -> BEHIND = node;
  }
  
  // return the result
  return child;
  err: // error happened
  free_memory(child);
  return NULL;
}

// rm_lnode() function
// function to remove the memory allocated for a lnode pointer
// the function will return a pointer to the ideal lnode to be deleted next
lnode * rm_lnode(lnode * node)
{
  // check params
  if (node == NULL)
    return NULL;  
  //          Parent
  //          |
  // Behind - Node - Front
  //          |
  //          Child
  
  // variable to return
  lnode * tmp = NULL;
  
  // handle behind and front
  if (node -> CHILD == NULL) {
    /***********************************/
    // <div>                   | <div>
    //   <div/>                |   <div/>
    //   <div/> --> to delete  |   
    //   <div/>                |   <div/>
    // </div>                  | </div>
    /***********************************/
    // link front with behind (if they exist)
    // return front if behind is NULL
    if ((node -> FRONT != NULL) && (node -> BEHIND != NULL)) {
      node -> BEHIND -> FRONT = node -> FRONT;
      node -> FRONT -> BEHIND = node -> BEHIND;
    } else if (node -> BEHIND != NULL)
      node -> BEHIND -> FRONT = NULL;
    else if (node -> FRONT != NULL)
      node -> FRONT -> BEHIND = NULL;      
    // return the front node
    tmp = node -> FRONT;
  } else /* node has childs */ {
    /***********************************/
    // <div>                   | <div>
    //   <div/>                |   <div/>
    //   <div>  --> to delete  |
    //     <div/>              |   <div/>
    //     <div/>              |   <div/>
    //   </div> --> to delete  | 
    //   <div/>                |   <div/>
    // </div>                  | </div>
    /***********************************/
    // link behind with first child
    // then link front with last child
    // check the existance of everything
    if (node -> BEHIND != NULL) {
      node -> BEHIND -> FRONT = node -> CHILD;
      node -> CHILD -> BEHIND = node -> BEHIND;
      node -> CHILD -> PARENT = NULL; // override parent
    } else // assign current node's parent if it exists
      node -> CHILD -> PARENT = node -> PARENT;
    // link the last child with the front node
    if (node -> FRONT != NULL) {
      tmp = find_lnode_child(node, (umax) -1);
      tmp -> FRONT = node -> FRONT;
      node -> FRONT -> BEHIND = tmp;
    }
    // return the first child
    tmp = node -> CHILD;
  }
  
  // release node's memory
  end:
  free_memory(node);
  return tmp;
}

// rm_lnode_fronts() function
// function to remove the front nodes of a node (childs of front nodes remain)
umax rm_lnode_fronts(lnode * node)
{
  // check params
  if (node == NULL)
    return 0;
    
  // list the front nodes remove them
  umax node_count = 0;
  lnode * tmp = node -> FRONT;
  while (tmp != NULL) {
    node = tmp -> FRONT;
    rm_lnode(tmp);
    tmp = node;
    node_count++;
  }
  
  // return the number of nodes deteled
  return node_count;
}

// rm_lnode_childs() function
// function to remove the direct child nodes of a node (childs of childs remain)
umax rm_lnode_childs(lnode * node)
{
  // check params
  if (node == NULL || node -> CHILD == NULL)
    return 0;
  
  // remove the childs of the node
  umax node_count = rm_lnode_fronts(node -> CHILD);
  rm_lnode(node -> CHILD);
  node -> CHILD = NULL;
  node_count++;
  return node_count;
}

// rm_lnode_list() function
// function to completely delete the list coming out of an lnode (recursive)
umax rm_lnode_list(lnode * node)
{
  // check params
  if (node == NULL)
    return 0;
  
  // start the removal
  umax node_count = 0;
  while (node != NULL) {
    node = rm_lnode(node);
    node_count++;
  }
  
  // return how many nodes were cleared  
  return node_count;
}

// the following count functions are basically a copy from the remove
// functions above but used to count nodes instead of removing them

// count_lnode_fronts() function
umax count_lnode_fronts(lnode * node)
{
  // check params
  if (node == NULL)
    return 0;
    
  // list the front nodes and check if they have children
  umax node_count = 0;
  lnode * tmp = node -> FRONT;
  while (tmp != NULL) {
    tmp = tmp -> FRONT;
    node_count++;
  }
  
  // return the number of nodes deleted
  return node_count;
}

// count_lnode_childs() function
umax count_lnode_childs(lnode * node)
{
  // check params
  if (node == NULL || node -> CHILD == NULL)
    return 0;
  
  // count the childs of the node
  return count_lnode_fronts(node -> CHILD) + 1;
}

// count_lnodes() function
umax count_lnodes(lnode * node)
{
  // check params
  if (node == NULL)
    return 0;
    
  // start the count
  // count nodes at the same parenting level in each iteration
  lnode * ptr = node;
  umax old_smlvl_cnt = count_lnode_fronts(node) + 1, new_smlvl_cnt = 0;
  lnode ** old_node_arr = allocate_memory(sizeof(lnode *), old_smlvl_cnt), ** new_node_arr = NULL;
  // add all the nodes at the same level to old_node_arr
  for (umax i = 0; i < old_smlvl_cnt; i++) {
    old_node_arr[i] = ptr;
    ptr = ptr -> FRONT;
  }
  
  // variable to return
  umax node_count = old_smlvl_cnt;
  // start the count
  while (old_smlvl_cnt != 0)
  {
    // go through each node to see if they have children
    for (umax i = 0; i < old_smlvl_cnt; i++)
      new_smlvl_cnt += count_lnode_childs(old_node_arr[i]);
    
    // allocate memory for the next level of nodes
    new_node_arr = allocate_memory(sizeof(lnode *), new_smlvl_cnt);
    if (new_node_arr == NULL) {
      free_memory(old_node_arr);
      return 0;
    }
    
    // add the new nodes
    for (umax i = 0, arr_pos = 0; i < old_smlvl_cnt; i++) {
      ptr = old_node_arr[i];
      if (ptr -> CHILD != NULL) {
      new_node_arr[arr_pos++] = ptr -> CHILD;
      ptr = ptr -> CHILD;
        while (ptr -> FRONT != NULL) {
          new_node_arr[arr_pos++] = ptr -> FRONT;
          ptr = ptr -> FRONT;
        }
      }
    }
    
    // setup the variables for the next loop
    free_memory(old_node_arr);
    old_node_arr = new_node_arr;
    new_node_arr = NULL;
    node_count += new_smlvl_cnt;
    old_smlvl_cnt = new_smlvl_cnt;
    new_smlvl_cnt = 0;
  }
  // for the last loop
  free_memory(old_node_arr);
  
  // return the result 
  return node_count;
}

// count_lnodes_parent_lvls() function
umax count_lnodes_parent_lvls(lnode * node)
{
  // check params
  if (node == NULL)
    return 0;
  // ok so, I have to traverse through all nodes keeping count of the parent level
  umax parent_lvls = 1;
  umax old_node_cnt = 1, new_node_cnt = 0;
  lnode * ptr = node, ** old_node_arr = {&node}, ** new_node_arr = NULL;
  while (old_node_cnt != 0)
  {
    // get how many nodes have children
    // and get those nodes into tmp
    bool is_new_par_lvl = false; 
    for (umax i = 0; i < old_node_cnt; i++)
      if (old_node_arr[i] -> CHILD != NULL) {
        if (is_new_par_lvl == false)
          parent_lvls++; // epik variable to return here
        new_node_cnt += count_lnode_childs(old_node_arr[i]);
      }
      
    // allocate memory for the new array to be created
    new_node_arr = allocate_memory(new_node_cnt, sizeof(lnode *));
    if (new_node_arr == NULL) {
      free_memory(old_node_arr);
      return 0;
    }
    
    // add all the child nodes to new_node_arr
    for (umax i = 0, arr_pos = 0; i < old_node_cnt; i++)
      if (old_node_arr[i] -> CHILD != NULL) {
        ptr = old_node_arr[i] -> CHILD;
        while (ptr != NULL) {
          new_node_arr[arr_pos++] = ptr;
          ptr = ptr -> FRONT;
        }
      }
    
    // setup the variables for the next loop
    free_memory(old_node_arr);
    old_node_arr = new_node_arr;
    new_node_arr = NULL;
    old_node_cnt = new_node_cnt;
    new_node_cnt = 0;
  }
  // for the last loop
  free_memory(old_node_arr);
  
  // return the result
  return parent_lvls;
}

// print_lnode_list()
// not to dissapoint, but this will only print the structure of the list and
// print the intergers relating the type of element contained in each lnode item
umax print_lnode_list(lnode * node)
{
  // check params
  if (node == NULL)
    return 0;
  
  // make a 2 dimensional array so that each row will refer to a single node
  // the position of the node in the row will determine its parenting level
  // and it can be visually inferred which is the direct parent
  
  // first, I need to count the number of nodes
  // after that I need to count the number of parenting levels
  
  // little representation
  // just for myself
  // number of nodes: 9
  // parenting levels: 4
  // [1, 0, 0 ,0]
  // [0, 1, 0, 0]
  // [0, 1, 0, 0]
  // [0, 0, 1, 0]
  // [1, 0, 0, 0]
  // [0, 1, 0, 0]
  // [0, 1, 0, 0]
  // [0, 0, 1, 0]
  // [0, 0, 0, 1]
  
  // allocate memory for the 2 dimensional array
  umax node_cnt = count_lnodes(node), parent_lvls = count_lnodes_parent_lvls(node);
  umax * node_diag = allocate_memory(sizeof(umax), node_cnt * parent_lvls);
  // ^ node_diag[node row][parent column]
  
  // analize the nodes at the same parenting level and then move to the next level
  lnode * ptr = node;
  umax old_smlvl_cnt = count_lnode_fronts(node) + 1,
       new_smlvl_cnt = 0;
  umax cur_node_pos = 0,
       cur_par_lvl = 0;
  lnode ** old_node_arr = allocate_memory(sizeof(lnode *), old_smlvl_cnt),
        ** new_node_arr = NULL;
  umax * old_node_pos = allocate_memory(sizeof(umax), old_smlvl_cnt),
       * new_node_pos = NULL;
  // add all the nodes at the same level to old_node_arr
  // and also, get their respective position on node_diag
  for (umax i = 0; i < old_smlvl_cnt; i++) {
    old_node_arr[i] = ptr;
    old_node_pos[i] = cur_node_pos;
    if (ptr -> CHILD != NULL)
      cur_node_pos += count_lnodes(ptr -> CHILD) + 1;
    else
      cur_node_pos++;
    ptr = ptr -> FRONT;
  }
  
  // start the loop
  while (old_smlvl_cnt != 0)
  {    
    // put each node in its position on node_diag
    for (umax i = 0; i < old_smlvl_cnt; i++) {
      ptr = old_node_arr[i];
      node_diag[(old_node_pos[i] * parent_lvls) + cur_par_lvl] = ptr -> TYPE;
      // count the childs to be added for the next parenting level
      new_smlvl_cnt += count_lnode_childs(ptr);
      cur_node_pos += count_lnodes(ptr);      
    }
    
    // allocate memory for the next level of nodes    
    // node array
    new_node_arr = allocate_memory(sizeof(lnode *), new_smlvl_cnt);
    if (new_node_arr == NULL) {
      free_memory(old_node_arr);
      return 0;
    }
    // node position array
    new_node_pos = allocate_memory(sizeof(umax), new_smlvl_cnt);
    if (new_node_pos == NULL) {
      free_memory(new_node_arr);
      free_memory(old_node_arr);
      return 0;
    }
    
    // get the new nodes and their position for the next loop
    for (umax i = 0, node_pos_index = 0; i < old_smlvl_cnt; i++)
    {
      ptr = old_node_arr[i] -> CHILD;
      if (ptr != NULL) {
        cur_node_pos = old_node_pos[i] + 1;
        while (ptr != NULL) {
          new_node_arr[node_pos_index] = ptr;
          new_node_pos[node_pos_index] = cur_node_pos;
          node_pos_index++;
          if (ptr -> CHILD != NULL)
            cur_node_pos += count_lnodes(ptr -> CHILD) + 1;
          else
            cur_node_pos++;
          ptr = ptr -> FRONT;
        }
      }
    }
    
    // setup the variables for the next loop
    free_memory(old_node_arr);
    old_node_arr = new_node_arr;
    new_node_arr = NULL;
    free_memory(old_node_pos);
    old_node_pos = new_node_pos;
    new_node_pos = NULL;
    old_smlvl_cnt = new_smlvl_cnt;
    new_smlvl_cnt = 0;
    cur_par_lvl++;
  }
  // for the last loop
  free_memory(old_node_arr);
  free_memory(old_node_pos);
  
  // print the node diagram (finally)
  printf("\nList node diagram:\n");
  for (umax i = 0; i < node_cnt; i++) {
    printf("[");
    for (umax j = 0; j < parent_lvls - 1; j++)
      printf("%2llu, ", node_diag[(i * parent_lvls) + j]);
    printf("%2llu]\n", node_diag[(i * parent_lvls) + parent_lvls - 1]);
  }
  
  // done!
  free_memory(node_diag);
  return node_cnt;
}

// find_lnode_index() function
// function to find lnode at an index position respect to the current node
lnode * find_lnode(lnode * node, lnode_dir dir, umax index)
{
  // check params
  if (node == NULL || dir == LNODE_DIR_NO_DIR)
    return NULL;
  
  // reuse the functions from above
  if (dir == LNODE_DIR_FRONT)
    return find_lnode_front(node, index);
  else if (dir == LNODE_DIR_BEHIND)
    return find_lnode_behind(node, index);
  else if (dir == LNODE_DIR_PARENT)
    return find_lnode_parent(node, index);
  else if (dir == LNODE_DIR_CHILD)
    return find_lnode_child(node, index);
  
  // huh?
  return NULL;
}