C Program to Implement Vlist

This is a C Program to implement VList. VList is a persistent data structure that combines the fast indexing of arrays with the easy extension of singly-linked lists. Like singly-linked they are persistent, and elements can be added to or removed from the front in constant time.

Here is source code of the C Program to Implement Vlist. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#include <stdio.h>
```
```
#include <stdlib.h>
```
```
 
```
```
typedef struct sublist {
```
```
    struct sublist* next;
```
```
    int *buf;
```
```
} sublist_t;
```
```
 
```
```
sublist_t* sublist_new(size_t s) {
```

    sublist_t* sub = malloc(sizeof(sublist_t) + sizeof(int) * s);

```
    sub->buf = (int*) (sub + 1);
```
```
    sub->next = 0;
```
```
    return sub;
```
```
}
```
```
 
```
```
typedef struct vlist_t {
```
```
    sublist_t* head;
```
```
    size_t last_size, ofs;
```
```
} vlist_t, *vlist;
```
```
 
```
```
vlist v_new() {
```
```
    vlist v = malloc(sizeof(vlist_t));
```
```
    v->head = sublist_new(1);
```
```
    v->last_size = 1;
```
```
    v->ofs = 0;
```
```
    return v;
```
```
}
```
```
 
```
```
void v_del(vlist v) {
```
```
    sublist_t *s;
```
```
    while (v->head) {
```
```
        s = v->head->next;
```
```
        free(v->head);
```
```
        v->head = s;
```
```
    }
```
```
    free(v);
```
```
}
```
```
 
```
```
inline size_t v_size(vlist v) {
```

    return v->last_size * 2 - v->ofs - 2;

```
}
```
```
 
```
```
int* v_addr(vlist v, size_t idx) {
```
```
    sublist_t *s = v->head;
```

    size_t top = v->last_size, i = idx + v->ofs;

```
 
```
```
    if (i + 2 >= (top << 1)) {
```

        fprintf(stderr, "!: idx %d out of range\n", (int) idx);

```
        abort();
```
```
    }
```
```
    while (s && i >= top) {
```
```
        s = s->next, i ^= top;
```
```
        top >>= 1;
```
```
    }
```
```
    return s->buf + i;
```
```
}
```
```
 
```

inline int v_elem(vlist v, size_t idx) {

```
    return *v_addr(v, idx);
```
```
}
```
```
 
```
```
int* v_unshift(vlist v, int x) {
```
```
    sublist_t* s;
```
```
    int *p;
```
```
 
```
```
    if (!v->ofs) {
```

        if (!(s = sublist_new(v->last_size << 1))) {

            fprintf(stderr, "?: alloc failure\n");

```
            return 0;
```
```
        }
```
```
        v->ofs = (v->last_size <<= 1);
```
```
        s->next = v->head;
```
```
        v->head = s;
```
```
    }
```
```
    *(p = v->head->buf + --v->ofs) = x;
```
```
    return p;
```
```
}
```
```
 
```
```
int v_shift(vlist v) {
```
```
    sublist_t* s;
```
```
    int x;
```
```
 
```

    if (v->last_size == 1 && v->ofs == 1) {

        fprintf(stderr, "!: empty list\n");

```
        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;
```
```
}
```
```
 
```
```
int main() {
```
```
    int i;
```
```
 
```
```
    vlist v = v_new();
```
```
    for (i = 0; i < 10; i++)
```
```
        v_unshift(v, i);
```
```
 
```
```
    printf("size: %d\n", v_size(v));
```
```
    for (i = 0; i < 10; i++)
```

        printf("v[%d] = %d\n", i, v_elem(v, i));

```
    for (i = 0; i < 10; i++)
```

        printf("shift: %d\n", v_shift(v));

```
 
```
```
    /* v_shift(v); *//* <- boom */
```
```
 
```
```
    v_del(v);
```
```
    return 0;
```
```
}
```

Output:

$ gcc VList.c
$ ./a.out
 
size: 10
 
v[0] = 9
v[1] = 8
v[2] = 7
v[3] = 6
v[4] = 5
v[5] = 4
v[6] = 3
v[7] = 2
v[8] = 1
v[9] = 0
 
shift: 9
shift: 8
shift: 7
shift: 6
shift: 5
shift: 4
shift: 3
shift: 2
shift: 1
shift: 0

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

« Prev - C Program to Implement Heap

» Next - C Program to Implement Skip List

Related Posts:

Practice Programming MCQs
Check Programming Books
Practice Design & Analysis of Algorithms MCQ
Practice Computer Science MCQs
Check Data Structure Books

Recommended Articles: