<commit_before>/*
 * BRLTTY - A background process providing access to the console screen (when in
 *          text mode) for a blind person using a refreshable braille display.
 *
 * Copyright (C) 1995-2015 by The BRLTTY Developers.
 *
 * BRLTTY comes with ABSOLUTELY NO WARRANTY.
 *
 * This is free software, placed under the terms of the
 * GNU General Public License, as published by the Free Software
 * Foundation; either version 2 of the License, or (at your option) any
 * later version. Please see the file LICENSE-GPL for details.
 *
 * Web Page: http://mielke.cc/brltty/
 *
 * This software is maintained by <NAME> <<EMAIL>>.
 */

#include "prologue.h"

#include "log.h"
#include "queue.h"
#include "thread.h"
#include "program.h"

#if defined(PTHREAD_MUTEX_INITIALIZER)
typedef pthread_mutex_t LockType;
#define LOCK_INITIALIZER PTHREAD_MUTEX_INITIALIZER

static void
acquireExclusiveLock (LockType *lock) {
  pthread_mutex_lock(lock);
}

static void
releaseLock (LockType *lock) {
  pthread_mutex_unlock(lock);
}

#else /* thread-safe queue management */
typedef unsigned char LockType;
#define LOCK_INITIALIZER 0

static void
acquireExclusiveLock (LockType *lock) {
}

static void
releaseLock (LockType *lock) {
}

#warning queues are not thread-safe on this platform
#endif /* thread-safe queue management */

static Element *discardedElementsList = NULL;
static LockType discardedElementsListLock = LOCK_INITIALIZER;

static void
lockDiscardedElementsList (void) {
  acquireExclusiveLock(&discardedElementsListLock);
}

static void
unlockDiscardedElementsList (void) {
  releaseLock(&discardedElementsListLock);
}

struct QueueStruct {
  Element *head;
  unsigned int size;
  void *data;
  ItemDeallocator *deallocateItem;
  ItemComparator *compareItems;
};

struct ElementStruct {
  Element *next;
  Element *previous;
  Queue *queue;
  int identifier;
  void *item;
};

static void
addElement (Queue *queue, Element *element) {
  {
    static int identifier = 0;
    element->identifier = ++identifier;
  }

  element->queue = queue;
  queue->size += 1;
}

static void
removeElement (Element *element) {
  element->queue->size -= 1;
  element->queue = NULL;
  element->identifier = 0;
}

static void
removeItem (Element *element) {
  if (element->item) {
    Queue *queue = element->queue;
    ItemDeallocator *deallocateItem = queue->deallocateItem;

    if (deallocateItem) deallocateItem(element->item, queue->data);
    element->item = NULL;
  }
}

static void
discardElement (Element *element) {
  removeItem(element);
  removeElement(element);

  lockDiscardedElementsList();
    element->next = discardedElementsList;
    discardedElementsList = element;
  unlockDiscardedElementsList();
}

static Element *
retrieveElement (void) {
  Element *element;

  lockDiscardedElementsList();
    if ((element = discardedElementsList)) {
      discardedElementsList = element->next;
      element->next = NULL;
    }
  unlockDiscardedElementsList();

  return element;
}

static Element *
newElement (Queue *queue, void *item) {
  Element *element;

  if (!(element = retrieveElement())) {
    if (!(element = malloc(sizeof(*element)))) {
      logMallocError();
      return NULL;
    }

    element->previous = element->next = NULL;
  }

  addElement(queue, element);
  element->item = item;
  return element;
}

static void
linkFirstElement (Element *element) {
  element->queue->head = element->previous = element->next = element;
}

static void
linkAdditionalElement (Element *reference, Element *element) {
  element->next = reference;
  element->previous = reference->previous;
  element->next->previous = element;
  element->previous->next = element;
}

static void
unlinkElement (Element *element) {
  Queue *queue = element->queue;
  if (element == element->next) {
    queue->head = NULL;
  } else {
    if (element == queue->head) queue->head = element->next;
    element->next->previous = element->previous;
    element->previous->next = element->next;
  }
  element->previous = element->next = NULL;
}

void
deleteElement (Element *element) {
  unlinkElement(element);
  discardElement(element);
}

typedef struct {
  Queue *queue;
  void *item;
} FindReferenceElementData;

static int
findReferenceElement (const void *item, void *data) {
  const FindReferenceElementData *fre = data;

  return fre->queue->compareItems(fre->item, item, fre->queue->data);
}

static void
linkElement (Element *element) {
  Queue *queue = element->queue;

  if (queue->head) {
    Element *reference;
    int isNewHead = 0;

    if (queue->compareItems) {
      FindReferenceElementData fre = {
        .queue = queue,
        .item = element->item
      };

      if (!(reference = findElement(queue, findReferenceElement, &fre))) {
        reference = queue->head;
      } else if (reference == queue->head) {
        isNewHead = 1;
      }
    } else {
      reference = queue->head;
    }

    linkAdditionalElement(reference, element);
    if (isNewHead) queue->head = element;
  } else {
    linkFirstElement(element);
  }
}

Element *
enqueueItem (Queue *queue, void *item) {
  Element *element = newElement(queue, item);

  if (element) linkElement(element);
  return element;
}

void
requeueElement (Element *element) {
  unlinkElement(element);
  linkElement(element);
}

void
moveElement (Element *element, Queue *queue) {
  unlinkElement(element);
  removeElement(element);
  addElement(queue, element);
  linkElement(element);
}

void *
dequeueItem (Queue *queue) {
  void *item;
  Element *element;

  if (!(element = queue->head)) return NULL;
  item = element->item;
  element->item = NULL;

  deleteElement(element);
  return item;
}

Queue *
getElementQueue (const Element *element) {
  return element->queue;
}

int
getElementIdentifier (const Element *element) {
  return element->identifier;
}

void *
getElementItem (const Element *element) {
  return element->item;
}

static int queueInitialized = 0;

static void
exitQueue (void *data) {
  lockDiscardedElementsList();
    while (discardedElementsList) {
      Element *element = discardedElementsList;
      discardedElementsList = element->next;
      free(element);
    }
  unlockDiscardedElementsList();

  queueInitialized = 0;
}

Queue *
newQueue (ItemDeallocator *deallocateItem, ItemComparator *compareItems) {
  Queue *queue;<commit_msg>Queues should use our own locks (rather than a pthread mutex directly). (dm)<commit_after>/*
 * BRLTTY - A background process providing access to the console screen (when in
 *          text mode) for a blind person using a refreshable braille display.
 *
 * Copyright (C) 1995-2015 by The BRLTTY Developers.
 *
 * BRLTTY comes with ABSOLUTELY NO WARRANTY.
 *
 * This is free software, placed under the terms of the
 * GNU General Public License, as published by the Free Software
 * Foundation; either version 2 of the License, or (at your option) any
 * later version. Please see the file LICENSE-GPL for details.
 *
 * Web Page: http://mielke.cc/brltty/
 *
 * This software is maintained by <NAME> <<EMAIL>>.
 */

#include "prologue.h"

#include "log.h"
#include "queue.h"
#include "lock.h"
#include "program.h"

static Element *discardedElements = NULL;

static LockDescriptor *
getDiscardedElementsLock (void) {
  static LockDescriptor *lock = NULL;

  return getLockDescriptor(&lock);
}

static void
lockDiscardedElements (void) {
  obtainExclusiveLock(getDiscardedElementsLock());
}

static void
unlockDiscardedElements (void) {
  releaseLock(getDiscardedElementsLock());
}

struct QueueStruct {
  Element *head;
  unsigned int size;
  void *data;
  ItemDeallocator *deallocateItem;
  ItemComparator *compareItems;
};

struct ElementStruct {
  Element *next;
  Element *previous;
  Queue *queue;
  int identifier;
  void *item;
};

static void
addElement (Queue *queue, Element *element) {
  {
    static int identifier = 0;
    element->identifier = ++identifier;
  }

  element->queue = queue;
  queue->size += 1;
}

static void
removeElement (Element *element) {
  element->queue->size -= 1;
  element->queue = NULL;
  element->identifier = 0;
}

static void
removeItem (Element *element) {
  if (element->item) {
    Queue *queue = element->queue;
    ItemDeallocator *deallocateItem = queue->deallocateItem;

    if (deallocateItem) deallocateItem(element->item, queue->data);
    element->item = NULL;
  }
}

static void
discardElement (Element *element) {
  removeItem(element);
  removeElement(element);

  lockDiscardedElements();
    element->next = discardedElements;
    discardedElements = element;
  unlockDiscardedElements();
}

static Element *
retrieveElement (void) {
  Element *element;

  lockDiscardedElements();
    if ((element = discardedElements)) {
      discardedElements = element->next;
      element->next = NULL;
    }
  unlockDiscardedElements();

  return element;
}

static Element *
newElement (Queue *queue, void *item) {
  Element *element;

  if (!(element = retrieveElement())) {
    if (!(element = malloc(sizeof(*element)))) {
      logMallocError();
      return NULL;
    }

    element->previous = element->next = NULL;
  }

  addElement(queue, element);
  element->item = item;
  return element;
}

static void
linkFirstElement (Element *element) {
  element->queue->head = element->previous = element->next = element;
}

static void
linkAdditionalElement (Element *reference, Element *element) {
  element->next = reference;
  element->previous = reference->previous;
  element->next->previous = element;
  element->previous->next = element;
}

static void
unlinkElement (Element *element) {
  Queue *queue = element->queue;
  if (element == element->next) {
    queue->head = NULL;
  } else {
    if (element == queue->head) queue->head = element->next;
    element->next->previous = element->previous;
    element->previous->next = element->next;
  }
  element->previous = element->next = NULL;
}

void
deleteElement (Element *element) {
  unlinkElement(element);
  discardElement(element);
}

typedef struct {
  Queue *queue;
  void *item;
} FindReferenceElementData;

static int
findReferenceElement (const void *item, void *data) {
  const FindReferenceElementData *fre = data;

  return fre->queue->compareItems(fre->item, item, fre->queue->data);
}

static void
linkElement (Element *element) {
  Queue *queue = element->queue;

  if (queue->head) {
    Element *reference;
    int isNewHead = 0;

    if (queue->compareItems) {
      FindReferenceElementData fre = {
        .queue = queue,
        .item = element->item
      };

      if (!(reference = findElement(queue, findReferenceElement, &fre))) {
        reference = queue->head;
      } else if (reference == queue->head) {
        isNewHead = 1;
      }
    } else {
      reference = queue->head;
    }

    linkAdditionalElement(reference, element);
    if (isNewHead) queue->head = element;
  } else {
    linkFirstElement(element);
  }
}

Element *
enqueueItem (Queue *queue, void *item) {
  Element *element = newElement(queue, item);

  if (element) linkElement(element);
  return element;
}

void
requeueElement (Element *element) {
  unlinkElement(element);
  linkElement(element);
}

void
moveElement (Element *element, Queue *queue) {
  unlinkElement(element);
  removeElement(element);
  addElement(queue, element);
  linkElement(element);
}

void *
dequeueItem (Queue *queue) {
  void *item;
  Element *element;

  if (!(element = queue->head)) return NULL;
  item = element->item;
  element->item = NULL;

  deleteElement(element);
  return item;
}

Queue *
getElementQueue (const Element *element) {
  return element->queue;
}

int
getElementIdentifier (const Element *element) {
  return element->identifier;
}

void *
getElementItem (const Element *element) {
  return element->item;
}

static int queueInitialized = 0;

static void
exitQueue (void *data) {
  lockDiscardedElements();
    while (discardedElements) {
      Element *element = discardedElements;
      discardedElements = element->next;
      free(element);
    }
  unlockDiscardedElements();

  queueInitialized = 0;
}

Queue *
newQueue (ItemDeallocator *deallocateItem, ItemComparator *compareItems) {
  Queue *queue;
{'fraction_non_alphanumeric': 0.1177922184749527, 'fraction_numerical': 0.0028789997532285925, 'mean_word_length': 3.9624489795918367, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 137, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '59643', 'n_tokens_mistral': 3762, 'n_tokens_neox': 3626, 'n_words': 1016}