Anonymous avatar Anonymous committed 86b0f89

Added the pthread_fcfs_rwlock 0.4.0 distribution. Some essential autoconf
files may be missing.

Comments (0)

Files changed (21)

+Relax, this is not the GPL.
+
+The license is in fact Public Domain as long as it is made clear that whoever
+wrote this code is not responsible for any damages it may cause.
+
+

pthreads/ChangeLog

+From 0.3.4 to 0.3.5:
+--------------------
+
+* Made test_rwlock an uninstalled binary.
+
+From 0.3.3 to 0.3.4:
+--------------------
+
+* Added the RLE Scheme to the distro.
+
+From 0.3.2 to 0.3.3:
+--------------------
+
+* Removed trailing whitespace.
+
+* Now mydebug just prints one line. (the more verbose debugging is #if'd
+out).
+
+* Changed mydebug to my_debug_print.
+
+* Changed the debug-less my_debug_print to { }. (so if (cond) my_debug_print()
+will work OK)
+
+From 0.3.1 to 0.3.2:
+--------------------
+
+* Now Removing queue junk at gain_read_generic.
+
+From 0.3.0 to 0.3.1:
+--------------------
+
+* Added a mydebug directive.
+
+* Printed the state of the queue and the rwlock.
+
+* Added another extract_first_non_disabled_item() at the end of 
+accept_pending_items().
+
+* The RWLock seems to work OK according to the dumps.
+
+From 0.2.0 to 0.3.0:
+--------------------
+
+* Changed the name of queue_poll to queue_peak.
+
+* Added queue_peak.
+
+* Removed a few redundant externs from queue.c
+
+* Changed the RWLock to RLE. Looks good, but I think accept_pending_items()
+need a little rework.
+
+* Re-worked accept_pending_items() - looks good.
+
+
+From 0.0.11 to 0.2.0:
+---------------------
+
+* Added an HTML page.
+
+* Put some meat in README.
+
+* Changed the version number to 0.2.0.
+
+* Added the man_MANs to EXTRA_DIST in man/Makefile.am so they will be
+included in the distribution.
+
+From 0.0.10 to 0.0.11:
+----------------------
+
+* Added an assert for num_readers > 0 in release().
+
+From 0.0.9 to 0.0.10:
+---------------------
+
+* Placed the man page in its own directory ($DIST/man).
+
+* Created man links to it.
+
+* Combined release_read() and release_write() into release().
+
+* Added a "Want Lock" debug message in gain_write()
+
+* Modified the man pages to reflect the release() change.
+
+From 0.0.8 to 0.0.9:
+--------------------
+
+* Added a man page. It is written in Perl POD and was spell checked.
+
+From 0.0.7 to 0.0.8:
+--------------------
+
+* Added some descriptive comments to pthread/rwlock_fcfs.h
+
+
+

pthreads/Docs/FCFS_RWLock_Scheme.txt

+The RWLock will use a queue. Each element of the queue will contain
+a condition variable and a flag that indicates if it contains a reader
+or a writer pending. 
+
+The RWLock will contain a counter that tells it how many readers are using 
+it at the moment (num_readers), and a flag that specifies if there's a 
+writer using the lock (is_writer). It also uses a common internal mutex 
+to protect against mutual exclusion (mymutex)
+
+Algorithm:
+
+accept_pending_items:
+---------------------
+
+Extracts the first element out of the queue. 
+
+If it is a writer, it sets is_writer to 1, and signals the condition 
+variable of the element.
+
+If it is a reader, it sets is_writer to 0, and polls+extracts 
+all the other items out of the head of the queue that are readers 
+(i.e it stops at the first writer or at the end of the queue).
+
+get_write_access:
+-----------------
+
+locks mymutex.
+
+Checks if is_writer is set or num_readers is greater than 0. If so, 
+it enqueues itself. (the mutex of the condition variable is mymutex)
+
+If not it sets is_writer to 1.
+
+Unlocks the mutex.
+
+
+
+get_read_access:
+----------------
+
+locks mymutex.
+
+If the queue is empty and is_writer is false it increments num_readers and unlock mutex.
+
+Else it enqueues itself, while using mymutex for waiting on the condition variable. When the condition variable is signalled, num_readers is incremented by 1.
+
+Unlocks mutex.
+
+release_write_access:
+---------------------
+
+locks mutex
+
+Sets is_writer to false. Then calls accept_pending_items.
+
+unlocks mutex
+
+release_read_access:
+--------------------
+
+locks mutex
+
+Decrements num_readers. If num_readers == 0 it calls accept_pending_items.
+
+unlocks mutex
+

pthreads/Docs/FCFS_RWLock_Scheme_RLE.txt

+Data Structures:
+================
+
+The RWLock will use a queue. Each element of the queue will contain:
+1. a condition variable 
+2. a flag that indicates if it contains readers or writers pending. 
+3. num_threads - an integer specifiying how many threads are waiting on it.
+4. was_first_thr_accepted - a flag that indicates if the first thread has
+already been accepted from it. (used only for a writers' pack).
+
+The RWLock will contain a counter that tells it how many readers are using 
+it at the moment (num_readers), and a flag that specifies if there's a 
+writer using the lock (is_writer). It also uses a common internal mutex 
+to protect against mutual exclusion (mymutex)
+
+Algorithm:
+==========
+
+accept_pending_items:
+---------------------
+
+Peek the first element out of the queue. 
+
+If it is a writers' pack, it decrements the number of threads by one, 
+and signals the condition variable, and sets was_first_thr_accepted to 1. 
+Afterwards, if (elem.num_threads == 0) it extracts and destroys the item.
+
+If it is a readers' pack, it broadcasts the condition variable. Then it
+extracts and destroys the item.
+
+get_write_access:
+-----------------
+
+locks mymutex.
+
+Checks if is_writer is set or num_readers is greater than 0. If so, 
+it enqueues itself. (the mutex of the condition variable is mymutex)
+
+If not it sets is_writer to 1.
+
+    Enqueuing: 
+    
+    peek the tail of the queue. If it is a writers' pack and
+    its was_first_thr_accepted is false, increase the number of threads 
+    there by 1 and wait on its condition variable. If not, enqueue a new 
+    writer's pack with a threads_num set to 1 and a new condition variable.
+
+
+Unlocks the mutex.
+
+
+get_read_access:
+----------------
+
+locks mymutex.
+
+If the queue is empty and is_writer is false it increments num_readers 
+and unlocks mutex.
+
+Else it enqueues itself, while using mymutex for waiting on the 
+condition variable. When the condition variable is signalled, 
+num_readers is incremented by 1.
+
+    Enqueueing: 
+    
+    peek the tail of the queue. If it is a readers' pack, 
+    increase the number of threads there by 1 and wait on its 
+    condition variable. If not, add a new readers pack with threads_num 
+    set to 1 and a new condition variable, which it will wait upon.
+
+Unlocks mutex.
+
+
+
+release_write_access:
+---------------------
+
+locks mutex
+
+Sets is_writer to false. Then calls accept_pending_items.
+
+unlocks mutex
+
+release_read_access:
+--------------------
+
+locks mutex
+
+Decrements num_readers. If num_readers == 0 it calls accept_pending_items.
+
+unlocks mutex
+
+./configure
+make
+make install

pthreads/Makefile.am

+SUBDIRS = man
+
+noinst_PROGRAMS = test_rwlock
+test_rwlock_SOURCES = test_rwlock.c
+test_rwlock_LDADD = libpthread_rwlock_fcfs.la
+
+lib_LTLIBRARIES = libpthread_rwlock_fcfs.la
+libpthread_rwlock_fcfsincludedir=$(includedir)/pthread
+libpthread_rwlock_fcfs_la_SOURCES = rwlock.c queue.c
+libpthread_rwlock_fcfs_la_LDFLAGS = -version-info 0:0:0
+libpthread_rwlock_fcfsinclude_HEADERS = rwlock_fcfs.h rwlock_fcfs_queue.h
+
+EXTRA_DIST += Docs/FCFS_RWLock_Scheme.txt Docs/FCFS_RWLock_Scheme_RLE.txt
+EXTRA_DIST += test_rwlock.c 
+EXTRA_DIST += test_queue.cpp
+
+EXTRA_DIST += pthread/rwlock_fcfs.h pthread/rwlock_fcfs_queue.h
+
+EXTRA_DIST += TODO
+
+

Empty file added.

+This a First-Come First-Served Readers/Writers Lock Implementation for
+POSIX Threads.
+
+For installation information consult the file "INSTALL".
+
+For information on how to use it consult the man page 
+("man/pthread_rwlock_fcfs.3thr"), its HTML version
+("man/pthread_rwlock_fcfs.html") or the file "test_rwlock.c".
+
+The FCFS RWLock Homepage is:
+
+http://vipe.technion.ac.il/~shlomif/rwlock/
+
+Enjoy!
+
+Wish List:
+----------
+
+* Port to ZThread, ACE, Win32 API, gthread, Apache's Portable Run-Time,
+Netscape Portable Run-Time, etc. 
+
+* Prepare an RPM SPEC.

pthreads/configure.in

+dnl Process this file with autoconf to produce a configure script.
+AC_INIT(rwlock.c)
+
+AM_INIT_AUTOMAKE(pthread_rwlock_fcfs, 0.4.0)
+
+AM_PROG_LIBTOOL
+
+dnl Checks for programs.
+AC_PROG_CC
+
+
+dnl Checks for libraries.
+dnl Replace `main' with a function in -lpthread:
+AC_CHECK_LIB(pthread, main)
+
+dnl Checks for header files.
+AC_HEADER_STDC
+AC_CHECK_HEADERS(sys/time.h unistd.h)
+
+debug_rwlock=no
+
+AC_ARG_ENABLE(debug-rwlock,
+ [  --enable-debug-rwlock  Enable an RWLock that prints debug notices on the screen. This is a debugging feature which should not be usually enabled],
+ [ debug_rwlock=yes
+ ])
+
+if test "x$debug_rwlock" = "xyes" ; then
+    AC_DEFINE(PTHREAD_RWLOCK_FCFS_DEBUG)
+fi
+
+dnl Checks for typedefs, structures, and compiler characteristics.
+AC_C_CONST
+AC_HEADER_TIME
+
+dnl Checks for library functions.
+AC_CHECK_FUNCS(gettimeofday)
+
+AC_OUTPUT([Makefile man/Makefile])

pthreads/man/Makefile.am

+man_MANS = pthread_rwlock_fcfs.3thr  \
+    pthread_rwlock_fcfs_alloc.3thr \
+    pthread_rwlock_fcfs_timed_gain_read.3thr \
+    pthread_rwlock_fcfs_timed_gain_write.3thr \
+    pthread_rwlock_fcfs_try_gain_read.3thr \
+    pthread_rwlock_fcfs_try_gain_write.3thr \
+    pthread_rwlock_fcfs_gain_read.3thr \
+    pthread_rwlock_fcfs_gain_write.3thr \
+    pthread_rwlock_fcfs_release.3thr \
+    pthread_rwlock_fcfs_destroy.3thr
+
+dist_targets += pthread_rwlock_fcfs.html
+
+dist-hook: $(dist_targets)
+
+PODPARAMS=--section=3thr --center="fcfs rwlock" --date="2002/01/02" --release="fcfs rwlock 0.2.0"
+
+pthread_rwlock_fcfs.html: pthread_rwlock_fcfs.pod
+	pod2html --noindex --netscape --title="A First-Come First Served Readers/Writers Lock for POSIX Threads" $< > $@
+
+pthread_rwlock_fcfs.3thr: pthread_rwlock_fcfs.pod
+	pod2man $(PODPARAMS) $< > $@
+
+EXTRA_DIST += $(man_MANS)
+EXTRA_DIST += pthread_rwlock_fcfs.pod create_man_links.sh pthread_rwlock_fcfs.html

pthreads/man/create_man_links.sh

+#!/bin/bash
+PREFIX=pthread_rwlock_fcfs
+for I in alloc {timed_,try_,}gain_{'read',write} release destroy ; do
+    echo ".so man3/${PREFIX}.3thr" > ${PREFIX}_$I.3thr
+    echo "    ${PREFIX}_$I.3thr \\"
+done
+

pthreads/man/pthread_rwlock_fcfs.pod

+=pod
+
+=head1 NAME
+
+pthread_rwlock_fcfs_alloc, 
+pthread_rwlock_fcfs_gain_read, pthread_rwlock_gain_write, 
+pthread_rwlock_fcfs_timed_gain_read, pthread_rwlock_fcfs_timed_gain_write,
+pthread_rwlock_fcfs_try_gain_read, pthread_rwlock_fcfs_try_gain_write,
+pthread_rwlock_fcfs_release,
+pthread_rwlock_fcfs_destroy - operations on a first-come first-served 
+readers/writers lock.
+
+
+=head1 SYNOPSIS
+
+B<#include E<lt>pthread/rwlock_fcfs.hE<gt>>
+
+B<pthread_rwlock_fcfs_t> * I<rwlock> = B<pthread_rwlock_fcfs_alloc>();
+
+B<void> B<pthread_rwlock_fcfs_gain_read>(B<pthread_rwlock_fcfs_t> * I<rwlock>);
+
+B<void> B<pthread_rwlock_fcfs_gain_write>(B<pthread_rwlock_fcfs_t> * I<rwlock>);
+
+B<void> B<pthread_rwlock_fcfs_try_gain_read>(B<pthread_rwlock_fcfs_t> * I<rwlock>);
+
+B<void> B<pthread_rwlock_fcfs_try_gain_write>(B<pthread_rwlock_fcfs_t> * I<rwlock>);
+
+B<int> B<pthread_rwlock_fcfs_timed_gain_read>(B<pthread_rwlock_fcfs_t> * I<rwlock>, B<const struct timespec> * I<abstime>, B<int> (*I<continue_callback>)(B<void> * context), B<void> * I<context>);
+
+B<int> B<pthread_rwlock_fcfs_timed_gain_write>(B<pthread_rwlock_fcfs_t> * I<rwlock>, B<const struct timespec> * I<abstime>, B<int> (*I<continue_callback>)(B<void> * context), B<void> * I<context>);
+
+B<void> B<pthread_rwlock_fcfs_release>(B<pthread_rwlock_fcfs_t> * I<rwlock>);
+
+B<void> B<pthread_rwlock_fcfs_destroy>(B<pthread_rwlock_fcfs_t> * I<rwlock>);
+
+=head1 DESCRIPTION
+
+A Readers/Writers Lock (or "rwlock" for short) is a mechanism that allows an 
+arbitrary number of readers, or alternatively one and only one writer to 
+access a resource at a given time. A First-Come First-Served RWLock makes sure
+every pending thread will get its turn eventually.
+
+To create a new rwlock call B<pthread_rwlock_fcfs_alloc>(). From then on, more
+than one thread can use the lock simultaneously.
+
+B<pthread_rwlock_fcfs_gain_read> and B<pthread_rwlock_fcfs_gain_write> can be
+used to gain read or write access for I<rwlock>. They block indefinitely until
+the access is granted.
+
+B<pthread_rwlock_fcfs_try_gain_read> and B<pthread_rwlock_fcfs_try_gain_write>
+attempt to gain a read or write permission and if they do not succeed they 
+exit immediately. They return 0 upon success and non-zero otherwise.
+
+B<pthread_rwlock_fcfs_timed_gain_read> and B<pthread_rwlock_fcfs_timed_gain_write> 
+attempt to gain a permission while initially waiting until I<abstime>. If by 
+that time access is not granted, then I<continue_callback> will be called to 
+find out if the functions should continue waiting.
+
+I<continue_callback> is responsible for setting a new value for I<abstime> and
+should return 1 if it wishes to continue wait for a permission or 0 otherwise. 
+I<callback_context> is the argument which it receives as an argument.
+
+If I<continue_callback> is set to NULL, then it will be ignored, and the 
+function will terminate once the initial wait is over. 
+
+B<pthread_rwlock_fcfs_timed_gain_read> and B<pthread_rwlock_fcfs_timed_gain_write> 
+return 0 upon success and 1 if they failed to gain a read or write permission.
+
+B<pthread_rwlock_fcfs_release> releases a previously granted 
+read or write permission.
+
+B<pthread_rwlock_fcfs_destroy> can be used to destroy a previously allocated
+I<rwlock>.
+
+=head1 ASYNC-SIGNAL SAFETY
+
+These RWLock functions are not async-signal safe, and should not be called
+from a signal handler.
+
+=head1 RETURN VALUE
+
+All condition variable functions return 0 on success and a non-zero error
+code on error.
+
+=head1 AUTHOR
+
+Shlomi Fish E<lt>shlomif@vipe.technion.ac.ilE<gt>.
+
+=head1 EXAMPLE
+
+See the F<test_rwlock.c> file inside the pthreads' FCFS RWLock distribution.
+
+=cut

pthreads/pthread/rwlock_fcfs.h

+#ifndef __PTHREAD_RWLOCK_FCFS_H
+#define __PTHREAD_RWLOCK_FCFS_H
+
+#include <pthread.h>
+
+#include <pthread/rwlock_fcfs_queue.h>
+
+/* This is the struct that is pointed to by the elements of the queue of
+ * the FCFS RWLock 
+ * */
+struct pthread_rwlock_fcfs_item_struct
+{
+    /* A condition variable to wake up the threads that waits upon this item */
+    pthread_cond_t cond;
+    /* A flag that specifies if it's a reader or a writer */
+    int is_writer;
+    /* A flag that disables this item */
+    int is_disabled;
+    /* An integer specifiying how many threads are waiting on it */
+    int num_threads;
+    /* A flag that indicates if the first thread in the pack has already
+     * been accepted. (Used only for a writers' pack */
+    int was_first_thr_accepted;
+};
+
+typedef struct pthread_rwlock_fcfs_item_struct pthread_rwlock_fcfs_item_t;
+
+/* The RWLock Struct */
+struct pthread_rwlock_fcfs_struct
+{
+    /* The queue that will be managed */
+    pthread_rwlock_fcfs_queue_t * queue;
+    /* The number of readers that are using the RWLock at the moment */
+    int num_readers;
+    /* Specifies if there is a writer locking the RWLock */
+    int is_writer;
+    /* A mutex to make sure no two threads _modify_ the RWLock struct
+     * at the moment */
+    pthread_mutex_t mutex;
+
+    /* A flag that indicates that no new threads should be accepted */
+    int is_destroyed;
+};
+
+typedef struct pthread_rwlock_fcfs_struct pthread_rwlock_fcfs_t;
+
+/************** Functions ***********/
+
+#ifdef PTHREAD_RWLOCK_FCFS_DEBUG
+#define PTHREAD_RWLOCK_FCFS_DEBUG_ARGS , char * id
+#define PTHREAD_RWLOCK_FCFS_DEBUG_CALL_ARGS , id
+#else
+#define PTHREAD_RWLOCK_FCFS_DEBUG_ARGS 
+#define PTHREAD_RWLOCK_FCFS_DEBUG_CALL_ARGS 
+#endif
+
+/* 
+ * Allocate a new FCFS RWLock
+ * */
+extern pthread_rwlock_fcfs_t * pthread_rwlock_fcfs_alloc(void);
+
+/*
+ * Wait indefinitely until a read access to the lock is granted.
+ * */
+extern void pthread_rwlock_fcfs_gain_read(pthread_rwlock_fcfs_t * rwlock PTHREAD_RWLOCK_FCFS_DEBUG_ARGS);
+
+/*
+ * Wait indefinitely until a write access to the lock is granted.
+ * */
+extern void pthread_rwlock_fcfs_gain_write(pthread_rwlock_fcfs_t * rwlock PTHREAD_RWLOCK_FCFS_DEBUG_ARGS);
+
+/*
+ * Release a previously gained read or write access
+ * */
+extern void pthread_rwlock_fcfs_release(pthread_rwlock_fcfs_t * rwlock PTHREAD_RWLOCK_FCFS_DEBUG_ARGS);
+
+/* 
+ * Destroy the RWLock
+ * */
+extern void pthread_rwlock_fcfs_destroy(pthread_rwlock_fcfs_t * rwlock);
+
+/*
+ * Wait until a certain time (abstime) to get a read access. If it is 
+ * not given, continue_callback is called and asks whether to continue 
+ * or not. 
+ * 
+ * If it wishes to continue, it is responsible for setting the new abstime.
+ *
+ * context is the context variable for continue_callback
+ * 
+ * */
+extern int pthread_rwlock_fcfs_timed_gain_read(
+        pthread_rwlock_fcfs_t * rwlock,
+        const struct timespec * abstime,
+        int (*continue_callback)(void * context),
+        void * context
+        PTHREAD_RWLOCK_FCFS_DEBUG_ARGS
+        );
+
+/*
+ * Wait until a certain time (abstime) to get a write access. If it is not 
+ * given, continue_callback is called and asks whether to continue or not. 
+ * 
+ * If it wishes to continue, it is responsible for setting the new abstime.
+ *
+ * context is the context variable for continue_callback
+ * 
+ * */
+extern int pthread_rwlock_fcfs_timed_gain_write(
+        pthread_rwlock_fcfs_t * rwlock,
+        const struct timespec * abstime,
+        int (*continue_callback)(void * context),
+        void * context
+        PTHREAD_RWLOCK_FCFS_DEBUG_ARGS
+        );
+
+/* 
+ * Attempt to gain a read access. If it is not given immidiately it returns an
+ * error code other than 0.
+ *
+ * Else, it returns 0
+ * */
+extern int pthread_rwlock_fcfs_try_gain_read(pthread_rwlock_fcfs_t * rwlock PTHREAD_RWLOCK_FCFS_DEBUG_ARGS);
+
+
+/* 
+ * Attempt to gain a write access. If it is not given immidiately it returns an
+ * error code other than 0.
+ *
+ * Else, it returns 0
+ * */
+extern int pthread_rwlock_fcfs_try_gain_write(pthread_rwlock_fcfs_t * rwlock PTHREAD_RWLOCK_FCFS_DEBUG_ARGS);
+
+    
+#endif /* #ifndef __PTHREAD_RWLOCK_FCFS_H */
+
+

pthreads/pthread/rwlock_fcfs_queue.h

+
+
+#ifndef __PTHREAD_RWLOCK_FCFS_QUEUE_H
+#define __PTHREAD_RWLOCK_FCFS_QUEUE_H
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#define IP_NOISE_MESSAGE_BUFSIZE 0x20000
+
+#ifndef __KERNEL__
+
+struct pthread_rwlock_fcfs_queue_item_struct
+{
+    void * data;
+    struct pthread_rwlock_fcfs_queue_item_struct * next;
+};
+
+typedef struct pthread_rwlock_fcfs_queue_item_struct pthread_rwlock_fcfs_queue_item_t;
+
+struct pthread_rwlock_fcfs_queue_struct
+{
+    pthread_rwlock_fcfs_queue_item_t * head;
+    pthread_rwlock_fcfs_queue_item_t * tail;
+
+    int num_msgs;
+};
+
+typedef struct pthread_rwlock_fcfs_queue_struct pthread_rwlock_fcfs_queue_t;
+
+extern pthread_rwlock_fcfs_queue_t * pthread_rwlock_fcfs_queue_alloc(void);
+
+extern void pthread_rwlock_fcfs_queue_destroy(pthread_rwlock_fcfs_queue_t * queue);
+
+extern void * pthread_rwlock_fcfs_queue_dequeue(pthread_rwlock_fcfs_queue_t * queue);
+
+extern void * pthread_rwlock_fcfs_queue_peak(pthread_rwlock_fcfs_queue_t * queue);
+
+extern void pthread_rwlock_fcfs_queue_enqueue(pthread_rwlock_fcfs_queue_t * queue, void * msg);
+
+extern int pthread_rwlock_fcfs_queue_is_empty(pthread_rwlock_fcfs_queue_t * queue);
+
+extern void * pthread_rwlock_fcfs_queue_peak_tail(pthread_rwlock_fcfs_queue_t * queue);
+
+
+#endif
+
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* #ifndef __PTHREAD_RWLOCK_FCFS_QUEUE_H */ 
+
+/*
+ * queue.c
+ * 
+ * This module implements a queue
+ *
+ * */
+
+
+#include <stdio.h>
+#include <stdlib.h>
+
+#include <pthread/rwlock_fcfs_queue.h>
+
+#ifdef DMALLOC
+#include "dmalloc.h"
+#endif
+
+pthread_rwlock_fcfs_queue_t * pthread_rwlock_fcfs_queue_alloc(void)
+{
+    pthread_rwlock_fcfs_queue_t * ret;
+
+    ret = malloc(sizeof(pthread_rwlock_fcfs_queue_t));
+
+    ret->head = NULL;
+    ret->tail = NULL;
+
+    ret->num_msgs = 0;
+
+    return ret;
+}
+
+void pthread_rwlock_fcfs_queue_destroy(pthread_rwlock_fcfs_queue_t * queue)
+{
+    free(queue);
+}
+
+void * pthread_rwlock_fcfs_queue_dequeue(pthread_rwlock_fcfs_queue_t * queue)
+{
+    pthread_rwlock_fcfs_queue_item_t * ret;
+    void * void_ret;
+    
+    /* If there are no messages present in the queue */
+    if (queue->head == NULL)
+    {
+        return NULL;
+    }
+    
+    /* Retrieve the first element */
+    ret = queue->head;
+    /* Remove it from the list */
+    queue->head = ret->next;
+    /* Mark this list as empty if it is indeed so */
+    if (queue->head == NULL)
+    {
+        queue->tail = NULL;
+    }
+
+    queue->num_msgs--;
+
+    void_ret = ret->data;
+    free(ret);
+    
+    return void_ret;
+}
+
+void * pthread_rwlock_fcfs_queue_peak(pthread_rwlock_fcfs_queue_t * queue)
+{
+    pthread_rwlock_fcfs_queue_item_t * ret;
+    void * void_ret;
+    
+    /* If there are no messages present in the queue */
+    if (queue->head == NULL)
+    {
+        return NULL;
+    }
+    
+    /* Retrieve the first element */
+    ret = queue->head;
+
+    void_ret = ret->data;
+    
+    return void_ret;
+}
+
+
+void pthread_rwlock_fcfs_queue_enqueue(pthread_rwlock_fcfs_queue_t * queue, void * msg)
+{
+    pthread_rwlock_fcfs_queue_item_t * msg_with_next;
+
+    msg_with_next = malloc(sizeof(pthread_rwlock_fcfs_queue_item_t));
+
+    msg_with_next->data = msg;
+
+    if (queue->tail == NULL)
+    {                
+        queue->head = queue->tail = msg_with_next;
+        msg_with_next->next = NULL;
+    }
+    else
+    {
+        /* Append this message to the end of the linked list */
+        queue->tail->next = msg_with_next;
+        /* Mark it as the end */
+        queue->tail = msg_with_next;
+        /* Signify that it is not connected to anything */
+        msg_with_next->next = NULL;
+    }
+
+    queue->num_msgs++;
+}
+
+int pthread_rwlock_fcfs_queue_is_empty(pthread_rwlock_fcfs_queue_t * queue)
+{
+    return (queue->head == NULL);
+}
+
+void * pthread_rwlock_fcfs_queue_peak_tail(pthread_rwlock_fcfs_queue_t * queue)
+{
+    pthread_rwlock_fcfs_queue_item_t * ret;
+    void * void_ret;
+    
+    /* If there are no messages present in the queue */
+    if (queue->tail == NULL)
+    {
+        return NULL;
+    }
+    
+    /* Retrieve the first element */
+    ret = queue->tail;
+
+    void_ret = ret->data;
+    
+    return void_ret;
+}
+
+
+
+

pthreads/rwlock.c

+#include <stdlib.h>
+#include <pthread.h>
+#include <errno.h>
+#include <stdio.h>
+#include <assert.h>
+
+#include <pthread/rwlock_fcfs.h>
+
+#ifdef DMALLOC
+#include <dmalloc.h>
+#endif
+
+static const pthread_mutex_t initial_mutex_constant = PTHREAD_MUTEX_INITIALIZER;
+static const pthread_cond_t initial_cond_constant = PTHREAD_COND_INITIALIZER;
+
+#ifdef PTHREAD_RWLOCK_FCFS_DEBUG
+#if 0
+static void my_debug_print(pthread_rwlock_fcfs_t * rwlock, char * id, char * msg)
+{
+    printf("%s - %s\n", id, msg);
+    printf("    Status: rwlock.num_readers == %i\n", rwlock->num_readers);
+    printf("    Status: rwlock.is_writer == %i\n", rwlock->is_writer);
+    {
+        int a;
+        pthread_rwlock_fcfs_queue_item_t * q_item;
+        pthread_rwlock_fcfs_item_t * data;
+
+        q_item = rwlock->queue->head;
+        a = 0;
+        while(q_item != rwlock->queue->tail)
+        {
+            data = (pthread_rwlock_fcfs_item_t *)q_item->data;
+            printf("    Status: Item %i: is_writer=%i\n", a, data->is_writer);
+            printf("    Status: Item %i: num_threads=%i\n", a, data->num_threads);
+            printf("    Status: Item %i: was_first_thr_accepted=%i\n", a, data->was_first_thr_accepted);
+
+            q_item = q_item->next;
+            a++;
+        }
+        if (q_item != NULL)
+        {
+            data = (pthread_rwlock_fcfs_item_t *)q_item->data;
+            printf("    Status: Item %i: is_writer=%i\n", a, data->is_writer);
+            printf("    Status: Item %i: num_threads=%i\n", a, data->num_threads);
+            printf("    Status: Item %i: was_first_thr_accepted=%i\n", a, data->was_first_thr_accepted);
+        }
+    }
+}
+#else
+#define my_debug_print(rwlock,id,msg) { printf("%s - %s\n", id, msg); }
+#endif
+#else
+#define my_debug_print(rwlock, id, msg) { }
+#endif
+
+pthread_rwlock_fcfs_t * pthread_rwlock_fcfs_alloc(void)
+{
+    pthread_rwlock_fcfs_t * rwlock;
+
+    rwlock = malloc(sizeof(pthread_rwlock_fcfs_t));
+
+    rwlock->queue = pthread_rwlock_fcfs_queue_alloc();
+
+    /* We don't have any readers now. */
+    rwlock->num_readers = 0;
+    /* Much less a writer */
+    rwlock->is_writer = 0;
+    /* This RWLock is alive and kicking */
+    rwlock->is_destroyed = 0;
+
+    /* Initialize the mutex */
+    rwlock->mutex = initial_mutex_constant;
+    pthread_mutex_init(&(rwlock->mutex), NULL);
+
+    return rwlock;
+}
+
+static int gain_write_generic(
+    pthread_rwlock_fcfs_t * rwlock,
+    int wait_for_access,
+    int is_timed,
+    const struct timespec * abstime,
+    int (*continue_callback)(void * context),
+    void * context
+    )
+{
+    /* If there aren't any readers or writers in the queue we
+     * can gain access immidiately */
+    if (rwlock->is_writer || (rwlock->num_readers > 0))
+    {
+        pthread_rwlock_fcfs_item_t * item;
+
+        if (! wait_for_access)
+        {
+            return 1;
+        }
+
+        item = (pthread_rwlock_fcfs_item_t *)pthread_rwlock_fcfs_queue_peak_tail(rwlock->queue);
+        if (
+                /* The queue is not empty */
+                (item != NULL) &&
+                /* It is a writers' pack */
+                item->is_writer &&
+                /* The first thread was not yet accepted from it */
+                (! item->was_first_thr_accepted)
+           )
+        {
+            item->num_threads++;
+        }
+        else
+        {
+
+            /* Someone is using the RWLock. Let's enqueue myself */
+            item = malloc(sizeof(pthread_rwlock_fcfs_item_t));
+            /* We are a writer, so let's designate ourselves as such */
+            item->is_writer = 1;
+
+            /* We want to gain access to the lock */
+            item->is_disabled = 0;
+
+            /* We created a new pack in which there's one thread */
+            item->num_threads = 1;
+
+            /* This is a new pack, so no threads were accepted yet. */
+            item->was_first_thr_accepted = 0;
+
+            /* Initialize the condition variable */
+            item->cond = initial_cond_constant;
+
+            pthread_cond_init(&(item->cond), NULL);
+
+            /* Let's put ourselves in the queue, so we will be release
+             * when necessary. */
+            pthread_rwlock_fcfs_queue_enqueue(rwlock->queue, item);
+
+        }
+
+
+        /* Wait upon the condition variable to gain access to the rwlock */
+        if (! is_timed)
+        {
+            pthread_cond_wait(&(item->cond), &(rwlock->mutex));
+        }
+        else
+        {
+            int ret;
+
+            /*
+             * We try to get a timed wait on cond. If it times-out, we ask
+             * the user if he wishes to continue.
+             */
+            do
+            {
+                ret = pthread_cond_timedwait(&(item->cond), &(rwlock->mutex), abstime);
+            } while
+                (
+                    (ret == ETIMEDOUT) &&
+                    (continue_callback != NULL) &&
+                    continue_callback(context)
+                );
+
+            /* We failed for some reason (probably a time out - let's disable
+             * this item, so it won't be processed.
+             * */
+            if (ret != 0)
+            {
+                item->num_threads--;
+                return ret;
+            }
+        }
+
+        /* Now we have a write access */
+        rwlock->is_writer = 1;
+
+        return 0;
+    }
+    else
+    {
+        /* Mark the lock as such that contains a writer */
+        rwlock->is_writer = 1;
+
+        return 0;
+    }
+}
+
+
+void pthread_rwlock_fcfs_gain_write(pthread_rwlock_fcfs_t * rwlock PTHREAD_RWLOCK_FCFS_DEBUG_ARGS)
+{
+    pthread_mutex_lock(&(rwlock->mutex));
+
+    my_debug_print(rwlock, id, "Want Lock!");
+
+    gain_write_generic(rwlock, 1, 0, NULL, NULL, NULL);
+
+    my_debug_print(rwlock, id, "Lock!");
+
+    pthread_mutex_unlock(&(rwlock->mutex));
+}
+
+int pthread_rwlock_fcfs_try_gain_write(pthread_rwlock_fcfs_t * rwlock PTHREAD_RWLOCK_FCFS_DEBUG_ARGS)
+{
+    int ret;
+
+    pthread_mutex_lock(&(rwlock->mutex));
+
+    my_debug_print(rwlock, id, "Want Try Lock!");
+
+    ret = gain_write_generic(rwlock, 0, 0, NULL, NULL, NULL);
+
+    my_debug_print(rwlock, id, ((ret == 0)? "Lock!" : "Failed Lock!"));
+
+    pthread_mutex_unlock(&(rwlock->mutex));
+
+    return ret;
+}
+
+
+/* This macro dequeues and frees a queue element */
+#define dequeue_and_destroy_item() \
+    {         \
+        pthread_cond_destroy(&(item->cond)); \
+        free(item);     \
+        pthread_rwlock_fcfs_queue_dequeue(rwlock->queue); \
+    }
+
+#define extract_first_non_disabled_item() \
+    {     \
+        /*       \
+         * This loop extracts items from the queue until it encounters a  \
+         * non-disabled item            \
+         * */ \
+        item = (pthread_rwlock_fcfs_item_t * )pthread_rwlock_fcfs_queue_peak(rwlock->queue);  \
+        /*  \
+         * As long as we did not reach the end of the queue and as long as the item   \
+         * is disabled - destroy the item, dequeue it and peak the next item \
+         * */   \
+        while ((item != NULL) && (item->num_threads == 0))      \
+        {       \
+            dequeue_and_destroy_item(); \
+            item = (pthread_rwlock_fcfs_item_t * )pthread_rwlock_fcfs_queue_peak(rwlock->queue);   \
+        }      \
+    }
+
+
+
+/*
+ * This function peaks and dequeues enough items from the queue in
+ * order to accept the next round of pending items. By round, I mean
+ * either an arbitrary number of readers or a single writer.
+ * */
+static void accept_pending_items(pthread_rwlock_fcfs_t * rwlock)
+{
+    pthread_rwlock_fcfs_item_t * item;
+
+    extract_first_non_disabled_item();
+
+    /* The queue is empty, so we don't need to release anything */
+    if (item == NULL)
+    {
+        return;
+    }
+
+    /* Check if it's a writer or a reader */
+    if (item->is_writer)
+    {
+        /* There is going to be one less writer waiting on the condition
+         * variable */
+        item->num_threads--;
+        /* Prohibit other writers from joining this pack from now on */
+        item->was_first_thr_accepted = 1;
+        /* Release the writer. */
+        pthread_cond_signal( &(item->cond) );
+
+        /* Check if there are more threads pending. If not - we can extract
+         * and destroy the item */
+        if (item->num_threads == 0)
+        {
+            /* We don't need the item anymore so let's deallocate it */
+            dequeue_and_destroy_item();
+        }
+    }
+    else
+    {
+        /* Release all the threads that are waiting on this item */
+
+        pthread_cond_broadcast(& (item->cond) );
+
+        /* Destroy and extract this pack */
+        dequeue_and_destroy_item();
+    }
+    /* I am doing it in order to remove junk from the queue. */
+    extract_first_non_disabled_item();
+}
+
+/*
+ * This functions eliminates disabled items from the head of the queue,
+ * so pending readers will be able to be accepted immidiately.
+ * */
+static void remove_junk_from_head_of_queue(pthread_rwlock_fcfs_t * rwlock)
+{
+    pthread_rwlock_fcfs_item_t * item;
+
+    extract_first_non_disabled_item();
+}
+
+#undef dequeue_and_destroy_item
+#undef extract_first_non_disabled_item
+
+/*
+ * It is possible to determine whether the thread that releases the lock is a
+ * reader or a writer according to the state of the lock.
+ * */
+extern void pthread_rwlock_fcfs_release(pthread_rwlock_fcfs_t * rwlock PTHREAD_RWLOCK_FCFS_DEBUG_ARGS)
+{
+    pthread_mutex_lock(&(rwlock->mutex));
+
+    my_debug_print(rwlock, id, "Unlock!");
+
+    /*
+     * If there is a writer locking the lock, than obviously he is the one
+     * that releases it.
+     * */
+    if (rwlock->is_writer)
+    {
+        rwlock->is_writer = 0;
+
+        accept_pending_items(rwlock);
+    }
+    else
+    {
+        /*
+         * Croak if there are also no readers - someone is trying to release
+         * a lock which he does not have...
+         * */
+        assert(rwlock->num_readers > 0);
+
+        rwlock->num_readers--;
+
+        /*
+         * Check if the lock is now free of readers. If so, we can accept
+         * pending writers.
+         * */
+
+        if (rwlock->num_readers == 0)
+        {
+            accept_pending_items(rwlock);
+        }
+    }
+
+    pthread_mutex_unlock(&(rwlock->mutex));
+}
+
+int
+    pthread_rwlock_fcfs_timed_gain_write(
+        pthread_rwlock_fcfs_t * rwlock,
+        const struct timespec * abstime,
+        int (*continue_callback)(void * context),
+        void * context
+        PTHREAD_RWLOCK_FCFS_DEBUG_ARGS
+        )
+{
+    int ret;
+
+    pthread_mutex_lock(&(rwlock->mutex));
+
+    my_debug_print(rwlock, id, "Want Timed Lock!");
+
+    ret = gain_write_generic(rwlock, 1, 1, abstime, continue_callback, context);
+
+    my_debug_print(rwlock, id, ((ret == 0)?"Lock!": "Failed Lock!"));
+
+    pthread_mutex_unlock(&(rwlock->mutex));
+
+    return ret;
+}
+
+
+static int gain_read_generic(
+    pthread_rwlock_fcfs_t * rwlock,
+    int wait_for_access,
+    int is_timed,
+    const struct timespec * abstime,
+    int (*continue_callback)(void * context),
+    void * context
+    )
+{
+    /*
+     * It is possible that there are some disabled items clogging the
+     * queue, which will prevent this thread from being accepted immidiately.
+     *
+     * Therefore, try to remove them
+     * */
+    remove_junk_from_head_of_queue(rwlock);
+
+    if ((rwlock->is_writer == 0) && pthread_rwlock_fcfs_queue_is_empty(rwlock->queue))
+    {
+        /* Increment the number of readers. */
+        rwlock->num_readers++;
+
+        /* Now we have read access */
+
+        return 0;
+    }
+    else
+    {
+        pthread_rwlock_fcfs_item_t * item;
+
+        if (! wait_for_access)
+        {
+            return 1;
+        }
+
+        item = (pthread_rwlock_fcfs_item_t *)pthread_rwlock_fcfs_queue_peak_tail(rwlock->queue);
+        if (
+                /* The queue is not empty */
+                (item != NULL) &&
+                /* It is a readers' pack */
+                (! item->is_writer)
+           )
+        {
+            /* Use this item */
+            item->num_threads++;
+        }
+        else
+        {
+
+            /* Let's enqueue myself */
+
+            item = malloc(sizeof(pthread_rwlock_fcfs_item_t));
+            /* We are a writer, so let's designate ourselves as such */
+            item->is_writer = 0;
+
+            /* We want to gain access to the lock */
+            item->is_disabled = 0;
+
+            /* This is a new pack with one thread waiting. */
+            item->num_threads = 1;
+
+            /* Initialize the condition variable */
+            item->cond = initial_cond_constant;
+
+            pthread_cond_init(&(item->cond), NULL);
+
+            /* Let's put ourselves in the queue, so we will be released
+             * when necessary. */
+            pthread_rwlock_fcfs_queue_enqueue(rwlock->queue, item);
+        }
+
+        /* Wait upon the condition variable to gain access to the rwlock */
+        if (! is_timed)
+        {
+            pthread_cond_wait(&(item->cond), &(rwlock->mutex));
+        }
+        else
+        {
+            int ret;
+
+            /*
+             * We try to get a timed wait on cond. If it times-out, we ask
+             * the user if he wishes to continue.
+             */
+            do
+            {
+                ret = pthread_cond_timedwait(&(item->cond), &(rwlock->mutex), abstime);
+            } while
+                (
+                    (ret == ETIMEDOUT) &&
+                    (continue_callback != NULL) &&
+                    continue_callback(context)
+                );
+
+            /* We failed for some reason (probably a time out - let's disable
+             * this item, so it won't be processed.
+             * */
+            if (ret != 0)
+            {
+                /* Let the controlling thread know we are no longer waiting
+                 * on the condition variable */
+
+                item->num_threads--;
+                return ret;
+            }
+        }
+
+        /* Now we have a read access */
+        rwlock->num_readers++;
+
+        return 0;
+    }
+}
+
+int pthread_rwlock_fcfs_timed_gain_read(
+        pthread_rwlock_fcfs_t * rwlock,
+        const struct timespec * abstime,
+        int (*continue_callback)(void * context),
+        void * context
+        PTHREAD_RWLOCK_FCFS_DEBUG_ARGS
+        )
+{
+    int ret;
+
+    pthread_mutex_lock(&(rwlock->mutex));
+
+    my_debug_print(rwlock, id, "Want Timed Lock!");
+
+    ret = gain_read_generic(rwlock, 1, 1, abstime, continue_callback, context);
+
+    my_debug_print(rwlock, id, ((ret == 0) ? "Lock!" : "Failed Lock!"));
+
+    pthread_mutex_unlock(&(rwlock->mutex));
+
+    return ret;
+}
+
+void pthread_rwlock_fcfs_gain_read(pthread_rwlock_fcfs_t * rwlock PTHREAD_RWLOCK_FCFS_DEBUG_ARGS)
+{
+    pthread_mutex_lock(&(rwlock->mutex));
+
+    my_debug_print(rwlock, id, "Want Lock!");
+
+    gain_read_generic(rwlock, 1, 0, NULL, NULL, NULL);
+
+    my_debug_print(rwlock, id, "Lock!");
+
+    pthread_mutex_unlock(&(rwlock->mutex));
+}
+
+int pthread_rwlock_fcfs_try_gain_read(pthread_rwlock_fcfs_t * rwlock PTHREAD_RWLOCK_FCFS_DEBUG_ARGS)
+{
+    int ret;
+
+    pthread_mutex_lock(&(rwlock->mutex));
+
+    my_debug_print(rwlock, id, "Want Try Lock!");
+
+    ret = gain_read_generic(rwlock, 0, 0, NULL, NULL, NULL);
+
+    my_debug_print(rwlock, id, ((ret == 0) ? "Lock!" : "Failed Lock!"));
+
+    pthread_mutex_unlock(&(rwlock->mutex));
+
+    return ret;
+}
+

pthreads/rwlock_fcfs.h

+#ifndef __PTHREAD_RWLOCK_FCFS_H
+#define __PTHREAD_RWLOCK_FCFS_H
+
+#include <pthread.h>
+
+#include <pthread/rwlock_fcfs_queue.h>
+
+/* This is the struct that is pointed to by the elements of the queue of
+ * the FCFS RWLock 
+ * */
+struct pthread_rwlock_fcfs_item_struct
+{
+    /* A condition variable to wake up the threads that waits upon this item */
+    pthread_cond_t cond;
+    /* A flag that specifies if it's a reader or a writer */
+    int is_writer;
+    /* A flag that disables this item */
+    int is_disabled;
+    /* An integer specifiying how many threads are waiting on it */
+    int num_threads;
+    /* A flag that indicates if the first thread in the pack has already
+     * been accepted. (Used only for a writers' pack */
+    int was_first_thr_accepted;
+};
+
+typedef struct pthread_rwlock_fcfs_item_struct pthread_rwlock_fcfs_item_t;
+
+/* The RWLock Struct */
+struct pthread_rwlock_fcfs_struct
+{
+    /* The queue that will be managed */
+    pthread_rwlock_fcfs_queue_t * queue;
+    /* The number of readers that are using the RWLock at the moment */
+    int num_readers;
+    /* Specifies if there is a writer locking the RWLock */
+    int is_writer;
+    /* A mutex to make sure no two threads _modify_ the RWLock struct
+     * at the moment */
+    pthread_mutex_t mutex;
+
+    /* A flag that indicates that no new threads should be accepted */
+    int is_destroyed;
+};
+
+typedef struct pthread_rwlock_fcfs_struct pthread_rwlock_fcfs_t;
+
+/************** Functions ***********/
+
+#ifdef PTHREAD_RWLOCK_FCFS_DEBUG
+#define PTHREAD_RWLOCK_FCFS_DEBUG_ARGS , char * id
+#define PTHREAD_RWLOCK_FCFS_DEBUG_CALL_ARGS , id
+#else
+#define PTHREAD_RWLOCK_FCFS_DEBUG_ARGS 
+#define PTHREAD_RWLOCK_FCFS_DEBUG_CALL_ARGS 
+#endif
+
+/* 
+ * Allocate a new FCFS RWLock
+ * */
+extern pthread_rwlock_fcfs_t * pthread_rwlock_fcfs_alloc(void);
+
+/*
+ * Wait indefinitely until a read access to the lock is granted.
+ * */
+extern void pthread_rwlock_fcfs_gain_read(pthread_rwlock_fcfs_t * rwlock PTHREAD_RWLOCK_FCFS_DEBUG_ARGS);
+
+/*
+ * Wait indefinitely until a write access to the lock is granted.
+ * */
+extern void pthread_rwlock_fcfs_gain_write(pthread_rwlock_fcfs_t * rwlock PTHREAD_RWLOCK_FCFS_DEBUG_ARGS);
+
+/*
+ * Release a previously gained read or write access
+ * */
+extern void pthread_rwlock_fcfs_release(pthread_rwlock_fcfs_t * rwlock PTHREAD_RWLOCK_FCFS_DEBUG_ARGS);
+
+/* 
+ * Destroy the RWLock
+ * */
+extern void pthread_rwlock_fcfs_destroy(pthread_rwlock_fcfs_t * rwlock);
+
+/*
+ * Wait until a certain time (abstime) to get a read access. If it is 
+ * not given, continue_callback is called and asks whether to continue 
+ * or not. 
+ * 
+ * If it wishes to continue, it is responsible for setting the new abstime.
+ *
+ * context is the context variable for continue_callback
+ * 
+ * */
+extern int pthread_rwlock_fcfs_timed_gain_read(
+        pthread_rwlock_fcfs_t * rwlock,
+        const struct timespec * abstime,
+        int (*continue_callback)(void * context),
+        void * context
+        PTHREAD_RWLOCK_FCFS_DEBUG_ARGS
+        );
+
+/*
+ * Wait until a certain time (abstime) to get a write access. If it is not 
+ * given, continue_callback is called and asks whether to continue or not. 
+ * 
+ * If it wishes to continue, it is responsible for setting the new abstime.
+ *
+ * context is the context variable for continue_callback
+ * 
+ * */
+extern int pthread_rwlock_fcfs_timed_gain_write(
+        pthread_rwlock_fcfs_t * rwlock,
+        const struct timespec * abstime,
+        int (*continue_callback)(void * context),
+        void * context
+        PTHREAD_RWLOCK_FCFS_DEBUG_ARGS
+        );
+
+/* 
+ * Attempt to gain a read access. If it is not given immidiately it returns an
+ * error code other than 0.
+ *
+ * Else, it returns 0
+ * */
+extern int pthread_rwlock_fcfs_try_gain_read(pthread_rwlock_fcfs_t * rwlock PTHREAD_RWLOCK_FCFS_DEBUG_ARGS);
+
+
+/* 
+ * Attempt to gain a write access. If it is not given immidiately it returns an
+ * error code other than 0.
+ *
+ * Else, it returns 0
+ * */
+extern int pthread_rwlock_fcfs_try_gain_write(pthread_rwlock_fcfs_t * rwlock PTHREAD_RWLOCK_FCFS_DEBUG_ARGS);
+
+    
+#endif /* #ifndef __PTHREAD_RWLOCK_FCFS_H */
+
+

pthreads/rwlock_fcfs_queue.h

+
+
+#ifndef __PTHREAD_RWLOCK_FCFS_QUEUE_H
+#define __PTHREAD_RWLOCK_FCFS_QUEUE_H
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#define IP_NOISE_MESSAGE_BUFSIZE 0x20000
+
+#ifndef __KERNEL__
+
+struct pthread_rwlock_fcfs_queue_item_struct
+{
+    void * data;
+    struct pthread_rwlock_fcfs_queue_item_struct * next;
+};
+
+typedef struct pthread_rwlock_fcfs_queue_item_struct pthread_rwlock_fcfs_queue_item_t;
+
+struct pthread_rwlock_fcfs_queue_struct
+{
+    pthread_rwlock_fcfs_queue_item_t * head;
+    pthread_rwlock_fcfs_queue_item_t * tail;
+
+    int num_msgs;
+};
+
+typedef struct pthread_rwlock_fcfs_queue_struct pthread_rwlock_fcfs_queue_t;
+
+extern pthread_rwlock_fcfs_queue_t * pthread_rwlock_fcfs_queue_alloc(void);
+
+extern void pthread_rwlock_fcfs_queue_destroy(pthread_rwlock_fcfs_queue_t * queue);
+
+extern void * pthread_rwlock_fcfs_queue_dequeue(pthread_rwlock_fcfs_queue_t * queue);
+
+extern void * pthread_rwlock_fcfs_queue_peak(pthread_rwlock_fcfs_queue_t * queue);
+
+extern void pthread_rwlock_fcfs_queue_enqueue(pthread_rwlock_fcfs_queue_t * queue, void * msg);
+
+extern int pthread_rwlock_fcfs_queue_is_empty(pthread_rwlock_fcfs_queue_t * queue);
+
+extern void * pthread_rwlock_fcfs_queue_peak_tail(pthread_rwlock_fcfs_queue_t * queue);
+
+
+#endif
+
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* #ifndef __PTHREAD_RWLOCK_FCFS_QUEUE_H */ 
+

pthreads/test_queue.cpp

+#include <stdio.h>
+#include <stdlib.h>
+
+#include <iostream.h>
+
+#include <pthread/rwlock_fcfs_queue.h>
+
+#ifdef DMALLOC
+#include "dmalloc.h"
+#endif
+
+int main()
+{
+    pthread_rwlock_fcfs_queue_t * queue; 
+    
+    queue = pthread_rwlock_fcfs_queue_alloc();
+    
+    int element;
+    int * ptr;
+
+    char op;
+
+    while(!cin.eof())
+    {
+        cout << "Op:\n";
+        cin >> op;
+        if (op == 'e')
+        {
+            cin >> element;
+            ptr = (int*)malloc(sizeof(int));
+            *ptr = element;
+            pthread_rwlock_fcfs_queue_enqueue(queue, ptr);
+        }
+        else if (op == 'd')
+        {
+            ptr = (int *)pthread_rwlock_fcfs_queue_dequeue(queue);
+            if (ptr == NULL)
+            {
+                cout << "Queue is empty!\n";
+            }
+            else
+            {
+                cout << "DeQed " << *ptr << "\n";
+                free(ptr);
+            }            
+        }
+        else if (op == 'p')
+        {
+            ptr = (int *)pthread_rwlock_fcfs_queue_poll(queue);
+            if (ptr == NULL)
+            {
+                cout << "Queue is empty!\n";
+            }
+            else
+            {
+                cout << "Polled " << *ptr << "\n";
+            }            
+        }
+    }
+
+    return 0;
+}

pthreads/test_rwlock.c

+#include <pthread.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+#include <string.h>
+
+#include <sys/time.h>
+
+#include <pthread/rwlock_fcfs.h>
+
+pthread_rwlock_fcfs_t * mylock;
+
+struct context_struct
+{
+    int writer;
+    int index;
+};
+
+typedef struct context_struct context_t;
+
+void * reader_thread(void * void_context)
+{
+    char id[100];
+    context_t * context;
+
+    context = (context_t *)void_context;
+
+    sprintf(id, "Reader %i", context->index);
+
+    while (1)
+    {
+        int which = rand()%3;
+        if (which == 0)
+        {
+            pthread_rwlock_fcfs_gain_read(mylock PTHREAD_RWLOCK_FCFS_DEBUG_CALL_ARGS);
+
+            usleep(rand()%1000000);
+
+            pthread_rwlock_fcfs_release(mylock PTHREAD_RWLOCK_FCFS_DEBUG_CALL_ARGS);
+
+            usleep(rand()%1000000);
+        }
+        else if (which == 1)
+        {
+            struct timeval now;
+            struct timespec timeout;
+            struct timezone tz;
+            int ret;
+            
+            gettimeofday(&now, &tz);
+            timeout.tv_nsec = (now.tv_usec + (rand()%1000000));
+            if (timeout.tv_nsec > 1000000)
+            {
+                timeout.tv_sec += timeout.tv_nsec / 1000000;
+                timeout.tv_nsec %= 1000000;
+            }
+            
+            timeout.tv_nsec *= 1000;
+            ret = pthread_rwlock_fcfs_timed_gain_read(
+                mylock,
+                &timeout,
+                NULL,
+                NULL
+                PTHREAD_RWLOCK_FCFS_DEBUG_CALL_ARGS
+                );
+
+            usleep(rand()%1000000);
+
+            if (ret == 0)
+            {
+                pthread_rwlock_fcfs_release(mylock PTHREAD_RWLOCK_FCFS_DEBUG_CALL_ARGS);
+            } 
+
+            usleep(rand()%1000000);
+            fflush(stdout);
+        }
+        else if (which == 2)
+        {
+            int ret;
+            ret = pthread_rwlock_fcfs_try_gain_read(mylock PTHREAD_RWLOCK_FCFS_DEBUG_CALL_ARGS);
+
+            usleep(rand()%1000000);            
+
+            if (ret == 0)
+            {
+                pthread_rwlock_fcfs_release(mylock PTHREAD_RWLOCK_FCFS_DEBUG_CALL_ARGS);
+            }
+
+            usleep(rand()%1000000);
+            fflush(stdout);
+        }
+    }
+
+    return NULL;
+}
+
+void * writer_thread(void * void_context)
+{
+    char id[100];
+    context_t * context;
+
+    context = (context_t *)void_context;
+
+    sprintf(id, "Writer %i", context->index);
+
+    while (1)
+    {
+        int which = rand()%3;
+        if (which == 0)
+        {
+            pthread_rwlock_fcfs_gain_write(mylock PTHREAD_RWLOCK_FCFS_DEBUG_CALL_ARGS);
+
+            usleep(rand()%1000000);
+
+            pthread_rwlock_fcfs_release(mylock PTHREAD_RWLOCK_FCFS_DEBUG_CALL_ARGS);
+
+            usleep(rand()%1000000);
+        }
+        else if (which == 1)
+        {
+            struct timeval now;
+            struct timespec timeout;
+            struct timezone tz;
+            int ret;
+            
+            gettimeofday(&now, &tz);
+            timeout.tv_nsec = (now.tv_usec + (rand()%1000000));
+            if (timeout.tv_nsec > 1000000)
+            {
+                timeout.tv_sec += timeout.tv_nsec / 1000000;
+                timeout.tv_nsec %= 1000000;
+            }
+            
+            timeout.tv_nsec *= 1000;
+            ret = pthread_rwlock_fcfs_timed_gain_write(
+                mylock,
+                &timeout,
+                NULL,
+                NULL
+                PTHREAD_RWLOCK_FCFS_DEBUG_CALL_ARGS
+                );
+
+            usleep(rand()%1000000);
+
+            if (ret == 0)
+            {
+                pthread_rwlock_fcfs_release(mylock PTHREAD_RWLOCK_FCFS_DEBUG_CALL_ARGS);
+            } 
+
+            usleep(rand()%1000000);
+            fflush(stdout);
+        }
+        else if (which == 2)
+        {
+            int ret;
+            ret = pthread_rwlock_fcfs_try_gain_write(mylock PTHREAD_RWLOCK_FCFS_DEBUG_CALL_ARGS);
+
+            usleep(rand()%1000000);            
+
+            if (ret == 0)
+            {
+                pthread_rwlock_fcfs_release(mylock PTHREAD_RWLOCK_FCFS_DEBUG_CALL_ARGS);
+            }
+
+            usleep(rand()%1000000);
+            fflush(stdout);
+        }
+    }
+
+    return NULL;
+}
+
+
+int main(int argc, char * argv[])
+{
+    context_t * context;
+    pthread_t * readers;
+    pthread_t * writers;
+    int check;
+
+    int a;
+    int arg;
+    int NUM_READERS = 5;
+    int NUM_WRITERS = 2;
+
+    for(arg=1;arg<argc;arg++)
+    {
+        if (!strcmp(argv[arg], "--num-readers"))
+        {
+            arg++;
+            if (arg == argc)
+            {
+                fprintf(stderr, "--num-readers accepts an argument!\n");
+                exit(-1);
+            }
+            NUM_READERS = atoi(argv[arg]);
+        }
+        else if (!strcmp(argv[arg], "--num-writers"))
+        {
+            arg++;
+            if (arg == argc)
+            {
+                fprintf(stderr, "--num-writers accepts an argument!\n");
+                exit(-1);                    
+            }
+            NUM_WRITERS = atoi(argv[arg]);
+        }
+        else
+        {
+            fprintf(stderr, "Unknown option - \"%s\"!\n", argv[arg]);
+            exit(-1);
+        }
+    }        
+
+    readers = malloc(sizeof(readers[0])*NUM_READERS);
+    writers = malloc(sizeof(writers[0])*NUM_WRITERS);
+
+    mylock = pthread_rwlock_fcfs_alloc();
+    for(a=0;a<NUM_READERS;a++)
+    {
+        context = malloc(sizeof(*context));
+        context->index = a;
+        context->writer = 0;
+        check = pthread_create(
+            &readers[a],
+            NULL,
+            reader_thread,
+            context
+            );
+        
+        if (check != 0)
+        {
+            fprintf(stderr, "Could not create Reader #%i!\n", a);
+            exit(-1);
+        }
+    }
+
+    for(a=0;a<NUM_WRITERS;a++)
+    {
+        context = malloc(sizeof(*context));
+        context->index = a;
+        context->writer = 0;
+        check = pthread_create(
+            &writers[a],
+            NULL,
+            writer_thread,
+            context
+            );
+        
+        if (check != 0)
+        {
+            fprintf(stderr, "Could not create Reader #%i!\n", a);
+            exit(-1);
+        }
+    }
+
+    while(1)
+    {
+        sleep(1);
+    }
+    return 0;
+}
+
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.