gdsl_list.c

书籍上的数据结构源代码

		{
		    fprintf (file, "<GDSL_LIST_NODE REF=\"%p\" CONTENT=\"%p\" SUCC=\"%p\" PRED=\"%p\">", 
			     (void*) tmp, (void*) _gdsl_node_get_content (tmp), 
			     (void*) _gdsl_node_get_succ (tmp), (void*) _gdsl_node_get_pred (tmp));
		}

	    if (write_f != NULL && _gdsl_node_get_content (tmp))
		{
		    write_f (_gdsl_node_get_content (tmp), file, 
			     get_location (list, tmp), user_data);
		}

	    fprintf (file, "</GDSL_LIST_NODE>\n");

	    tmp = _gdsl_node_get_succ (tmp);
	}

    fprintf (file, "</GDSL_LIST>\n");
}

extern void
gdsl_list_dump (const gdsl_list_t list, gdsl_write_func_t write_f, FILE* file, 
		void* user_data)
{
    _gdsl_node_t tmp;

    assert (list != NULL);
    assert (file != NULL);

    tmp = _gdsl_node_get_succ (list->d);

    fprintf (file, "<GDSL_LIST REF=\"%p\" NAME=\"%s\" CARD=\"%ld\" HEAD=\"%p\" TAIL=\"%p\">\n", 
	     (void*) list, list->name ? list->name : "", list->card, (void*) list->d, (void*) list->z);

    if (_gdsl_node_get_content (list->d))
	{
	    fprintf (file, "<GDSL_LIST_HEAD REF=\"%p\" CONTENT=\"%p\" SUCC=\"%p\" PRED=\"%p\"/>\n", 
		     (void*) list->d, (void*) _gdsl_node_get_content (list->d), 
		     (void*) _gdsl_node_get_succ (list->d), (void*) _gdsl_node_get_pred (list->d));
	}
    else
	{
	    fprintf (file, "<GDSL_LIST_HEAD REF=\"%p\" CONTENT=\"\" SUCC=\"%p\" PRED=\"%p\"/>\n", 
		     (void*) list->d, (void*) _gdsl_node_get_succ (list->d), (void*) _gdsl_node_get_pred (list->d));
	}

    while (tmp != list->z)
	{
	    if (_gdsl_node_get_content (tmp))
		{
		    fprintf (file, "<GDSL_LIST_NODE REF=\"%p\" CONTENT=\"%p\" SUCC=\"%p\" PRED=\"%p\">", 
			     (void*) tmp, (void*) _gdsl_node_get_content (tmp),
			     (void*) _gdsl_node_get_succ (tmp), (void*) _gdsl_node_get_pred (tmp));
		}
	    else
		{
		    fprintf (file, "<GDSL_LIST_NODE REF=\"%p\" CONTENT=\"\" SUCC=\"%p\" PRED=\"%p\">", 
			     (void*) tmp, (void*) _gdsl_node_get_succ (tmp), 
			     (void*) _gdsl_node_get_pred (tmp));
		}
      
	    if (write_f != NULL && _gdsl_node_get_content (tmp))
		{
		    write_f (_gdsl_node_get_content (tmp), file, 
			     get_location (list, tmp), user_data);
		}
      
	    fprintf (file, "</GDSL_LIST_NODE>\n");

	    tmp = _gdsl_node_get_succ (tmp);
	}

    if (_gdsl_node_get_content (list->z))
	{
	    fprintf (file, "<GDSL_LIST_TAIL REF=\"%p\" CONTENT=\"%p\" PRED=\"%p\" SUCC=\"%p\"/>\n</GDSL_LIST>\n", 
		     (void*) list->z, (void*) _gdsl_node_get_content (list->z), 
		     (void*) _gdsl_node_get_pred (list->z), (void*) _gdsl_node_get_succ (list->z));
	}
    else
	{
	    fprintf (file, "<GDSL_LIST_TAIL REF=\"%p\" CONTENT=\"\" PRED=\"%p\" SUCC=\"%p\"/>\n</GDSL_LIST>\n", 
		     (void*) list->z, (void*) _gdsl_node_get_pred (list->z), 
		     (void*) _gdsl_node_get_succ (list->z));
	}
}

/******************************************************************************/
/* Cursor specific functions                                                  */
/******************************************************************************/

extern gdsl_list_cursor_t
gdsl_list_cursor_alloc (const gdsl_list_t list)
{
    gdsl_list_cursor_t c;

    assert (list != NULL);

    c = (gdsl_list_cursor_t) malloc (sizeof (struct _gdsl_list_cursor));

    if (c == NULL)
	{
	    return NULL;
	}

    c->c = _gdsl_node_get_succ (list->d);
    c->l = list;

    return c;
}

extern void
gdsl_list_cursor_free (gdsl_list_cursor_t c)
{
    assert (c != NULL);

    free (c);
}

extern void
gdsl_list_cursor_move_to_head (gdsl_list_cursor_t c)
{
    assert (c != NULL);

    c->c = _gdsl_node_get_succ (c->l->d);
}

extern void
gdsl_list_cursor_move_to_tail (gdsl_list_cursor_t c)
{
    assert (c != NULL);

    c->c = _gdsl_node_get_pred (c->l->z);
}

extern gdsl_element_t
gdsl_list_cursor_move_to_value (gdsl_list_cursor_t c, gdsl_compare_func_t comp_f, void* v)
{
    assert (c != NULL);
    assert (comp_f != NULL);

    return update_cursor (c, search_by_function (c->l, comp_f, v));
}

extern gdsl_element_t
gdsl_list_cursor_move_to_position (gdsl_list_cursor_t c, ulong pos)
{
    assert (c != NULL);
    assert (pos > 0 && pos <= c->l->card);

    return update_cursor (c, search_by_position (c->l, pos));
}

extern void
gdsl_list_cursor_step_forward (gdsl_list_cursor_t c)
{
    assert (c != NULL);

    c->c = _gdsl_node_get_succ (c->c);
}

extern void
gdsl_list_cursor_step_backward (gdsl_list_cursor_t c)
{
    assert (c != NULL);

    c->c = _gdsl_node_get_pred (c->c);
}

extern bool
gdsl_list_cursor_is_on_head (const gdsl_list_cursor_t c)
{
    assert (c != NULL);

    /* Returns FALSE if L's cursor is on l->s node */
    if (gdsl_list_is_empty (c->l))
	{
	    return FALSE;
	}

    return (bool) (c->c == _gdsl_node_get_succ (c->l->d));
}

extern bool
gdsl_list_cursor_is_on_tail (const gdsl_list_cursor_t c)
{
    assert (c != NULL);

    /* Returns FALSE if L's cursor is on l->s node */
    if (gdsl_list_is_empty (c->l))
	{
	    return FALSE;
	}

    return (bool) (c->c == _gdsl_node_get_pred (c->l->z));
}

extern bool 
gdsl_list_cursor_has_succ (const gdsl_list_cursor_t c)
{
    assert (c != NULL);

    return (bool) (_gdsl_node_get_succ (c->c) != c->l->z);
}

extern bool 
gdsl_list_cursor_has_pred (const gdsl_list_cursor_t c)
{
    assert (c != NULL);

    return (bool) (_gdsl_node_get_pred (c->c) != c->l->d);
}

extern void
gdsl_list_cursor_set_content (gdsl_list_cursor_t c, gdsl_element_t e)
{
    assert (c != NULL);

    if (c->c == c->l->d)
	{
	    return;
	}

    if (c->c == c->l->z)
	{
	    return;
	}

    _gdsl_node_set_content (c->c, e);
}

extern gdsl_element_t
gdsl_list_cursor_get_content (const gdsl_list_cursor_t c)
{
    assert (c != NULL);

    if (c->c == c->l->d)
	{
	    return NULL;
	}
    
    if (c->c == c->l->z)
	{
	    return NULL;
	}

    return _gdsl_node_get_content (c->c);
}

extern gdsl_element_t
gdsl_list_cursor_insert_after (gdsl_list_cursor_t c, void* v)
{
    gdsl_element_t e;
    _gdsl_node_t   n;

    assert (c != NULL);

    if (c->c == c->l->d)
	{
	    return NULL;
	}

    if (c->c == c->l->z)
	{
	    return NULL;
	}

    n = _gdsl_node_alloc ();

    if (n == NULL)
	{
	    return NULL;
	}

    e = c->l->alloc_func (v);

    if (e == NULL)
	{
	    _gdsl_node_free (n);
	    return NULL;
	}

    _gdsl_node_set_content (n, e);
    _gdsl_list_insert_after (n, c->c);

    c->l->card++;

    return e;
}

extern gdsl_element_t
gdsl_list_cursor_insert_before (gdsl_list_cursor_t c, void* v)
{
    gdsl_element_t e;
    _gdsl_node_t   n;

    assert (c != NULL);

    if (c->c == c->l->d)
	{
	    return NULL;
	}

    if (c->c == c->l->z)
	{
	    return NULL;
	}

    n = _gdsl_node_alloc ();

    if (n == NULL)
	{
	    return NULL;
	}

    e = c->l->alloc_func (v);

    if (e == NULL)
	{
	    _gdsl_node_free (n);
	    return NULL;
	}

    _gdsl_node_set_content (n, e);
    _gdsl_list_insert_before (n, c->c);

    c->l->card++;

    return e;
}

extern gdsl_element_t
gdsl_list_cursor_remove (gdsl_list_cursor_t c)
{
    gdsl_element_t e;
    _gdsl_node_t   tmp;

    assert (c != NULL);

    if (c->c == c->l->d)
	{
	    return NULL;
	}

    if (c->c == c->l->z)
	{
	    return NULL;
	}

    tmp = _gdsl_node_get_succ (c->c);

    _gdsl_list_remove (c->c);
    e = _gdsl_node_get_content (c->c);
    _gdsl_node_free (c->c);
    c->c = tmp;
    c->l->card--;

    return e;
}

extern gdsl_element_t
gdsl_list_cursor_remove_after (gdsl_list_cursor_t c)
{
    gdsl_element_t e;
    _gdsl_node_t   tmp;

    assert (c != NULL);

    if (c->c == c->l->d)
	{
	    return NULL;
	}

    tmp = _gdsl_node_get_succ (c->c);

    if (tmp == c->l->z)
	{
	    return NULL;
	}

    _gdsl_list_remove (tmp);
    e = _gdsl_node_get_content (tmp);
    _gdsl_node_free (tmp);

    c->l->card--;

    return e;
}

extern gdsl_element_t
gdsl_list_cursor_remove_before (gdsl_list_cursor_t c)
{
    gdsl_element_t e;
    _gdsl_node_t   tmp;

    assert (c != NULL);

    if (c->c == c->l->z)
	{
	    return NULL;
	}

    tmp = _gdsl_node_get_pred (c->c);

    if (tmp == c->l->d)
	{
	    return NULL;
	}

    _gdsl_list_remove (tmp);
    e = _gdsl_node_get_content (tmp);
    _gdsl_node_free (tmp);

    c->l->card--;

    return e;
}

extern gdsl_list_cursor_t
gdsl_list_cursor_delete (gdsl_list_cursor_t c)
{
    gdsl_element_t e;

    assert (c != NULL);

    e = gdsl_list_cursor_remove (c);

    if (e != NULL)
	{
	    c->l->free_func (e);
	    return c;
	}

    return NULL;
}

extern gdsl_list_cursor_t
gdsl_list_cursor_delete_after (gdsl_list_cursor_t c)
{
    gdsl_element_t e;

    assert (c != NULL);

    e = gdsl_list_cursor_remove_after (c);

    if (e != NULL)
	{
	    c->l->free_func (e);
	    return c;
	}

    return NULL;
}

extern gdsl_list_cursor_t
gdsl_list_cursor_delete_before (gdsl_list_cursor_t c)
{
    gdsl_element_t e;

    assert (c != NULL);

    e = gdsl_list_cursor_remove_before (c);

    if (e != NULL)
	{
	    c->l->free_func (e);
	    return c;
	}

    return NULL;
}

/******************************************************************************/
/* Private functions                                                          */
/******************************************************************************/

static gdsl_element_t 
default_alloc (void* e)
{
    return e;
}

static void 
default_free (gdsl_element_t e)
{
    ;
}

static _gdsl_node_t 
search_by_function (gdsl_list_t l, gdsl_compare_func_t comp_f, const void* value)
{
    _gdsl_node_t left;
    _gdsl_node_t right;

    left = _gdsl_node_get_succ (l->d);
    right = _gdsl_node_get_pred (l->z);

    while (left != _gdsl_node_get_succ (right))
	{
	    if (comp_f (_gdsl_node_get_content (left), (void*) value) == 0)
		{
		    return left;
		}
            
	    if (left == right)
		{
		    return NULL;
		}

	    if (comp_f (_gdsl_node_get_content (right), (void*) value) == 0)
		{
		    return right;
		}

	    left = _gdsl_node_get_succ (left);
	    right = _gdsl_node_get_pred (right);
	}

    return NULL;
}

static _gdsl_node_t 
search_by_position (gdsl_list_t l, ulong pos)
{
    ulong        m;
    _gdsl_node_t tmp;

    if (pos <= 0 || pos > l->card)
	{
	    return NULL;
	}

    m = (l->card / 2) + 1;

    if (pos < m)
	{
	    tmp = _gdsl_node_get_succ (l->d);

	    while (pos > 1)
		{
		    tmp = _gdsl_node_get_succ (tmp);
		    pos--;
		}
	}
    else
	{
	    pos = l->card - pos;
	    tmp = _gdsl_node_get_pred (l->z);

	    while (pos > 0)
		{
		    tmp = _gdsl_node_get_pred (tmp);
		    pos--;
		}
	}

    return tmp;
}

static gdsl_element_t 
update_cursor (gdsl_list_cursor_t c, _gdsl_node_t n)
{
    if (n == NULL) 
	{
	    return NULL;
	}

    c->c = n;

    return _gdsl_node_get_content (n);
}

static _gdsl_node_t 
sort (_gdsl_node_t u, gdsl_compare_func_t comp_f, _gdsl_node_t z)
{
    _gdsl_node_t s;
    _gdsl_node_t t;

    if (_gdsl_node_get_succ (u) == z) 
	{
	    return u;
	}

    s = u;
    t = _gdsl_node_get_succ (_gdsl_node_get_succ (_gdsl_node_get_succ (u)));
    while (t != z)
	{
	    u = _gdsl_node_get_succ (u);
	    t = _gdsl_node_get_succ (_gdsl_node_get_succ (t));
	}

    t = _gdsl_node_get_succ (u);
    _gdsl_node_set_succ (u, z);

    return merge (sort (s, comp_f, z), sort (t, comp_f, z), comp_f, z);
}

static _gdsl_node_t 
merge (_gdsl_node_t s, _gdsl_node_t t, gdsl_compare_func_t comp_f, _gdsl_node_t z)
{
    _gdsl_node_t u = z;
    
    do 
	{
#ifndef USES_MAX
	    /* 
	     * The two first tests below are not necessary if in [1]
	     * we set the max value 
	     */
	    if (t == z)
		{
		    _gdsl_node_link (u, s);
		    u = s;
		    s = _gdsl_node_get_succ (s);
		    continue;
		}

	    /* same as above for this test */
	    if (s == z)
		{
		    _gdsl_node_link (u, t);
		    u = t;
		    t = _gdsl_node_get_succ (t); 
		    continue;
		}
#endif

	    if (comp_f (_gdsl_node_get_content (s), _gdsl_node_get_content (t)) <= 0)
		{
		    _gdsl_node_link (u, s);
		    u = s;
		    s = _gdsl_node_get_succ (s);
		}
	    else
		{
		    _gdsl_node_link (u, t);
		    u = t;
		    t = _gdsl_node_get_succ (t);
		}
	} 
    while (u != z);
    
    u = _gdsl_node_get_succ (z);
    _gdsl_node_set_succ (z, z);
    
    return u;
}

static gdsl_location_t
get_location (gdsl_list_t list, _gdsl_node_t node)
{
    gdsl_location_t location = GDSL_LOCATION_UNDEF;

    if (node == _gdsl_node_get_succ (list->d))
	{
	    location |= GDSL_LOCATION_HEAD;
	}

    if (node == _gdsl_node_get_pred (list->z))
	{
	    location |= GDSL_LOCATION_TAIL;
	}

    return location;
}


/** EMACS **
 * Local variables:
 * mode: c
 * c-basic-offset: 4
 * End:
 */