1/*---------------------------------------------------------------------------*
2 *  linklist_impl.c  *
3 *                                                                           *
4 *  Copyright 2007, 2008 Nuance Communciations, Inc.                               *
5 *                                                                           *
6 *  Licensed under the Apache License, Version 2.0 (the 'License');          *
7 *  you may not use this file except in compliance with the License.         *
8 *                                                                           *
9 *  You may obtain a copy of the License at                                  *
10 *      http://www.apache.org/licenses/LICENSE-2.0                           *
11 *                                                                           *
12 *  Unless required by applicable law or agreed to in writing, software      *
13 *  distributed under the License is distributed on an 'AS IS' BASIS,        *
14 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. *
15 *  See the License for the specific language governing permissions and      *
16 *  limitations under the License.                                           *
17 *                                                                           *
18 *---------------------------------------------------------------------------*/
19
20
21
22#include <stdlib.h>
23
24#include "pmemory.h"
25#include "plog.h"
26
27#include "linklist.h"
28
29extern void *lts_alloc(int num, int size);
30
31
32/* very simple static memory allocation:
33   1. pool of linked list nodes - from static allocated array
34   2. each node is marked "used" when allocated; marked "unused" when deallocated
35   3. since the stress linked lists deal with single words, an array will suffice.
36*/
37
38#ifdef USE_STATIC_SLTS
39#define NUM_ALLOC_NODES 30  /* Max 30 syllables per word */
40
41typedef struct LNodeAllocElement
42{
43  LNode node;
44  short usedflag;
45} LNodeAllocElement;
46
47static LNodeAllocElement g_LNodeAllocArray[NUM_ALLOC_NODES];
48
49void ClearLNodeArray()
50{
51  int i;
52  LNode *n;
53
54  for(i=0; i<NUM_ALLOC_NODES; i++){
55    g_LNodeAllocArray[i].usedflag = 0;
56    n = &(g_LNodeAllocArray[i].node);
57    n->data = 0;
58    n->next = n->prev = 0;
59  }
60}
61
62static LNode *AllocNode()
63{
64  int i;
65
66  /* return first unused element */
67  for(i=0; i<NUM_ALLOC_NODES; i++){
68    if(g_LNodeAllocArray[i].usedflag == 0){
69      g_LNodeAllocArray[i].usedflag = 1;
70
71	  /* zero out the node first*/
72	  (g_LNodeAllocArray[i].node).data = NULL;
73	  (g_LNodeAllocArray[i].node).prev = NULL;
74	  (g_LNodeAllocArray[i].node).next = NULL;
75
76      return &(g_LNodeAllocArray[i].node);
77    }
78  }
79  /* ran out of nodes */
80  return NULL;
81}
82
83static void FreeNode(LNode *n)
84{
85  int i;
86  long addr;
87
88  /* compare addresses of pointers */
89  for(i=0; i<NUM_ALLOC_NODES; i++){
90    addr = (long) (&(g_LNodeAllocArray[i].node));
91    if(addr == (long)n){
92      g_LNodeAllocArray[i].usedflag = 0;
93      return;
94    }
95  }
96
97  /* not found. don't do anything */
98   return;
99}
100
101
102#else /* !USE_STATIC_SLTS */
103
104static LNode *AllocNode()
105{
106  return (LNode *)lts_alloc(1, sizeof(LNode));
107}
108static void FreeNode(LNode *n)
109{
110  FREE(n);
111}
112
113#endif
114
115
116
117/* Inserts after current element
118   At return, current element will be point to newly created node
119
120   handle static allocation later - possibly using a pool of nodes?
121   For now, dynamically allocate a new list node with the data
122*/
123LListResult Insert(LList *list, void *data)
124{
125  LNode *newnode = AllocNode();
126  if(newnode == NULL){
127     return LListResourceAllocError;
128  }
129  newnode->data = data;
130
131  if(list->head == NULL){
132    /* if list is empty, assign to head */
133    list->head = newnode;
134    (list->head)->next = NULL;
135    (list->head)->prev = NULL;
136
137    /* update curr to newly inserted node */
138    list->curr = list->head;
139    list->tail = list->head;
140    return LListSuccess;
141  }
142
143    /* curr not specified, insert from the end */
144  if(list->curr == NULL){
145    list->curr = list->tail;
146  }
147
148  /* in cases with single node, default to insert at end */
149  if(list->curr == list->tail){
150    /* insert at the end */
151    newnode->prev = list->curr;
152    newnode->next = NULL;
153    (list->curr)->next = newnode;
154
155    /* update both curr and end */
156    list->curr = newnode;
157    list->tail = newnode;
158    return LListSuccess;
159
160  }else if(list->curr == list->head){
161    /* insert at head */
162    newnode->next = list->head;
163    newnode->prev = NULL;
164    (list->head)->prev = newnode;
165
166    /* update curr to newly inserted node */
167    list->curr = list->head;
168    list->head = newnode;
169
170    return LListSuccess;
171
172  }else{
173    /* insert somewhere in middle */
174    newnode->prev = list->curr;
175    newnode->next = (list->curr)->next;
176    (list->curr)->next = newnode;
177    (newnode->next)->prev = newnode;
178
179    /* update curr to newly inserted node */
180    list->curr = newnode;
181    return LListSuccess;
182  }
183}
184
185/* Deletes at current element
186   At return, current element will point to previous node
187
188   handle static deallocation later - possibly using a pool of nodes?
189   For now, dynamically free a new list node
190*/
191
192LListResult Delete(LList *list)
193{
194  LNode *curr;
195
196  if(list->head == NULL){
197    return LListEmpty;
198  }
199
200  /* start deleting from the end if curr not specified */
201  if(list->curr == NULL){
202    list->curr = list->tail;
203  }
204
205  curr = list->curr;
206
207  if(curr == list->head){
208  /* delete from the head */
209    list->head = curr->next;
210
211    if(list->head != NULL){
212      (list->head)->prev = NULL;
213    }
214
215    FreeNode(curr);
216    list->curr = list->head;
217    return LListSuccess;
218
219  }else if(curr == list->tail){
220    /* delete from the end */
221    list->tail = curr->prev;
222
223    if(list->tail != NULL){
224      (list->tail)->next = NULL;
225    }
226
227    FreeNode(curr);
228    list->curr = list->tail;
229    return LListSuccess;
230
231  }else{
232    /* delete somewhere in the middle */
233    list->curr = curr->next;
234
235    /* still check, just in case*/
236    if(curr->next != NULL){
237      (curr->next)->prev = curr->prev;
238    }
239    if(curr->prev != NULL){
240      (curr->prev)->next = curr->next;
241    }
242
243    FreeNode(curr);
244    return LListSuccess;
245  }
246}
247
248