Template Version: @(#)sac_nextcase 1.68 02/23/09 SMI
This information is Copyright 2009 Sun Microsystems
1. Introduction
1.1. Project/Component Working Name:
Public linked lists
1.2. Name of Document Author/Supplier:
Author: Garrett D'Amore
1.3 Date of This Document:
08 September, 2009
4. Technical Description
Problem
-------
Unlike virtually every other FOSS, we Solaris has not common faciility that
is *public* for driver developers for managing linked lists.
Yet managing linked lists is one of the most common tasks that device driver
developers are faced with.
Solaris has a facility, but it was never reviewed by ARC and remains some
form of private.
Solution
--------
We propose that the definitions and declarations that make up sys/list.h
are added to the public Committed DDI. Note that these linked lists are
actually doubly linked to allow O(1) insertions and removals anywhere on
the list, as well as to allow efficient traversal in either direction.
We are requesting Patch binding, although at present four of the functions
interfaces described here are not present on Solaris 10 and would need to
be backported. (The Patch binding makes this possible if some enterprising
individual should choose to this, although the project team has no specific
intention to do this at this time.) The functions not present on S10 are
identified in the Exported Interfaces table below.
Details
-------
<sys/list.h> contains the following types:
typedef struct list_node list_node_t;
This is an opaque structure node on a linked list. It can be placed
as a member of a structure that will be linked together. (Its valid to
take the size of this structure, but individual members remain private.)
typedef struct list list_t;
This is an opaque structure representing a linked list itself. It
is valid to take the size of this structure, but individual members remain
private.
The following functions are used to access linked lists. Note that the linked
lists themselves are not protected by any locks; it is the responsibility of
the developer to provide locking to protect the linkage of lists created
with these functions.
void list_create(list_t *, size_t size, size_t offset);
This function initializes a new list. The driver supplies the storage
for the list handle, and the size of an individual element, and the
offset of a list_node_t within the element to use for the links of
the list.
void list_destroy(list_t *);
This function destroys the list handle, including freeing up any
resources which may have been internally allocated for the list.
The list *must* be empty when this function is called.
void list_insert_after(list_t *, void *reference_item, void *new_item);
void list_insert_before(list_t *, void *reference_item, void *new_item);
These functions insert new_item into the linked list at a location
after or before the reference item, which must already be on the list.
void list_insert_head(list_t *, void *new_item);
void list_insert_tail(list_t *, void *new_item);
These functions insert the new_item on the list at either the head or
tail of the list. (The head is the first item, the tail is the last item).
void list_remove(list_t *, void *item);
This function removes the item from the list.
void *list_remove_head(list_t *);
void *list_remove_tail(list_t *);
These functions remove the head (first) or tail (last) item from the
list. The item removed is returned to the caller. If the list is empty
when these functions are called, then no change is made and NULL is
returned to the caller.
void *list_head(list_t *);
void *list_tail(list_t *);
These functions simply return the head (first) or tail (last) item on
the list. NULL is returned if the list is empty.
void *list_next(list_t * void *reference_item);
void *list_prev(list_t * void *reference_item);
These functions returne the next or previous item in the list, relative
to the named reference item which must be linked on the list.
int list_is_empty(list_t *);
This functions returns zero if the list has items in it, or non-zero
otherwise.
void list_link_init(list_node_t *node);
This function initializes the list_node_t. It is functionally equivalent
to bzero(node, sizeof (*node));
int list_link_active(list_node_t *);
This functions returns non-zero if the node is on an active list.
void list_move_tail(list_t *dst, list_t *src);
This function is used to append the items on the src list to the end of
the dst list. It is mandatory that the two lists were initialized using
identical size and offset parameters. Upon completion, the src list will
be empty.
void list_link_replace(list_node_t *, list_node_t *);
This function swaps two items on a list. Note that the items need not
be on the same list, but extreme care must be used to ensure that both
lists are locked, and that the lists were initialized with identical
size and offset parameters.
Interface Tables
----------------
Exported Interfaces
+-----------------------+---------------+-------------------------------+
| Interface | Stability | Comments |
+-----------------------+---------------+-------------------------------+
| <sys/list.h> | Committed | Header file |
| list_node_t | Committed | Opaque datatype |
| list_t | Committed | |
| sizeof (list_node_t) | Committed | Sizes are committed |
| sizeof (list_t) | Committed | |
| list_create() | Committed | List handling functions |
| list_destroy() | Committed | |
| list_insert_after() | Committed | |
| list_insert_before() | Committed | |
| list_insert_head() | Committed | |
| list_insert_tail() | Committed | |
| list_remove() | Committed | |
| list_remove_head() | Committed | Not currently in S10 |
| list_remove_tail() | Committed | Not currently in S10 |
| list_move_tail() | Committed | |
| list_head() | Committed | |
| list_tail() | Committed | |
| list_next() | Committed | |
| list_prev() | Committed | |
| list_is_empty() | Committed | |
| list_link_init() | Committed | Not currently in S10 |
| list_link_replace() | Committed | Not currently in S10 |
| list_link_active() | Committed | |
+-----------------------+---------------+-------------------------------+
Imported Interfaces
None.
6. Resources and Schedule
6.4. Steering Committee requested information
6.4.1. Consolidation C-team Name:
ON
6.5. ARC review type: FastTrack
6.6. ARC Exposure: open
