LibreOffice Module vcl (master)  1
list.cxx
Go to the documentation of this file.
1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 /*
3  * This file is part of the LibreOffice project.
4  *
5  * This Source Code Form is subject to the terms of the Mozilla Public
6  * License, v. 2.0. If a copy of the MPL was not distributed with this
7  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
8  *
9  * This file incorporates work covered by the following license notice:
10  *
11  * Licensed to the Apache Software Foundation (ASF) under one or more
12  * contributor license agreements. See the NOTICE file distributed
13  * with this work for additional information regarding copyright
14  * ownership. The ASF licenses this file to you under the Apache
15  * License, Version 2.0 (the "License"); you may not use this file
16  * except in compliance with the License. You may obtain a copy of
17  * the License at http://www.apache.org/licenses/LICENSE-2.0 .
18  */
19 
20 /*[]---------------------------------------------------[]*/
21 /*| |*/
22 /*| list.c - bidirectional list class |*/
23 /*| |*/
24 /*| |*/
25 /*| Author: Alexander Gelfenbain |*/
26 /*[]---------------------------------------------------[]*/
27 
28 #include <assert.h>
29 #include <cstdlib>
30 
31 #include "list.h"
32 
33 namespace {
34 
35 /*- private data types */
36 struct lnode {
37  struct lnode *next;
38  struct lnode *prev;
39 
40  void *value;
41 
42 };
43 
44 }
45 
46 struct list_ {
47  lnode *head, *tail, *cptr;
48  size_t aCount;
50 };
51 
52 /*- private methods */
53 
54 static lnode *newNode(void *el)
55 {
56  lnode *ptr = static_cast<lnode *>(std::malloc(sizeof(lnode)));
57  assert(ptr != nullptr);
58 
59  ptr->value = el;
60 
61  return ptr;
62 }
63 
64 static lnode *appendPrim(list pThis, void *el)
65 {
66  lnode *ptr = newNode(el);
67  lnode **flink, *blink;
68 
69  if (pThis->tail != nullptr) {
70  flink = &(pThis->tail->next);
71  blink = pThis->tail;
72  } else {
73  flink = &pThis->head;
74  blink = nullptr;
75  pThis->cptr = ptr; /*- list was empty - set current to this element */
76  }
77 
78  *flink = ptr;
79  pThis->tail = ptr;
80 
81  ptr->prev = blink;
82  ptr->next = nullptr;
83 
84  pThis->aCount++;
85  return ptr;
86 }
87 
88 /*- public methods */
89 list listNewEmpty() /*- default ctor */
90 {
91  list pThis = static_cast<list>(std::malloc(sizeof(struct list_)));
92  assert(pThis != nullptr);
93 
94  pThis->aCount = 0;
95  pThis->eDtor = nullptr;
96  pThis->head = pThis->tail = pThis->cptr = nullptr;
97 
98  return pThis;
99 }
100 
101 void listDispose(list pThis) /*- dtor */
102 {
103  assert(pThis != nullptr);
104  listClear(pThis);
105  std::free(pThis);
106 }
107 
109 {
110  assert(pThis != nullptr);
111  pThis->eDtor = f;
112 }
113 
114 /* calling this function on an empty list is a run-time error */
115 void *listCurrent(list pThis)
116 {
117  assert(pThis != nullptr);
118  assert(pThis->cptr != nullptr);
119  return pThis->cptr->value;
120 }
121 
122 int listCount(list pThis)
123 {
124  assert(pThis != nullptr);
125  return pThis->aCount;
126 }
127 
128 int listIsEmpty(list pThis)
129 {
130  assert(pThis != nullptr);
131  return pThis->aCount == 0;
132 }
133 
134 int listNext(list pThis)
135 {
136  return listSkipForward(pThis, 1);
137 }
138 
139 int listSkipForward(list pThis, int n)
140 {
141  int m = 0;
142  assert(pThis != nullptr);
143 
144  if (pThis->cptr == nullptr) return 0;
145 
146  while (n != 0) {
147  if (pThis->cptr->next == nullptr) break;
148  pThis->cptr = pThis->cptr->next;
149  n--;
150  m++;
151  }
152  return m;
153 }
154 
155 int listToFirst(list pThis)
156 {
157  assert(pThis != nullptr);
158 
159  if (pThis->cptr != pThis->head) {
160  pThis->cptr = pThis->head;
161  return 1;
162  }
163  return 0;
164 }
165 
166 int listToLast(list pThis)
167 {
168  assert(pThis != nullptr);
169 
170  if (pThis->cptr != pThis->tail) {
171  pThis->cptr = pThis->tail;
172  return 1;
173  }
174  return 0;
175 }
176 
177 list listAppend(list pThis, void *el)
178 {
179  assert(pThis != nullptr);
180 
181  appendPrim(pThis, el);
182  return pThis;
183 }
184 
186 {
187  lnode *ptr = nullptr;
188  if (pThis->cptr == nullptr) return pThis;
189 
190  if (pThis->cptr->next != nullptr) {
191  ptr = pThis->cptr->next;
192  pThis->cptr->next->prev = pThis->cptr->prev;
193  } else {
194  pThis->tail = pThis->cptr->prev;
195  }
196 
197  if (pThis->cptr->prev != nullptr) {
198  if (ptr == nullptr) ptr = pThis->cptr->prev;
199  pThis->cptr->prev->next = pThis->cptr->next;
200  } else {
201  pThis->head = pThis->cptr->next;
202  }
203 
204  if (pThis->eDtor) pThis->eDtor(pThis->cptr->value); /* call the dtor callback */
205 
206  std::free(pThis->cptr);
207  pThis->aCount--;
208  pThis->cptr = ptr;
209  return pThis;
210 }
211 
213 {
214  lnode *node = pThis->head, *ptr;
215 
216  while (node) {
217  ptr = node->next;
218  if (pThis->eDtor) pThis->eDtor(node->value); /* call the dtor callback */
219  std::free(node);
220  pThis->aCount--;
221  node = ptr;
222  }
223 
224  pThis->head = pThis->tail = pThis->cptr = nullptr;
225  assert(pThis->aCount == 0);
226  return pThis;
227 }
228 
229 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
void listDispose(list pThis)
Definition: list.cxx:101
int listNext(list pThis)
Definition: list.cxx:134
int listCount(list pThis)
Definition: list.cxx:122
static lnode * appendPrim(list pThis, void *el)
Definition: list.cxx:64
list listNewEmpty()
Definition: list.cxx:89
int listToFirst(list pThis)
Definition: list.cxx:155
Definition: list.cxx:46
void(* list_destructor)(void *)
Definition: list.h:41
list listClear(list pThis)
Definition: list.cxx:212
list_destructor eDtor
Definition: list.cxx:49
int listSkipForward(list pThis, int n)
Definition: list.cxx:139
int listToLast(list pThis)
Definition: list.cxx:166
list listAppend(list pThis, void *el)
Definition: list.cxx:177
int listIsEmpty(list pThis)
Definition: list.cxx:128
size_t aCount
Definition: list.cxx:48
Any value
list listRemove(list pThis)
Definition: list.cxx:185
void(* f)(TrueTypeTable *)
Definition: ttcr.cxx:474
void listSetElementDtor(list pThis, list_destructor f)
Definition: list.cxx:108
void * listCurrent(list pThis)
Definition: list.cxx:115
tuple m
static lnode * newNode(void *el)
Definition: list.cxx:54
tuple next
lnode * head
Definition: list.cxx:47
lnode * tail
Definition: list.cxx:47
lnode * cptr
Definition: list.cxx:47