-
Notifications
You must be signed in to change notification settings - Fork 0
/
docs.ltx
5138 lines (4134 loc) · 202 KB
/
docs.ltx
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
% Copyright 1996-2012
% Kaz Kylheku <kaz@kylheku.com>
% Vancouver, Canada
% All rights reserved.
%
% BSD License:
%
% Redistribution and use in source and binary forms, with or without
% modification, are permitted provided that the following conditions
% are met:
%
% 1. Redistributions of source code must retain the above copyright
% notice, this list of conditions and the following disclaimer.
% 2. Redistributions in binary form must reproduce the above copyright
% notice, this list of conditions and the following disclaimer in
% the documentation and/or other materials provided with the
% distribution.
% 3. The name of the author may not be used to endorse or promote
% products derived from this software without specific prior
% written permission.
%
% THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
% IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
% WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
%
\documentclass{article}
\usepackage{makeidx}
\usepackage[margin=1.0in]{geometry}
\makeatletter
\newcommand{\defsubsection}{\@startsection
{subsection}
{2}
{0pt}
{2.0ex plus 0.1ex minus 0.05ex}
{-0pt}
{\normalfont\normalsize\bfseries}}
\newcommand{\defsubsubsection}{\@startsection
{subsection}
{3}
{0ex}
{2.0ex plus 0.1ex minus 0.05ex}
{1.0ex}
{\normalfont\normalsize\bfseries}}
\renewcommand{\paragraph}{\@startsection
{paragraph}
{4}
{0ex}
{2.0ex plus 0.1ex minus 0.05ex}
{1.0ex}
{\normalsize\bfseries}}
\makeatother
\title{Kazlib---Reusable Components\\for C and C++ Programming}
\author{Kaz Kylheku}
\date{Release 1.21\\May 8, 2012}
\makeindex
\setcounter{tocdepth}{1}
\setcounter{secnumdepth}{4}
\begin{document}
\catcode`\_=11
\def\indextype#1{\index{#1@{\tt #1} type}}
\def\indexmacro#1{\index{#1@{\tt #1} macro}}
\def\indexobject#1{\index{#1@{\tt #1} object}}
\def\indexfunc#1{\index{#1@{\tt #1} function}}
\def\indexenum#1{\index{#1@{\tt #1} enum constant}}
\def\indexcppns#1{\index{#1@{\tt #1} C"+"+ namespace}}
\def\indexcppclass#1#2{\index{#1@{\tt #1} C"+"+ namespace!#2@{\tt #2} class}
\index{#2@{\tt #2} class}}
\def\indexcppspecial#1#2#3{\index{#1@{\tt #1}
C"+"+ namespace!#2@{\tt #2}
class!#2@{\tt #2::#2} #3}
\index{#2@{\tt #2::#2} #3}}
\def\indexcppfunc#1#2#3{\index{#1@{\tt #1}
C"+"+ namespace!#2@{\tt #2}
class!#3@{\tt #2::#3} function}
\index{#3@{\tt #2::#3} function}}
\def\synopsis{\paragraph*{Synopsis}}
\def\constraints{\paragraph*{Constraints}}
\def\description{\paragraph*{Description}}
\def\example{\paragraph*{Example}}
\maketitle
\abstract{The aim of the Kazlib project is to provide a well-documented
programming interface featuring commonly needed programming abstractions,
accompanied by a high quality, portable reference implementation.
Kazlib consists of four independent components: a list module, a hash table
module, a dictionary module and an exception handling module. The reference
implementations of the first three of these are based on, respectively, the
following algorithms: doubly linked circular list with sentinel node,
extendible hashing, and red-black tree.}
\tableofcontents
\section{Introduction}
This document establishes the provisions required of an implementation of the
Kazlib library, and describes a reference implementation thereof.
This document specifies
\begin{itemize}
\item the names and types of identifiers and preprocessor symbols made
available by each component;
\item identifier name spaces reserved for future use by each component;
\item the interface syntax and semantics of each component operation;
\item the conditions required for the well-defined execution of each operation;
\item the externally visible behavior of each component, including global
side effects and the effects on the subject data structures;
\item and the implementation language of Kazlib.
\end{itemize}
Furthermore, this document describes, but does not specify
\begin{itemize}
\item the implementation details of structure objects manipulated by the
operations of each component;
\item objects and functions that are defined by the implementation of
each component but are not externally visible;
\item the algorithms and implementation details of the operations.
\end{itemize}
Finally, this document does {\em not\/} specify or describe
\begin{itemize}
\item the specific choices for parameters which may be adjusted by an
installation or implementation of Kazlib.
\item the size of any data structure which will exceed the capacity of
a particular installation.
\item the mechanisms or procedures for the translation of Kazlib and
their integration with other translation units.
\end{itemize}
\section{References}
\label{sec:references}
\begin{trivlist}
\item ISO 9899:1990, {\it Programming Languages---C.}
\item {\it Introduction to Algorithms}, Thomas H. Cormen, Charles E.
Leiserson, Ronald L. Rivest, eighth printing, 1992.
\end{trivlist}
\section{Definitions and conventions}
The following terms shall be interpreted in accordance with the definitions
below. Other terms appearing in this document shall be defined upon their
first mention, indicated by {\it italic\/} type. Any terms not explicitly
defined in this document should be interpreted according to ISO 9899-1990,
clause 3. Failing that, they should be interpreted according to other works
listed in section \ref{sec:references}.
\nobreak
\defsubsection{implementation}: A library and set of C language headers
which conforms to the specifications of this Document.
\index{production mode}
\indexmacro{NDEBUG}
\defsubsection{production mode}: A mode of operating the implementation
in such a way that maximum efficiency of execution is achieved at the expense
of the verification of constraints. An implementation shall provide
a production mode, which is enabled in an implementation-defined
manner.\footnote{An implementation may have to supply a separate set of
libraries for production and for verification use, for instance. The
manner of selecting libraries varies with each programming environment.} Each
translation unit of the program which includes a Kazlib header shall ensure that the macro {\tt
NDEBUG} is defined prior to the inclusion of that header, otherwise the
implementation is not said to be operated in production mode.
\index{verification mode}
\defsubsection{verification mode}: A mode of operating the implementation in
such a way that maximum error checking is obtained at the cost of
execution efficiency. An implementation shall provide a verification mode, which
is enabled in an implementation-defined manner. If any translation unit which
includes a Kazlib header defines the macro name {\tt NDEBUG}\footnote{The
intent is that the standard {\tt assert} macro may be exploited
by the implementation's headers for the purpose of provisioning verification
mode.} prior to including that header, the implementation is not said to be in
verification mode. The least requirements of a Kazlib implementation operated
in verification mode, is that it shall stop translation or execution of any
program which violates a constraint.
\index{undefined behavior}
\defsubsection{undefined behavior}: Behavior of a program, upon violation of a
requirement with respect to the use of Kazlib, or upon use of corrupt or
incorrect data, for which this document does not impose any requirements.
Additional undefined behaviors are:
\begin{itemize}
\item any behavior that is undefined by the C language standard;
\item evaluation of an object whose contents are indeterminate;
\item a violation of any explicit constraint stated in
this document, if that program was built using Kazlib in production
mode;\footnote{The intent is that violations of constraints are diagnosed by
the implementation in verification mode, and hence do not lead to undefined
behavior.}
\item a violation of any requirement stated in this document that
is not designated as a constraint, and is introduced using the word
{\it shall}; and
\item any other construct for which no definition of behavior can be deduced
from this document.
\end{itemize}
If a program invokes undefined behavior of any kind, the Kazlib implementation
is absolved from any requirements as to what events should ensue. The
implementation may respond by invoking undefined behavior in the C language
sense, or it may detect the behavior and terminate with a diagnostic message.
\defsubsection{implementation-defined}: An adjective which, when appearing
in the description of a feature, represents a requirement that the
implementor must supply a definition, and document that
definition. This adjective is applied to both behavior and to results.
Implementation-defined behavior is behavior which depends on the
characteristics of an implementation.\footnote{It is not considered adequate
for the implementor to allow implementation-defined behavior to produce
unpredictable effects or to terminate the program when such behavior is
invoked.} When said of a result,
implementation-defined means that a value is successfully computed, but depends
on the characteristics of the implementation. It is possible for the presence of a
requirement on a program to be described as implementation-defined, giving the
implementor a choice whether to make that requirement or not. If a program
violates a requirement whose presence is implementation-defined, that program's
behavior is undefined in any implementation which elects to in fact impose that
requirement.
\index{implementation-defined}
\defsubsection{unpredictable result}: A successfully computed value which is
unreliable because some procedure or data failed to satisfy a property required
by the computation.
\defsubsection{constraint}: A semantic restriction with which a program must
comply. Some sections of this Document contain paragraphs under the heading
{\it Constraints\/} which list all constraints pertaining to the described
feature. When operated in production mode, the Kazlib implementation
is not required to diagnose constraint violations. When operated in
verification mode, the Kazlib implementation must halt translation or
execution of a program which violates a constraint.
\index{constraint}
\defsubsection{comparison function}: A function which accepts two arguments
\index{comparison function}
and returns a value of type int based on
a ranking comparison of these arguments, and which satisfies the following
additional semantic properties. If the two arguments are deemed to be equal, the
function must return zero. If the first argument is determined to have a
greater rank than the second, a positive value is returned. Otherwise if the
first argument is determined to have a lesser rank than the second, a negative
value is returned. The rank is computed as if each value has associated with it
an integer, not necessarily unique, and as if these integers are compared for ordinary equality or
inequality when values are said to be compared. The assignment of integers is
up to the designer of the comparison function, and does not change between
successive invocations of the function.\footnote{Of course, an actual
comparison function need not assign actual integer ranks to data items, but it
must behave as if such ranks were assigned.}
If a comparison function is invoked in the context of an operation on some data
structure, it shall not invoke any operation on any component of that same
structure.\footnote{Thus, if a comparison function is invoked from, for
instance, {\tt list_sort}, it must not call any list operations that
inspect or modify the list being sorted, or any of its constituent nodes.}
\defsubsection{opaque data type}: A data type whose precise definition is
not documented, and which is intended to be manipulated only using the
documented interface, which consists of a set of functions. Many data types in
Kazlib are described as opaque. A program which bypasses the documented
interfaces in inspecting or manipulating these data types invokes undefined
behavior, and is not portable among Kazlib implementations.
\defsubsection{user}: \index{user} The program which uses Kazlib.
\defsubsection{user data}: \index{user data} Data provided by the program
to which Kazlib stores a pointer, but otherwise does not inspect or modify.
\section{Environment}
\label{sec:environment}
The translation and use of Kazlib requires a conforming, hosted implementation
of the C language which meets the following additional minimal requirements:
\begin{enumerate}
\item The C implementation distinguishes external names by at least their
initial 15 characters\footnote{The ISO 9899:1990 standard demands only that
external names be distinguished by their initial six characters.}. External
names that are distinct in their first 15 characters are treated by the
implementation as distinct names. Upper and lower case letters in external
identifiers need not be treated as distinct.
\item The C implementation does not claim the identifier \verb|__cplusplus|
for its internal use as a preprocessor symbol or keyword.
\end{enumerate}
If Kazlib headers are used by a C++ program, the C++ implementation
meets these additional requirements:
\begin{enumerate}
\item the C++ implementation identifies itself by predefining the preprocessor
symbol \verb|__cplusplus|;
\item the C++ implementation is be capable of linkage against
the C implementation with which the Kazlib source files units were translated.
\end{enumerate}
The Kazlib headers shall not make use of any names that are claimed
by the C++ programming language, and shall ensure that the \verb|extern "C"|
mechanism is used for all declarations when they are included into a C++
translation unit, or otherwise provide compatibility with C++.\footnote{The
intent is that the Kazlib implementation could, in principle, provide
a separate set of headers for use with each language.}
Furthermore, Kazlib supports C++ programming in particular. Certain sections of
Kazlib headers, enabled by preprocessing directives when the \verb|__cplusplus|
preprocessor symbol is present, provide definitions in the C++ language of
class templates and other kinds of entities.
In programming environments that support the programming mechanism of multiple
threads of execution an implementation of Kazlib may be designated as {\it
thread safe}. To be called thread safe, it must guarantee that the use of an
object by one thread cannot visibly interact or interfere with the concurrent
or interleaved use of another object by another thread. If a Kazlib
implementation that is not thread safe is provided for an environment which
supports threads, it shall be accompanied by documentation which describes
the extent of this limitation.
A Kazlib implementation can also be designated as being {\it async safe}.
The minimum requirement for this designation is that an operation on an object
can be interrupted by delivery of an asynchronous signal and from within the
catching function for that signal, it is safe to perform an operation on
another object. An implementation shall document that it is async safe,
or the extent to which it fails to be async safe.
\section{General restrictions}
\subsection{Headers}
The Kazlib headers may be included in any order, and may be included more than
once. Prior to the inclusion of a Kazlib header, the translation unit shall not
define any macro name that has the same spelling as a C language keyword. The
Kazlib headers may behave as though they include arbitrary standard C headers,
so any requirements related to the inclusion of standard headers apply to
Kazlib headers. A header shall be included before the first reference to any
of the functions, types or macros that it defines.
If one or more preprocessor symbols whose names begin with the sequence
\verb|KAZLIB_| are defined prior to the inclusion of a Kazlib header,
the behavior is implementation-defined.
\subsection{Reserved macros}
A Kazlib header defines all of the macros explicitly listed in the section of
this document that defines the contents of that header. It may also define
additional macros that belong to the macro namespace reserved by that header.
The translation unit that includes the header shall not \verb|#define| or
\verb|#undef| any of these macros.
A header may define function-like macros that supplement existing functions,
provided that such macros do not cause multiple evaluation of arguments except
as explicitly permitted, and are safe to use wherever the corresponding
function call would be. These function-like macros may be subject to
\verb|#undef|.\footnote{In principle, an implementation may provide, within the
reserved namespaces, additional functions not specified in this document, and
function-like macro equivalents of these functions. A program that uses such
identifiers in a block or function scope should use {\tt \#undef} on these
identifiers prior to their use.}
\subsection{Reserved symbols}
Each Kazlib header provides file scope declarations for the typedef names,
struct tags, enum constants and function names listed in its corresponding
section in this document. Moreover, each header may define additional such
names that fall into the documented reserved namespaces.
The behavior is undefined if a translation unit that includes a Kazlib header
defines any identifier that is the same as an identifier reserved by the header
in the same scope and namespace.\footnote{Therefore, it is permitted to redeclare
or redefine the identifiers reserved by a previously included Kazlib header,
provided that the declarations or definitions are in a different namespace or
scope. Reserved names may be redeclared in a block scope, or used as
statement labels which have function scope and are in their own namespace.}
The behavior is also undefined if the program contains a definition of an
object or function with external linkage whose name matches an external object
of unction defined by Kazlib component that is used as part of the
program, or whose name is in a namespace reserved by that
component.\footnote{This restriction exists whether or not the corresponding Kazlib
header is included.}
Lastly, the behavior is undefined if a translation unit defines a macro whose
name is in the space of reserved symbols of a Kazlib header that is included in
that translation unit.
\subsection{Argument aliasing}
Kazlib provides functions that operate on objects of various types. Pointers
to objects are passed to these functions, thereby giving rise to the
possibility of {\it aliasing}---passing of objects that wholly or partially
overlap. The program shall not present aliased objects to any Kazlib function.
Objects of distinct types shall not be aliased in a function call under any
circumstances.
The aliasing of two or more objects of compatible type is permitted only as
explicitly documented in the description of a function; in all such
circumstances, only exact overlapping is permitted.\footnote{That is to say,
where explicitly allowed, a pointer to the same object may be specified for two
(or more) parameters of like type.}
\subsection{Object initialization}
The Kazlib opaque data types can only be initialized with the initialization
functions provided by the Kazlib library, or by implementation-defined
initialization functions.\footnote{Of course, the use of implementation-defined
functions results in programs that are not portable among library
implementations.} An opaque object that is initialized by a method other than
by being passed to an appropriate initialization function, or that is not
initialized at all, has indeterminate contents. A pointer to an object having
indeterminate contents may be passed to an initialization function; the object
then has well-determined contents.
An object whose initialization function is capable of indicating failure is
considered indeterminate if the attempt to initialize that object using that
function does in fact fail. The program shall not attempt to deinitialize such
an object. The implementation shall reclaim any resources that were allocated
for an object whose initialization failed. This reclamation need
not be immediate, but may be delayed; however, the delay shall not
give rise to the possibility of resource leaks in any correct program.
Those objects for which deinitialization operations are defined should be
subject to these operations when these objects are no longer needed. Failure
to apply the deinitialization functions may result in the leakage of resources.
\subsection{Object copying}
Certain data types may be sensitive to their own location in memory. This
means that copying their values by assignment or \verb|memcpy| results in the
copy having an indeterminate value which cannot be used. All opaque types in
Kazlib are assumed to have this property; copying the value of an opaquely
typed object to another suitably typed object causes the destination
object to have indeterminate contents.
\section{List component}
The List component provides a set of functions, macros and type declarations
which together provide a library for maintaining a possibly empty ordered set
of elements, called a {\it list}. This list has the following properties:
\index{List}\begin{enumerate}
\item If the list is not empty, a first and last element can be identified.
In a list having only one element, that one element is both the first and
last element.
\item Each element that is not the last element has another element as its
{\it successor}.
\index{successor!of a list element}
\index{List!successor of an element}
\item Each element that is not the first element has a {\it
predecessor}.
\index{predecessor!of a list element}
\index{List!predecessor of an element}
\item No element is the predecessor or successor of more than one element.
\item If one element is the successor of another, the other is necessarily the
predecessor of the first.
\item Each element is associated with arbitrary {\it satellite\/} data.
\end{enumerate}
The {\it size} of a list, also known as the {\it list count}, is simply the
number of elements contained in it.\index{size!of a list}\index{List!count}
A list imposes a maximum value on the number of nodes that may be in it
simultaneously. This is known as the list's {\it capacity}. A list that
has the maximum number of nodes is said to be full.
\subsection{Interface}
\subsubsection{The {\tt list.h} header}
Each C or C++ translation unit that is to use the functionality of
the List component shall include the header \verb|list.h|. This header
shall contain declarations of types and external functions, and definitions of
macros.
The following typedef names shall be defined:\index{List!typedef names}
\index{typedefs!defined by List}
\begin{verbatim}
list_t listcount_t
lnode_t lnodepool_t
\end{verbatim}
In addition, the following structure tags may be defined:\index{List!tag names}
\index{tags!defined by List}
\begin{verbatim}
struct list_t
struct lnode_t
struct lnodepool_t
\end{verbatim}
The following external function names shall be declared:
\index{List!function names}\index{functions!defined by List}
\begin{verbatim}
list_append list_prev
list_contains list_process
list_count list_return_nodes
list_create list_sort
list_del_first list_find
list_del_last list_transfer
list_delete list_verify
list_destroy lnode_borrow
list_destroy_nodes lnode_create
list_extract lnode_destroy
list_first lnode_get
list_init lnode_init
list_ins_after lnode_is_in_a_list
list_ins_before lnode_pool_create
list_is_sorted lnode_pool_destroy
list_isempty lnode_pool_init
list_isfull lnode_pool_isempty
list_last lnode_pool_isfrom
list_merge lnode_put
list_next lnode_return
list_prepend
\end{verbatim}
The following preprocessor symbols (macros) shall be defined:
\index{List!macro names}\index{macros!defined by List}
\indexmacro{LISTCOUNT_T_MAX}
\indexmacro{LIST_H}
\begin{verbatim}
LISTCOUNT_T_MAX
LIST_H\end{verbatim}
\index{symbols!reserved by List}\index{List!reserved symbols}
Macro identifiers which begin with the upper-case prefix \verb|LIST| are
reserved for future extensions to the \verb|list.h| header, as are
names in the ordinary and tag namespaces which begin with
\verb|list_| or \verb|lnode_|. External names which begin with \verb|list_| or
\verb|lnode_| are reserved by the Kazlib library regardless of what header
files are included.
\subsubsection{The {\tt list_t} type}
\indextype{list_t}
The type \verb|list_t| is an opaque data type which maintains information about the
current state of a single list. A list consists of an instance of the
\verb|list_t| type, plus zero or more instances of the type \verb|lnode_t|. An
instance of the \verb|list_t| type can be dynamically created using the
\verb|list_create| function, and destroyed by the \verb|list_destroy| function.
Alternately, the program can declare an object of type \verb|list_t| and have
it initialized via the \verb|list_init| function.
\subsubsection{The {\tt listcount_t} type}
\indextype{listcount_t}
\indexmacro{LISTCOUNT_T_MAX}
The type \verb|listcount_t| is an unsigned integral type which represents
the number of nodes in a list. The specific choice of unsigned integral type
is implementation defined. The \verb|LISTCOUNT_T_MAX| macro expands to a
constant expression of type \verb|listcount_t| which specifies the maximum
value of that type.\footnote{For example, if the implementation defines
{\tt listcount_t} as an alias for the type unsigned long, then
{\tt LISTCOUNT_T_MAX} must have the same value as {\tt ULONG_MAX}.}
\subsubsection{The {\tt lnode_t} type}
\indextype{lnode_t}
The type \verb|lnode_t| is an opaque type that represents a single node of a
list. A node contains a a reference to satellite data provided by the user,
and also stores the key that is associated with the node when it is inserted.
Nodes may be dynamically created by the \verb|lnode_create| function.
Alternately, the program may supply an \verb|lnode_t| object that can be
initialized by the \verb|lnode_init| function.
\subsubsection{The {\tt lnodepool_t} type}
\indextype{lnodepool_t}
The \verb|lnodepool_t| type provides an alternate method for supplying list
nodes to the application. A user-supplied or dynamically allocated fixed size
array of nodes is converted into a a {\it pool\/} of nodes from which free
nodes may be obtained and to which they may be returned. A user-supplied node
pool is created by the function \verb|lnode_pool_init| which requires a pointer
to an object of type \verb|lnode_pool_t|, a pointer to the first element of an
array of \verb|lnode_t| objects, as well as an integer representing the size of
the array. Alternately, the function \verb|lnode_pool_create| will dynamically
allocate an object of type \verb|lnode_pool_t| containing the specified number
of list nodes.
\subsubsection{The {\tt list_append} function}
\indexfunc{list_append}
\index{List!appending a node}
\index{append node to list}
\synopsis
\begin{verbatim}
void list_append(list_t *, lnode_t *);\end{verbatim}
\constraints
The second argument shall not refer to a node that is already in a list
or in a list node pool. The first argument shall not refer to a list
that is full.
\description
The append operation causes the node pointed at by the second
argument to become the last node in the list pointed at by the first
argument.\footnote{That is to say, after the operation, the
{\tt list_last} function, when applied to the list, shall return a pointer
to that node.}
If the first argument is an expression with side effects, the behavior
is undefined.\footnote{Thus, the implementation may provide a macro
version of {\tt list_append} which evaluates the first argument
more than once.}
\index{macros!and side effects}
\subsubsection{The {\tt list_contains} function}
\indexfunc{list_contains}
\index{List!testing for presence of node}
\nobreak
\synopsis
\begin{verbatim}
int list_contains(list_t *, lnode_t *node);\end{verbatim}
\nobreak
\description
\nobreak
The \verb|list_contains| function shall return 1 if the node
pointed at by the second argument is in the list pointed at by the first
argument. Otherwise, it shall return 0.
\subsubsection{The {\tt list_count} function}
\indexfunc{list_count}
\index{List!count}
\index{List!size}
\synopsis
\begin{verbatim}
listcount_t list_count(list_t *);\end{verbatim}
\description
The \verb|list_count| function returns a value which represents the number
of nodes currently stored in the list pointed at by the argument.
\subsubsection{The {\tt list_create} function}
\indexfunc{list_create}
\index{List!creation of}
\index{create!list object}
\synopsis
\begin{verbatim}
list_t *list_create(listcount_t);\end{verbatim}
\description
The \verb|list_create| function instantiates and initializes an object of
type \verb|list_t|, and returns a pointer to it unless insufficient
resources exist for the creation of the object, in which case a null
pointer is returned.
The value of the function's argument establishes, for the entire duration
of the list object, its capacity.
The newly created list object is empty.
\subsubsection{The {\tt list_del_first} function}
\index{List!first node}
\indexfunc{list_del_first}
\index{List!deletion}
\index{delete!first node of a list}
\synopsis
\begin{verbatim}
lnode_t *list_del_first(list_t *);\end{verbatim}
\constraints
The argument shall not point to an empty list.
\description
The \verb|list_del_first| function removes the first node from the
list pointed at by the argument and returns a pointer to that
node.
If the argument is an expression with side effects, the behavior is
undefined.\index{macros!and side effects}
\subsubsection{The {\tt list_del_last} function}
\index{List!last node}
\indexfunc{list_del_last}
\index{List!deletion}
\index{delete!last node of a list}
\synopsis
\begin{verbatim}
lnode_t *list_del_last(list_t *);\end{verbatim}
\constraints
The argument shall not point to an empty list.
\description
The \verb|list_del_last| function removes the last node from the list
specified by the argument, and returns a pointer to that node. If,
prior to the operation, that node had a predecessor, that predecessor
shall become the new last node of the list. Otherwise, the list
shall become empty.
The new value of the list count shall be one less than its value
prior to the call to this function.
If the argument is an expression with side effects, the behavior is
undefined.\index{macros!and side effects}
\subsubsection{The {\tt list_delete} function}
\indexfunc{list_delete}
\index{List!deletion}
\index{delete!arbitrary node of a list}
\synopsis
\begin{verbatim}
lnode_t *list_delete(list_t *, lnode_t *);\end{verbatim}
\constraints
The second argument shall point to a node that is inside the list
pointed at by the first argument.
\description
The \verb|list_delete| function removes the node pointed at by its
second argument from the list pointed at by its first argument.
A pointer to the deleted node is returned.
\subsubsection{The {\tt list_destroy} function}
\indexfunc{list_destroy}
\index{List!destruction of}
\synopsis
\begin{verbatim}
void list_destroy(list_t *);\end{verbatim}
\constraints
The argument shall point to an empty list.
\description
The empty list pointed at by the argument is destroyed. If the list has
not been created by a call to the \verb|list_create| function, the
behavior is undefined.
A pointer that previously referred to a list that has been disposed by
\verb|list_destroy| has an indeterminate value.
\subsubsection{The {\tt list_destroy_nodes} function}
\indexfunc{list_destroy_nodes}
\synopsis
\begin{verbatim}
void list_destroy_nodes(list_t *);\end{verbatim}
\description
The nodes, if any, contained in the list pointed at by the argument are
disposed of as if by a call to the \verb|lnode_destroy| function. If any
node contained in the list was created by means other than the
\verb|lnode_create| function, the behavior is undefined.
After the operation, the list is empty.
Any pointer that referred to any of the destroyed nodes takes on an
indeterminate value.
\subsubsection{The {\tt list_extract} function}
\index{List!node range extraction}
\indexfunc{list_extract}
\synopsis
\begin{verbatim}
void list_extract(list_t *, list_t *, lnode_t *, lnode_t *);\end{verbatim}
\constraints
The second argument points to the {\it source list}. The third
argument is either null, or points to a node that is an occupant
of the source list. This node is called the {\it starting node}.
The fourth argument is either null, or points to a node that is
an occupant of the source list. This node is called the {\it ending
node}. If the starting node and ending node are both specified, and are
distinct nodes, then the starting node shall appear earlier in the source
list than the ending node.
The transfer request shall not call for the capacity of the destination
list to be exceeded.
\description
The \verb|list_extract| function moves nodes from the source
list to the {\it destination list\/} pointed at by the first
argument.\footnote{This right-to-left direction of transfer is consistent
with the semantics of standard C library functions such as {\tt memmove} or
{\tt strcpy}.}
If the third and fourth arguments are not null, the entire range of nodes
from the starting node and to the ending node, inclusive, is transferred
from the source list to the end of the destination list, where they appear
in their original order. Other nodes in the source list, if any, are
unaffected.
If the third and fourth arguments both point to the same node, that
node alone is transferred to the end of the destination list.
If either the third argument or the fourth argument is null, or both are null,
no transfer of nodes takes place.
The source and destination list may be the same object.
\subsubsection{The {\tt list_first} function}
\index{List!first node}
\indexfunc{list_first}
\synopsis
\begin{verbatim}
lnode_t *list_first(list_t *);\end{verbatim}
\description
If the list pointed at by the argument is an empty list, a null pointer
is returned. Otherwise, a pointer to the first node in that list is
returned.
If the argument is an expression with side effects, the behavior is
undefined.\index{macros!and side effects}
\subsubsection{The {\tt list_init} function}
\indexfunc{list_init}
\synopsis
\begin{verbatim}
list_t *list_init(list_t *, listcount_t);\end{verbatim}
\constraints
The second argument shall not have a zero value.
\description
The \verb|list_init| function initializes the list object pointed at by the
first argument, turning it into a valid, empty list. If the object is an
already initialized list, the behavior is undefined. A list returned by
\verb|list_create| is considered initialized. The second argument
specifies the maximum number of nodes that may simultaneously occupy the
list.
The value returned is that of the first argument.
\subsubsection{The {\tt list_ins_after} function}
\indexfunc{list_ins_after}
\index{insert!node into list}
\index{List!insertion}
\synopsis
\begin{verbatim}
void list_ins_after(list_t *, lnode_t *, lnode_t *);\end{verbatim}
\constraints
The first argument shall point to a list that is not already full. The
second argument shall point to a node, called the {\it new node}, that is not
already an occupant of the list pointed at by the first argument, nor
of any other list or node pool object. The third
argument shall point to a node, called the {\it reference node}, that is an
occupant of the list.
\description
The new node becomes an occupant of the list, such that its predecessor
is the reference node. If the reference node has a successor, the
new node is inserted between the reference node and that successor.
Otherwise, the new node becomes the last node of the list.
\subsubsection{The {\tt list_ins_before} function}
\indexfunc{list_ins_before}
\index{insert!node into list}
\index{List!insertion}
\synopsis
\begin{verbatim}
void list_ins_before(list_t *, lnode_t *, lnode_t *);\end{verbatim}
\constraints
The first argument shall point to a list that is not already full. The
second argument shall point to a node, called the {\it new node}, that is not
already an occupant of the list pointed at by the first argument, nor
of any other list or node pool object. The third
argument shall point to a node, called the {\it reference node}, that is an
occupant of the list.
\description
The new node becomes an occupant of the list, such that its successor
is the reference node. If the reference node has a predecessor, the
new node is inserted between the reference node and that predecessor.
Otherwise, the new node becomes the first node of the list.
\subsubsection{The {\tt list_is_sorted} function}
\label{list:is:sorted}
\indexfunc{list_is_sorted}
\synopsis
\begin{verbatim}
int list_is_sorted(list_t *,
int (const void *, const void *));\end{verbatim}
\description
The first argument points to a list object. The second is assumed to
point to a comparison function.
If the list has exactly one node or is empty, $1$ is returned
unconditionally. Otherwise, nodes of the list are examined to
determine whether they are in a sorted order according to the comparison
function. This is true if the integer ranks of their data items,
examined from the first node of the list through to the last node, form a
monotonically increasing sequence. If the nodes are in order, the value $1$
is returned. Otherwise $0$ is returned.
If the list has two or more nodes, and the second argument is a pointer to
a function that has the correct type, but does not satisfy the semantic
properties of a comparison function, the result is unpredictable, but is
guaranteed to be one of the values~$0$~or~$1$.
\subsubsection{The {\tt list_isempty} function}
\indexfunc{list_isempty}
\synopsis
\begin{verbatim}
int list_isempty(list_t *);\end{verbatim}
\description
The \verb|list_isempty| function returns $1$ if the list pointed at by
the first argument is empty. Otherwise it returns $0$.
\subsubsection{The {\tt list_isfull} function}
\indexfunc{list_isfull}
\synopsis
\begin{verbatim}
int list_isfull(list_t *);\end{verbatim}
\description
The \verb|list_isfull| function returns $1$ if the list pointed at by
the first argument is full. Otherwise it returns $0$.
A list is considered full when it contains the maximum number of nodes
that was specified upon its initialization.
If the argument is an expression with side effects, the behavior is
undefined.\index{macros!and side effects}
\subsubsection{The {\tt list_last} function}
\index{List!last node}
\indexfunc{list_last}
\synopsis
\begin{verbatim}
lnode_t *list_last(list_t *);\end{verbatim}
\description
If the list pointed at by its first argument is empty, the \verb|list_last|
function returns a null pointer. Otherwise it returns a pointer to the
last node.
If the argument is an expression with side effects, the behavior is
undefined.\index{macros!and side effects}
\subsubsection{The {\tt list_merge} function}
\index{List!merge operation}
\indexfunc{list_merge}
\synopsis
\begin{verbatim}
void list_merge(list_t *, list_t *,
int (const void *, const void *));\end{verbatim}
\constraints
The list pointed at by the first argument is called the {\it destination
list}. The second argument points to the {\it source list}. The third
argument points to a comparison function. The sum of the number of nodes
occupying the source list and the destination list shall not exceed the
maximum number of nodes that are permitted to occupy the destination list.
Furthermore, both the source and destination list shall be sorted such that
a call to \verb|list_is_sorted| given a pointer to either list as a first
argument, and the pointer to the comparison function as its second
argument, shall yield the value $1$.
\description
Nodes from the sorted source list are merged into the sorted destination
list. After the operation, the source list is empty and the destination
list contains all of the nodes it contained prior to the operation, as well
as all of the nodes that the source list contained. The nodes are in sorted
order according to the comparison function.
If the third argument is a pointer to a function that has the correct type,
but does not fulfill the semantic properties of a comparison function, the
order of the nodes in the destination list is unpredictable.
If the source and destination list are the same object, the
\verb|list_merge| operation has no effect.
\subsubsection{The {\tt list_next} function}
\indexfunc{list_next}
\synopsis
\begin{verbatim}
lnode_t *list_next(list_t *, lnode_t *);\end{verbatim}
\constraints
The node pointed at by the second argument is an occupant of the list pointed
at by the first argument.
\description
If the node pointed at by the second argument has a successor, a pointer to
that successor is returned. Otherwise, a null pointer is returned.
If the second argument is an expression which has side effects, the behavior
is undefined.\index{macros!and side effects}
\subsubsection{The {\tt list_prepend} function}
\indexfunc{list_prepend}
\index{List!prepending a node}
\index{prepend node to list}
\synopsis
\begin{verbatim}
void list_prepend(list_t *, lnode_t *);\end{verbatim}
\constraints
The second argument shall not refer to a node that is already in a list
or in a list node pool. The first argument shall not refer to a list
that is full.
\description
The prepend operation causes the node pointed at by the second
argument to become the first node in the list pointed at by the first
argument. After the operation, the \verb|list_first| function, when
applied to the list, shall return a pointer to that node.
If, prior to to the operation, the list is empty, then the prepended node
shall become the first node in that list, otherwise, the prepended node
becomes the predecessor of what was previously the first node.
If the first argument is an expression with side effects, the behavior
is undefined.\index{macros!and side effects}
\subsubsection{The {\tt list_prev} function}
\indexfunc{list_prev}
\synopsis
\begin{verbatim}
lnode_t *list_prev(list_t *, lnode_t *);\end{verbatim}
\constraints
The node pointed at by the second argument is an occupant of the list pointed