{"id":789,"date":"2014-03-09T20:59:26","date_gmt":"2014-03-09T19:59:26","guid":{"rendered":"http:\/\/trigonakis.com\/blog\/?p=789"},"modified":"2014-03-09T20:59:26","modified_gmt":"2014-03-09T19:59:26","slug":"the-simplest-linked-list-implementation-in-c","status":"publish","type":"post","link":"http:\/\/trigonakis.com\/blog\/2014\/03\/09\/the-simplest-linked-list-implementation-in-c\/","title":{"rendered":"The simplest linked list implementation in C"},"content":{"rendered":"<p>I recently needed to develop a way to perform pseudo-random memory accesses in a C program, in order to fool the hardware prefetchers. Without going into any details, my solution was to represent some continuous memory as a linked list with random next pointers.<\/p>\n<p>Naturally, the simplest list that can be developed has nodes that do not contain any other elements apart from the next pointers that link the nodes together. In C, this can be easily done with a structure similar to the following:<\/p>\n<pre lang=\"c\">\r\nstruct node\r\n{\r\n  struct node* next;\r\n}\r\n<\/pre>\n<p>However, one can leverage the flexibility of C to even avoid using the <code>node<\/code> structure: you are allowed to cast some memory to any type you like. For instance, you can use 8 bytes as an integer(<code>uint64_t<\/code>) , or as a pointer to an integer (<code>uint64_t*<\/code>).<\/p>\n<p>Doing so, we can develop, what I believe is, the simplest linked list possible.<br \/>\nThe code that generates a random list is the following:<\/p>\n<pre lang=\"c\">\r\nstatic void\r\ncreate_rand_list(volatile uint64_t* list, size_t n)\r\n{\r\n  srand(time(NULL));\r\n  uint8_t* used = calloc(n, sizeof(uint8_t));\r\n  assert (used != NULL);\r\n\r\n  size_t idx = 0;\r\n  size_t used_num = 0;\r\n  while (used_num < n - 1)\r\n    {\r\n      used[idx] = 1;\r\n      used_num++;\r\n\r\n      size_t nxt;\r\n      do\r\n        {\r\n          nxt = rand() % n;\r\n        }\r\n      while (used[nxt]);\r\n  \r\n      list[idx] = (uint64_t) (list + nxt);\r\n      idx = nxt;\r\n    }\r\n\r\n  list[idx] = 0; \t\t\/* NULL pointer in the last element *\/\r\n\r\n  free(used);\r\n}\r\n<\/pre>\n<p>The \"magic\" happens when we set <code>list[idx] = (uint64_t) (list + nxt)<\/code>, so we set the \"next\" pointer for the location idx.<br \/>\nWhat is even more interesting is how we can now parse and get the size of the list:<\/p>\n<pre lang=\"c\">\r\nstatic void\r\nlist_parse(volatile uint64_t* l)\r\n{\r\n  while (*l != 0)\r\n    {\r\n      l = (uint64_t*) *l;\r\n    }\r\n}\r\n\r\nstatic size_t\r\nlist_size(volatile uint64_t* l)\r\n{\r\n  size_t s = 1;\r\n  while (*l != 0)\r\n    {\r\n      l = (uint64_t*) *l;\r\n      s++;\r\n    }\r\n  return s;\r\n}\r\n<\/pre>\n<p>Pretty slick, right? \ud83d\ude42<\/p>\n","protected":false},"excerpt":{"rendered":"<p>I recently needed to develop a way to perform pseudo-random memory accesses in a C program, in order to fool the hardware prefetchers. Without going into any details, my solution was to represent some continuous memory as a linked list with random next pointers. Naturally, the simplest list that can be developed has nodes that [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"jetpack_publicize_message":"","jetpack_is_tweetstorm":false,"jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[203,28],"tags":[29,213,214],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p1ouW6-cJ","_links":{"self":[{"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/posts\/789"}],"collection":[{"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/comments?post=789"}],"version-history":[{"count":5,"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/posts\/789\/revisions"}],"predecessor-version":[{"id":794,"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/posts\/789\/revisions\/794"}],"wp:attachment":[{"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/media?parent=789"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/categories?post=789"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/tags?post=789"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}