linked_list.h revision 5821806d5e7f356e8fa4b058a389a808ea183019 
1// Copyright (c) 2008, Google Inc.
2// All rights reserved.
3//
4// Redistribution and use in source and binary forms, with or without
5// modification, are permitted provided that the following conditions are
6// met:
7//
8//     * Redistributions of source code must retain the above copyright
9// notice, this list of conditions and the following disclaimer.
10//     * Redistributions in binary form must reproduce the above
11// copyright notice, this list of conditions and the following disclaimer
12// in the documentation and/or other materials provided with the
13// distribution.
14//     * Neither the name of Google Inc. nor the names of its
15// contributors may be used to endorse or promote products derived from
16// this software without specific prior written permission.
17//
18// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29
30// ---
31// Author: Sanjay Ghemawat <opensource@google.com>
32//
33// Some very basic linked list functions for dealing with using void * as
34// storage.
35
36#ifndef TCMALLOC_LINKED_LIST_H_
37#define TCMALLOC_LINKED_LIST_H_
38
39#include <stddef.h>
40
41namespace tcmalloc {
42
43inline void *SLL_Next(void *t) {
44  return *(reinterpret_cast<void**>(t));
45}
46
47inline void SLL_SetNext(void *t, void *n) {
48  *(reinterpret_cast<void**>(t)) = n;
49}
50
51inline void SLL_Push(void **list, void *element) {
52  SLL_SetNext(element, *list);
53  *list = element;
54}
55
56inline void *SLL_Pop(void **list) {
57  void *result = *list;
58  *list = SLL_Next(*list);
59  return result;
60}
61
62// Remove N elements from a linked list to which head points.  head will be
63// modified to point to the new head.  start and end will point to the first
64// and last nodes of the range.  Note that end will point to NULL after this
65// function is called.
66inline void SLL_PopRange(void **head, int N, void **start, void **end) {
67  if (N == 0) {
68    *start = NULL;
69    *end = NULL;
70    return;
71  }
72
73  void *tmp = *head;
74  for (int i = 1; i < N; ++i) {
75    tmp = SLL_Next(tmp);
76  }
77
78  *start = *head;
79  *end = tmp;
80  *head = SLL_Next(tmp);
81  // Unlink range from list.
82  SLL_SetNext(tmp, NULL);
83}
84
85inline void SLL_PushRange(void **head, void *start, void *end) {
86  if (!start) return;
87  SLL_SetNext(end, *head);
88  *head = start;
89}
90
91inline size_t SLL_Size(void *head) {
92  int count = 0;
93  while (head) {
94    count++;
95    head = SLL_Next(head);
96  }
97  return count;
98}
99
100}  // namespace tcmalloc
101
102#endif  // TCMALLOC_LINKED_LIST_H_
103