| /*---------------------------------------------------------------------------* |
| * linklist_impl.c * |
| * * |
| * Copyright 2007, 2008 Nuance Communciations, Inc. * |
| * * |
| * Licensed under the Apache License, Version 2.0 (the 'License'); * |
| * you may not use this file except in compliance with the License. * |
| * * |
| * You may obtain a copy of the License at * |
| * http://www.apache.org/licenses/LICENSE-2.0 * |
| * * |
| * Unless required by applicable law or agreed to in writing, software * |
| * distributed under the License is distributed on an 'AS IS' BASIS, * |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * |
| * See the License for the specific language governing permissions and * |
| * limitations under the License. * |
| * * |
| *---------------------------------------------------------------------------*/ |
| |
| |
| |
| #include <stdlib.h> |
| |
| #include "pmemory.h" |
| #include "plog.h" |
| |
| #include "linklist.h" |
| |
| extern void *lts_alloc(int num, int size); |
| |
| |
| /* very simple static memory allocation: |
| 1. pool of linked list nodes - from static allocated array |
| 2. each node is marked "used" when allocated; marked "unused" when deallocated |
| 3. since the stress linked lists deal with single words, an array will suffice. |
| */ |
| |
| #ifdef USE_STATIC_SLTS |
| #define NUM_ALLOC_NODES 30 /* Max 30 syllables per word */ |
| |
| typedef struct LNodeAllocElement |
| { |
| LNode node; |
| short usedflag; |
| } LNodeAllocElement; |
| |
| static LNodeAllocElement g_LNodeAllocArray[NUM_ALLOC_NODES]; |
| |
| void ClearLNodeArray() |
| { |
| int i; |
| LNode *n; |
| |
| for(i=0; i<NUM_ALLOC_NODES; i++){ |
| g_LNodeAllocArray[i].usedflag = 0; |
| n = &(g_LNodeAllocArray[i].node); |
| n->data = 0; |
| n->next = n->prev = 0; |
| } |
| } |
| |
| static LNode *AllocNode() |
| { |
| int i; |
| |
| /* return first unused element */ |
| for(i=0; i<NUM_ALLOC_NODES; i++){ |
| if(g_LNodeAllocArray[i].usedflag == 0){ |
| g_LNodeAllocArray[i].usedflag = 1; |
| |
| /* zero out the node first*/ |
| (g_LNodeAllocArray[i].node).data = NULL; |
| (g_LNodeAllocArray[i].node).prev = NULL; |
| (g_LNodeAllocArray[i].node).next = NULL; |
| |
| return &(g_LNodeAllocArray[i].node); |
| } |
| } |
| /* ran out of nodes */ |
| return NULL; |
| } |
| |
| static void FreeNode(LNode *n) |
| { |
| int i; |
| long addr; |
| |
| /* compare addresses of pointers */ |
| for(i=0; i<NUM_ALLOC_NODES; i++){ |
| addr = (long) (&(g_LNodeAllocArray[i].node)); |
| if(addr == (long)n){ |
| g_LNodeAllocArray[i].usedflag = 0; |
| return; |
| } |
| } |
| |
| /* not found. don't do anything */ |
| return; |
| } |
| |
| |
| #else /* !USE_STATIC_SLTS */ |
| |
| static LNode *AllocNode() |
| { |
| return (LNode *)lts_alloc(1, sizeof(LNode)); |
| } |
| static void FreeNode(LNode *n) |
| { |
| FREE(n); |
| } |
| |
| #endif |
| |
| |
| |
| /* Inserts after current element |
| At return, current element will be point to newly created node |
| |
| handle static allocation later - possibly using a pool of nodes? |
| For now, dynamically allocate a new list node with the data |
| */ |
| LListResult Insert(LList *list, void *data) |
| { |
| LNode *newnode = AllocNode(); |
| if(newnode == NULL){ |
| return LListResourceAllocError; |
| } |
| newnode->data = data; |
| |
| if(list->head == NULL){ |
| /* if list is empty, assign to head */ |
| list->head = newnode; |
| (list->head)->next = NULL; |
| (list->head)->prev = NULL; |
| |
| /* update curr to newly inserted node */ |
| list->curr = list->head; |
| list->tail = list->head; |
| return LListSuccess; |
| } |
| |
| /* curr not specified, insert from the end */ |
| if(list->curr == NULL){ |
| list->curr = list->tail; |
| } |
| |
| /* in cases with single node, default to insert at end */ |
| if(list->curr == list->tail){ |
| /* insert at the end */ |
| newnode->prev = list->curr; |
| newnode->next = NULL; |
| (list->curr)->next = newnode; |
| |
| /* update both curr and end */ |
| list->curr = newnode; |
| list->tail = newnode; |
| return LListSuccess; |
| |
| }else if(list->curr == list->head){ |
| /* insert at head */ |
| newnode->next = list->head; |
| newnode->prev = NULL; |
| (list->head)->prev = newnode; |
| |
| /* update curr to newly inserted node */ |
| list->curr = list->head; |
| list->head = newnode; |
| |
| return LListSuccess; |
| |
| }else{ |
| /* insert somewhere in middle */ |
| newnode->prev = list->curr; |
| newnode->next = (list->curr)->next; |
| (list->curr)->next = newnode; |
| (newnode->next)->prev = newnode; |
| |
| /* update curr to newly inserted node */ |
| list->curr = newnode; |
| return LListSuccess; |
| } |
| } |
| |
| /* Deletes at current element |
| At return, current element will point to previous node |
| |
| handle static deallocation later - possibly using a pool of nodes? |
| For now, dynamically free a new list node |
| */ |
| |
| LListResult Delete(LList *list) |
| { |
| LNode *curr; |
| |
| if(list->head == NULL){ |
| return LListEmpty; |
| } |
| |
| /* start deleting from the end if curr not specified */ |
| if(list->curr == NULL){ |
| list->curr = list->tail; |
| } |
| |
| curr = list->curr; |
| |
| if(curr == list->head){ |
| /* delete from the head */ |
| list->head = curr->next; |
| |
| if(list->head != NULL){ |
| (list->head)->prev = NULL; |
| } |
| |
| FreeNode(curr); |
| list->curr = list->head; |
| return LListSuccess; |
| |
| }else if(curr == list->tail){ |
| /* delete from the end */ |
| list->tail = curr->prev; |
| |
| if(list->tail != NULL){ |
| (list->tail)->next = NULL; |
| } |
| |
| FreeNode(curr); |
| list->curr = list->tail; |
| return LListSuccess; |
| |
| }else{ |
| /* delete somewhere in the middle */ |
| list->curr = curr->next; |
| |
| /* still check, just in case*/ |
| if(curr->next != NULL){ |
| (curr->next)->prev = curr->prev; |
| } |
| if(curr->prev != NULL){ |
| (curr->prev)->next = curr->next; |
| } |
| |
| FreeNode(curr); |
| return LListSuccess; |
| } |
| } |
| |