i have problem in understanding the v_unshift function as it checks for v->ofs as 0 and creates a sublist ,it means sublist is full , but in the initial instance of vlist creation it has a sublist and ofs as 0 ,then why it needs to create a sublist in first insertion.
also please explain the ofs and buf as i want to understand it more better.
struct sublist
{
struct sublist* next;
int *buf;
};
/*
* Vlist Node Declaration
*/
typedef struct vlist_t
{
sublist* head;
int last_size, ofs;
}*vlist;
/*
* Vlist Class Declaration
*/
class v_list
{
public:
sublist *sublist_new(int);
vlist v_new();
void v_del(vlist);
int v_size(vlist);
int* v_addr(vlist, int);
int v_elem(vlist, int);
int* v_unshift(vlist, int);
int v_shift(vlist);
v_list()
{}
};
*
* Creating new sublist
*/
sublist *v_list::sublist_new(int s)
{
sublist* sub = (sublist *)malloc(sizeof(sublist) + sizeof(int) * s);
sub->buf = (int*)(sub + 1);
sub->next = 0;
return sub;
}
/*
* Creating Vlist from Sublist
*/
vlist v_list::v_new()
{
vlist v = new(vlist_t);
v->head = sublist_new(1);
v->last_size = 1;
v->ofs = 0;
return v;
}
/*
* Deleting Vlist
*/
void v_list::v_del(vlist v)
{
sublist *s;
while (v->head)
{
s = v->head->next;
free(v->head);
v->head = s;
}
free(v);
}
/*
* Compute Length of Vlist
*/
int v_list::v_size(vlist v)
{
return v->last_size * 2 - v->ofs - 2;
}
int *v_list::v_addr(vlist v, int idx)
{
sublist *s = v->head;
int top, i;
top = v->last_size;
i = idx + v->ofs;
if (i + 2 >= (top << 1))
{
cout<<"!: idx "<<idx<<" out of range"<<endl;
abort();
}
while (s && i >= top)
{
s = s->next;
i ^= top;
top >>= 1;
}
return s->buf + i;
}
/*
* Locate Element at any position in the Vlist
*/
int v_list::v_elem(vlist v, int idx)
{
return *v_addr(v, idx);
}
/*
* Add Element in the Vlist
*/
int *v_list::v_unshift(vlist v, int x)
{
sublist* s;
int *p;
if (!v->ofs)
{
if (!(s = sublist_new(v->last_size << 1)))
{
cout<<"allocation failure"<<endl;
return 0;
}
v->ofs = (v->last_size <<= 1);
s->next = v->head;
v->head = s;
}
*(p = v->head->buf + --v->ofs) = x;
return p;
}
/*
* Remove Element from the Vlist
*/
int v_list::v_shift(vlist v)
{
sublist* s;
int x;
if (v->last_size == 1 && v->ofs == 1)
{
cout<<"empty list"<<endl;
abort();
}
x = v->head->buf[v->ofs++];
if (v->ofs == v->last_size)
{
v->ofs = 0;
if (v->last_size > 1)
{
s = v->head;
v->head = s->next;
v->last_size >>= 1;
free(s);
}
}
return x;
}