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.

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. typedef struct sublist {
  5.     struct sublist* next;
  6.     int *buf;
  7. } sublist_t;
  8.  
  9. sublist_t* sublist_new(size_t s) {
  10.     sublist_t* sub = malloc(sizeof(sublist_t) + sizeof(int) * s);
  11.     sub->buf = (int*) (sub + 1);
  12.     sub->next = 0;
  13.     return sub;
  14. }
  15.  
  16. typedef struct vlist_t {
  17.     sublist_t* head;
  18.     size_t last_size, ofs;
  19. } vlist_t, *vlist;
  20.  
  21. vlist v_new() {
  22.     vlist v = malloc(sizeof(vlist_t));
  23.     v->head = sublist_new(1);
  24.     v->last_size = 1;
  25.     v->ofs = 0;
  26.     return v;
  27. }
  28.  
  29. void v_del(vlist v) {
  30.     sublist_t *s;
  31.     while (v->head) {
  32.         s = v->head->next;
  33.         free(v->head);
  34.         v->head = s;
  35.     }
  36.     free(v);
  37. }
  38.  
  39. inline size_t v_size(vlist v) {
  40.     return v->last_size * 2 - v->ofs - 2;
  41. }
  42.  
  43. int* v_addr(vlist v, size_t idx) {
  44.     sublist_t *s = v->head;
  45.     size_t top = v->last_size, i = idx + v->ofs;
  46.  
  47.     if (i + 2 >= (top << 1)) {
  48.         fprintf(stderr, "!: idx %d out of range\n", (int) idx);
  49.         abort();
  50.     }
  51.     while (s && i >= top) {
  52.         s = s->next, i ^= top;
  53.         top >>= 1;
  54.     }
  55.     return s->buf + i;
  56. }
  57.  
  58. inline int v_elem(vlist v, size_t idx) {
  59.     return *v_addr(v, idx);
  60. }
  61.  
  62. int* v_unshift(vlist v, int x) {
  63.     sublist_t* s;
  64.     int *p;
  65.  
  66.     if (!v->ofs) {
  67.         if (!(s = sublist_new(v->last_size << 1))) {
  68.             fprintf(stderr, "?: alloc failure\n");
  69.             return 0;
  70.         }
  71.         v->ofs = (v->last_size <<= 1);
  72.         s->next = v->head;
  73.         v->head = s;
  74.     }
  75.     *(p = v->head->buf + --v->ofs) = x;
  76.     return p;
  77. }
  78.  
  79. int v_shift(vlist v) {
  80.     sublist_t* s;
  81.     int x;
  82.  
  83.     if (v->last_size == 1 && v->ofs == 1) {
  84.         fprintf(stderr, "!: empty list\n");
  85.         abort();
  86.     }
  87.     x = v->head->buf[v->ofs++];
  88.  
  89.     if (v->ofs == v->last_size) {
  90.         v->ofs = 0;
  91.         if (v->last_size > 1) {
  92.             s = v->head, v->head = s->next;
  93.             v->last_size >>= 1;
  94.             free(s);
  95.         }
  96.     }
  97.     return x;
  98. }
  99.  
  100. int main() {
  101.     int i;
  102.  
  103.     vlist v = v_new();
  104.     for (i = 0; i < 10; i++)
  105.         v_unshift(v, i);
  106.  
  107.     printf("size: %d\n", v_size(v));
  108.     for (i = 0; i < 10; i++)
  109.         printf("v[%d] = %d\n", i, v_elem(v, i));
  110.     for (i = 0; i < 10; i++)
  111.         printf("shift: %d\n", v_shift(v));
  112.  
  113.     /* v_shift(v); *//* <- boom */
  114.  
  115.     v_del(v);
  116.     return 0;
  117. }

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.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement

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

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.