/* * Copyright © 2006 Keith Packard * Copyright © 2006 Carl Worth * * Permission to use, copy, modify, distribute, and sell this software and its * documentation for any purpose is hereby granted without fee, provided that * the above copyright notice appear in all copies and that both that copyright * notice and this permission notice appear in supporting documentation, and * that the name of the copyright holders not be used in advertising or * publicity pertaining to distribution of the software without specific, * written prior permission. The copyright holders make no representations * about the suitability of this software for any purpose. It is provided "as * is" without express or implied warranty. * * THE COPYRIGHT HOLDERS DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO * EVENT SHALL THE COPYRIGHT HOLDERS BE LIABLE FOR ANY SPECIAL, INDIRECT OR * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE * OF THIS SOFTWARE. */ #include #include #include #include #include #include "cairo-skiplist-private.h" #define ELT_DATA(elt) (void *) ((char*) (elt) - list->data_size) #define NEXT_TO_ELT(next) (skip_elt_t *) ((char *) (next) - offsetof (skip_elt_t, next)) /* Four 256 element lookup tables back to back implementing a linear * feedback shift register of degree 32. */ static unsigned const lfsr_lut[1024] = { 0x00000000, 0x9a795537, 0xae8bff59, 0x34f2aa6e, 0xc76eab85, 0x5d17feb2, 0x69e554dc, 0xf39c01eb, 0x14a4023d, 0x8edd570a, 0xba2ffd64, 0x2056a853, 0xd3caa9b8, 0x49b3fc8f, 0x7d4156e1, 0xe73803d6, 0x2948047a, 0xb331514d, 0x87c3fb23, 0x1dbaae14, 0xee26afff, 0x745ffac8, 0x40ad50a6, 0xdad40591, 0x3dec0647, 0xa7955370, 0x9367f91e, 0x091eac29, 0xfa82adc2, 0x60fbf8f5, 0x5409529b, 0xce7007ac, 0x529008f4, 0xc8e95dc3, 0xfc1bf7ad, 0x6662a29a, 0x95fea371, 0x0f87f646, 0x3b755c28, 0xa10c091f, 0x46340ac9, 0xdc4d5ffe, 0xe8bff590, 0x72c6a0a7, 0x815aa14c, 0x1b23f47b, 0x2fd15e15, 0xb5a80b22, 0x7bd80c8e, 0xe1a159b9, 0xd553f3d7, 0x4f2aa6e0, 0xbcb6a70b, 0x26cff23c, 0x123d5852, 0x88440d65, 0x6f7c0eb3, 0xf5055b84, 0xc1f7f1ea, 0x5b8ea4dd, 0xa812a536, 0x326bf001, 0x06995a6f, 0x9ce00f58, 0xa52011e8, 0x3f5944df, 0x0babeeb1, 0x91d2bb86, 0x624eba6d, 0xf837ef5a, 0xccc54534, 0x56bc1003, 0xb18413d5, 0x2bfd46e2, 0x1f0fec8c, 0x8576b9bb, 0x76eab850, 0xec93ed67, 0xd8614709, 0x4218123e, 0x8c681592, 0x161140a5, 0x22e3eacb, 0xb89abffc, 0x4b06be17, 0xd17feb20, 0xe58d414e, 0x7ff41479, 0x98cc17af, 0x02b54298, 0x3647e8f6, 0xac3ebdc1, 0x5fa2bc2a, 0xc5dbe91d, 0xf1294373, 0x6b501644, 0xf7b0191c, 0x6dc94c2b, 0x593be645, 0xc342b372, 0x30deb299, 0xaaa7e7ae, 0x9e554dc0, 0x042c18f7, 0xe3141b21, 0x796d4e16, 0x4d9fe478, 0xd7e6b14f, 0x247ab0a4, 0xbe03e593, 0x8af14ffd, 0x10881aca, 0xdef81d66, 0x44814851, 0x7073e23f, 0xea0ab708, 0x1996b6e3, 0x83efe3d4, 0xb71d49ba, 0x2d641c8d, 0xca5c1f5b, 0x50254a6c, 0x64d7e002, 0xfeaeb535, 0x0d32b4de, 0x974be1e9, 0xa3b94b87, 0x39c01eb0, 0xd03976e7, 0x4a4023d0, 0x7eb289be, 0xe4cbdc89, 0x1757dd62, 0x8d2e8855, 0xb9dc223b, 0x23a5770c, 0xc49d74da, 0x5ee421ed, 0x6a168b83, 0xf06fdeb4, 0x03f3df5f, 0x998a8a68, 0xad782006, 0x37017531, 0xf971729d, 0x630827aa, 0x57fa8dc4, 0xcd83d8f3, 0x3e1fd918, 0xa4668c2f, 0x90942641, 0x0aed7376, 0xedd570a0, 0x77ac2597, 0x435e8ff9, 0xd927dace, 0x2abbdb25, 0xb0c28e12, 0x8430247c, 0x1e49714b, 0x82a97e13, 0x18d02b24, 0x2c22814a, 0xb65bd47d, 0x45c7d596, 0xdfbe80a1, 0xeb4c2acf, 0x71357ff8, 0x960d7c2e, 0x0c742919, 0x38868377, 0xa2ffd640, 0x5163d7ab, 0xcb1a829c, 0xffe828f2, 0x65917dc5, 0xabe17a69, 0x31982f5e, 0x056a8530, 0x9f13d007, 0x6c8fd1ec, 0xf6f684db, 0xc2042eb5, 0x587d7b82, 0xbf457854, 0x253c2d63, 0x11ce870d, 0x8bb7d23a, 0x782bd3d1, 0xe25286e6, 0xd6a02c88, 0x4cd979bf, 0x7519670f, 0xef603238, 0xdb929856, 0x41ebcd61, 0xb277cc8a, 0x280e99bd, 0x1cfc33d3, 0x868566e4, 0x61bd6532, 0xfbc43005, 0xcf369a6b, 0x554fcf5c, 0xa6d3ceb7, 0x3caa9b80, 0x085831ee, 0x922164d9, 0x5c516375, 0xc6283642, 0xf2da9c2c, 0x68a3c91b, 0x9b3fc8f0, 0x01469dc7, 0x35b437a9, 0xafcd629e, 0x48f56148, 0xd28c347f, 0xe67e9e11, 0x7c07cb26, 0x8f9bcacd, 0x15e29ffa, 0x21103594, 0xbb6960a3, 0x27896ffb, 0xbdf03acc, 0x890290a2, 0x137bc595, 0xe0e7c47e, 0x7a9e9149, 0x4e6c3b27, 0xd4156e10, 0x332d6dc6, 0xa95438f1, 0x9da6929f, 0x07dfc7a8, 0xf443c643, 0x6e3a9374, 0x5ac8391a, 0xc0b16c2d, 0x0ec16b81, 0x94b83eb6, 0xa04a94d8, 0x3a33c1ef, 0xc9afc004, 0x53d69533, 0x67243f5d, 0xfd5d6a6a, 0x1a6569bc, 0x801c3c8b, 0xb4ee96e5, 0x2e97c3d2, 0xdd0bc239, 0x4772970e, 0x73803d60, 0xe9f96857, 0x00000000, 0x3a0bb8f9, 0x741771f2, 0x4e1cc90b, 0xe82ee3e4, 0xd2255b1d, 0x9c399216, 0xa6322aef, 0x4a2492ff, 0x702f2a06, 0x3e33e30d, 0x04385bf4, 0xa20a711b, 0x9801c9e2, 0xd61d00e9, 0xec16b810, 0x944925fe, 0xae429d07, 0xe05e540c, 0xda55ecf5, 0x7c67c61a, 0x466c7ee3, 0x0870b7e8, 0x327b0f11, 0xde6db701, 0xe4660ff8, 0xaa7ac6f3, 0x90717e0a, 0x364354e5, 0x0c48ec1c, 0x42542517, 0x785f9dee, 0xb2eb1ecb, 0x88e0a632, 0xc6fc6f39, 0xfcf7d7c0, 0x5ac5fd2f, 0x60ce45d6, 0x2ed28cdd, 0x14d93424, 0xf8cf8c34, 0xc2c434cd, 0x8cd8fdc6, 0xb6d3453f, 0x10e16fd0, 0x2aead729, 0x64f61e22, 0x5efda6db, 0x26a23b35, 0x1ca983cc, 0x52b54ac7, 0x68bef23e, 0xce8cd8d1, 0xf4876028, 0xba9ba923, 0x809011da, 0x6c86a9ca, 0x568d1133, 0x1891d838, 0x229a60c1, 0x84a84a2e, 0xbea3f2d7, 0xf0bf3bdc, 0xcab48325, 0xffaf68a1, 0xc5a4d058, 0x8bb81953, 0xb1b3a1aa, 0x17818b45, 0x2d8a33bc, 0x6396fab7, 0x599d424e, 0xb58bfa5e, 0x8f8042a7, 0xc19c8bac, 0xfb973355, 0x5da519ba, 0x67aea143, 0x29b26848, 0x13b9d0b1, 0x6be64d5f, 0x51edf5a6, 0x1ff13cad, 0x25fa8454, 0x83c8aebb, 0xb9c31642, 0xf7dfdf49, 0xcdd467b0, 0x21c2dfa0, 0x1bc96759, 0x55d5ae52, 0x6fde16ab, 0xc9ec3c44, 0xf3e784bd, 0xbdfb4db6, 0x87f0f54f, 0x4d44766a, 0x774fce93, 0x39530798, 0x0358bf61, 0xa56a958e, 0x9f612d77, 0xd17de47c, 0xeb765c85, 0x0760e495, 0x3d6b5c6c, 0x73779567, 0x497c2d9e, 0xef4e0771, 0xd545bf88, 0x9b597683, 0xa152ce7a, 0xd90d5394, 0xe306eb6d, 0xad1a2266, 0x97119a9f, 0x3123b070, 0x0b280889, 0x4534c182, 0x7f3f797b, 0x9329c16b, 0xa9227992, 0xe73eb099, 0xdd350860, 0x7b07228f, 0x410c9a76, 0x0f10537d, 0x351beb84, 0x65278475, 0x5f2c3c8c, 0x1130f587, 0x2b3b4d7e, 0x8d096791, 0xb702df68, 0xf91e1663, 0xc315ae9a, 0x2f03168a, 0x1508ae73, 0x5b146778, 0x611fdf81, 0xc72df56e, 0xfd264d97, 0xb33a849c, 0x89313c65, 0xf16ea18b, 0xcb651972, 0x8579d079, 0xbf726880, 0x1940426f, 0x234bfa96, 0x6d57339d, 0x575c8b64, 0xbb4a3374, 0x81418b8d, 0xcf5d4286, 0xf556fa7f, 0x5364d090, 0x696f6869, 0x2773a162, 0x1d78199b, 0xd7cc9abe, 0xedc72247, 0xa3dbeb4c, 0x99d053b5, 0x3fe2795a, 0x05e9c1a3, 0x4bf508a8, 0x71feb051, 0x9de80841, 0xa7e3b0b8, 0xe9ff79b3, 0xd3f4c14a, 0x75c6eba5, 0x4fcd535c, 0x01d19a57, 0x3bda22ae, 0x4385bf40, 0x798e07b9, 0x3792ceb2, 0x0d99764b, 0xabab5ca4, 0x91a0e45d, 0xdfbc2d56, 0xe5b795af, 0x09a12dbf, 0x33aa9546, 0x7db65c4d, 0x47bde4b4, 0xe18fce5b, 0xdb8476a2, 0x9598bfa9, 0xaf930750, 0x9a88ecd4, 0xa083542d, 0xee9f9d26, 0xd49425df, 0x72a60f30, 0x48adb7c9, 0x06b17ec2, 0x3cbac63b, 0xd0ac7e2b, 0xeaa7c6d2, 0xa4bb0fd9, 0x9eb0b720, 0x38829dcf, 0x02892536, 0x4c95ec3d, 0x769e54c4, 0x0ec1c92a, 0x34ca71d3, 0x7ad6b8d8, 0x40dd0021, 0xe6ef2ace, 0xdce49237, 0x92f85b3c, 0xa8f3e3c5, 0x44e55bd5, 0x7eeee32c, 0x30f22a27, 0x0af992de, 0xaccbb831, 0x96c000c8, 0xd8dcc9c3, 0xe2d7713a, 0x2863f21f, 0x12684ae6, 0x5c7483ed, 0x667f3b14, 0xc04d11fb, 0xfa46a902, 0xb45a6009, 0x8e51d8f0, 0x624760e0, 0x584cd819, 0x16501112, 0x2c5ba9eb, 0x8a698304, 0xb0623bfd, 0xfe7ef2f6, 0xc4754a0f, 0xbc2ad7e1, 0x86216f18, 0xc83da613, 0xf2361eea, 0x54043405, 0x6e0f8cfc, 0x201345f7, 0x1a18fd0e, 0xf60e451e, 0xcc05fde7, 0x821934ec, 0xb8128c15, 0x1e20a6fa, 0x242b1e03, 0x6a37d708, 0x503c6ff1, 0x00000000, 0xca4f08ea, 0x0ee744e3, 0xc4a84c09, 0x1dce89c6, 0xd781812c, 0x1329cd25, 0xd966c5cf, 0x3b9d138c, 0xf1d21b66, 0x357a576f, 0xff355f85, 0x26539a4a, 0xec1c92a0, 0x28b4dea9, 0xe2fbd643, 0x773a2718, 0xbd752ff2, 0x79dd63fb, 0xb3926b11, 0x6af4aede, 0xa0bba634, 0x6413ea3d, 0xae5ce2d7, 0x4ca73494, 0x86e83c7e, 0x42407077, 0x880f789d, 0x5169bd52, 0x9b26b5b8, 0x5f8ef9b1, 0x95c1f15b, 0xee744e30, 0x243b46da, 0xe0930ad3, 0x2adc0239, 0xf3bac7f6, 0x39f5cf1c, 0xfd5d8315, 0x37128bff, 0xd5e95dbc, 0x1fa65556, 0xdb0e195f, 0x114111b5, 0xc827d47a, 0x0268dc90, 0xc6c09099, 0x0c8f9873, 0x994e6928, 0x530161c2, 0x97a92dcb, 0x5de62521, 0x8480e0ee, 0x4ecfe804, 0x8a67a40d, 0x4028ace7, 0xa2d37aa4, 0x689c724e, 0xac343e47, 0x667b36ad, 0xbf1df362, 0x7552fb88, 0xb1fab781, 0x7bb5bf6b, 0x4691c957, 0x8cdec1bd, 0x48768db4, 0x8239855e, 0x5b5f4091, 0x9110487b, 0x55b80472, 0x9ff70c98, 0x7d0cdadb, 0xb743d231, 0x73eb9e38, 0xb9a496d2, 0x60c2531d, 0xaa8d5bf7, 0x6e2517fe, 0xa46a1f14, 0x31abee4f, 0xfbe4e6a5, 0x3f4caaac, 0xf503a246, 0x2c656789, 0xe62a6f63, 0x2282236a, 0xe8cd2b80, 0x0a36fdc3, 0xc079f529, 0x04d1b920, 0xce9eb1ca, 0x17f87405, 0xddb77cef, 0x191f30e6, 0xd350380c, 0xa8e58767, 0x62aa8f8d, 0xa602c384, 0x6c4dcb6e, 0xb52b0ea1, 0x7f64064b, 0xbbcc4a42, 0x718342a8, 0x937894eb, 0x59379c01, 0x9d9fd008, 0x57d0d8e2, 0x8eb61d2d, 0x44f915c7, 0x805159ce, 0x4a1e5124, 0xdfdfa07f, 0x1590a895, 0xd138e49c, 0x1b77ec76, 0xc21129b9, 0x085e2153, 0xccf66d5a, 0x06b965b0, 0xe442b3f3, 0x2e0dbb19, 0xeaa5f710, 0x20eafffa, 0xf98c3a35, 0x33c332df, 0xf76b7ed6, 0x3d24763c, 0x8d2392ae, 0x476c9a44, 0x83c4d64d, 0x498bdea7, 0x90ed1b68, 0x5aa21382, 0x9e0a5f8b, 0x54455761, 0xb6be8122, 0x7cf189c8, 0xb859c5c1, 0x7216cd2b, 0xab7008e4, 0x613f000e, 0xa5974c07, 0x6fd844ed, 0xfa19b5b6, 0x3056bd5c, 0xf4fef155, 0x3eb1f9bf, 0xe7d73c70, 0x2d98349a, 0xe9307893, 0x237f7079, 0xc184a63a, 0x0bcbaed0, 0xcf63e2d9, 0x052cea33, 0xdc4a2ffc, 0x16052716, 0xd2ad6b1f, 0x18e263f5, 0x6357dc9e, 0xa918d474, 0x6db0987d, 0xa7ff9097, 0x7e995558, 0xb4d65db2, 0x707e11bb, 0xba311951, 0x58cacf12, 0x9285c7f8, 0x562d8bf1, 0x9c62831b, 0x450446d4, 0x8f4b4e3e, 0x4be30237, 0x81ac0add, 0x146dfb86, 0xde22f36c, 0x1a8abf65, 0xd0c5b78f, 0x09a37240, 0xc3ec7aaa, 0x074436a3, 0xcd0b3e49, 0x2ff0e80a, 0xe5bfe0e0, 0x2117ace9, 0xeb58a403, 0x323e61cc, 0xf8716926, 0x3cd9252f, 0xf6962dc5, 0xcbb25bf9, 0x01fd5313, 0xc5551f1a, 0x0f1a17f0, 0xd67cd23f, 0x1c33dad5, 0xd89b96dc, 0x12d49e36, 0xf02f4875, 0x3a60409f, 0xfec80c96, 0x3487047c, 0xede1c1b3, 0x27aec959, 0xe3068550, 0x29498dba, 0xbc887ce1, 0x76c7740b, 0xb26f3802, 0x782030e8, 0xa146f527, 0x6b09fdcd, 0xafa1b1c4, 0x65eeb92e, 0x87156f6d, 0x4d5a6787, 0x89f22b8e, 0x43bd2364, 0x9adbe6ab, 0x5094ee41, 0x943ca248, 0x5e73aaa2, 0x25c615c9, 0xef891d23, 0x2b21512a, 0xe16e59c0, 0x38089c0f, 0xf24794e5, 0x36efd8ec, 0xfca0d006, 0x1e5b0645, 0xd4140eaf, 0x10bc42a6, 0xdaf34a4c, 0x03958f83, 0xc9da8769, 0x0d72cb60, 0xc73dc38a, 0x52fc32d1, 0x98b33a3b, 0x5c1b7632, 0x96547ed8, 0x4f32bb17, 0x857db3fd, 0x41d5fff4, 0x8b9af71e, 0x6961215d, 0xa32e29b7, 0x678665be, 0xadc96d54, 0x74afa89b, 0xbee0a071, 0x7a48ec78, 0xb007e492, 0x00000000, 0x803e706b, 0x9a05b5e1, 0x1a3bc58a, 0xae723ef5, 0x2e4c4e9e, 0x34778b14, 0xb449fb7f, 0xc69d28dd, 0x46a358b6, 0x5c989d3c, 0xdca6ed57, 0x68ef1628, 0xe8d16643, 0xf2eaa3c9, 0x72d4d3a2, 0x1743048d, 0x977d74e6, 0x8d46b16c, 0x0d78c107, 0xb9313a78, 0x390f4a13, 0x23348f99, 0xa30afff2, 0xd1de2c50, 0x51e05c3b, 0x4bdb99b1, 0xcbe5e9da, 0x7fac12a5, 0xff9262ce, 0xe5a9a744, 0x6597d72f, 0x2e86091a, 0xaeb87971, 0xb483bcfb, 0x34bdcc90, 0x80f437ef, 0x00ca4784, 0x1af1820e, 0x9acff265, 0xe81b21c7, 0x682551ac, 0x721e9426, 0xf220e44d, 0x46691f32, 0xc6576f59, 0xdc6caad3, 0x5c52dab8, 0x39c50d97, 0xb9fb7dfc, 0xa3c0b876, 0x23fec81d, 0x97b73362, 0x17894309, 0x0db28683, 0x8d8cf6e8, 0xff58254a, 0x7f665521, 0x655d90ab, 0xe563e0c0, 0x512a1bbf, 0xd1146bd4, 0xcb2fae5e, 0x4b11de35, 0x5d0c1234, 0xdd32625f, 0xc709a7d5, 0x4737d7be, 0xf37e2cc1, 0x73405caa, 0x697b9920, 0xe945e94b, 0x9b913ae9, 0x1baf4a82, 0x01948f08, 0x81aaff63, 0x35e3041c, 0xb5dd7477, 0xafe6b1fd, 0x2fd8c196, 0x4a4f16b9, 0xca7166d2, 0xd04aa358, 0x5074d333, 0xe43d284c, 0x64035827, 0x7e389dad, 0xfe06edc6, 0x8cd23e64, 0x0cec4e0f, 0x16d78b85, 0x96e9fbee, 0x22a00091, 0xa29e70fa, 0xb8a5b570, 0x389bc51b, 0x738a1b2e, 0xf3b46b45, 0xe98faecf, 0x69b1dea4, 0xddf825db, 0x5dc655b0, 0x47fd903a, 0xc7c3e051, 0xb51733f3, 0x35294398, 0x2f128612, 0xaf2cf679, 0x1b650d06, 0x9b5b7d6d, 0x8160b8e7, 0x015ec88c, 0x64c91fa3, 0xe4f76fc8, 0xfeccaa42, 0x7ef2da29, 0xcabb2156, 0x4a85513d, 0x50be94b7, 0xd080e4dc, 0xa254377e, 0x226a4715, 0x3851829f, 0xb86ff2f4, 0x0c26098b, 0x8c1879e0, 0x9623bc6a, 0x161dcc01, 0xba182468, 0x3a265403, 0x201d9189, 0xa023e1e2, 0x146a1a9d, 0x94546af6, 0x8e6faf7c, 0x0e51df17, 0x7c850cb5, 0xfcbb7cde, 0xe680b954, 0x66bec93f, 0xd2f73240, 0x52c9422b, 0x48f287a1, 0xc8ccf7ca, 0xad5b20e5, 0x2d65508e, 0x375e9504, 0xb760e56f, 0x03291e10, 0x83176e7b, 0x992cabf1, 0x1912db9a, 0x6bc60838, 0xebf87853, 0xf1c3bdd9, 0x71fdcdb2, 0xc5b436cd, 0x458a46a6, 0x5fb1832c, 0xdf8ff347, 0x949e2d72, 0x14a05d19, 0x0e9b9893, 0x8ea5e8f8, 0x3aec1387, 0xbad263ec, 0xa0e9a666, 0x20d7d60d, 0x520305af, 0xd23d75c4, 0xc806b04e, 0x4838c025, 0xfc713b5a, 0x7c4f4b31, 0x66748ebb, 0xe64afed0, 0x83dd29ff, 0x03e35994, 0x19d89c1e, 0x99e6ec75, 0x2daf170a, 0xad916761, 0xb7aaa2eb, 0x3794d280, 0x45400122, 0xc57e7149, 0xdf45b4c3, 0x5f7bc4a8, 0xeb323fd7, 0x6b0c4fbc, 0x71378a36, 0xf109fa5d, 0xe714365c, 0x672a4637, 0x7d1183bd, 0xfd2ff3d6, 0x496608a9, 0xc95878c2, 0xd363bd48, 0x535dcd23, 0x21891e81, 0xa1b76eea, 0xbb8cab60, 0x3bb2db0b, 0x8ffb2074, 0x0fc5501f, 0x15fe9595, 0x95c0e5fe, 0xf05732d1, 0x706942ba, 0x6a528730, 0xea6cf75b, 0x5e250c24, 0xde1b7c4f, 0xc420b9c5, 0x441ec9ae, 0x36ca1a0c, 0xb6f46a67, 0xaccfafed, 0x2cf1df86, 0x98b824f9, 0x18865492, 0x02bd9118, 0x8283e173, 0xc9923f46, 0x49ac4f2d, 0x53978aa7, 0xd3a9facc, 0x67e001b3, 0xe7de71d8, 0xfde5b452, 0x7ddbc439, 0x0f0f179b, 0x8f3167f0, 0x950aa27a, 0x1534d211, 0xa17d296e, 0x21435905, 0x3b789c8f, 0xbb46ece4, 0xded13bcb, 0x5eef4ba0, 0x44d48e2a, 0xc4eafe41, 0x70a3053e, 0xf09d7555, 0xeaa6b0df, 0x6a98c0b4, 0x184c1316, 0x9872637d, 0x8249a6f7, 0x0277d69c, 0xb63e2de3, 0x36005d88, 0x2c3b9802, 0xac05e869}; static unsigned lfsr_random(void) { static unsigned state = 0x12345678; unsigned next; next = lfsr_lut[((state>> 0) & 0xFF) + 0*256]; next ^= lfsr_lut[((state>> 8) & 0xFF) + 1*256]; next ^= lfsr_lut[((state>>16) & 0xFF) + 2*256]; next ^= lfsr_lut[((state>>24) & 0xFF) + 3*256]; return state = next; } /* * Initialize an empty skip list */ void skip_list_init (skip_list_t *list, skip_list_compare_t compare, size_t elt_size) { int i; list->compare = compare; list->elt_size = elt_size; list->data_size = elt_size - sizeof (skip_elt_t); for (i = 0; i < MAX_LEVEL; i++) { list->chains[i] = NULL; list->freelists[i] = NULL; } list->max_level = 0; } void skip_list_fini (skip_list_t *list) { skip_elt_t *elt; int i; while ((elt = list->chains[0])) { skip_list_delete_given (list, elt); } for (i=0; ifreelists[i]; while (elt) { skip_elt_t *nextfree = elt->prev; free (ELT_DATA(elt)); elt = nextfree; } } } /* * Generate a random level number, distributed * so that each level is 1/4 as likely as the one before * * Note that level numbers run 1 <= level <= MAX_LEVEL */ static int random_level (void) { /* tricky bit -- each bit is '1' 75% of the time */ long int bits = lfsr_random() | lfsr_random(); int level = 0; while (++level < MAX_LEVEL) { if (bits & 1) break; bits >>= 1; } return level; } static void * alloc_node_for_level (skip_list_t *list, unsigned level) { if (list->freelists[level-1]) { skip_elt_t *elt = list->freelists[level-1]; list->freelists[level-1] = elt->prev; return ELT_DATA(elt); } return malloc (list->elt_size + (level-1) * sizeof (skip_elt_t *)); } static void free_elt (skip_list_t *list, skip_elt_t *elt) { elt->prev = list->freelists[elt->prev_index]; list->freelists[elt->prev_index] = elt; } /* * Insert 'data' into the list */ void * skip_list_insert (skip_list_t *list, void *data, int unique) { skip_elt_t **update[MAX_LEVEL]; skip_elt_t *prev[MAX_LEVEL]; char *data_and_elt; skip_elt_t *elt, **next; int i, level, prev_index; /* * Find links along each chain */ next = list->chains; for (i = list->max_level; --i >= 0; ) { for (; (elt = next[i]); next = elt->next) { int cmp = list->compare (list, ELT_DATA(elt), data); if (unique && 0 == cmp) return ELT_DATA(elt); if (cmp > 0) break; } update[i] = next; if (next != list->chains) prev[i] = NEXT_TO_ELT (next); else prev[i] = NULL; } level = random_level (); prev_index = level - 1; /* * Create new list element */ if (level > list->max_level) { level = list->max_level + 1; prev_index = level - 1; prev[prev_index] = NULL; update[list->max_level] = list->chains; list->max_level = level; } data_and_elt = alloc_node_for_level (list, level); memcpy (data_and_elt, data, list->data_size); elt = (skip_elt_t *) (data_and_elt + list->data_size); elt->prev_index = prev_index; elt->prev = prev[prev_index]; /* * Insert into all chains */ for (i = 0; i < level; i++) { elt->next[i] = update[i][i]; if (elt->next[i] && elt->next[i]->prev_index == i) elt->next[i]->prev = elt; update[i][i] = elt; } return data_and_elt; } void * skip_list_find (skip_list_t *list, void *data) { int i; skip_elt_t **next = list->chains; skip_elt_t *elt; /* * Walk chain pointers one level at a time */ for (i = list->max_level; --i >= 0;) while (next[i] && list->compare (list, data, ELT_DATA(next[i])) > 0) { next = next[i]->next; } /* * Here we are */ elt = next[0]; if (elt && list->compare (list, data, ELT_DATA (elt)) == 0) return ELT_DATA (elt); return NULL; } void skip_list_delete (skip_list_t *list, void *data) { skip_elt_t **update[MAX_LEVEL], *prev[MAX_LEVEL]; skip_elt_t *elt, **next; int i; /* * Find links along each chain */ next = list->chains; for (i = list->max_level; --i >= 0; ) { for (; (elt = next[i]); next = elt->next) { if (list->compare (list, ELT_DATA (elt), data) >= 0) break; } update[i] = &next[i]; if (next == list->chains) prev[i] = NULL; else prev[i] = NEXT_TO_ELT (next); } elt = next[0]; assert (list->compare (list, ELT_DATA (elt), data) == 0); for (i = 0; i < list->max_level && *update[i] == elt; i++) { *update[i] = elt->next[i]; if (elt->next[i] && elt->next[i]->prev_index == i) elt->next[i]->prev = prev[i]; } while (list->max_level > 0 && list->chains[list->max_level - 1] == NULL) list->max_level--; free_elt (list, elt); } void skip_list_delete_given (skip_list_t *list, skip_elt_t *given) { skip_elt_t **update[MAX_LEVEL], *prev[MAX_LEVEL]; skip_elt_t *elt, **next; int i; /* * Find links along each chain */ if (given->prev) next = given->prev->next; else next = list->chains; for (i = given->prev_index + 1; --i >= 0; ) { for (; (elt = next[i]); next = elt->next) { if (elt == given) break; } update[i] = &next[i]; if (next == list->chains) prev[i] = NULL; else prev[i] = NEXT_TO_ELT (next); } elt = next[0]; assert (elt == given); for (i = 0; i < (given->prev_index + 1) && *update[i] == elt; i++) { *update[i] = elt->next[i]; if (elt->next[i] && elt->next[i]->prev_index == i) elt->next[i]->prev = prev[i]; } while (list->max_level > 0 && list->chains[list->max_level - 1] == NULL) list->max_level--; free_elt (list, elt); }